Met at campus career fair. Submitted resume. Invited to first round. A lot of chatting, then tech questions. Invited to second round at HQ. Tech interview in the morning, then lunch, and a lot more chatting and getting to know Facebook.

Questions:

Round 1:

• Function to check if two words are anagrams.
• Function to check if any three numbers sum to x.

Round 2:

You are given two streams of data, representing very sparse vectors. You are guaranteed that the two incoming streams are of the same size.

a) Give a data structure optimized for producing the dot product of those sparse vectors. Analyze your runtime/space complexity.

b) What if you are now told that v1 is much sparser than v2? Give another (or the same) data structure optimized for the dot product of any such two vectors (where one is more sparse than the other). Analyze your runtime/space complexity.