|
|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有帐号？FreeOZ用户注册
x
很久没上来了，来SYD找工作焦头烂额，C++的工作机会，实在是太少太少了，尤其是工作经历不长，水平不突出的我，没有real-time和low-latency编程经验，没有financial经验，真是太难了。还是Java和.NET在这里受欢迎。真是入错行当,真是走很多弯路啊。非常的郁闷。看来得转型了。
昨天Google冒出来给面试通知了。
看了人家给了些sample面试题，看了很久都没思路呢，真是太难了，只能归根于个人水平太差了
1. How do you sort 10 million 7-digit phone numbers with ~1MB RAM? How would you solve this using one pass and no intermediate files? What if 1MB RAM was a firm limit?
2. Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing...why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?
3. Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefg is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?
4. Given a dictionary of English words, find sets of anagrams. For instance, “pots”, “stop”, and “tops” are all anagrams of one another because each can be found by permuting the letters of the others.
5. Write functions for the following date problems: given two dates, compute the number of days between them; given a date, return it’s day of the week; given a month and year, produce a calendar of the month as an array of characters
6. Given a very long sequence (say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? (i.e. how many bits are turned on in the entire sequence)
7. Although Quicksort uses only O(logn) stack space on the average, it can use linear space in the worst case. Explain why, then modify the program to use only logarithmic space in the worst case.
8. Write a program for finding the kth-smallest element in the array x[0...n-1] in O(n) expected time. Your algorithm may permute the elements of x.
9. Build the fastest possible complete function to generate a sorted array of random integers without duplicates. (You need feel constrained to use any prescribed interface for set representation)
10. Implement heap-based priority queues to run as quickly as possible; at what values of n are they faster than sequential structures?
[ 本帖最后由 yangarnet 于 31-10-2012 14:06 编辑 ] |
评分
-
查看全部评分
|
发表于 25-10-2012 08:55:45
收藏
赞
踩
楼主
发表于 25-10-2012 13:07:09
发表于 25-10-2012 13:56:00
