Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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));
}
}
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));
}
}
#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;
}
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))
#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;
}
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;
}
}
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;
}
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;
}
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;
}
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;
}
}
#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();
}
#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();
}
#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();
}
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
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
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;
}
}
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;
}
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;
}
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"
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"
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)
- settyblue July 27, 2016public 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; } }