7区最近有啥蔬菜好种的吗？# gardening - 拈花惹草
c*s
1 楼
不是local的，cst 6am == pst 2pm的skype电面。
没问背景，直接做题。
3个题：
（1） 旋转有序数组 没重复元素 找最小元
（2） 股票那个题，买一次，卖一次，求买进那天、卖出那天、最大利润
（3） batman, 就是n个人，batman认识所有人，所有人都不认识batman，返回batman
的id，没有的话返回-1。给了个api是bool AknowsB(int a,int b)
我说了思路 如果a认识b则b不可能是batman，否则a不可能是batman
然后写代码，一共写了3段，不断优化。
第一段，用了个vector标识是否可能是batman，再用一个vector 每次
收集为true的id。判断相邻两个是否认识，每次扔掉一半，直到剩下一个人，再喝所有
人检查一遍，决定输出他还是-1。时间复杂度O(n)，空间复杂度O(n)。
他说代码可以写得简单点。
第二段，只用了一个vector a,每次判断a[0],a[1]是否认识，决定删掉谁。
他说可以O(1)空间。
第三段，保存一个可能的batman的id x，然后每次判断x和i是否认识，决定是否让
x = i，最后再判断一下输出x还是-1。时间O(n)空间O(1)。 这个就是最优的了。
3个题都做完，大概用了33分钟的样子。原计划面试一个小时。于是面试官让我问问题
，我就问了他们组的设置，组的规模，游戏设计的时间周期，手机游戏和电脑游戏需要
考虑问题的不同，公司对心员工的培训，他们面临的最大挑战之类的。他很热情，闲扯
了一下之后，发现才45-46分钟的样子，但我问不出其他问题了，就say goodbye了。
已经通过了，还要再继续面。
没问背景，直接做题。
3个题：
（1） 旋转有序数组 没重复元素 找最小元
（2） 股票那个题，买一次，卖一次，求买进那天、卖出那天、最大利润
（3） batman, 就是n个人，batman认识所有人，所有人都不认识batman，返回batman
的id，没有的话返回-1。给了个api是bool AknowsB(int a,int b)
我说了思路 如果a认识b则b不可能是batman，否则a不可能是batman
然后写代码，一共写了3段，不断优化。
第一段，用了个vector
收集为true的id。判断相邻两个是否认识，每次扔掉一半，直到剩下一个人，再喝所有
人检查一遍，决定输出他还是-1。时间复杂度O(n)，空间复杂度O(n)。
他说代码可以写得简单点。
第二段，只用了一个vector
他说可以O(1)空间。
第三段，保存一个可能的batman的id x，然后每次判断x和i是否认识，决定是否让
x = i，最后再判断一下输出x还是-1。时间O(n)空间O(1)。 这个就是最优的了。
3个题都做完，大概用了33分钟的样子。原计划面试一个小时。于是面试官让我问问题
，我就问了他们组的设置，组的规模，游戏设计的时间周期，手机游戏和电脑游戏需要
考虑问题的不同，公司对心员工的培训，他们面临的最大挑战之类的。他很热情，闲扯
了一下之后，发现才45-46分钟的样子，但我问不出其他问题了，就say goodbye了。
已经通过了，还要再继续面。
