Facebook Interview Question
SDETsCountry: United States
import sys
def buildCharHash(chars):
h = {}
for char in chars:
if char not in h.keys():
h[char] = 1
else:
h[char] += 1
return h
def buildStringHash(strings):
h = {}
for string in strings:
l = len(string)
if l not in h.keys():
h[l] = [ string ]
else:
h[l].append(string)
return h
def canBeFormed(s, hc):
cnt = {}
for ch in s:
if ch in hc.keys():
if ch not in cnt.keys():
cnt[ch] = 1
else:
cnt[ch] += 1
if hc[ch] == 1:
del(hc[ch])
elif hc[ch] > 1:
hc[ch] -= 1
else:
return None
return cnt
chrs = map(str, sys.stdin.readline().strip().split(' '))
strs = map(str, sys.stdin.readline().strip().split(' '))
hc = buildCharHash(chrs)
hs = buildStringHash(strs)
answer = ''
ks = hs.keys()
while len(ks) > 0:
k = ks.pop()
candidates = hs[k]
for cand in candidates:
chg = canBeFormed(cand, hc.copy())
if chg != None:
# Discount from hc using chg
for j in chg.keys():
hc[j] -= chg[j]
if hc[j] == 0:
del hc[j]
# Add to total string
answer += cand
print answer
import sys
def buildCharHash(chars):
h = {}
for char in chars:
if char not in h.keys():
h[char] = 1
else:
h[char] += 1
return h
def buildStringHash(strings):
h = {}
for string in strings:
l = len(string)
if l not in h.keys():
h[l] = [ string ]
else:
h[l].append(string)
return h
def canBeFormed(s, hc):
cnt = {}
for ch in s:
if ch in hc.keys():
if ch not in cnt.keys():
cnt[ch] = 1
else:
cnt[ch] += 1
if hc[ch] == 1:
del(hc[ch])
elif hc[ch] > 1:
hc[ch] -= 1
else:
return None
return cnt
chrs = map(str, sys.stdin.readline().strip().split(' '))
strs = map(str, sys.stdin.readline().strip().split(' '))
hc = buildCharHash(chrs)
hs = buildStringHash(strs)
answer = ''
ks = hs.keys()
while len(ks) > 0:
k = ks.pop()
candidates = hs[k]
for cand in candidates:
chg = canBeFormed(cand, hc.copy())
if chg != None:
# Discount from hc using chg
for j in chg.keys():
hc[j] -= chg[j]
if hc[j] == 0:
del hc[j]
# Add to total string
answer += cand
print answer
import sys
def buildCharHash(chars):
h = {}
for char in chars:
if char not in h.keys():
h[char] = 1
else:
h[char] += 1
return h
def buildStringHash(strings):
h = {}
for string in strings:
l = len(string)
if l not in h.keys():
h[l] = [ string ]
else:
h[l].append(string)
return h
def canBeFormed(s, hc):
cnt = {}
for ch in s:
if ch in hc.keys():
if ch not in cnt.keys():
cnt[ch] = 1
else:
cnt[ch] += 1
if hc[ch] == 1:
del(hc[ch])
elif hc[ch] > 1:
hc[ch] -= 1
else:
return None
return cnt
chrs = map(str, sys.stdin.readline().strip().split(' '))
strs = map(str, sys.stdin.readline().strip().split(' '))
hc = buildCharHash(chrs)
hs = buildStringHash(strs)
answer = ''
ks = hs.keys()
while len(ks) > 0:
k = ks.pop()
candidates = hs[k]
for cand in candidates:
chg = canBeFormed(cand, hc.copy())
if chg != None:
# Discount from hc using chg
for j in chg.keys():
hc[j] -= chg[j]
if hc[j] == 0:
del hc[j]
# Add to total string
answer += cand
print answer
public String longString(String sa[], char ca[]) {
Set<String> memo = new HashSet<>();
return recFind(sa, buildCharMap(String.valueOf(ca)), memo, "", 0);
}
public String recFind(String sa[], Map<Character, Integer> charMap,
Set<String> memo, String istr, int i) {
System.out.println(istr+","+i);
if (i >= sa.length)
return istr;
String str1 = "";
if (isValid(istr + sa[i], charMap, memo))
str1 = recFind(sa, charMap, memo, istr + sa[i], i + 1);
String str0 = recFind(sa, charMap, memo, istr, i + 1);
if (str1.length() > str0.length())
return str1;
return str0;
}
public boolean isValid(String str, Map<Character, Integer> charMap, Set<String> memo) {
if (memo.contains(str))
return true;
Map<Character, Integer> strMap = buildCharMap(str);
for (char c : strMap.keySet())
if (!(charMap.containsKey(c) && strMap.get(c) <= charMap.get(c)))
return false;
memo.add(str);
return true;
}
public Map<Character, Integer> buildCharMap(String str) {
Map<Character, Integer> charMap = new HashMap<>();
for (char c : str.toCharArray())
if (charMap.containsKey(c))
charMap.put(c, charMap.get(c) + 1);
else
charMap.put(c, 1);
return charMap;
}
Don't understand why people post the incorrect answer. The python even cannot give the correct answer for the attached the example. This problem is high dimension knapsack problem. Because it has 26 constraint conditions and state is very sparse, we cannot scan all the stats like normal dynamic programming. I think we can use DFS + Memorization
Can you provide more details? what do you mean combinations of strings?
- tiandiao123 October 03, 2017