CareerCup

Design a system for showing quotes on the web.
For example, when the user is looking at page A, part of which is reproduced in page B, the system could highlight part of page A present the user with a link to page B.
This is an open-ended system design question.

What constitutes a quote?
How do you find quotes?
How do you make it scale to the web?
How do you handle updates?
How would you arrange the servers?
What data structures would you use?
How much storage would you need?
How would the user agent present information about quotes?

Implement second/minute/hour/day counters Feb. 4, 2011 8:59pm
Implement the API that counts the number of events in the last sec/min/hr/day:
SMHDCounter {
void Increment();
int LastSecCount(); // also functions for minute, hour
int LastDayCount();
}
Additional requirements
- you require that the data be quite fresh
- how much storage will they take up
- make sure this works for an active counter, getting 100s of events a second.
- keep the implementation fast. E.g. under 10 mS. Or even better motivate by saying we might have 50 of these SMHD counters on a single status page, and ask the candidate how fast their solution should be.

consider a B2C website like Amazon, which will receive thousands requests from buyer per minutes. How will you design the "shop cart " component for it? where should the customs' shop cart data stored?

generic HashMap implementation

Design a scalable server for the hangman game

How do you search thrgough huge flat file?

Determining trending topics


How do you think Twitter determines trending topics?

If needed, explain that trending topics are N most common occurring substrings across all tweets in a given time window, which is constantly moving. Later you can expand the question by putting the scale constraint considering the rate at which tweets come in, etc.

Estimate the # of unique strings with limited memory
Given a large array of strings S = [s1, s2, ... sN], determine Uniq(S) = how many unique strings there are in S.
(b) How large can N be to solve on one machine using only memory?
(c*) What if N is too large to fully fit in memory?

compare "write through cache" and "look aside cache"

implement adding two unsigned numbers without using "+" or "++"

Given a matrix with 1's and 0's, find the number of groups of 1's. A group is defined by horiz/vertically adjacent 1's.

Given an array and a key, sum min subarray whose sum is no less than key. O(n) Time needed

single machine,，given a dictionary(key->value),every entry takes 1KB，totally10 Million个entry，single mutex protecting the dictionary，mutex takes 512 Byte，What potential problems do you see and how would you address them?

Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0

giving lots of intervals [ai, bi], find a point intersect with the most number of intervals

FInd the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 --> 2 4 6

You are given intervals of contiguous integers, like [1, 10), [15, 25), [40, 50), which are non-overlapping and of a fixed size.
Design a data structure to store these intervals and have the operations of insert, delete, and find functions

Design a system to detect typos and provide suggestions to users.

You are going to take some numbers as an input from a file. You need to witer a program to find longest increasing sequence. You should process it as soon as you are taking an input. After finishing the last input immediately you should be able to tell the sequence. Input: 1 5 3 4 6 4 Output: 3 4 6

Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.

Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
design and implement algorithms that correct typos, offering guidance, encouragement, and confirmation along the way

A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.

Implement a read/write lock, given a mutex that has lock() and trylock() interface

Mix two binary strings with special constraints.

You have a file consists of billions of records.
It cannot fit into memory, so you need to reverse every word in that file and save to another file.

estimate the back-end capacity for mobile check in feature

write an iterator function that returns next node in inorder traversal sequence in binary trees. You can write an init() function to initialize what you need

Generate a random 4 letter word from /usr/share/dict/words

A file contains a billion integers, try to find any one integer that is not in the file.

How would you implement hash table on your own? Write the code for implementing your own hash table?

If you wanted to make a highly concurrent cache with a least recently used replacement policy, what data structures would you use? How would this scale per number of threads?

Given a string and a pattern('.' Matches any single character.'*' Matches zero or more of the preceding element.), find the first substring matching this pattern.

• Design the recommendation system for search keywords

• Design a system to support Facebook status update

Design a system for showing quotes on the web?

For example, when the user is looking at page A, part of which is reproduced in page B, the system could highlight part of page A present the user with a link to page B.
What constitutes a quote?
How do you find quotes?
How do you make it scale to the web?
How do you handle updates?
How would you arrange the servers?
What data structures would you use?

FB has decided to award user who submits the billionth search query on a given day a car, by showing them a banner on their search result page. How would you implement such a system?

design the backend system(data structure) of facebook's "like" button

Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then,
starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice).
Whoever reaches N first wins.
The candidate should write a function that given N decides who wins (first or second player)?

Implement a thread-safe Blocking queue in C/C++(POSIX) or Java

design a distributed system to find the 1000th visitor of google.com

Design the backend for a Gmail-like mail system

design and implement a memcache

Design a DHT

Design a site similar to tinyurl.com

given a stream of quotes for a stock from the last trading day. Assume its already time sorted. Find the maximum amount of money you could have made on this stock by making at most N transactions. A buy and a sell is counted as one transaction. For parts N = 1, N = 2 and N = Inf and the generic solution for N = some number (open ended)

• Write a function that finds all the different ways you can split up a word into a concatenation of two other words.

range sum query，array，given i,j.
get sum array[i,j]:

requirement: n^1/2 space/time complexity

Given: for every paper authored, there is a citation count vector. The h-index is a measure of researcher importance.
h-index: The largest number i such that there are i papers each with at least i citations.
1. Suppose that the citation-vector is sorted, how to efficiently compute the h-index?
2. Suppose that the citation-vector is not sorted, how to efficiencly compute the h-index? time complexity? an algorithm with time complexity n?

Definition w-index: The largest number i such that there are i papers, with the lowest paper having at least one citation, the next one has at least two citations and so on, ith paper has i citations.

The citation vector is sorted. How efficiently can you compute the w index? Code this

\e

Google is going to provide an over-the-wire service that the phone companies can use. This over-the-wire protocol will support three operations:
(1) void I_GAVE_OUT(n) -- the phone company is telling us that it handed out phone number (n).
(2) bool IS_TAKEN_(n) -- we are telling the phone company whether (n) is taken.
(3) number GIVE_ME_ONE() - the phone company is letting us tell them what number to hand out next.

ww

q