Google Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
2
of 8 vote

Looks like you can actually make it O(NK). Basically you create a trie and any time you process a word you check if it is in the trie. If it is, you return true, if not you add reverse of the word to trie and continue to the next one. If you added the last word, it means the answer is no.

- aleksey.klishin May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
13
of 13 votes

If I understand your approach, then you are assuming that in order for two words to combine and form a palindrome, then they must be reflections of each other (e.g. "hi" and "ih" -or- "hello" and "olleh". This is not true. Consider the following:

{"hellol","leh"}
-or-
{"hello", "lleh"}
-or-
{"hellolle", "h"}

Maybe I'm misinterpreting your description?

- dogsitter May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 on dogsitter's comment

- um01 May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

looks like it's difficult for variable length k

- Anonymous May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
7
of 7 votes

We can expand on aleksey.khishin's solution.
The complete algo steps would be like:

1. add the word to trie
2. Each time we pick a work reverse it and search it in the trie.character by character
3a. If the word match but the we still dont reach the sentinel eg. input word is "h" and we already have a "hellolle" in trie. Here we match "h" and then have "ellole" to go. In such a situation we list all the words from "e" onwards which is just "ellole" in this case and check if they are palindrome. if so we have the desired pair.
3b. If a part of input reversed word matches and we reach a sentinel in trie but there is still a suffix of input reveresed remaining e.g. "leh" is in trie and we have "hellol" as new word from the input. Then we will match "hel" from reversed "leh" but "lol" is yet remaining. Here we just check if remaining portion is palindrome. if so we have the desired pair.

Keeping doing this till we reach end of list of input words

- um01 May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi @um01 can you explain with an example that will be great.

- madhur.eng May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 votes

1) Add the first word to the trie ( A B)
2) Take the second word (D E E D B A) and reverse it (A B D E E D)
3) See how many letters in the reversed word you can match in the trie (the first 2)
4) Take the rest of the string (D E E D) see if it is a palindrome if it is you are done return true
5) add the second word to the trie (D E E D B A)
6) go back to step 2 with the next word
7) when out of words return false

- DR A.D.M May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@DRADM, this will not work if first word to be inserted in trie is DEEDBA. And second word comes as AB so if you reverse it (BA) and try to compare in trie. You will end up returning false.

In this scenario, apart from reversing word (BA) and checking trie, we have to take original word (AB) and try to match with the reverse of words which are inserted in tried (DEEDBA) so that will match here.

But it will be expensive to lookup word(AB) in reverse side in trie (DEEDBA).

So to simplify, we need to maintain two tries, when we insert DEEDBA in one trie, we will add ABDEED in second trie. And then for second word first we try to lookup reverse (BA) in first trie and original (AB) in second trie

Here it will be there in second trie and we can apply rest of the logic

- jenish.shah May 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

extending reverse trie solution:
for each word, check if it exists in trie otherwise reverse and insert 3 copies as follows:

for 'hello'
add 'olleh', 'lleh' and 'olle'
This is because for 'hello' possible palindrome could be exact reflection or reflection excluding last 'o' (hell-o-lleh) or reflection excluding first 'h' (olle-h-ello)

trie construction is 3*KN and comparison/reversal is K. So time complexity is O(KN)

- mihya May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@um01 If strings are of variable length then what is k here ?

- xyz May 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@um01 +1. Code based on the algorithm explained by um01. Code finds all one-one pair.

static void findPairs(String[] words, Node root) {
		if (root == null)
			return;

		for (int i = 0, l = words.length; i < l; i++) {
			String str = words[i], s = reverse(str);

			Node curr = root;

			for (int j = 0, len = str.length(); j < len; j++) {
				if (!curr.child.containsKey(s.charAt(j))) {
					// insert word if the first char is not matched or there are
					// characters remaining in both strings
					if (j == 0 || (j < len && !curr.isTerminal)) {
						insert(root, str, i);
						break;
					}

					// chrs remaining in the word
					if (curr.isTerminal && j < len) {
						if (isPalindrome(s.substring(j))) {
							// pair found
							System.out.println(words[curr.index] + ", " + str);
						}

						insert(root, str, i);
						break;
					}
				} else {
					curr = curr.child.get(s.charAt(j));

					// both strings exactly matched
					if (curr.isTerminal) {
						if (j == len - 1) {
							System.out.println(words[curr.index] + ", " + str);
						}
					}
				}
			}

			// chrs remaining in word in Trie
			if (!curr.isTerminal) {
				// continue to check rest is palindrome or not
				StringBuilder rest = new StringBuilder("");

				while (!curr.isTerminal) {
					for (Entry<Character, Node> e : curr.child.entrySet()) {
						rest.append(e.getKey());
						curr = e.getValue();
					}
				}

				if (isPalindrome(rest.toString())) {
					System.out.println(words[curr.index] + ", " + str);
				}
			}
		}
	}

- lazzycoder May 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@aleksey.klishin. what do you mean? DEEDBA, AB are not pair of palindrome. I doubt it is a counter example to @DR A.D.M's solution?

- allen.lipeng47 May 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@um01 for your 3a, if we already have 'hellolle' and 'hellsl' in trie and we now have 'h', we need to check if 'ellolle' and 'ellsl', if one of them is palindrome, we add the pair in our result set. Am I right? If I'm right, for one word, we need to check all possible words after 'h' in tries, how is the time complexity?

- liuweizi610 August 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Maintain 2 tries, one for all words and one for reverse of all words.

For each word w:

1. Search for w in reverse-trie.
Possible results:
- Exact match is found (palindrome found)
- If a leaf or the end of some word in trie is hit before reaching the end of w, the remainder of w must be a palindrome in order for there to be a palindrome with the path traversed so far in the trie

2. Search for reverse of w, w' in non-reverse-trie.
Possible results:
- Exact match is found (palindrome found)
- If we reach the end of w' before hitting the end of a word in the trie, some remainder of the trie rooted at this ending node must be a palindrome in order for there to be a palindrome
- If a leaf is hit before reaching the end of w', then there is no palindrome yet

3. Add w into the non-reverse trie and add w' into the reverse trie

Time complexity: O(k) to reverse each word, traverse tries, and insert into tries * O(n) words = O(kn)

If we know all words are of the same length, then that greatly simplifies the solution and we can simply convert a list of words into a hash set and search for the reverse of each word in the set, which is also O(kn).

- JW May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is k here?

This is my solution in python in O(n^2):

def isPalindrome(string):
	str_length = len(string)
	start = 0 ;
	end = str_length-1

	while(start < end ):
		if( string[start] is not string[end]):
			return False
		
		start+=1
		end-=1
	return True


def testpalindrome(array):
	length = len(array)
	i=0
	pal_dict = dict()
	palindrome_indexes = []
	comparisons = 0;
	while ( i < length):
		j=0
		while( j < length):
			if( i != j):
				key = str(j)+str(i)
				if( key in pal_dict ):
					palindrome_indexes.append(key)
					pal_dict[key]=1
					palindrome_indexes.append(array[i] +"-" + array[j])
				else:
					full_string = array[i] + array[j]
					if( isPalindrome(full_string)):
						palindrome_indexes.append(array[i] +"-" + array[j])
						if( len(array[i]) == len(array[j])):
							pal_dict[str(i)+str(j)]=1
					comparisons+=1
			j+=1
		i+=1

	print "Comparisons : "+ str(comparisons) + "( " + str(length)+ " ) "+ " palindrome indexes: " + str(palindrome_indexes)


testpalindrome(["bat","tabloid","cat","junk"]);   
testpalindrome(["bat","tabloid","cat","ototac","junk"]);   
testpalindrome(["bat","tabloid","cat","tacoto","junk"]);   
testpalindrome(["tacoto","bat","tabloid","cat","junk"]);

- Bharath May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was wondering if we can solve using DP, the intent is to make use of the comparisons already done for palindrome matched pairs. For e.g. if the list is (abc, cat, rat, tac, pat) since cat & tac are palindromes, reuse the comparison results done for cat when iterating for tac.
And also we do not have to compare previous words in the list as we iterate.
If you look at the 2d table, we have to compute only n^2/2 entries as the lower half of the table is self filled and in the remaining entries, palindrome pairs don't have to be recomputed.

- Rishy May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

n^2/2 ~= n^2, but expected n

- Anonymous May 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
public class Palindrome {

public static String reverse(String A) {
String reverse = "";
for (int i = A.length()-1; i >= 0; i--) {
reverse = reverse + A.charAt(i);
}
return reverse;
}

public static void main(String[] args) {
String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
Map<String, String> wordReverseMap = new HashMap<String, String>();

for (int i = 0; i < s.length; i++) {
if (wordReverseMap.containsKey(s[i])) {
System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
} else {
wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
}
}
}
}
}

- deadman May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can solve this problem like this
For simplicity Lets assume that given words are only alphabetical words, we can expand it further no other characters. Also assume that all alphabets are lower case. We can amend algo to accommodate both case.

Two words can be palindrome combined if start char of one is same as end char of another word. Here Idea is create 2 Maps, one for the start char of each word and another for end char of each word.If there are more then one words with same start or end char then they should be stored in the linked list for same key.

Pseudo code:

1. Take two map. Key of the map is char and Value is a list with each node containing a word

2. Iterate through the given array of words

3. For each word, create entry in the first Map for the first char of the word
e.g. for word "pramod" add key value p -> pramod

4. Also create entry in second map for the last char of the word
e.g. for word "pramod" add key value d -> pramod

These steps will complete in O(n) time

5. Now lets iterate through all Keys of the First Map

6. For each key found, get its corresponding value list e.g. key "p" with value "pramod", "praveen" "prime"

7. Iterate over each word in the list for key "P"
Check last char of the value e.g. "d" here for "pramod"

8. Look for the entry in another map with key "d"
8.1 If entry not found there is no possibility of palindrome for this word, just skip it
8.2 If entry found then look for the palindrome property of the word in second dictionary.
8.2.1 If both are the match then save it into the result

O(n) to iterate through all keys
For each key we are comparing only with words which ends by same char so discarding everything else. This is reducing the comparison from O(n2) to O(n) best case. However in worst case it can turn out to O(n2). Eg if all words given starts with 'p' and ends with 'd'

I am thinking if we can further improve this algo to make it work O(n) for worst case
I am ignoring O(k) which is implicit here when words are compared for palindrome

Please point out any mistake in algo or computation of complexity

- pc May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks like Trie is the right solution, above solution is one level of trie

- pc May 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms_Learning
{
    class  TrieNode
    {
        private Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
        private string word;
        public void AddString(string s, string word)
        {
            if (s == "$")
            {
                this.word = word;
                return;
            }
            char character = s[0];
            TrieNode child;
            if (Children.ContainsKey(character))
                child = Children[character];
            else
            {
                child = new TrieNode();
                Children[character] = child;
            }
            if (s.Length == 1)
            {
                child.AddString("$", word);
            }
            else
            {
                string newString = s.Remove(0, 1);
                child.AddString(newString, word);
            }
        }
        public List<string> GetChildWords()
        {
            List<string> result = new List<string>();
            if (word != "")
                result.Add(word);
            else
            {
                foreach (TrieNode child in Children.Values)
                {
                    result.AddRange(child.GetChildWords());
                }
            }
            return result;


        }
        public List<string> GetWordsStartingWith(string prefix)
        {
            char firstCharacter = prefix[0];
            if (prefix.Length==1)
            {

                if (Children.ContainsKey(firstCharacter))
                {
                    TrieNode child = Children[firstCharacter];
                    return child.GetChildWords();
                }
                else
                    return new List<string>();
            }
            else
            {
                if (Children.ContainsKey(firstCharacter))
                {
                    TrieNode child = Children[firstCharacter];
                    string newString = prefix.Remove(0, 1);
                    return child.GetWordsStartingWith(newString);
                }
                else
                    return new List<string>();
            }
        }

    }
   
    class Program
    {
       

        
        static void Main(string[] args)
        {
            List<string> input = new List<string>();
            input.Add("bat");
            input.Add("tab");
            input.Add("tba");
            input.Add("cat");

            FindPalindrome(input);
            
        }

        private static void FindPalindrome(List<string> input)
        {
            TrieNode root = new TrieNode();
            foreach (string s in input)
            {
                root.AddString(s, s);
            }
            foreach (string s in input)
            {
                string reverse = new string(s.Reverse().ToArray());
                List<string> wordsStartingWithReverse = root.GetWordsStartingWith(reverse);
                foreach (string word in wordsStartingWithReverse)
                {
                    if (CanFormPalindrom(word, s))
                    {
                        Console.WriteLine(word + "," + s);
                    }
                }


            }
        }

        static bool CanFormPalindrom(string a,string b)
        {
            string c = a + b;
            for(int i = 0; i<c.Length/2;i++)
            {
                int j = c.Length - 1 - i;
                if (c[i] != c[j])
                    return false;
            }
            return true;
        }
     
     
       
    }
   

}

- Muhammad Adel May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work on {'ab','ccba'}

- y.s August 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. for each word create dictionary entries for possiblePalindrome=>[word]
We do this by:
a) adding an entry for the word reversed if it is not a palindrome.
b) taking any palindrome suffixes of the word and reversing the prefix.
Don't include the first char in this check because there has to be some prefix chars remaining after we find the suffix palindrome so we can know what chars can be added to the suffix palindrome to make it symmetrical.
i.e. For the word 'cata' the palindrome suffixes are 'ata', 'a'.
The dictionary entries for would be: 'c'=>['cata'], 'tac'=>['cata'], 'atac'=>['cata'].
The entry is an array because multiple words might have the same possible palindrome.

2. Now for each word in the list you can look up the words that are palindrome pairs.

findPalindromePairs(['cata', 'c', 'atac', 'tac', 'cat', 'a']);
returns 
   atac, cata
   cata, c
   cata, atac
   cata, tac
   cat, tac
   tac, cat

function findPalindromePairs(list, hash) {

  // for each word, add entries for each possible palindrome pair
  // build dictionary of possiblePalindromePair=>[word] // several words might have same palindrome pairs
  
  list.forEach(function (word) {
    findPossiblePalindromePairs(word, hash);
  });

  // look up each word in the list from the dictionary
  var pairs = [];
  list.forEach(function (word) {
    if (hash[word]) {
      hash[word].forEach(function (match) {
        pairs.push([match, word]);
      });
    }
  });

  return pairs;
}

function findPossiblePalindromePairs(word, hash) {

  // don't add reverse self if word is a palindrome
  // otherwise it will match to itself
  if (!isPalindrome(word)) {
    var wordReversed = reverseWord(word);

    if (!hash[wordReversed]) {
      hash[wordReversed] = [word];
    } else {
      hash[wordReversed].push(word)
    }
  }

  var start = 1; // skip first char
  while (start < word.length) {

    // search for char that matches end char
    if (word[start] === word[word.length - 1]) {

      var palindromeSuffix = word.substring(start, word.length);

      if (isPalindrome(palindromeSuffix)) {
        var prefixReversed = reverseWord(word.substring(0, start))
        if (!hash[prefixReversed]) {
          hash[prefixReversed] = [word];
        } else {
          hash[prefixReversed].push(word)
        }
      }
    }

    start++;
  }
}

function isPalindrome(word) {
  var start = 0;
  var end = word.length - 1;
  while (start < end) {
    if (word.charAt(start) !== word.charAt(end)) {
      return false;
    }
    start++;
    end--;
  }
  return true;
}

function reverseWord(word) {
  var ret = '';
  for (var i = 0; i < word.length; i++) {
    ret = word.charAt(i) + ret;
  }
  return ret;
}

- justinm May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. For each word, store the reverse of the word and the reverse of that word without the last character, in a hashmap where the value is a list containing the actual word(s)
2. For each word, lookup hashmap and return the current word and list of value attached.
3. Use a hashset for removing duplicates before returning the values

- ro May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will not work for i/p like this :- {"hellol","leh"}

- infinity May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is one tricky question, okay here is the solution idea and code.

assume you have these input: [bat , tab , tabaa , aatab]

that output should be [ bat , tab ] [ tabaa, bat ] [ bat , aatab ]

step 1: we will store all words as following in hash table as following that has *key as string*
and value as *hash set* let say for strings to make it easier
( but in my code I store only the index of the word )

for word "bat"

b -> { bat }
ba -> { bat }
bat -> { bat }

no we store it also in reverse direction but not reverse string like this

t - > { bat }
at -> { bat }
bat -> { bat } // it will not repeated since its hash set


this operation will take O(NK) where k is the length of maximum word in the input

Step 2: we will iterate through the words again, and for each word we get the reverse of this word
and look in the hash table for the potential string that will cause them to give correct answer.

ex. if we have bat, we will look for "tab" and in the step one we will have in key "tab" 3 strings
which is { tab , tabaa , aatab }

we will check ( battab && tabbat ), ( battabaa & tabaabat ) , ( tabaatab && tabtabaa) and we will
pick the correct ones without repeating ( sure this will cost us another hash set to make sure no
duplicates in output )

here in my code, I used indices rather than store strings, and the output is pair indices for the
2 words.

Sure someone will ask, is the second for loop O( N K ), try your self any sample input, and you
will find that it will never exceed O( N K ) !

bool isPalindrome(const string& w){
	for (int i = 0; i < w.size(); i++){
		if (w[i] != w[w.size() - 1 - i])
			return false;
	}
	
	return true;
}


vector<pair<int, int> > findPalindrome(const vector<string>& words){
	unordered_map<string, unordered_set<int> > wordsMap;
	unordered_set< pair< int, int > > visitedPairs;

	// O( N * K ) where K is the length of the maximum word characters length in the vector
	for (int i = 0; i < words.size(); i++){
		string s;
		string revDirS;

		s.reserve(words[i].size());
		revDirS.reserve(words[i].size());

		for (int j = 0; j < words[i].size(); j++){
                        // ex. tabaa -> t , ta , tab , taba, tabaa
			s += words[i][j];

                        //ex. tabaa -> a , aa , baa , abaa , tabaa  
			revDirS = words[i][words[i].size() - 1 - j] + revDirS; 

			wordsMap[s].insert(i); // saving the indices rather than the words
			wordsMap[revDirS].insert(i);
		}
	}

	vector< pair<int, int> > ret;

	for (int i = 0; i < words.size(); i++){
		string revWord(words[i]);

		reverse(revWord.begin(), revWord.end());

		for (auto wordsIndex : wordsMap[revWord]){

			if (i == wordsIndex)
				continue; 

			int minIndex = min(i, wordsIndex);
			int maxIndex = max(i, wordsIndex);

			if (visitedPairs.count(make_pair(minIndex, maxIndex)) == 0){

				if (isPalindrome(words[i] + words[wordsIndex])){
					ret.push_back(make_pair(i, wordsIndex));
					visitedPairs.insert(make_pair(minIndex, maxIndex));

				}else if (isPalindrome(words[wordsIndex] + words[i])){
					ret.push_back(make_pair(wordsIndex,i));
					visitedPairs.insert(make_pair(minIndex, maxIndex));
				}
			}
		}
	}

	return ret;
}

- LaithBasilDotNet May 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

void printPalindromePairs(string words[], unsigned int size) {
	
	unordered_map<string, int> wordMap;
	for (unsigned int i = 0; i < size; i++) {
		string word = words[i];
		reverse(word.begin(), word.end());
		unordered_map<string, int>::iterator it = wordMap.find(word);
		if (it == wordMap.end()) {
			wordMap[words[i]] = i;
		}
		else {
			cout << "FOUND : " << words[i] << ", " << word << endl;
			wordMap.erase(it);
		}
	}
}

int main() {
	
	string words[] = {"bat", "cat", "ami", "tac", "tab"};
	printPalindromePairs(words, 5);
	return 0;

}

- Katamaran May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My take on this, I assume all words are of same length which is given in the question as k and contain characters from 1 to 256 in ASCII

1. Iterate over the array going through each word. - O(n)
2. For each word make a bitmap using the character set from ASCII - O(k)
3. Store the bitmap created as the key of a HashMap. (If you want, you can store the index of the word as value)
4. While iterating over the next elements , if you find the calculated bit map as a key, then you have found a pair.

Creating the bit map for each word will be O(k) operation and pushing and getting from the HasMap will be O(1) so the total time complexity will come to O(nk).

- randomCoder1988 May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will work only for words with all unique characters. My bad.

- randomCoder1988 May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript:

var words = ["bat", "tabloid", "cat", "tacoto", "junk", "tab"];
var num = 0;

for (i = 0; i < words.length-1; i++ )
	for (j = i + 1; j < words.length; j++ ){
		num += ispalindrome(words[i], words[j]);
	}

alert (num);

function ispalindrome(word1, word2){
	reverseWord1 = word1.split("").reverse().join("");
	reverseWord2 = word2.split("").reverse().join("");
	
	if ( word1 + word2 == reverseWord2 + reverseWord1 || word2 + word1 == reverseWord1 + reverseWord2 )
		return 1;
	return 0;
}

output: 2

- d.pavel203 May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in case, all words are of equal length - solution is simple. We can simply keep inserting the words in a hashset and while inserting a word - we check if reverse of word already exists in set. If it exists, answer is yes and we break, else answer is no when we reach the end of list.

Complexity is when words are of different length. Here is the proposal, ran over several cases and seem to work fine
1. We shall maintain 2 tries - one for original words (trie1) and one for reversed words (trie2).
2. For each word, check if exists in the trie1. If not, insert it in trie1. Also, look for the word in trie2 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie2 forms the prefix of final palindrome and current word forms the suffix.
3. Reverse each word, check if exists in the trie2. If not, insert it in trie2. Also, look for the word in trie1 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie1 forms the suffix of final palindrome and current word forms the prefix.

Complexity is O (2kn) since each workd is traversed twice

- anonymous May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Should work in O(k * n)...
Basic idea is you go through all Strings and create the possible palindromes.
This is done by reversing the String and checking if substrings of this reversal build a palindrome
with the original String.
(abcb) -> Possible Endings: bcba, cba, a

Furthermore when adding new candidates we cut off parts from the front and check if the rest
is in our palindrome candidates. If the center part is also a palindrome, we have a full palindrome.
(abc) -> Possible Endings: cba
(abc) (dad | cba)

public static String palindromeKN(String[] strs) {
		// Hashtable storing all possible palindrome endings
		Hashtable<String, String> possibleValues = new Hashtable<String, String>();

		for (int i = 0; i < strs.length; i++) {
			String candidate = strs[i];

			// Is our String one of the possible Endings?
			if (possibleValues.containsKey(candidate)) {
				return (possibleValues.get(candidate) + candidate);
			}
			
			
			// Create all possible endings that will lead to a palindrome
			// abcb => bcba, cba, a (go through reverse, cut off a letter and check for palindrome)
			String reverse = new StringBuilder(strs[i]).reverse().toString();
			for (int j = 0; j < reverse.length(); j++) {
				String subString = reverse.substring(j); // cut off first j letters
				if (possibleValues.containsKey(subString)) { // check if this substring is part of the possibilities
					String center = reverse.substring(0, j);
					if (isPalindrome(center)) { // if substring is a possibility, is the rest (what we cut off) also a palindrome?
						return (possibleValues.get(subString) + candidate);
					}
				}
				
				// if the substring is a possible suffix for our candidate add it to hash table
				if (isPalindrome(candidate + subString)) {
					possibleValues.put(subString, candidate);
				}
			}
		}
		return "";
	}
	
	public static boolean isPalindrome(String a) {
		int length = a.length();
		if (length <= 1)
			return true;
		
		for (int i = 0; i < length / 2; i++) {
			if (a.charAt(i) != a.charAt(length - 1 - i)) {
				return false;
			}
		}
		return true;
	}

- snegele May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in the part you are testing to see if the center is palindrome as well you need to check to see whether the size of substring and possibleValues.get(substring) has the same length. e.g. abb + (dccd | a) does not lead to a palindrome.

- Masoud June 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't understand that if (isPalindrome(center)) . Can you explain with an example?

- mbriskar June 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another problem here is that for every string you check every possible reversed substring and the complexity will be (n*k^2) because of this.

- mbriskar June 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

*Edit* sorry for double post, wasn't logged in...

Should work in O(k * n)...
Basic idea is you go through all Strings and create the possible palindromes.
This is done by reversing the String and checking if substrings of this reversal build a palindrome
with the original String.
(abcb) -> Possible Endings: bcba, cba, a

Furthermore when adding new candidates we cut off parts from the front and check if the rest
is in our palindrome candidates. If the center part is also a palindrome, we have a full palindrome.
(abc) -> Possible Endings: cba
(abc) (dad | cba)

public static String palindromeKN(String[] strs) {
		// Hashtable storing all possible palindrome endings
		Hashtable<String, String> possibleValues = new Hashtable<String, String>();

		for (int i = 0; i < strs.length; i++) {
			String candidate = strs[i];

			// Is our String one of the possible Endings?
			if (possibleValues.containsKey(candidate)) {
				return (possibleValues.get(candidate) + candidate);
			}
			
			
			// Create all possible endings that will lead to a palindrome
			// abcb => bcba, cba, a (go through reverse, cut off a letter and check for palindrome)
			String reverse = new StringBuilder(strs[i]).reverse().toString();
			for (int j = 0; j < reverse.length(); j++) {
				String subString = reverse.substring(j); // cut off first j letters
				if (possibleValues.containsKey(subString)) { // check if this substring is part of the possibilities
					String center = reverse.substring(0, j);
					if (isPalindrome(center)) { // if substring is a possibility, is the rest (what we cut off) also a palindrome?
						return (possibleValues.get(subString) + candidate);
					}
				}
				
				// if the substring is a possible suffix for our candidate add it to hash table
				if (isPalindrome(candidate + subString)) {
					possibleValues.put(subString, candidate);
				}
			}
		}
		return "";
	}
	
	public static boolean isPalindrome(String a) {
		int length = a.length();
		if (length <= 1)
			return true;
		
		for (int i = 0; i < length / 2; i++) {
			if (a.charAt(i) != a.charAt(length - 1 - i)) {
				return false;
			}
		}
		return true;
	}

- snegele May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have proposed a Trie solution. I don't think O(nk) is an achievable solution. The worst case would be O(n*(k^2)) in the case of {a, aa, aaa, aaaa, aaaaa}.

A detailed Trie structure is proposed and a solution with example is shown as well. Follow this for more details: cpluspluslearning-petert.blogspot.co.uk/2015/05/data-structure-and-algorithm-trie-and.html

- peter tang May 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check my analysis for this problem: allenlipeng47.com/PersonalPage/index/view/166/nkey

- allen.lipeng47 June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isPalindrome(String inputString) {
    if (inputString.length() == 0 || inputString.length() == 1) {
        return true;
    }
    boolean currentSame = inputString.charAt(0) == inputString.charAt(inputString.length() - 1);
    String remaining = inputString.substring(1, inputString.length() - 1);
    return (same && isPalindrome(remaining));
}

public static class Pair<F, S> {
    F first;
    S second;

    public Pair(F first, S second) {
        this.first = first;
        this.second = second;
    }
}

public static List<Pair<String, String>> getPalindromes(List<String> inputList) {
    Set<String> inputSet = new HashSet<>();
    inputSet.addAll(inputList);
    for (String current : inputList) {
        StringBuilder sb = new StringBuilder(current);
        String reverse = sb.reverse().toString();
        for (int i = 0; i < reverse.length(); i++) {
            String currentReverse = reverse.substring(i);
            if (stringSet.contains(currentReverse)) {
                if (isPalindrome(current + currentReverse)) {
                    returnList.add(new Pair(current, currentReverse));
                }
            }
        }
    }
    return returnList;
}

- buntybittoo June 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Approach:
For a given string, the possible palindromes are a concatenation of the string and a subset of the string's reverse substrings.

For example, if the given string is: "CATA".
The reverse of this string is: "ATAC".
And the set of substrings of the reverse is: {"ATAC", "TAC", "AC", "C"}

Now all possible palindromes with "CATA" can be obtained from a subset of this set.

All possible palindromes with "CATA" are:
"CATA" + "ATAC"
"CATA" + "TAC"
"CATA" + "C"

How this algorithm works:
- Goes through the input list and puts each string in a HashSet for quick lookup
- For each inputString:
-- Find out the reverse of the string
---- For each substring of the reverse:
-------- if it exists in the set:
------------ if concatenating it with the string creates a palindrome
---------------- add the pair to the result

- buntybittoo June 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:
Maintain a trie of words like following:
For each word:
1) Check if reverse of it is already present in trie:
--> Already present: The pair is found. print the pair.
--> Partially present: either new word is longer or existing word is longer. Check is remaining part is palindrome. If yes, your pair is found, print the pair.

2) Add the word to trie.

e.g. input array ["abcd", "cba", "a", "ta", "bc", .... .... ....]
1) check if reverse of "abcd" is in trie ---- no
2) enter "abcd" in try
3) check if reverse of "abc" i.e. "cba" is in trie - yes partially, remaining "d" is palindrome - print the pair.
4) enter "abc" in trie..
5) check reverse of "a" in trie.. will partially match with "abcd", but remaining "bcd" is not palindrome - NO match
6) enter "a" in palindrome
7) check reverse "ta" ... matches with "a" and "t" is remaining... hence match - print pair.
.. similarly for "ba" and so on...

complexity should be N times O(K) where N is number of words... K is len of max size word

- rawat.nav November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Runtime can't better better than O(n^2).

Proof: generate a set such that any pair would make a palindrome (easy). This means the #results = n^2. If your algorithm has less than n^2, it's not likely that it'll produce enough results.

With that in mind, keep it simple: use 2 loops but using other tricks to quickly check if a pair can make a palindrome or not.

- misoul August 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- nitinguptaiit April 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the 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.palindromsWithinString.add(myId);

                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)) {
                    resultHelpers.add(new ResultHelper(myId, pCrawl.idOfThisString));

                }


            }

            for (int rem : pCrawl.palindromsWithinString) {
                resultHelpers.add(new ResultHelper(myId, rem));
            }

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


    }

}

- nitinguptaiit April 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

JavaScript solution, tested on jsfiddle.net/jacklehamster/j5qbharr
Not 100% sure it's O(nk) though. It kinda looks like O(n * k^2)

function findPalinPair(array) {
    
    function flip(str) {
        return str.split("").reverse().join("");
    }
    
    function isPalin(str) {
        for(var i=0;i<str.length/2;i++) {
            if(str.charAt(i)!=str.charAt(str.length-1-i)) {
                return false;
            }
        }
        return true;
    }
    
    //    hash will store all the possible matches
    var hash = {};
    var wordsSeen = {};
    
    for(var i=0;i<array.length;i++) {
        var word = array[i];
        wordsSeen[word] = true;
        if(hash[word]) {
            return isPalin(word+hash[word])?[word,hash[word]]:[hash[word],word];
        }
        
        // first reverse the entry (tacoto=>otocat)
        var rev = flip(word);
        // we know that the reverse would be a match. (tacotootocat)
        hash[rev] = word;
        // some substrings of the reverse (like "cat") are also match
        for(var j=1;j<rev.length-1;j++) {
            var splitLeft = rev.slice(0,j);
            var splitRight = rev.slice(j);
            if(isPalin(splitLeft + word)) {
                if(wordsSeen[splitLeft]) {
                    return [splitLeft,word];
                }
                hash[splitLeft] = word;
            }
            if(isPalin(word + splitRight)) {
                if(wordsSeen[splitRight]) {
                    return [word,splitRight];
                }
                hash[splitRight] = word;
            }
        }
    }
    return null;
}


function test(array) {
    var result = findPalinPair(array);
    document.body.innerHTML += (result?result.join("-"):"nothing") + "<br>";
}

test(["bat","tab","cat","junk"]); // bat-tab
test(["bat","tabloid","cat","junk"]);    //    null
test(["bat","tabloid","cat","ototac","junk"]);    // cat-ototac
test(["bat","tabloid","cat","tacoto","junk"]);    // tacoto-cat
test(["tacoto","bat","tabloid","cat","junk"]);    // tacoto-cat

//    Test with a bunch of random numbers
function testNumber() {
    var array = [];
    for(var i=0;i<100000;i++) {
        array.push(""+Math.floor(Math.random()*100000000));
    }
    test(array);
}

for(var i=0;i<10;i++) testNumber();

- Jack Le Hamster May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

test

- Bharath May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Flip inversion may help in Mergesort

Sorry... it won't help.. I was wrong

- s100banerjee May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

form a list which contains the original words and reverse of each of the word, the size of this new list will be twice the original, perform lexicographic sorting on this list, compare adjacent words, if a word appears twice we get a palindrome, at the end divide the number of such palindromes found by 2 .
like
{bat,tab,cat} reverse list={tab,bat,tac} after meging these two and lexicographic sorting we get
{bat,bat,cat,tab,tab,tac}
we get 2 such pairs (bat,bat) and (tab,tab)
2/2 =1 overall (removing double count)

- abhinav May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

consider {"abhi","ihba", "abhin"}

So the new list will be {"abhi","abhi","ihba","ihba","abhin","nihba"}

Your algo will return 1 but the answer is 2.

- VS May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

consider {"abhi","ihba", "abhin"}

So the new list will be {"abhi","abhi","ihba","ihba","abhin","nihba"}

Your algo will return 1 but the answer is 2.

- VS May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sort will cost you n log (n)

- DR A.D.M May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

As we find a single pair of word we get the answer, right? Or we need to find the number of pair of words? Although worst case complexity will remain same...

- s100banerjee May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Answer:
Can we do it like this?
Create a Hashset of these words.
Then take an iterator from this HashSet. Take out each word and find if the reverse is there in the HashSet. If found remove both of them and go on like this.
reversing a word takes O(k) time.

- s100banerjee May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Assumes 2 words forma a palindrome only if they are reflections of each other, which is not necessarily true. Ex. "hellol" + "leh"

- JW May 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

all words are in equal length of k OR different lengths?

- Anonymous May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Palindrome {

public static String reverse(String A) {
String reverse = "";
for (int i = A.length()-1; i >= 0; i--) {
reverse = reverse + A.charAt(i);
}
return reverse;
}

public static void main(String[] args) {
String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
Map<String, String> wordReverseMap = new HashMap<String, String>();

for (int i = 0; i < s.length; i++) {
if (wordReverseMap.containsKey(s[i])) {
System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
} else {
wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
}
}
}
}

- Deadman May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Palindrome {

	public static String reverse(String A) {
		String reverse = "";
		for (int i = A.length()-1; i >= 0; i--) {
			reverse = reverse + A.charAt(i);
		}
		return reverse;
	}

	public static void main(String[] args) {
		String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
		Map<String, String> wordReverseMap = new HashMap<String, String>();

		for (int i = 0; i < s.length; i++) {
			if (wordReverseMap.containsKey(s[i])) {
				System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
			} else {
				wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
			}
		}
	}
}

- deadman May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesnt work for "batt" and "tab"

- HSLee May 16, 2015 | Flag


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