## Google Interview Question for Software Engineers

• 0

Country: United States
Interview Type: Phone Interview

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

``````public class Main {

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

if(checkToepliz(matrix)){
System.out.println("It is toepliz matrix.");
}else{
System.out.println("It is not a toepliz matrix.");
}
}

public static boolean checkToepliz(int[][] matrix){
for(int i=0; i<matrix.length-1; i++){
for(int j=0; j<matrix[0].length-1; j++){
if(matrix[i][j] != matrix[i+1][j+1]){
return false;
}
}
}
return true;
}
}``````

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

Short and simple in Python:

``````def is_toepliz(matrix):
diags = collections.defaultdict(set)
for r, row in enumerate(matrix):
for c, col in enumerate(row):
diags[c - r] |= {matrix[r][c]}
if len(diags[c - r]) > 1: return False
return True``````

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

``````package com.eb.corealgo;

public class Toepliez {

public boolean isToepliez(int matrix[][]){

boolean isTpepliez=false;

try{

int rows=matrix.length;

int col=1;

int startElement=matrix[0][0];

for(int i=1;i<rows;i++){

int nextElement=matrix[i][col++];

if(nextElement==startElement){
startElement=nextElement;
if(i==rows-1){
isTpepliez=true;
}
continue;
}else if(i==rows-1){
break;
}
}

}
catch(Exception e){
e.printStackTrace();
}

return isTpepliez;
}

//test app
public static void main(String args[]){

Toepliez tz=new Toepliez();

int matrix[][]={

{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}
};

System.out.println(tz.isToepliez(matrix));
}
}``````

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

``````package com.eb.corealgo;

public class Toepliez {

public boolean isToepliez(int matrix[][]){

boolean isTpepliez=false;

try{

int rows=matrix.length;

int col=1;

int startElement=matrix[0][0];

for(int i=1;i<rows;i++){

int nextElement=matrix[i][col++];

if(nextElement==startElement){
startElement=nextElement;
if(i==rows-1){
isTpepliez=true;
}
continue;
}else if(i==rows-1){
break;
}
}

}
catch(Exception e){
e.printStackTrace();
}

return isTpepliez;
}

//test app
public static void main(String args[]){

Toepliez tz=new Toepliez();

int matrix[][]={

{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}
};

System.out.println(tz.isToepliez(matrix));
}
}``````

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

``````#include <iostream>
#include <vector>
using namespace std;

bool checkD(int row, int col, vector<vector<int>> M){
int m=M[0].size();  // number of rows    <= m-1
int n=M.size();     // number of columns <= n-1
int curr, next;

while(true){
curr = M[col][row];

// advance to next cell along diagonal
col++;
row++;

// check next diagonal cell is identical
if( col<n && row<m ){
next = M[col][row];
if( curr!=next ){
return false;
}
}else{
break;
}
}
return true;
}

bool isToepliz(vector<vector<int>> M){
int m=M[0].size();  // number of rows    <= m-1
int n=M.size();     // number of columns <= n-1

// horizontal-percolation at row=0
for(int col=0; col<n; col++){
if(!checkD(0, col, M)){ return false; }
}

// vertical-percolation at col=0
for(int row=0; row<m; row++){
if(!checkD(row, 0, M)){ return false; }
}

// passed both test
return true;
}

void printM(vector<vector<int>> M){
int m = M[0].size();
int n = M.size();
for(int row=0; row<m; row++){
for(int col=0; col<n; col++){
cout << M[col][row] << " ";
}
cout << endl;
}
}

void isToeplizTest(){
cout << "Input matrix, M:" << endl;
vector<vector<int>> M = {
{6,4,1,0},
{7,6,4,1},
{8,7,6,4},
{9,8,7,6},
{2,9,8,7}
};
printM(M);
cout << "Is M toepliz? " <<(isToepliz(M)? "true":"false") << endl;
}

int main(){
isToeplizTest();
return 0;
}``````

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

``````def is_toepliz( matrix) :

col= 0
rw = 0
#move along diagonals strarting from first row. if a diagonal is non-constant return False
while (rw < len(matrix[0]) ) :
current_row = matrix[0][rw]
j = 0
k = 0
while (j < len(matrix) and (rw+k) < len(matrix[0])) :
if matrix[j][rw+k] != current_row :
return False
j = j+1
k = k+1
rw = rw +1

# move along diagonals strarting from first column. if a diagonal is non-constant return False
while(col < len(matrix)) :
current_col = matrix[col][0]
j,k = 0, 0
while (k < len(matrix[0]) and (col +j) < len(matrix)) :
if matrix[col + j][k] != current_col :
return False
j = j + 1
k = k + 1
col = col +1

return True

#examples

matrix = [[1,1,5,0,5],
[0,1,1,5,0],
[0,0,1,1,5],
[0,0,0,1,1]
]

matrix2 = [ [0,1],
[2,1],
[3,1]]

matrix3 = [[1,0,2],
[0,1,0],
[3,0,1]]

for i in range(len(matrix)):
print(matrix[i])

print(is_toepliz(matrix))

for i in range(len(matrix2)):
print(matrix2[i])
print(is_toepliz(matrix2))

for i in range(len(matrix3)):
print(matrix3[i])
print(is_toepliz(matrix3))``````

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

``````public static bool CheckIfToepliz(int [][] matrix){

for(int height = 0 ;  height < matrix.Length -1 ; height++){
for(int width = 0 ; width < matrix[0].Length - 1 ; width++){
if(matrix[height][width] != matrix[height +1 ][width +1])
return false;
}
}
return true;
}``````

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

``````public static bool CheckIfToepliz(int [][] matrix){

for(int height = 0 ;  height < matrix.Length -1 ; height++){
for(int width = 0 ; width < matrix[0].Length - 1 ; width++){
if(matrix[height][width] != matrix[height +1 ][width +1])
return false;
}
}
return true;
}``````

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

``````#include <iostream>
#define M 4
#define N 5

// bottom left to right
bool
checkBTR(int (&A)[M][N]) {
for(int u = M-1; u >= 0; --u) { int l = A[u][0];
for(int i = u, j = 0; i<M; ++i, ++j) {
if(A[i][j] != l) return false;
}
}
return true;
}

// top right to left
bool
checkTRL(int (&A)[M][N]) {
for(int u = N-1; u > 0; --u) { int l = A[0][u];
for(int j = u, i = 0; j<N; ++i, ++j) {
if(A[i][j] != l) return false;
}
}
return true;
}

// driver program
int main(const int argc, const char* argv[]) {
int A[M][N] = {{6, 7, 8, 9, 2},
{4, 6, 7, 8, 9},
{1, 4, 6, 7, 8},
{0, 1, 4, 6, 7}};

if(checkBTR(A) && checkTRL(A))
std::cout << "True" << std::endl;
else
std::cout << "False" << std::endl;

return 0;
}``````

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

I dont think that it is google question.

``````public class Solution {

public static void main(String [] args) {

int [][] matrix = { {6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}};

System.out.println(isToepliz(matrix));

}

public static boolean isToepliz(int [][] matrix) {

int row = matrix.length;
int coloumn = matrix[0].length;

for (int i = 0; i < coloumn; i++) {
int value = matrix[0][i];

for (int first = 0, second = i; first < row && second < coloumn; first++, second++) {
if (matrix[first][second] != value) {
return false;
}
}

}

return true;
}

}``````

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

``````function IsToepliz(oMtx,nRows,nColumns)
{
var nConst;
for(var i=0; i<nColumns; i++)
for(var j=0, nConst=oMtx[0][i]; j<nRows && j+i<nColumns; j++)
if(oMtx[j][j+i] != nConst)
return false;

for(var i=1; i<nRows; i++)
for(var j=0, nConst=oMtx[i][0]; j<nColumns && j+i<nRows; j++)
if(oMtx[i+j][j] != nConst)
return false;

return true;
}``````

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

int isrowfine(int** a,int* ax,int i,int col,int dir,int row){
int j=0, itr=0,itr1=0;
if(dir==0){
j=col-1;
itr=col-1-i;
for(j=col-1;j>=i;j--){
if(ax[itr]!=a[i][j])return 0;
itr--;
}
return 1;
}
j=0;
itr=row-1-i;
for(j=0;j<=i;j++){
if(ax[itr]!=a[i][j])return 0;
itr++;
}
return 1;

}
int istoepliz(int**a,int row,int col){
int i=0;
int *ax=new int[col],dir=0;
for(i=0;i<col;i++){
ax[i]=a[0][i];
}
for(i=1;i<row;i++){
if(!isrowfine(a,ax,i,col,dir,row)){
return 0;
}
}
for(i=0;i<col;i++){
ax[i]=a[row-1][i];
}
dir=1;
for(i=row-2;i>=0;i--){
if(!isrowfine(a,ax,i,col,dir,row)){
return 0;
}
}
return 1;
}

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

int isrowfine(int** a,int* ax,int i,int col,int dir,int row){
int j=0, itr=0,itr1=0;
if(dir==0){
j=col-1;
itr=col-1-i;
for(j=col-1;j>=i;j--){
if(ax[itr]!=a[i][j])return 0;
itr--;
}
return 1;
}
j=0;
itr=row-1-i;
for(j=0;j<=i;j++){
if(ax[itr]!=a[i][j])return 0;
itr++;
}
return 1;

}
int istoepliz(int**a,int row,int col){
int i=0;
int *ax=new int[col],dir=0;
for(i=0;i<col;i++){
ax[i]=a[0][i];
}
for(i=1;i<row;i++){
if(!isrowfine(a,ax,i,col,dir,row)){
return 0;
}
}
for(i=0;i<col;i++){
ax[i]=a[row-1][i];
}
dir=1;
for(i=row-2;i>=0;i--){
if(!isrowfine(a,ax,i,col,dir,row)){
return 0;
}
}
return 1;
}

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

``````public class Toepliz {

public static void main(String[] args) {
int[][] m = {
{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}
};

System.out.println(isToepliz(m));

int[][] m2 = {
{6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,2,8},
{0,1,4,6,7}
};

System.out.println(isToepliz(m2));
}

public static boolean isToepliz(int[][] m) {
int col = m[0].length-1;
int c1 = -1, r1 = -1;
int val = -1;

while (col >= 0) {
c1 = col;
r1 = 0;
val = m[r1][c1];
if (!checkDiagonal(val, m, r1,c1)) {
return false;
}

col--;
}

int row = 1;
while (row < m.length) {
c1 = 0;
r1 = row;
val = m[r1][c1];
if (!checkDiagonal(val, m, r1,c1)) {
return false;
}
row++;
}

return true;
}

private static boolean checkDiagonal(int val, int[][] m, int r1, int c1) {
while(c1 < m[0].length && r1 < m.length) {
if (m[r1][c1] != val) {
return false;
}
r1++;
c1++;
}
return true;
}
}``````

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

{{

bool checkmatrix(const std::vector< std::vector<int>> &a)
{
for (int i = 0; i != N; ++i)
for (int j = 0; j != N; ++j)
if (i > 0 && j > 0 && a[i][j] != a[i-1][j-1]) return false;
return true;
}

}}

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

``````#include<stdio.h>
#include<conio.h>
int main()
{   int m,n,i,j,k,a[10][10];
printf("enter the m and n \n");
scanf("%d%d",&m,&n);
printf("enter the elements of matrix \n");
for(i=0;i<m;i++) {
for(j=0;j<n;j++) {
scanf("%d",&a[i][j]); } }
for(i=0;i<m-1;i++) {
for(j=0;j<n-1;j++) {
if(a[i][j]==a[i+1][j+1])
k=1;
else {
k=2;
goto abc;
} }  }
abc:
if(k==1)
printf("true");
else
printf("false");
getch();
}``````

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

``````#include<stdio.h>
#include<conio.h>
int main()
{   int m,n,i,j,k,a[10][10];
printf("enter the m and n \n");
scanf("%d%d",&m,&n);
printf("enter the elements of matrix \n");
for(i=0;i<m;i++) {
for(j=0;j<n;j++) {
scanf("%d",&a[i][j]); } }
for(i=0;i<m-1;i++) {
for(j=0;j<n-1;j++) {
if(a[i][j]==a[i+1][j+1])
k=1;
else {
k=2;
goto abc;
} }  }
abc:
if(k==1)
printf("true");
else
printf("false");
getch();
}``````

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

``````#include<stdio.h>
#include<conio.h>
int main()
{   int m,n,i,j,k,a[10][10];
printf("enter the m and n \n");
scanf("%d%d",&m,&n);
printf("enter the elements of matrix \n");
for(i=0;i<m;i++) {
for(j=0;j<n;j++) {
scanf("%d",&a[i][j]); } }
for(i=0;i<m-1;i++) {
for(j=0;j<n-1;j++) {
if(a[i][j]==a[i+1][j+1])
k=1;
else {
k=2;
goto abc;
} }  }
abc:
if(k==1)
printf("true");
else
printf("false");
getch();
}``````

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

``````def diffbyone(arr1, arr2):
#this func assumes the two arrays have the same length
#key point is the two array are only different by the last elmt of the first array, and the first element of the last array

m = len(arr1)
for i in range(0, m-1, 1):
if arr1[i] == arr2[i+1]:
continue
else:
return False
return True

def isToepliz(arr):
n = len(arr)
result = True
for i in range(n-1):
result = result and diffbyone(arr[i], arr[i+1])
return result``````

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

A = [ [6,7,8,9,1]
,[4,6,7,8,9]
,[1,4,6,7,8]
,[0,1,4,6,7]
,[0,1,4,6,6]
,[0,1,4,6,6]
,[0,1,4,6,6]
,[0,1,4,6,6]

]

``````def check_toepliz(A):
previous = ''.join([str(a) for a in A[0]])
flag = True
for i in xrange(1,min(len(A[0]),len(A))):
current = ''.join( [str(a) for a in A[i][i:] ] )
previous = previous[:-1]
if int(previous) != int(current):
flag = False
break
previous = current
return flag``````

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

Why do u need two for loops???..this can easily be done by an O(M) algorithm!!

``````public class ToePliz {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {{6, 7, 8, 9, 2},
{4, 6, 7, 8, 9},
{1, 4, 6, 7, 8},
{0, 1, 3, 6, 7}};

System.out.println(toePliz(matrix));
}

private static boolean toePliz(int[][] arr){
int zeroth = arr[0][0];
for(int i=0 ; i< arr.length; i++){
if(arr[i][i] != zeroth)
return false;
}

return true;
}

}``````

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

``````boolean isToepliz ( int [][] matrix ){
if ( matrix == null ) return false;

int height = matrix.length;
if ( height == 0 ) return true;

int width = matrix[0].length;
if ( width == 0 ) return true;

for ( int i = height - 1; i >=0; i-- ){
int initialValue = matrix [i][0];
for ( int j = 1; j + i < height && i < width; j++)
if ( matrix [j+i][j] != initialValue )
return false;

}

//Now, the other diagonals.
for ( int i = 1; i < width; i++){
int initialValue = matrix [0][i];
for ( int j = 1; j + i <height && j < width; j++)
if ( matrix [j][i+j] != initialValue) return false;
}
return true;
}``````

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

``````Input : arr[0..n-1][0..m-1]

1) for rowNum = 1 to n-1 (no need to check the first row)
2) 	for colNum = 1 to m-1 (no need to check the first element for each row)
3)		if ( arr[rowNum][colNum] != arr[rowNum-1][colNum-1]) => return false
(if element does't match it's precending-left-diagonal-parent, return false)
4) return true(if all values match their corresponding preceding-left-diagonal-parent, return true)

public static boolean isToepliz(int[][] matrix)
{
int l = matrix.length;

for (int rowNum = 1; rowNum < l ; rowNum++)
{
for( int colNum = 1; colNum < matrix[rowNum].length; colNum++)
{
if ( matrix[rowNum][colNum] != matrix[rowNum-1][colNum-1])
{
return false;
}
}
}
return true;
}``````

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

``````public boolean isToepliz(int[][] input)
{
for(int line=0 ; line<input.length-1; line++)
{
for(int column=0; column<input[0].length-1;column++ )
if(input[line][column]!=input[line+1][column+1]) return false;
}
return true;
}``````

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

``````public boolean isToepliz(int[][] input)
{
for(int line=0 ; line<input.length-1; line++)
{
for(int col=0; col<input[0].length-1;col++ )
if(input[line][col]!=input[line+1][col+1]) return false;
}
return true;
}``````

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

Can be solved in O(m+n) time

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

item=[[6, 7, 8, 9, 2], [4, 6, 7, 8, 9], [1, 4, 6, 7, 8], [0, 1, 4, 6, 7]]
check= len(item)
check=check-1
count=0
count2=1
last=0
m=[]
while count < check:
val=item[count]
val2=item[count2]
if val[:-1]==val2[1:]:
m.append(1)
elif val[:-1]!=val2[1:]:
last=1
break
count+=1
count2+=1
if last==0:
print "Toepliz"
else:
print "Not Toepliz"

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

yes

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

item=[[6, 7, 8, 9, 2], [4, 6, 7, 8, 9], [1, 4, 6, 7, 8], [0, 1, 4, 6, 7]]
check= len(item)
check=check-1
count=0
count2=1
last=0
m=[]
while count < check:
val=item[count]
val2=item[count2]
if val[:-1]==val2[1:]:
m.append(1)
elif val[:-1]!=val2[1:]:
last=1
break
count+=1
count2+=1
if last==0:
print "Toepliz"
else:
print "Not Toepliz"

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

``````def check_toepliz(grid):
diag_val = dict()

for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
diag = i - j
if diag not in diag_val:
diag_val[diag] = grid[i][j]
elif diag_val[diag] is not grid[i][j]:
return False

return True
grid = [[5,6,7],[4,5,6],[3,4,5]]
print check_toepliz(grid)``````

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

``````public static void isToepliz(int[][] matrix) {
for (int i = 0; i < matrix[0].size; i++) {
if (!isDiagonalConstant(matrix, i, 0) return false;
}
for (int j = 1; j < matrix.size; j++) {
if (!isDiagonalConstant(matrix, i, 0) return false;
}

return true;``````

}

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.

### 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.