Google

  www.google.com
  www.google.com

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.