## Google Interview Question for Dev Leads

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````# assume due to feedbacks, zig-zag means
# diagonals starting from upper-left, going down until
# lower and if at bottom-left go to bottom-right
# printing the elements into up-left diagonale
#
# e.g- the desired order in this case:
# [[0, 1, 2, 3, 4],
#  [5, 6, 7, 8, 9],
#  [a, b, c, d, e]]
# is: 0, 5, 1, a, 6, 2, b, 7, 3, c, 8, 4, d, 9, e
#
# or in this case:
# [[0, 1]
#  [2, 3]
#  [4, 5]]
# 0, 2, 1, 4, 3, 5
#
# in python3:
def traverse(matrix):
cols = len(matrix[0])
rows = len(matrix)
print('matrix {0}:'.format(matrix), end=' ')

for i in range (0, rows):
for j in range (0, min(i + 1, cols)):
print(matrix[i - j][j], end= ' ')

for j in range (1, cols):
for i in range (0, min(cols - j, rows)):
print(matrix[rows - i - 1][j + i], end=' ')

print()

traverse([[1,2,3],[4,5,6],[7,8,9]])
traverse([[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14]])
traverse([[0,1],[2,3],[4,5]])
traverse([[1],[2],[3]])
traverse([[1, 2, 3]])

#output:
#matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]: 1 4 2 7 5 3 8 6 9
#matrix [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]: 0 5 1 10 6 2 11 7 3 12 8 4 13 9 14
#matrix [[0, 1], [2, 3], [4, 5]]: 0 2 1 4 3 5
#matrix [[1], [2], [3]]: 1 2 3
#matrix [[1, 2, 3]]: 1 2 3``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Yeah need more details...define zig-zag fashion...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Nitish is on the right track. Correct result would be 1, 4, 2, 7, 5, 3, 8, 6, 9

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think correct series will be 1 4 7 8 5 2 3 6 9, as per nitish's code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n^2) (have to traverse each of the elements in the matrix).

I did this by first printing the upper-left triangle in the matrix (with the opposite/minor diagonal inclusive) and then printing the bottom-right triangle (minor diagonal exclusive). Just involves some index play and need to make sure you don't get an ArrayOutOfBoundsException.

Below solution is in Java:

``````public class PrintZigZag {

public static void main(String[] args) {
int[][] test1 = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printZigZag(test1);

System.out.println();   // new line for a new test

int[][] test2 = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
printZigZag(test2);
}

// matrix is N x N
public static void printZigZag(int[][] matrix) {
int len = matrix.length;

// upper left triangle (including minor diagonal)
for(int i=1; i<=len; i++) {
for(int j=1; j<=i; j++) {
int next = matrix[i - j][j-1];
System.out.print(next + " ");
}
}

// lower right triangle (excluding minor diagonal)
for(int i=1; i<len; i++) {
for(int j=i; j<len; j++) {
int next = matrix[len + i - j - 1][j];
System.out.print(next + " ");
}
}
}
}``````

Running above two tests yields:

``````1 4 2 7 5 3 8 6 9
1 5 2 9 6 3 13 10 7 4 14 11 8 15 12 16``````

Oops, didn't read the question too well. A solution for N x M matrix is required. Slight changes to the above code does the trick:

``````public class PrintZigZag {

public static void main(String[] args) {
int[][] test1 = new int[][]{{1, 2}, {4, 5}, {7, 8}};
printZigZag(test1);

System.out.println();   // new line for a new test

int[][] test2 = new int[][]{{1, 2, 3}, {5, 6, 7}, {9, 10, 11}, {13, 14, 15}};
printZigZag(test2);
}

// matrix is N x N
public static void printZigZag(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;

// upper left triangle (including minor diagonal)
for(int i=1; i<=N; i++) {
for(int j=1; j<=Math.min(M, i); j++) {
int next = matrix[i - j][j-1];
System.out.print(next + " ");
}
}

// lower right triangle (excluding minor diagonal)
for(int i=1; i<M; i++) {
for(int j=i; j<M; j++) {
int next = matrix[N + i - j - 1][j];
System.out.print(next + " ");
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If you're dealing with sparse matrices you might want to take a slightly different approach. This algorithm runs in O(n log n), where n is the number of non-zero entries.

``````# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return

# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return

def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row

if e.col > self.cols:
self.cols = e.col

return

class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return

def __iter__(self):
return self

def __next__(self):
if self.index == len(self.elements):
raise StopIteration

e = self.elements[self.index]
self.index += 1
return e``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You might want to take a different approach if you're dealing with sparse matrices. This runs in O(n log n), where n is the number of non-zero entries. This assumes zig-zag means going bottom-left to top right for each diagonal. If you want to alternate direction you need to sort each diagonal separately, I think.

``````# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return

# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return

def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row

if e.col > self.cols:
self.cols = e.col

return

class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return

def __iter__(self):
return self

def __next__(self):
if self.index == len(self.elements):
raise StopIteration

e = self.elements[self.index]
self.index += 1
return e``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function traverseDiagonal(n, m, matrix, sequence) {
while (matrix[n][m] !== undefined) {
sequence.push(matrix[n][m++])
if (matrix[--n] === undefined) {
return
}
}
}
module.exports = function (matrix) {
var sequence = []
var N = matrix.length
var M = matrix.length > 0 ? matrix[0].length : null

if (M === null) {
throw new Error('Length of `M` cannot be zero.')
}
var m, n
m = n = 0
for (; n < N; ++n) {
traverseDiagonal(n, m, matrix, sequence)
}
n--
m++
for (; m < M; ++m) {
traverseDiagonal(n, m, matrix, sequence)
}
return sequence
}

var matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

var sequence = module.exports(matrix)

console.log(sequence.toString())``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MatrixZigZag {

public static void main(String[] args) {
// TODO Auto-generated method stub

Object[][] m1 = {{"a", "b", "c"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"}};

System.out.println(zigZag(m1, 0, 0));
// The above prints a b d c e g f h j i k l

Object[][] m2 = {{"a", "b", "c", "d"},
{"e", "f", "g", "h"}};

System.out.println(zigZag(m2, 0, 0));
// The above prints a b e c f d g h
}

public static String zigZag(Object[][] m, int i, int j) {

StringBuilder sb = new StringBuilder("");
while (true) {
sb.append(m[i][j].toString() + " ");
if (i == m.length - 1 && j == m[0].length - 1) {
break;
}
if (checkStart(m, i, j)) {
int[] symm =  symmAfter(m, i, j);
i = symm[0];
j = symm[1];

} else {
i++;
j--;
}

}
return sb.deleteCharAt(sb.length() - 1).toString();
}
public static int[] symmAfter(Object[][] m, int i, int j) {
int[] newPos = new int[2];
newPos[0] = Math.max(0, i - m[0].length + 1 + j);
newPos[1] = Math.min(i + j, m[0].length - 1);

if (newPos[1] < m[0].length - 1) {
newPos[1]++;
} else {
newPos[0]++;
}

return newPos;
}
public static boolean checkStart(Object[][] m, int i, int j) {
if (i == m.length - 1 || j == 0) {
return true;
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public List<Integer> printZigZagMatrix(int[][] matrix ){
List<Integer> result = new ArrayList<>();
int i=0,j=0;
int[] dx = {-1,1};//up,down
int[] dy = {1,-1};
int d=0;
int[] ex = {0,1};//right,down
int[] ey = {1,0};
int e = 0;
while(true){
result.add(matrix[i][j]);
//if no up, then go right and start coming down diagnally
//if no down go down and start going up
int ii  = i+dx[d];
int jj  = j+dy[d];
if(ii<0 || jj<0 || ii>=matrix.length || jj>=matrix[0].length){
//change direction
d = (d+1)%2;
if(i==matrix.length-1){
i = i+ex[0];
j = j+ey[0];
}else if(j==matrix[0].length-1){
i = i+ex[1];
j = j+ey[1];
}else{
i = i+ex[e];
j = j+ey[e];
}

result.add(matrix[i][j]);
if(i==matrix.length-1 && j==matrix[0].length-1){
break;
}
e = (e+1)%2;
}
i  = i+dx[d];
j  = j+dy[d];
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public List<Integer> printZigZagMatrix(int[][] matrix ){
List<Integer> result = new ArrayList<>();
int i=0,j=0;
int[] dx = {-1,1};//up,down
int[] dy = {1,-1};
int d=0;
int[] ex = {0,1};//right,down
int[] ey = {1,0};
int e = 0;
while(true){
result.add(matrix[i][j]);
//if no up, then go right and start coming down diagnally
//if no down go down and start going up
int ii  = i+dx[d];
int jj  = j+dy[d];
if(ii<0 || jj<0 || ii>=matrix.length || jj>=matrix[0].length){
//change direction
d = (d+1)%2;
if(i==matrix.length-1){
i = i+ex[0];
j = j+ey[0];
}else if(j==matrix[0].length-1){
i = i+ex[1];
j = j+ey[1];
}else{
i = i+ex[e];
j = j+ey[e];
}

result.add(matrix[i][j]);
if(i==matrix.length-1 && j==matrix[0].length-1){
break;
}
e = (e+1)%2;
}
i  = i+dx[d];
j  = j+dy[d];
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PrintMatrixZigZag {
private static int[][] arr;
private static int n;
private static int m;
private static Set<String> covered;
private static List<String> queue;
private static String sep = ":";

public static void main(String a[]) {
n = 3;
m = 4;
arr = new int[n][m];
arr[0] = new int[] { 1, 2, 3, 4 };
arr[1] = new int[] { 5, 6, 7, 8 };
arr[2] = new int[] { 9, 10, 11, 12 };
covered = new HashSet<String>();
queue = new ArrayList<String>();
queue.add(0 + sep + 0);
System.out.print(arr[0][0]+"\t");
while (queue.size() != 0) {
queue = printNum(queue);
}
}

private static List<String> printNum(List<String> queue) {
List<String> aux = new ArrayList<String>();
for (String tmp : queue) {
String[] inds = tmp.split(sep);
int i = Integer.parseInt(inds[0]);
int j = Integer.parseInt(inds[1]);
if (j == 0 && i < n-1) {
aux.add(i + 1 + sep + j);
System.out.print(arr[i + 1][j] + "\t");
}
if (j < m - 1 && !covered.contains(tmp)) {
aux.add(i + sep + (j + 1));
System.out.print(arr[i][j + 1] + "\t");
}
covered.add(tmp);
}
return aux;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Ruby:

``````def traverse(array)
array.each_with_index.flat_map{|r,i| r.each_with_index.map{|c,j| [c,i,j]}}
.sort_by{|m,i,j| [(i+j),j]}.map{|a,i,j| a}
end

traverse([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
=> [1, 4, 2, 7, 5, 3, 8, 6, 9]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Site ate my first comment, so trying again.

In Ruby:

``````def traverse(array)
array.each_with_index.flat_map{|r,i| r.each_with_index.map{|c,j| [c,i,j]}}
.sort_by{|m,i,j| [(i+j),j]}.map{|a,i,j| a}
end

traverse([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
=> [1, 4, 2, 7, 5, 3, 8, 6, 9]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void printZigZag(int[][] arr){
int rows=arr.length, columns=arr[0].length;
int i=0,j=0;
while (i<arr.length && j<arr[0].length){
System.out.print("\n"+arr[i][j]+"\t");
while(i>0 && j<columns-1){
i--;j++;
System.out.print(arr[i][j]+"\t");
}
if(j==columns-1)i++;
else if(i==0)j++;

if(i>=rows || j>=columns)break;
System.out.print("\n"+arr[i][j]+"\t");
while(i< rows-1 && j>0){
i++;j--;
System.out.print(arr[i][j]+"\t");
}
if(i==rows-1)j++;
else if(j==0)i++;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void printZigZag2(Matrix matrix) {
int ctr = 0;
int i = 0;
int j = 0;
final int m = matrix.getRows();
final int n = matrix.getCols();
while (ctr < (m * n)) {
System.out.println(matrix.getVal(i, j));
ctr++;
if (i == 0) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else if (j == (n - 1)) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else {
i--;
j++;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void printZigZag2(Matrix matrix) {
int ctr = 0;
int i = 0;
int j = 0;
final int m = matrix.getRows();
final int n = matrix.getCols();
while (ctr < (m * n)) {
System.out.println(matrix.getVal(i, j));
ctr++;
if (i == 0) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else if (j == (n - 1)) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else {
i--;
j++;
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void zigzagTraversal(int a[][]){
if(a.length==0)
return;
int i=0;
int j=0;
int count=0;
while(i<a.length || count<a[0].length){
if(i>a.length-1){
i=a.length-1;
count++;
}

int row=i, column=count;
while(row>=0 && column<a[0].length){
System.out.print(a[row][column]);
row--;
column++;
}
i++;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You donâ€™t need to write so much code. Have two functions to print one dimensional array.
One will print it left to right.
Other will print it right to left.

Now traverse the given array row wise
If index is even print left to right otherwise right to left.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````def zig_zag(matrix):
row = 0
col = 0

direction = 1
while col < len(matrix[0]):
while 0 <= row < len(matrix):
print matrix[row][col],
row += direction

row -= direction

direction = -1*direction
col += 1

m = [[1,2,3],[4,5,6],[7,8,9]]
zig_zag(m)``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More