k******4
发帖数: 7 | 1 为了防止违反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，虽然都没有去成...
最后祝大家找工作顺利！ | h*****a
发帖数: 40 | | j**********3
发帖数: 3211 | | l*****v
发帖数: 122 | 4 Write a iterator to iterate a nested array.
能不能稍微详细讲下怎么运用stack的啊？ | a***0
发帖数: 53 | | s***c
发帖数: 639 | 6 第一题如果是用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***0
发帖数: 53 | 7
请问hashmap用closed hashing可以么？
【在 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定义不需实现。
| d**********o
发帖数: 279 | 8 没想出怎么用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*****a
发帖数: 237 | | k******4
发帖数: 7 | 10 哈哈，我当时面的时候也随口说了一句，这题cpp不好搞啊，结果他说well, let's do
it in cpp then. 当时心里一万个草泥马奔腾啊！
其实cpp需要一个好的表示方式，代码写起来倒也还简单，就是构造数组比较费行数。
mitbbs代码太难看了，放到gist上：
https://gist.github.com/anonymous/9bcbe32ed4405fa7978f
【在 s***c 的大作中提到】
: 第一题如果是用cpp，输入咋个弄法
| | | k******4
发帖数: 7 | 11 这个和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*******5
发帖数: 52 | 12 如果用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********a
发帖数: 155 | 13 不需要用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**********o
发帖数: 279 | 14 原来大家都喜欢python啊， 哈哈
不过明显stack 的清晰很多。 我还是和大牛有很大差距。 | c*********n
发帖数: 1057 | 15 楼主能不能说下8的解法？还有时间复杂度？这种要递归的怎么分析复杂度我一直不太
会。还有9的复杂度？ | r****t
发帖数: 10904 | 16 第一题最简，最快写法应该是这样，直接了当。
太多人把 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 |
|
