trunks7j
BAN USER- 1of 1 vote
AnswersSort a singly-linked list of unknown size using constant space.
- trunks7j in United States| Report Duplicate | Flag | PURGE
Google 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 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer System Design - 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 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
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 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
Find the 1000th largest element using quickselect, which is quick sort modified to only recurse on half of each partition containing the kth largest element. Then, iterate once more to find all elements less then or equal to the 1000th largest element.
import random
def swap(A, x, y):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
def qselect(A, k, left=None, right=None):
left = left or 0
right = right = len(A) - 1
pivot = random.randint(left, right)
pivotVal = A[pivot]
# Move pivot out of the sorting range
swap(A, pivot, right)
swapIndex, i = left, left
while i <= right - 1:
if A[i] < pivotVal:
swap(A, i, swapIndex)
swapIndex += 1
i += 1
# Move pivot to final position
swap(A, right, swapIndex)
# Check if pivot matches, else recurse on the correct half
rank = len(A) - swapIndex
if k == rank:
return A[swapIndex]
elif k < rank:
return qselect(A, k, left=swapIndex+1, right=right)
else:
return qselect(A, k, left=left, right=swapIndex-1)
def find_largest(A, k):
kth_largest = qselect(A, k)
result = []
for item in A:
if item >= kth_largest:
result.append(item)
return result
Solution in python
def find_substring(S, k=1):
if len(S) < 2:
return S
charmap = {} # Track counts for each char
unique = 0 # Track the number of unique characters
longest = '' # Track the longest word
start, end = 0, 0 # Iteration pointers
while end < len(S):
if unique <= k:
end += 1
newchar = S[end - 1]
charmap[newchar] = charmap.get(newchar, 0) + 1
if charmap[newchar] == 1:
unique += 1
else:
start += 1
remchar = S[start - 1]
charmap[remchar] = charmap[remchar] - 1
if charmap[remchar] == 0:
unique -= 1
if len(S[start:end]) > len(longest) and unique <= k:
longest = S[start:end]
return longest
input = 'aabbcbbbadef'
print find_substring(input, k=2)
My solution in python, which is very close to thiago's vector answer:
def find_longest_word(words, letters):
# Maintain a global map of letter counts to check against
table = {}
for letter in letters:
table[letter] = table.get(letter, 0) + 1
longest = ''
for word in words:
# Construct a letter map for this word and short circuit if the word is not valid
wordtable = {}
valid = True
for letter in word:
wordtable[letter] = wordtable.get(letter, 0) + 1
if wordtable[letter] > table.get(letter, 0):
valid = False
break
if valid and len(word) > len(longest):
longest = word
return longest
My solution is similar to Abhi's except that it recurses with a power of 2 search instead of switching to linear once a 1 is found. I'm not positive but I think it is faster on average case. Complexity should still be log n. Below is an implementation in Python:
import random
def findIndex(L, offset=0, tries=0):
skip, curr, last = 0, 0, 0
while True:
tries = tries + 1
if L[curr] == 1:
if last >= curr - 1:
return offset + curr, tries
return findIndex(L[last:curr], last + offset, tries)
elif curr == len(L) - 1:
return len(L), tries
last = curr
curr = min(len(L) - 1, 2 ** skip)
skip = skip + 1
length = 1000 * 1000 * 100
position = random.randint(0, length)
L = [0] * position
L.extend([1] * (length - position))
print "found position at %s in %s tries" % findIndex(L)
A simple solution in python, which iteratively maps the weights to a 0 - 1.0 space, which random.random() is applied to
- trunks7j May 02, 2013