## Google Interview Question for Software Engineers

• 0
of 0 votes

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;``````

}

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