Google

www.google.com
Engaged Employer

## Interview Question

Software Engineer Interview Los Angeles, CA

# 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)
Answer

## Interview Answer

4 Answers

1

#!/usr/bin/python

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_guy on Mar 24, 2013
0

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)

idispatch on Apr 17, 2013
0

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);
}

Rahul on May 4, 2013
0

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]+",");
}
}
}
}

Ben H on Jul 27, 2013

## Add Answers or Comments

To comment on this, Sign In or Sign Up.