Facebook Interview Question for SDETs


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you provide more details? what do you mean combinations of strings?

- tiandiao123 October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zimek October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zimek October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ruge October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Phoenix October 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Weed out strings that can't be formed using characters.
Concatenate remaining strings.

- sri November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Feng January 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

dynamic programming problem.

- Anonymous October 09, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More