This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company? Learn More.

# `Google` `Software Engineer` Interview Question

`"Third person: Given a 2-d array, write code to print it out in a snake pattern. For example, if the array is this: 1, 2, 3 4, 5, 6 7, 8, 9 the routine prints this: 1,2,3,6,9,8,7,4,5 The array is an NxN array. The final question was just how to write a connection pool (i.e, a class that returns connections to the user, and if the user is done, returns them back to the pool)"`

Part of a `Software Engineer` Interview Review - one of `3,029` `Google` Interview Reviews

Answers & Comments

▲

0

▼

of 0votes

arr = [[1, 2, 3, 4],

[5, 6, 7, 8],

[9, 10,11,12],

[13,14,15,16]]

# arr = [[1,2,3],[4,5,6],[7,8,9]]

rows = len(arr)

cols = len(arr[0])

LEFT, RIGHT, UP, DOWN = 0, 1, 2, 3

delta=[(-1,0), # LEFT

(1,0), # RIGHT

(0,-1), # UP

(0,1)] # DOWN

change_direction=(UP, # LEFT now goes UP

DOWN, # RIGHT now goes DOWN

RIGHT, # UP now goes RIGHT

LEFT) # DOWN now goes LEFT

def snake(x, y):

visited = [] # this matrix holds True for every point we had visited

for i in range(rows):

visited.append([False]*cols) # initially False - never visited

direction = RIGHT # initial direction

route = [(x, y)] # we are located at x,y on map

visited[y][x] = True

while True:

nx,ny = delta[direction]

nx += x

ny += y

# change direction if new coordinate is not valid

if nx >= cols or nx < 0 or ny>=rows or ny < 0 or visited[ny][nx]:

direction = change_direction[direction]

nx,ny = delta[direction]

nx += x

ny += y

# if still not valid - break

if nx >= cols or nx < 0 or ny>=rows or ny < 0 or visited[ny][nx]:

break

# advance to new coordinates

x, y = nx, ny

route.append((x, y)) # add it to route

visited[y][x] = True # mark this place as visited

print(",".join([str(arr[y][x]) for x,y in route]))

if __name__ == '__main__':

snake(0,0)

[5, 6, 7, 8],

[9, 10,11,12],

[13,14,15,16]]

# arr = [[1,2,3],[4,5,6],[7,8,9]]

rows = len(arr)

cols = len(arr[0])

LEFT, RIGHT, UP, DOWN = 0, 1, 2, 3

delta=[(-1,0), # LEFT

(1,0), # RIGHT

(0,-1), # UP

(0,1)] # DOWN

change_direction=(UP, # LEFT now goes UP

DOWN, # RIGHT now goes DOWN

RIGHT, # UP now goes RIGHT

LEFT) # DOWN now goes LEFT

def snake(x, y):

visited = [] # this matrix holds True for every point we had visited

for i in range(rows):

visited.append([False]*cols) # initially False - never visited

direction = RIGHT # initial direction

route = [(x, y)] # we are located at x,y on map

visited[y][x] = True

while True:

nx,ny = delta[direction]

nx += x

ny += y

# change direction if new coordinate is not valid

if nx >= cols or nx < 0 or ny>=rows or ny < 0 or visited[ny][nx]:

direction = change_direction[direction]

nx,ny = delta[direction]

nx += x

ny += y

# if still not valid - break

if nx >= cols or nx < 0 or ny>=rows or ny < 0 or visited[ny][nx]:

break

# advance to new coordinates

x, y = nx, ny

route.append((x, y)) # add it to route

visited[y][x] = True # mark this place as visited

print(",".join([str(arr[y][x]) for x,y in route]))

if __name__ == '__main__':

snake(0,0)

▲

0

▼

of 0votes

public static void printSpiral(Array a)

{

ps(a, 0, a.size()-1);

}

public static void ps(Array a, int s, int f)

{

if (f < s) return;

for (int i = s; i <= f; i++) System.out.println(a.get(i,s));

for (int j = s+1; j < f; j++) System.out.println(a.get(f, j));

for (int i = f; i >= s; i--) System.out.println(a.get(i, f));

for (int j = f-1; j > s; j--) System.out.println(a.get(s,j));

ps(a, s+1, f-1);

}

{

ps(a, 0, a.size()-1);

}

public static void ps(Array a, int s, int f)

{

if (f < s) return;

for (int i = s; i <= f; i++) System.out.println(a.get(i,s));

for (int j = s+1; j < f; j++) System.out.println(a.get(f, j));

for (int i = f; i >= s; i--) System.out.println(a.get(i, f));

for (int j = f-1; j > s; j--) System.out.println(a.get(s,j));

ps(a, s+1, f-1);

}

▲

0

▼

of 0votes

public static void print2DArraySnakePattern(int[][] arr) {

if (arr == null) {

return;

}

for (int i=0; i < arr.length; i++) {

if (i % 2 == 0) {

for (int j=0; j < arr[0].length;j++) {

System.out.print(arr[i][j]+",");

}

} else {

for (int j=arr[0].length -1; j >= 0;j--) {

System.out.print(arr[i][j]+",");

}

}

}

}

if (arr == null) {

return;

}

for (int i=0; i < arr.length; i++) {

if (i % 2 == 0) {

for (int j=0; j < arr[0].length;j++) {

System.out.print(arr[i][j]+",");

}

} else {

for (int j=arr[0].length -1; j >= 0;j--) {

System.out.print(arr[i][j]+",");

}

}

}

}

** To comment on this question, Sign In with Facebook or Sign Up **

vote

import math;

# test several small sized matrices

def main():

for N in range(0, 8):

A = [];

count = 1;

for row in range(0, N):

A.append([]);

for col in range(0, N):

A[row].append(count);

count += 1;

printMat(A);

print snake(A);

# prints the matrix in standard form

def printMat(A):

if len(A) == 0:

print "[\t[\t]\t]";

return;

print "[\t",

for row in range(0, len(A)):

if row == 0:

print "[\t",

else:

print "\t[\t",

for col in range(0, len(A[row])):

if col == len(A[row]) - 1:

if row == len(A) - 1:

print str(A[row][col]) + "]\t]";

else:

print str(A[row][col]) + "]";

else:

print str(A[row][col]) + ",\t",

# return array reading the matrix in snake fashion

def snake(A):

N = len(A);

array = [];

# outermost layer is 0

for layer in range(0, int(math.floor((N + 1) / 2))):

d_u_count_range = max(4 * N - 8 * layer - 4, 0);

l_r_count_range = d_u_count_range / 4;

u_d_count_range = d_u_count_range / 2;

r_l_count_range = 3 * l_r_count_range;

for count in range(0, d_u_count_range):

# append left to right values

if count < l_r_count_range:

array.append(A[layer][layer + count]);

# append up to down values

elif count < u_d_count_range:

array.append(A[layer + count - l_r_count_range]

[N - 1 - layer]);

# append right to left values

elif count < r_l_count_range:

array.append(A[layer + l_r_count_range]

[N - 1 - layer - (count - u_d_count_range)]);

# append down to up values

else:

array.append(A[layer + l_r_count_range - (count - r_l_count_ran\

ge)]

[layer]);

# append center value if matrix had odd dimensions

if N % 2 == 1:

array.append(A[(N - 1) / 2][(N - 1) / 2]);

return array;

if __name__ == '__main__':

main();

random_guyonMar 24, 2013