Facebook Interview Report
- 5of 5 votes
AnswersGiven a hashmap M which is a mapping of characters to arrays of substitute characters, and an input string S, return an array of all possible mutations of S (where any character in S can be substituted with one of its substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersDesign a realtime service that tells users which of their friends are currently online.
Your service must implement two functions:// Return a list of friends of `user_id` that are online List<user_id> getOnlineFriends(user_id) // Tell the service that `user_id` is online setOnline(user_id)
You may assume that you have access to the function `getFriendIds(user_id)` which returns you a list of all friend ids for a given user id
- trunks7j February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer System Design - 1of 1 vote
AnswersGiven an array of real numbers A of length n, and some integer k such that 0 <= k < n, write a function that returns the kth largest number in A, where k=0 refers to the largest number.
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: A = [0.5, 2.5, 1], n=3, k=1 Expected output: 1
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm