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
Answer

Interview Answer

5 Answers

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 &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<

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 -> current string, value -> reversed string.
2. Traverse the hashmap, add the strings to a list, where key == Value.
3. return list.

Anonymous on May 13, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.