今年6月毕业的多伦多大学EE应届生，目前在一中厂上班，9月份开始寻找大厂工作，内推new grad Canada，10月中旬接到OA，OA两道题非常简单，浇花的园丁，和minimum rotation of dominos。11月初接到电面，面试官听口音是个华人小哥，上来先简单介绍了一下彼此然后直接开始做题。
上来先简单介绍了一下彼此然后直接开始做题
You are allowed three operations (each ofthese is considered a ‘hop’), these are:
-
Divide by 3
-
Divide by 2
-
Subtract 1
Given a positive integer as input, computethe minimum number of hops to reduce the number down to 1.
My answer:
7:
subtract 1 -> 6
divide by 3 -> 2
subtract 1 -> 1
10:
subtract 1 -> 9
divide 3 -> 3
divide 3 -> 1
fn = min(fn -1, fn/2, fn/3)+1
def num_hops(n):
f= [n]*(n+1)
f[1] = 0
for i in range(1,n):
if i*3 <= n:
f[i*3] = min(f[i*3],f+1)
if i*2 <= n:
f[i*2] = min(f[i*2],f+1)
if i+1 <= n:
f[i+1] = min(f[i+1],f+1)
return f[n]
i 1 2 3 4 5 6 7 8 9 10
f 0 1 1 2 3 2 3 3 2 3
这是一道DP的题，我用了数列存答案，当然这样的空间复杂度会比较高，这道题写完后还给他解释了一遍从1到10的对应数列idx的值, 最后就剩下了15分钟 本来想着面试官会继续follow up如何提高空间复杂度，比如说用深度递归，结果他直接甩了第二道题。
Ram was driving past a street with a lot ofhigh rise buildings. Ram wondered, were there any three buildings such thateach is double the height of the previous one. Could you help him figure outthat?
Assume that heights are whole numbers.
Main question: Can you find out how manysuch occurrences are there?
3, 1, 2, 7, 4
return 1
3 1 2 7 4 4 1
return 2
第二题开始只剩下15分钟的时间了，读题理解题还有举例子就花去了5分钟时间。由于过度紧张忽略了题中的关键字眼“previous”，我直接写了一个sort整个list，然后用set和dictionary去解的function。其实sort是没有必要的。这道题要比第一题简单，可惜读题没读清楚，在和面试官clarify的时候他可能也没理解我的思路（感觉他的英文不是很好）。