Google Interview Question
Country: Germany
Interview Type: Phone Interview
l=[] #l[y][x]
#_________0123456789
l.append('100000000')
l.append('110111111')
l.append('111110001')
l.append('000111011')
sx,sy=-1,-1
ex,ey=-1,-1
c=-1
def pix(x,y): #-1 if out of image
if x<0 or x>=len(l[0]) or y<0 or y>=len(l):
return -1
return int(l[y][x])
def isStart(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc!=pix(x-1,y) and cc==pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1)and cc!=pix(x+1,y+1):
return cc
return -1
def isEnd(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc==pix(x-1,y) and cc!=pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1) and cc!=pix(x+1,y+1):
return cc
return -1
def isLine(x,y):
cc=pix(x,y)
if cc!=pix(x,y-1) and cc==pix(x-1,y) and cc!=pix(x,y+1):
return cc
return -1
def draw():
for y in range(len(l)):
for x in range(len(l[0])):
cl = pix(x,y)
if y == sy and y == ey and sx<=x and x <= ex:
print("\033[33;1;%d;9m%d\033[m" %(40+7*cl,cl), end='')
else:
print("\033[33;%dm%d\033[m" %(40+7*cl,cl), end='')
print()
draw()
for i in range(len(l)*len(l[0])):
x = i % len(l[0])
y = int(i / len(l[0]))
cs = isStart(x,y)
cl = isLine(x,y)
ce = isEnd(x,y)
if c>=0:
if ce>=0:
ex,ey=x,y
print("\033[42mFOUN x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d \033[7msx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
break
elif cl>=0: #continue
print("\033[46mCONT x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs<0: #broken no new line
c,sx,sy,ex,ey=cs,-1,-1,-1,-1
print("\033[41mFAIL x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else: #restart new line
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[43mRETR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs>=0:
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[44mSTAR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else:
print("NONE x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
draw()
l=[] #l[y][x]
l.append('100000000')
l.append('110111111')
l.append('111110001')
l.append('000111011')
sx,sy=-1,-1
ex,ey=-1,-1
c=-1
def pix(x,y): #-1 if out of image
if x<0 or x>=len(l[0]) or y<0 or y>=len(l):
return -1
return int(l[y][x])
def isStart(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc!=pix(x-1,y) and cc==pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1)and cc!=pix(x+1,y+1):
return cc
return -1
def isEnd(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc==pix(x-1,y) and cc!=pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1) and cc!=pix(x+1,y+1):
return cc
return -1
def isLine(x,y):
cc=pix(x,y)
if cc!=pix(x,y-1) and cc==pix(x-1,y) and cc!=pix(x,y+1):
return cc
return -1
def draw():
for y in range(len(l)):
for x in range(len(l[0])):
cl = pix(x,y)
if y == sy and y == ey and sx<=x and x <= ex:
print("\033[33;1;%d;9m%d\033[m" %(40+7*cl,cl), end='')
else:
print("\033[33;%dm%d\033[m" %(40+7*cl,cl), end='')
print()
draw()
for i in range(len(l)*len(l[0])):
x = i % len(l[0])
y = int(i / len(l[0]))
cs = isStart(x,y)
cl = isLine(x,y)
ce = isEnd(x,y)
if c>=0:
if ce>=0:
ex,ey=x,y
print("\033[42mFOUN x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d \033[7msx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
break
elif cl>=0: #continue
print("\033[46mCONT x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs<0: #broken no new line
c,sx,sy,ex,ey=cs,-1,-1,-1,-1
print("\033[41mFAIL x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else: #restart new line
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[43mRETR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs>=0:
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[44mSTAR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else:
print("NONE x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
draw()
{
- MR February 29, 2020l=[] #l[y][x]
#_________0123456789
l.append('100000000')
l.append('110111111')
l.append('111110001')
l.append('000111011')
sx,sy=-1,-1
ex,ey=-1,-1
c=-1
def pix(x,y): #-1 if out of image
if x<0 or x>=len(l[0]) or y<0 or y>=len(l):
return -1
return int(l[y][x])
def isStart(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc!=pix(x-1,y) and cc==pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1)and cc!=pix(x+1,y+1):
return cc
return -1
def isEnd(x,y):
cc=pix(x,y)
if cc!=pix(x-1,y-1) and cc!=pix(x,y-1) and cc!=pix(x+1,y-1) and cc==pix(x-1,y) and cc!=pix(x+1,y) and cc!=pix(x-1,y+1) and cc!=pix(x,y+1) and cc!=pix(x+1,y+1):
return cc
return -1
def isLine(x,y):
cc=pix(x,y)
if cc!=pix(x,y-1) and cc==pix(x-1,y) and cc!=pix(x,y+1):
return cc
return -1
def draw():
for y in range(len(l)):
for x in range(len(l[0])):
cl = pix(x,y)
if y == sy and y == ey and sx<=x and x <= ex:
print("\033[33;1;%d;9m%d\033[m" %(40+7*cl,cl), end='')
else:
print("\033[33;%dm%d\033[m" %(40+7*cl,cl), end='')
print()
draw()
for i in range(len(l)*len(l[0])):
x = i % len(l[0])
y = int(i / len(l[0]))
cs = isStart(x,y)
cl = isLine(x,y)
ce = isEnd(x,y)
if c>=0:
if ce>=0:
ex,ey=x,y
print("\033[42mFOUN x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d \033[7msx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
break
elif cl>=0: #continue
print("\033[46mCONT x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs<0: #broken no new line
c,sx,sy,ex,ey=cs,-1,-1,-1,-1
print("\033[41mFAIL x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else: #restart new line
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[43mRETR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
elif cs>=0:
c,sx,sy,ex,ey=cs,x,y,x,y
print("\033[44mSTAR x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
else:
print("NONE x=%2d y=%2d v=%2d cs=%2d cl=%2d ce=%2d c=%2d sx=%2d sy=%2d ex=%2d ey=%2d\033[m" %(x,y,pix(x,y),cs,cl,ce,c,sx,sy,ex,ey))
draw()
}