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.

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
 
SUBSCRIPTIONS
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Amazed

    Mazes fascinated even the ancient Greeks. Mike Schilli uses his Go programming skills to create a maze and then efficiently travel through it.

  • A taste of tiling with X-Tile
  • Tiling Desktops

    Tiling desktops have been experiencing a resurgence in popularity. Here are a few options that can help keep your desktop better organized.

  • FOSSPicks

    Calibre 3.0, WereSync 1.0b, COLMAP 3.1, Tor Browser 7.0, Dungeon Crawl Stone Soup 0.20, and much more!

  • Web Design with GIMP

    Good homepage design is a question of the layout. Sometimes the best option is to use a graphics program to design the page, then translate the result into HTML code. The versatile image manipulation program GIMP can help.

comments powered by Disqus

Direct Download

Read full article as PDF:

Price $2.95

News