Jane Street Interview Question: Given a list of words, right ... | Glassdoor

## Interview Question

Software Engineer Interview City of London, England (UK)

# Given a list of words, right a function to return a list of

pairs of palindromes

0

Presume you mean pairs of ANAGRAMS? Otherwise why would palindromes come in pairs?

Simple O(n^2) implementation in Python:

for left in words:
for right in words:
if (not left==right and sorted(left)==sorted(right)):
print (left, right)

Anonymous on Aug 6, 2012
0

from itertools import combinations

def find_anagrams(words):
return [(a, b) for a, b in combinations(set(words), 2) if sorted(a) == sorted(b)]

Edward Betts on Sep 12, 2012
1

A simple C++ solutions. O(nlogn).

void reverse(string &amp;s) {
int len = s.length();
for(int i = 0, j = len-1; i palindromes(vector words) {
if(words.empty()) return words;

vector pal;

sort(words.begin(), words.end());

vector::iterator it = words.begin();
for(; it != words.end(); ) {
string tmp = *it;
reverse(tmp);
if(binary_search(++it, words.end(), tmp)) {
pal.push_back(tmp);
cout&lt;

nriver on Oct 28, 2012
0

std::vector getPalindromePairs(std::vector words) {
std::vector pairs;
for (auto word : words) {
std::string str = word;
std::reverse(str.begin(), str.end());
if (word == str) {
pairs.push_back(word);
}
}
return pairs;
}

Worst case is O(nm) where m is the longest string length.

Daniel on Dec 3, 2013
0

1. Build a HashMap key -&gt; current string, value -&gt; reversed string.
2. Traverse the hashmap, add the strings to a list, where key == Value.
3. return list.

Anonymous on May 13, 2015