骑驴找马结束，分享面试题回馈贵版 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

骑驴找马结束，分享面试题回馈贵版

骑驴找马结束，分享面试题回馈贵版# JobHunting - 待字闺中

b*d2015-08-26 07:08

1 楼

amazon上挂了个camcorder卖。病人就写信询问了
Please send pictures attachment & accessories from your personal e-m ail to
可就一个盒子的外观啊。。
照片有啥意义啊。。。。
这是trick还是？谢谢指教

k*42015-08-26 07:08

2 楼

为了防止违反NDA，就不列出公司名了，就是一些常见公司。
1. Write a iterator to iterate a nested array.
For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
用了stack存(array, index)的tuple。
2. LeetCode 原题，120 - Triange。有一点变种，给的是一维数组。
3. Implement HashTable 主要看dynamic expanding
4. Implement MaxHeap.
5. Topology sort，就是版上常见的给一些排过序的未知语言的词，求该语言的字母序
。要求实现核心算法。可以给出一些helper function定义不需实现。
6. LeetCode 付费题 157 & 158 - Read N Characters Given Read4()。提供int
read4(char* buf)，实现int read(char* buf, int len)。read4函数读至多4个字符，
除非EOF，并返回实际读到的字符个数。题没有难度要注意一些细节问题。
7. Given an array with length n + 1. The array contains numbers from 1 to n,
with one of the number duplicated. Now find the duplicated number.
讨论各种解法以及时间空间复杂度，最后实现O(N)时间O(1)空间的解法。数组可以
mutate.
8. Given a bag of characters and a dictionary, find longest string that can
be constructed.
9. Given a grid of characters and a dictionary, find all possible words from
grid.
以上两题都用的标准Trie树解法。讨论复杂度，和优化方案。
10. Given a grid with 'o' and 'x'. Find minimum steps from top-left to
bottom-right without touching 'x'.
a) You can only move right or move down. (BFS or DP)
b) You can move in all 4 directions. (BFS)
11. CS basics. Thread & Process, address space, how memory mapped file works
, etc.
同时感谢版上大牛们的内推：mitbbsfanfan, xjm，虽然都没有去成...
最后祝大家找工作顺利！

l*i2015-08-26 07:08

3 楼

JJWW又不付钱的不要理

h*a2015-08-26 07:08

4 楼

恭喜！

d*r2015-08-26 07:08

5 楼

Don't bother.

j*32015-08-26 07:08

6 楼

恭喜，请问是几年工作经验?

L*32015-08-26 07:08

7 楼

仔细看看email address，来回几次后，接下来就是付钱的email，让你寄到尼日利亚
呵呵

l*v2015-08-26 07:08

8 楼

Write a iterator to iterate a nested array.
能不能稍微详细讲下怎么运用stack的啊？

L*32015-08-26 07:08

9 楼

仔细看看email address，来回几次后，接下来就是付钱的email，让你寄到尼日利亚
呵呵

a*02015-08-26 07:08

10 楼

mark

b*d2015-08-26 07:08

11 楼

是不是最近被某些evil buyer盯上了？又来个inquiry的。。。

s*c2015-08-26 07:08

12 楼

第一题如果是用cpp，输入咋个弄法

【在 k******4 的大作中提到】

: 为了防止违反NDA，就不列出公司名了，就是一些常见公司。
: 1. Write a iterator to iterate a nested array.
: For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
: call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
: 用了stack存(array, index)的tuple。
: 2. LeetCode 原题，120 - Triange。有一点变种，给的是一维数组。
: 3. Implement HashTable 主要看dynamic expanding
: 4. Implement MaxHeap.
: 5. Topology sort，就是版上常见的给一些排过序的未知语言的词，求该语言的字母序
: 。要求实现核心算法。可以给出一些helper function定义不需实现。

a*02015-08-26 07:08

13 楼

请问hashmap用closed hashing可以么？

【在 k******4 的大作中提到】

d*o2015-08-26 07:08

14 楼

没想出怎么用stack, 大牛讲解一下？
"""
Write a iterator to iterate a nested array.
For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
"""
def traverse(l):
if not l:
return
for i in l:
if isinstance(i, list):
traverse(i)
else:
print i
class NestIterator(object):
def __init__(self, l):
self.l = l
self.cur = -1
self.iterator = None

def next(self):
if self.iterator and self.iterator._has_next_element():
return self.iterator.next()
else:
self.iterator = None
if self.cur >= len(self.l)-1:
return None
self.cur += 1
if isinstance(self.l[self.cur], list):
self.iterator = NestIterator(self.l[self.cur])
if self.iterator._has_next_element():
return self.iterator.next()
else:
self.iterator = None
if self._has_next_element():
return self.next()
else:
return None
else:
return self.l[self.cur]
def _has_next_element(self):
"""It is impossible to know if there is next value."""
if (self.cur + 1 <= len(self.l) - 1 or
bool(self.iterator and self.iterator._has_next_element())):
return True
return False
def print_with_iter(l):
iter = NestIterator(l)
for i in range(100):
ele = iter.next()
if ele:
print 'output:', ele
print '================'
if __name__=='__main__':
traverse([1, 2, [3, [4, 5], [6, 7], 8], 9, 10])
print_with_iter([1, 2, [3, [4, 5], [6, 7], 8], 9, 10])
print_with_iter([1, 2, [], [3, [4, 5], [6, 7], 8], 9, [11, 12, 15],10, []])

数据验证：
output: 1
output: 2
output: 3
output: 4
output: 5
output: 6
output: 7
output: 8
output: 9
output: 10
================
output: 1
output: 2
output: 3
output: 4
output: 5
output: 6
output: 7
output: 8
output: 9
output: 11
output: 12
output: 15
output: 10
================

q*a2015-08-26 07:08

15 楼

恭喜！

k*42015-08-26 07:08

16 楼

哈哈，我当时面的时候也随口说了一句，这题cpp不好搞啊，结果他说well, let's do
it in cpp then. 当时心里一万个草泥马奔腾啊！
其实cpp需要一个好的表示方式，代码写起来倒也还简单，就是构造数组比较费行数。
mitbbs代码太难看了，放到gist上：
https://gist.github.com/anonymous/9bcbe32ed4405fa7978f

【在 s***c 的大作中提到】

: 第一题如果是用cpp，输入咋个弄法

k*42015-08-26 07:08

17 楼

这个和tree的iterator是一样的，stack里放(数组，当前下标)。一开始把整个数据放
进去，下标是0。next()的时候看当前元素是数字还是数组。如果是数字就输出，是数
组的话把数组push到stack里去。当前数组做完了就pop出来。记得正确更新下标就行了。
代码见：
https://gist.github.com/anonymous/9bcbe32ed4405fa7978f

【在 l*****v 的大作中提到】

: Write a iterator to iterate a nested array.
: 能不能稍微详细讲下怎么运用stack的啊？

f*52015-08-26 07:08

18 楼

如果用python的话stack里不用放当前下标。当栈顶是数组的话就弹出数组，然后逆序
入栈。以下是python代码，假定只有list 和 basic type 两种类型
class ListIter(object):
def __init__(self, lst):
self.stack = [lst]
def next(self):
if len(self.stack) == 0:
raise StopIteration
while isinstance(self.stack[-1],list):
l = self.stack.pop()
self.stack.extend([i for i in reversed(l) if not isinstance(i,
list) or len(i)>0])
if len(self.stack) == 0:
raise StopIteration
return self.stack.pop()
def __iter__(self):
return self

v*a2015-08-26 07:08

19 楼

不需要用stack，两个指针足够。
class Iterator:

def __init__(self, arr):
self.arr = arr
self.major = 0
self.minor = -1

def next(self):
if type(self.arr[self.major]) != list:
val = self.arr[self.major]
self.major += 1
self.minor = -1
return val
else:
self.minor += 1
if self.minor >= len(self.arr[self.major]):
self.major += 1
self.minor = -1
return self.next()
else:
val = self.arr[self.major][self.minor]
return val

def hasNext(self):
#print self.major, self.minor, '////////////'
if self.major >= len(self.arr):
return False
elif self.major == len(self.arr) - 1:
if type(self.arr[-1]) == list and self.minor >= len(self.arr[-1]
) - 1:
return False
return True

d*o2015-08-26 07:08

20 楼

原来大家都喜欢python啊，哈哈
不过明显stack 的清晰很多。我还是和大牛有很大差距。

c*n2015-08-26 07:08

21 楼

楼主能不能说下8的解法？还有时间复杂度？这种要递归的怎么分析复杂度我一直不太
会。还有9的复杂度？

r*t2015-08-26 07:08

22 楼

第一题最简，最快写法应该是这样，直接了当。
太多人把 python 当 java 写了，除非限制了不让递归。
def iflatten(iterable):
for item in iterable:
try:
for j in iflatten(item):
yield j
except TypeError:
yield item
except StopIteration:
continue
array = [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
print array
for i in iflatten(array):
print i