4. social network, billions id, every id has about 100 friends roughly, what is max connections between any two ppls. write algorithm to return min connections between two ids: int min_connection(id1, id2)
you can call following functions expand(id) return friends list of id expandall(list) return friends union of all the ids in the list intersection(list1, list2) return intersection removeintersection(list1, list2)
5. Open google.com, you type some words in the edit box to search something, it will return lots of search results. Among these returning results (that is, website link), you may only CLICK some results that are interesting to you. The system will record the “CLICK”action. Finally, you will have the search results (i.e. url) and “CLICK” informatin at hand. Question: how do you find the similarity of these searching?
6. 如何找出最热门的话题(根据tweets)。如果一个话题一直热门,我们不想考虑怎么办
7. Discuss design challenges of a distributed web crawler running on commercial PCs. How to utilize network bandwidth of those PCs efficiently?
8. Design a site similar to tinyurl.com
9. large log file,含有 customer id, product id, time stamp想得到在某一天中某个custom看网页的次数1. 足够memory 2. limited memory
24. how to design data structures for a facebook network and how to design an algorithm to find connection? How to optimize it if data is distributed into multiple computers?
25. design a deck class and member function to randomly select a card from those cards which haven’t been selected before. (You can assume the number of this function call will never be larger than the number of cards) For example, we have a deck of four card: 1,2,3,4. First it may select 3, then next time it should randomly select one from 1,2,4… And design a member function to reset.
26. google search design problem. How to distribute data and how to design backup system
27. 设计一个online chat system
28. design bit.ly url shortening web service。算法设计,后端存储,中间层cache,前端load balance,最后是web analytics。
29. Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
30. Suppose there are 2 persons A and B on FB . A should be able to view the pictures of B only if either A is friend of B or A and B have at least one common friend . The interviewer discussed it for nearly 30 minutes . The discussion mainly included following points: 1. How are you going to store the list of friends for a given user? 2. File system vs DB 3. Given list of friends of 2 users, how are you going to find common friends? 4. If you are going to store the friends in DB then how will the table look like? 5. How many servers do you need? 6. How are you going to allocate work to servers? 7. How many copies of data will you need? 8. What problems will you face if you are maintaining multiple copies of data.