I**********s 发帖数: 441 | 1 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co | t******e 发帖数: 1293 | 2 赞这个详细的准备资料
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| P*******b 发帖数: 1001 | 3 准备了不少啊
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| w******1 发帖数: 520 | 4 刚开始我以为是GOOGLE 面了你这么多的题目, 吓了一身冷汗。 原来是你自己准备的
题目 | s********l 发帖数: 998 | 5 me2~
【在 w******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚开始我以为是GOOGLE 面了你这么多的题目, 吓了一身冷汗。 原来是你自己准备的 : 题目
| y*c 发帖数: 904 | | y**i 发帖数: 1112 | | B*****t 发帖数: 335 | 8 bloom filter 好像需要根据字符串的个数才能确定位数组大小和hash的个数,任意无
穷字符串流怎么用bloom filter?
能不能搞个外部的trie? 也许有更好的方法。
对
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| W***i 发帖数: 9134 | | w*****e 发帖数: 197 | 10 I think the best to do is to ask the interviewer:
1. if we can go through the stream multiple times and
2. if we must build a deterministic algorithm or a probabilistic one.
which I think is very reasonable.
And Bloom filter is essentially a hashing algorithm, and it can not
confirm whether the strings are identical or not (it is used to quickly
confirm two things are not identical, i.e., no hit.) So it is unlikely
the correct answer here.
If we can only go though the stream a limited amount of
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| | | N*D 发帖数: 3641 | 11 赞,这都研究透了,能拿多少offer就看rp了。
问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| Z*****Z 发帖数: 723 | 12 赞!
那个sequence的规律是啥啊?
Get sequence 1, 11, 21, 1211, ...
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| I**********s 发帖数: 441 | 13 Interviewer的意思应该是只能过一次. Bloom filter唯一的问题是false positive,
即虽然不是同一个string, 但是映射到bit array上是一样的. 如果可以和先前的
string比较, 就可以解决这个false positive的问题, 是这个问题的很好的解决方法.
【在 w*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think the best to do is to ask the interviewer: : 1. if we can go through the stream multiple times and : 2. if we must build a deterministic algorithm or a probabilistic one. : which I think is very reasonable. : And Bloom filter is essentially a hashing algorithm, and it can not : confirm whether the strings are identical or not (it is used to quickly : confirm two things are not identical, i.e., no hit.) So it is unlikely : the correct answer here. : If we can only go though the stream a limited amount of
| I**********s 发帖数: 441 | 14 以前有人贴过的,
1
11 : 1个1
21 : 2个1
1211: 1个2, 2个1
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赞! : 那个sequence的规律是啥啊? : Get sequence 1, 11, 21, 1211, ...
| Z*****Z 发帖数: 723 | 15 欧了,多谢
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前有人贴过的, : 1 : 11 : 1个1 : 21 : 2个1 : 1211: 1个2, 2个1
| l******l 发帖数: 497 | | x******3 发帖数: 245 | | m*****g 发帖数: 226 | | w*****e 发帖数: 197 | 19 You can not keep "先前的string".
This is the whole point of the problem here.
If you want to keep previous strings,
then you need to keep the whole stream,
because you don't know which string
is going to show up again.
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Interviewer的意思应该是只能过一次. Bloom filter唯一的问题是false positive, : 即虽然不是同一个string, 但是映射到bit array上是一样的. 如果可以和先前的 : string比较, 就可以解决这个false positive的问题, 是这个问题的很好的解决方法.
| I**********s 发帖数: 441 | 20 是用2-way好还是n-way好, 什么情况下哪个好. 读和写分别要多少次, 给出具体的硬盘
大小和内寸大小, 举例说明该用多少次. 读该怎么读, 写该怎么写, 等等. 这里讲到一
些: http://en.wikipedia.org/wiki/External_sorting
什么奇巧的算法都不用, 就考基本功, 对系统处理的基本理解. 也许就是考查思维方式
吧..
【在 m*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问外部排序有什么细节要问的
| | | I**********s 发帖数: 441 | 21 没错, 上面blueants说的"根据字符串的个数才能确定位数组大小和hash的个数"也对.
无穷多输入就把整个bit-array都变成1了. 当时面试的GG说的是很大的输入, 似乎没说
无穷. 我也问过trie, 但是他说可能会用很多内存也不合适.
【在 w*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You can not keep "先前的string". : This is the whole point of the problem here. : If you want to keep previous strings, : then you need to keep the whole stream, : because you don't know which string : is going to show up again.
| m*****g 发帖数: 226 | 22 恩
看上去是跟file system和os有关
不过此类题目没有定论,怎么答都行。基本就是讨论了
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是用2-way好还是n-way好, 什么情况下哪个好. 读和写分别要多少次, 给出具体的硬盘 : 大小和内寸大小, 举例说明该用多少次. 读该怎么读, 写该怎么写, 等等. 这里讲到一 : 些: http://en.wikipedia.org/wiki/External_sorting : 什么奇巧的算法都不用, 就考基本功, 对系统处理的基本理解. 也许就是考查思维方式 : 吧..
| x***n 发帖数: 464 | | f*******r 发帖数: 1086 | 24 祝好运!
赞的~
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| z*****u 发帖数: 378 | | w**********8 发帖数: 97 | 26 赞楼主人品和实力!
真得很佩服,居然准备得这么全面。
就算此处不留人,自有留人处!good luck!
我也按照这个list好好准备一下了~
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| h**k 发帖数: 3368 | 27 multi-thread programming问的有多细?
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| c******f 发帖数: 2144 | | l**Q 发帖数: 50 | | c****l 发帖数: 1280 | | | | t*******r 发帖数: 2293 | | I**********s 发帖数: 441 | 32 程序的大体构架, 有些什么线程, 分别干嘛, 怎么合作, 线程池的作用, 如果进来的数
据包太多怎么办等等.
【在 h**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : multi-thread programming问的有多细?
| h**k 发帖数: 3368 | 33 多谢。你们讨论的内容局限在具体的语言上,比如Java,还是和编程语言无关?
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 程序的大体构架, 有些什么线程, 分别干嘛, 怎么合作, 线程池的作用, 如果进来的数 : 据包太多怎么办等等.
| I**********s 发帖数: 441 | 34 无关.
【在 h**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢。你们讨论的内容局限在具体的语言上,比如Java,还是和编程语言无关?
| J*********r 发帖数: 5921 | | c**c 发帖数: 2593 | 36 我看了下wikipedia上的介绍,bloom filter近年还出现了一些变种,
其中有一个Stable Bloom Filters,把过期的东西删掉,让filter不
会变满;还有一个Scalable Bloom Filters,当一个filter变满的时
候就按一定条件再加一个filter,也都是各有用途的思路。
.
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没错, 上面blueants说的"根据字符串的个数才能确定位数组大小和hash的个数"也对. : 无穷多输入就把整个bit-array都变成1了. 当时面试的GG说的是很大的输入, 似乎没说 : 无穷. 我也问过trie, 但是他说可能会用很多内存也不合适.
| g***3 发帖数: 2304 | | l****i 发帖数: 396 | | P***P 发帖数: 1387 | 39 有这么多时间复习准备这些东西还不如踏踏实实做点项目....... | c******n 发帖数: 4965 | 40 bloom filter doesn't work. ultimately u need to store the entire
set of uniq keys
so mem is the same
【在 w*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think the best to do is to ask the interviewer: : 1. if we can go through the stream multiple times and : 2. if we must build a deterministic algorithm or a probabilistic one. : which I think is very reasonable. : And Bloom filter is essentially a hashing algorithm, and it can not : confirm whether the strings are identical or not (it is used to quickly : confirm two things are not identical, i.e., no hit.) So it is unlikely : the correct answer here. : If we can only go though the stream a limited amount of
| | | g*********s 发帖数: 1782 | 41 just curious if u really prepare all of the items being listed here.
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| I**********s 发帖数: 441 | 42 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o comparison
- swap two numbers with +/-
- swap two numbers with ^
- given an integer, find the closest number that is palindrome
- implement putlong() by putchar()
2. Bit array
3. Linked list
- find cycle,
- find position of cycle starts
- reverse LL
- delete a node in middle
- each node contains a value pointer pointing to a node,
duplicate LL.
- remove duplicates from sorted/un-sorted LL.
- find n-th to last node to end
- number is represented by LL, add 2 numbers
4. Array
- Longest common substring (LCSubstr)
- Longest common subsequence (LCS).
- Longest increasing subsequence (LIS).
- Longest palingdrome in string.
- array, elements are +/-, find subsequence of max sum
- circular array, elements are +/-, find subsequence of max sum
- find all pairs of integers add up to a sum
- find all pairs of integers add up to a sum,
integers are +/- and sorted
- find one missing number in N numbers in range [0, N]
- find two missing number in N numbers in range [0, N].
- binary search circular array
- Given {a1, a2, a3, ..}, {b1, b2, b3, ...},
get {a1, b1, a2, b2, ...}
- Given 2 arrays A and B, A large enough to hold both,
merge B into A.
5. String
- KMP, Rabin-Karp, Boyer Moore
- reverse string
- reverse words in string
- strcpy, strcmp, strstr, atoi, itoa, strdup
- remove duplicate characters in O(1) space
- Given dictionary, transform one word to another of same length.
- Given large text, find min cover distance of n words.
- find longest word made of other words
- find first non-repeated char
- remove specified char from a string
6. Matrix
- matrix elements are +/-, find submatrix of max sum
- rotate a matrix by 90 degrees
- each cell is black/white, find max subsquare with black border.
- binary matrix, find largest square matrix with 1s
- binary matrix, find largest rectangle matrix with 1s
7. Stack
- implement stack by queue.
- augmented stack with O(1) push, pop, min
- use single array to implement 3 stacks
- sort a stack in ascending order using only
push/pop/top/isEmpty/isFull
8. Queue
- implement queue by 2 stacks
9. Priority Queue
10. Heap
- create heap on array
11. Young Tableau
- find element
- get k-th element
12. BST
- pre/in/post-order traversal, recursive and iterative
- pre/in/post-order traversal, recursive and iterative,
with parent pointer
- find height
- determine IsBST
- find "next" node of a given node in inorder sequence
- find k-th inorder element
- find range of elements
- find diameter
- find all path adding to a sum
- Check if a tree is balanced
- Convert sorted array into balanced BST
- Find first common ancestor of two nodes in a BT or BST
- Link each node to its right sibling
- Print by level (BFS)
- Print by level (BFS) in reverse order
- Determine if 2 BSTs have the same structure
- Create a mirror BT of a BT
- Replicate a linked structure
13. 2-3-4 Tree
14. Red-Black Tree
15. Splay Tree
16. AVL Tree
17. Trie
18. Suffix Array
19. Suffix Tree
- LCSubstr (longest common substring)
- Longest repeated substring
- longest palindrome
- substring search
- data compression
20. B-Tree
21. KD Tree
22. Range Tree
23. Hash Table
24. Bloom filter
25. Disjoint set
26. Graph
- DFS, BFS
- find path existence between two nodes
- Min vertice set covering all edges
- shortest path
- minimum spanning tree
- min edge coverage by vertex
Sorting
1. Bubble sort
2. Insertion sort
3. Selection sort
4. Shell sort
5. Heap sort
6. Quick sort
7. Merge sort
8. N-way merge sort (external sort)
9. Counting sort
10. Bucket sort
Search
1. Linear search
2. Binary search
- Binary search, iterative/recursive
- find missing number is sorted array
- search in circular sorted array
3. Quick Select
Dynamic programming
1. BST
2. COV
3. ILP
4. KS
5. LCS
6. LSP
7. MCM
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP
13. Given array a[], when i < j, get max(a[i] - a[j]).
14. levenshtein edit distance
15. Coin Change problem.
Large-scale system
1. Bloom filter
2. Bit-array/bit-map
3. Heap
4. Hash table
- d-left hashing
5. Sub-division
6. Database indexing
7. Inverted index
8. External sort
9. Map-reduce
Discrete math, Probability and Statistics, Numerical Computation
1. Permutation
- 3 colors, how many ways to color a cube?
- robot, ways to go to diagonal corner on NxN matrix?
- print all combinations of valid n-pairs of parentheses
- print all subsets of a set
2. Combination
3. Sampling
4. Random number generator
- What's a good random number generator?
- Given random generator [1, 2, 3, 4, 5],
generate random in [1..7].
5. Reservoir sampling
6. Find median in stream
7. Card shuffling
8. Primality testing
9. Find prime numbers: naive, sieve of Eratosthenes, sieve of Atkin
10. Randomized primality testing, what's good random generator
11. Fibonacci sequence
12. Factorial numbers
13. Frobenous numbers
14. Newton-Ralphson algorithm
15. Bayes theorem
Computational algebra
1. Convex-hull
2. Closest pairs
Computational theory
1. Automata theory
2. DFA
3. NFA
4. Regular language
5. Pumping lemma
6. Turing machine
7. NP-completeness
1. TSP
2. Vertex-cover problem
3. Set-covering problem.
4. Subset-sum problem.
OS
1. Process and thread
2. Semaphore, mutex, monitor
3. Function call/call frame
4. Context switch
5. Multi-threading
6. Multi-process
7. Thread safety
8. Big/Little-endian
9. Heap/stack
10. Malloc/free
11. Virtual memory, page fault, thrashing
12. DMA (Direct Memory Access)
Networking
1. 7-layer OSI model
2. 4-layer TCP/UDP model
3. TCP/UDP
4. TCP 3-way handshake (ACK machanism),
flow control, congestion control
5. Things happen after entering url
6. Routing protocols: BGP, OSPF, RIP
7. Subnet mask, packet routing on same/different network.
8. Performance
Database
1. Normalization
2. External sorting
3. B-tree, B+-tree.
4. Relational algebra
Compiler
1. LL, SLR, LALR, LR, GLR
2. recursive precedence
3. Operator precedence
4. Postfix evaluation of arithmetic expression
- implement a calculator
C/C++/Java
1. const char *, char * const, const char * const
2. static
3. volatile
4. explicit
5. Object/class
6. Inheritance
7. Encapsulation
8. Polymorphism
9. operator overloading
10. Composition/inheritance
11. Interface, abstract class
12. Struct/class
13. 4 default methods of a C++ struct/class
14. deep copy/shallow copy
15. C++ name hiding
16. C++ smart pointer
17. friend function/class
18. Multiple inheritance
19. Virtual inheritance
20. Constructor
21. Copy/assignment constructor
22. Virtual destructor
23. Virtual function, vtable
24. Pure virtual function
25. Macro, typedef, inline
26. C, C++, Java comparison
27. Garbage collection
28. Dangling pointer, free null pointer, memory leak
29. New/Delete
30. Malloc/free/realloc/calloc
31. Lock
32. Dead lock's four conditions
33. #pragma directive
34. Exception handling
35. try/catch/finally
36. final, finally, finalize
37. Java object reflection
38. C++ templates, java generics
39. Effect of keeping constructor private
40. Pass by Value, reference, pointer
41. Reference v.s. pointer
42. In-memory file system data structures and algorithms?
43. Implement singleton
44. Implement singleton w/o static/global variable
45. Thread programming possible problems
46. sizeof operator.
47. Java: vector v.s. ArrayList
48. int (a*)[10]
49. Implement a lock.
50. Implement a buffer for DataOutputStream.
51. awk, tr, uniq, grep
Other problems
1. 2 eggs, 100 floors, find floor that breaks egg
minimizing number of drops.
2. 5 quart jug and 3 quart jug, measure 4 quarts of water.
3. 100 lockers, open every other i-th locker (i = 1, 2, ..., 100).
Final open?
4. Men on island, can see hat on others only. N men, C hats,
days to remove?
5. 8/12 balls, find the one lighter/heavier
6. 8/12 balls, find one weighs different
7. 2 fuses each burns in 1 hour, measure 45 minutes
8. Bridge crossing, 1, 2, 5, 10. Minual number to pass bridge
9. Orange, apple, orange and apple, all labeled wrong. Find out.
10. 3 light switches, only one can be on at a time. Find it out.
11. Find the biggest, 2 biggest, biggest & smallest
12. n*m*k cube, how many are on the surface?
13. Test a pen, ATM machine, webpage, vending machine, program crash?
14. Given phone #, print all word representations on phone pad.
15. Find overlap of rectangles
16. Find median of two sorted arrays.
17. N computers each hold N numbers. Find median of these N*N numbers.
18. Recontruct a BT from pre/in/post-order traversal
19. Recontruct a BST from pre/in/post-order traversal
20. Find longest prefix common to all strings
21. Implement LRU cache system, O(1) find and update
22. Shifted sorted array, rotate.
23. Histogram, find max internal rectangle.
24. Tournament problem
25. N people, 1 celebrity, find celebrity in O(n) time.
26. 4 jars, 1 polluted so pills weigh +1, find out which jar
27. 25 horses, 5 horses maximal each match. Find the fastest 3
28. Mirror, why left/right reversed, not up/down?
29. How is next_permutation() in STL implemented?
30. N line segments on number axis, calculate common coverage
31. wild card match on patterns * (0-n) and ? (1).
32. Find number of trailing zeros in n!
33. Print square matrix in a spiral inwardly.
34. Find one's phone number given resume only
35. N stairs, each time can go up 1 or 2. How many ways to go up?
36. Find majority element in an array.
37. Two cubes as a calendar
38. Coin change problem
39. Josephus Circle, last survivor?
40. Pick marbles, strategy to win?
41. Get sequence 1, 11, 21, 1211, ...
42. C program that prints itself
43. Print week given date
44. enter code, allow one miss
45. Check equality of two number sets | l*********y 发帖数: 370 | 43 谢谢楼主,真全啊。
都学过,不过真要复习一遍得2个月吧。 | p*****2 发帖数: 21240 | 44
可能要半年。
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢楼主,真全啊。 : 都学过,不过真要复习一遍得2个月吧。
| l*****a 发帖数: 14598 | 45 太夸张了
但是确实DP那一列都看不懂
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 可能要半年。
| a********n 发帖数: 1287 | | w**z 发帖数: 8232 | 47 就找一码工,至于嘛。估计全搞懂,半个PHD也有了吧 | l***2 发帖数: 486 | | b****z 发帖数: 176 | 49 支持一下
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| b****p 发帖数: 216 | | | | b****p 发帖数: 216 | | l****f 发帖数: 6 | | c********g 发帖数: 30 | 53 这个第三题的更好方法的是什么呢?
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| b*********s 发帖数: 115 | | m******s 发帖数: 1469 | 55 Mark
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| E******g 发帖数: 204 | 56 Mark
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| P**********k 发帖数: 1629 | 57 Mark
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| f*******w 发帖数: 1243 | | p******e 发帖数: 14 | | m*****n 发帖数: 2152 | 60 要是我遇到这种题,就在硬盘上建trie,看谁狠。
【在 I**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对 : 重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许 : 是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :( : 总结: 面试既是技术活, 又是运气活. : 无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助. : Interview Qs : Data Structures : 1. Integer : - find number of 1s : - next largest smaller
| | | d*****o 发帖数: 310 | |
|