## Google Interview Question for SDE1s

• 6

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.

Comment hidden because of low score. Click to expand.
13

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?

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

+1 on dogsitter's comment

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

looks like it's difficult for variable length k

Comment hidden because of low score. Click to expand.
7

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

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

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

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

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

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

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

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)

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

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

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

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

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

@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?

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

@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?

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

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"]);``````

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.

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

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

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

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

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

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

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;

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;
TrieNode child;
if (Children.ContainsKey(character))
child = Children[character];
else
{
child = new TrieNode();
Children[character] = child;
}
if (s.Length == 1)
{
}
else
{
string newString = s.Remove(0, 1);
}
}
public List<string> GetChildWords()
{
List<string> result = new List<string>();
if (word != "")
else
{
foreach (TrieNode child in Children.Values)
{
}
}
return result;

}
public List<string> GetWordsStartingWith(string prefix)
{
char firstCharacter = prefix;
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>();

FindPalindrome(input);

}

private static void FindPalindrome(List<string> input)
{
TrieNode root = new TrieNode();
foreach (string s in input)
{
}
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;
}

}

}``````

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

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

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

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

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

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

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

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;

}``````

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

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

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

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

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

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

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

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

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.

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

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

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

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.

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

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

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

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<>();
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)) {
}
}
}
}
return returnList;
}``````

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

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

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

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

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.

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

``test``

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

}

}``````

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();``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

test

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

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)

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

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.

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

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.

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

sort will cost you n log (n)

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

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

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

Doesnt work for "batt" and "tab"

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.