Solving a classic interview problem with Go
Exploration
So, how does the algorithm find all adjacent neighbors, starting with a given tile? The explore()
function in Listing 2 takes the matrix with all tiles, the start position, and the seen
notepad. It defines a to-do list dubbed examine
and calls append()
to add the candidates to be examined to the end of this initially empty array slice. It later removes processed items from the slice from the front, by reassigning the slice minus the first element (examine[1:]
) to the examine
variable in line 11.
The neighbors()
function called in line 22 is defined in Listing 3 and searches all adjacent tiles. It returns an array slice whose elements are flattened by the ...
operator in line 23 of Listing 2, when it passes them to the append()
function, which extends the examine
array slice with the candidates.
Listing 3
neighbors.go
01 package main 02 03 func neighbors( 04 tiles [][]int, cur pos) []pos { 05 var max pos 06 max.x = len(tiles) - 1 07 if max.x < 2 { 08 panic("Illegal array") 09 } 10 max.y = len(tiles[0]) - 1 11 12 found := []pos{} 13 add(&found, pos{cur.x - 1, cur.y}, max) 14 add(&found, pos{cur.x + 1, cur.y}, max) 15 add(&found, pos{cur.x, cur.y - 1}, max) 16 add(&found, pos{cur.x, cur.y + 1}, max) 17 18 return found 19 } 20 21 func add( 22 found *[]pos, cand pos, max pos) { 23 if cand.x > 0 && cand.y > 0 && 24 cand.x <= max.x && cand.y <= max.y { 25 *found = append(*found, cand) 26 } 27 }
Listing 4
dump.go
01 package main 02 03 import ( 04 "fmt" 05 ) 06 07 func dump(tiles [][]int, max []pos) { 08 disp := make([][]string, len(tiles)) 09 10 for i, row := range tiles { 11 disp[i] = make([]string, len(row)) 12 for j, _ := range disp[i] { 13 disp[i][j] = "o" 14 } 15 } 16 17 for _, pos := range max { 18 disp[pos.x][pos.y] = "X" 19 } 20 21 for _, row := range disp { 22 fmt.Printf("%v\n", row) 23 } 24 }
In other words, the procedure implements a queue that appends new entries to the end and processes old ones from the start, step by step with each pass of the for
loop starting in line 9. The queue relies on the "first in, first out" principle (i.e., it propagates "breadth first" through the labyrinth of tiles). If a stack ("first in, last out") were to be used instead, explore()
would first drill down deep ("depth first") before looking for directly adjacent neighbors. The same behavior would apply if the algorithm did a recursive instead of an iterative search. It would repeatedly call itself when it found new neighbors. A good candidate can weigh all these different implementation strategies against each other, and that kind of thoughtful analysis is something the interviewer would certainly be pleased to see.
The neighbors()
function in Listing 3 expects the tile matrix in tiles
, as well as the current start position as X/Y coordinates (cur
). It returns all adjacent neighbors as an array slice of pos
types. To accomplish that, it scans all tiles that lie to the north, south, west, and east by adding or subtracting a value of 1
to or from the coordinates. At the same time, it uses the add()
function in line 21 to ensure that the neighbors found in this way really are neighbors (i.e., that they do not lie outside the matrix by using values outside the frame defined in max
or have coordinates with values less than zero).
To let the add()
function from line 21 in Listing 3 not only read the array slice passed to it, but also modify it, the callers do not pass in the found
slice variable in lines 13 to 16 as a value, but instead use the &
notation for a pointer. In the function declaration for add()
starting in line 21, found
is therefore also marked as a pointer to an array slice of pos
structures (found *[]pos
).
The append()
function called in line 25, which is built into Go, accesses the array slice by first using *found
to dereference the incoming pointer. Without this detour via the pointer, found
would be a copy of the original data structure in neighbors()
. In this case, add()
would have read access to the slice, but would not be able to modify its elements permanently, since all changes to the copy would be lost after exiting the sub-function.
Pointer or Value?
However, attentive readers might now be asking themselves why the two-dimensional seen
array slice from the main program in Listing 1 was passed as a value earlier on and not as a pointer. How could the explore()
function modify it in a way so that the changes were visible in the main program in Listing 1?
This is because although Go passes array slices as values, the second dimension of the seen
data structure in Listing 1 consists of pointers to array slices. Go does not flatten these slices, but passes them to the subroutine as pointers, which can therefore modify the values behind the pointers so that the main program actually sees the changes in the data structure as intended.
For more on this "values or pointers" topic, also known as "call-by-value" versus "call-by-name" (especially for those of you who are interested in computer history), I can recommend the 1982 essay "Real Programmers Don't use Pascal" [5] by Ed Post. It explains that Nicklaus Wirth, the inventor of Pascal, was once asked during a lecture how he pronounced his name. "He replied: 'You can either call me by name, pronouncing it "Veert," or call me by value, "Worth"'." The author of the humorous pamphlet then elaborates: "One can tell immediately from this comment that Nicklaus Wirth is a Quiche Eater. The only parameter passing mechanism endorsed by Real Programmers is call-by-value-return."
Listing 4 finally implements a dump()
function for the graphical output of the positions of the longest chain of connected tiles. To do this, it creates a matrix with string entries that is the same size as the original tile matrix. The algorithm marks the fields of the longest chain found with X
and assigns an o
to all other positions. The matrix output at the command line in Figure 3 shows the result: The algorithm has correctly identified the U-shaped rectangle collection in the lower right corner as the largest contiguous group.
If you want to compile the Go code in this issue, which is split into four listings for clarity, into a binary named connected
, the call from Listing 5 is all you need. Since all four listings define the package main package, they can all access the type constructs and functions spread out in the different parts. For example, Listing 4 knows what a pos
structure is, or Listing 1 knows where to find the dump()
function, just because they define the same package main
.
Listing 5
Compiling the Binary
01 $ go build connected.go \ 02 explore.go neighbors.go dump.go
Changing the Question
In job interviews, it is not unusual to bring up alternative questions after the solution has been found: What would have to be changed if "contiguous" were now to apply not only to tiles that share a side, but also to those that have only one corner that touches a neighbor of the same color?
In this case, the algorithm would also identify the blue group as the largest, but with an additional element, the tile from the third column in the first row. The only thing that would have to be modified in the code for this would be the neighbors()
function. It would not only have to look for candidates in all four cardinal directions, but also diagonally scan four further neighbors by permuting both the X and Y values with +1
and -1
.
« Previous 1 2 3 Next »
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
Linux Servers Targeted by Akira Ransomware
A group of bad actors who have already extorted $42 million have their sights set on the Linux platform.
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs