## Facebook Interview Question for Software Engineer Interns

Interview Type: Phone Interview

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

``````from itertools import combinations

def is_palindrome(my_dict, key_combos):
results = {}

for keys in key_combos:
phrase = my_dict[keys[0]]+my_dict[keys[1]]

if phrase == phrase[::-1]:
results[keys[0]] = my_dict[keys[0]]
results[keys[1]] = my_dict[keys[1]]

return results

if __name__ == "__main__":
my_dict = {"i1": "xenonex", "i2": "xenon", "i3": "none"}

key_combo = list(combinations(my_dict.keys(), 2))
key_combo_reverse = [(i[1], i[0]) for i in key_combo]
key_combo.extend(key_combo_reverse)

results = is_palindrome(my_dict, key_combo)
print(results)``````

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

``````from itertools import combinations

def is_palindrome(my_dict, key_combos):
results = {}

for keys in key_combos:
phrase = my_dict[keys[0]]+my_dict[keys[1]]

if phrase == phrase[::-1]:
results[keys[0]] = my_dict[keys[0]]
results[keys[1]] = my_dict[keys[1]]

return results

if __name__ == "__main__":
my_dict = {"i1": "xenonex", "i2": "xenon", "i3": "none"}

key_combo = list(combinations(my_dict.keys(), 2))
key_combo_reverse = [(i[1], i[0]) for i in key_combo]
key_combo.extend(key_combo_reverse)

results = is_palindrome(my_dict, key_combo)
print(results)``````

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

``````bool isPalindromePair(const string& s1, const string& s2)
{
int totalLength = s1.length() + s2.length();
int maxIndex = totalLength / 2;

for (int idx = 0; idx <= maxIndex; idx++)
{
const string* ptr1 = &s1;
int idx1 = idx;
if (idx1 >= s1.length())
{
ptr1 = &s2;
idx1 -= s1.length();
}

const string* ptr2 = &s2;
int idx2 = idx;
if (idx2 >= s2.length())
{
ptr2 = &s1;
idx2 -= s2.length();
}
idx2 = ptr2->length() - 1 - idx2;

if (ptr1->at(idx1) != ptr2->at(idx2))
return false;
}
return true;
}

void main()
{
vector<string> dictionary = { "none", "xenon", "nonexexenon" };

vector<pair<string*, string*>> results;
for (int i = 0; i < dictionary.size(); i++)
for (int j = i+1; j < dictionary.size(); j++)
if (isPalindromePair(dictionary[i], dictionary[j]) || isPalindromePair(dictionary[j], dictionary[i]))
results.push_back(make_pair(&dictionary[i], &dictionary[j]));

for (auto&& pair : results)
printf("%s %s\n", pair.first->c_str(), pair.second->c_str());

_getch();
}``````

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

I think it would be better to concatenate two strings, and starts from two ends to the middle to check if the pair is palindrome.

String palindrome (String str1, String str2)
{
String str = str1.concat(str2);
int headPointer = 0; endPointer = str.length() -1;

{
return "Not Palidrome";
endPointer++;
}

return "Palindrome";
else
return "Non Palindrome";
}

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

1) Brute force solution : for look for all pairs (si, sj) with (i < j) check if (si concat sj) is a palindrome. Complexity O(n^2 l) where l is max length of input strings

2)
a) Construct trie over all input strings (mark leaves as regular)
b) All all input strings reverse and add to trie (mark these leaves as reversed)
c) For each node on trie, count number of leaves of type reversed that can be reached via paths that are palindromes , say c(node) is this count
d) Sum c(node) where node is a regular leaf

Complexity O(nl) , but very difficult to prove complexity and get working code in 45 minutes

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

Here is solution using trie

``````public class PairOfPalindrome {

static class ResultHelper {
public int index1, index2;

public ResultHelper(int index1, int index2) {
this.index1 = index1;
this.index2 = index2;
}

@Override
public String toString() {
return "{" +
"index1=" + index1 +
", index2=" + index2 +
'}';
}
}

static class TrieNode {

public boolean isLeaf = false;
public Map<Character, TrieNode> children = new HashMap<>();
public List<Integer> palindromsWithinString = new ArrayList<>();
public int idOfThisString = -1;
}

static class Trie {

TrieNode root;

void insert(String toInsert, int myId) {
if (root == null)
root = new TrieNode();

TrieNode pCrawl = root;

for (int i = toInsert.length() - 1; i >= 0; i--) {

char currentChar = toInsert.charAt(i);

if (!pCrawl.children.containsKey(currentChar))
pCrawl.children.put(currentChar, new TrieNode());

if (isPalindrome(toInsert, 0, i))

pCrawl = pCrawl.children.get(currentChar);

}
pCrawl.isLeaf = true;
pCrawl.idOfThisString = myId;

}

private boolean isPalindrome(String toInsert, int from, int to) {

while (from < to && toInsert.charAt(from) == toInsert.charAt(to)) {
from++;
to--;
}

if (from == to)
return true;
return false;
}

public List<ResultHelper> search(String toSearch, int myId) {

List<ResultHelper> resultHelpers = new ArrayList<>();
if (search(toSearch, myId, resultHelpers))
return resultHelpers;
else
return Collections.EMPTY_LIST;

}

private boolean search(String toSearch, int myId, List<ResultHelper> resultHelpers) {
if (null == root)
return false;

TrieNode pCrawl = root;

for (int i = 0; i < toSearch.length(); i++) {

char currentChar = toSearch.charAt(i);

if (!pCrawl.children.containsKey(currentChar))
return false;

pCrawl = pCrawl.children.get(currentChar);

if (pCrawl.idOfThisString >= 0 && pCrawl.idOfThisString != myId
&& isPalindrome(toSearch, i, toSearch.length() - 1)) {

}

}

for (int rem : pCrawl.palindromsWithinString) {
}

return true;
}

}

public static void main(String args[]) {

String[] list = {"abc", "xyxcba", "geekst", "or", "keeg", "bc"};

Trie trie = new Trie();
for (int i = 0; i < list.length; i++)
trie.insert(list[i], i);

for (int i = 0; i < list.length; i++) {
List<ResultHelper> result = trie.search(list[i], i);
if (!result.isEmpty())
System.out.println(result);
}

}

}``````

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.

### 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.