Amazon Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

Known best solution for longest palindrom 0(n) "akalin.cx/longest-palindrome-linear-time", I found the idea is quite similar to string matching in that we need to restart the search where it is most make sense (to give a potential better result). While DP solution is generally used, the solution is not any better than a simple solution that consider all position a potential center of the palindrome and then extend its two-ends to the maximal length.

- LinhHA05 July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@LinHA05
Agree! Not only is the DP solution not any faster, but also its code is not any shorter... The simple solution you suggested is a O(N^2) solution btw.

- Chih.Chiu.19 July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
Use Dynamic programming

LP(i,j) = 1 if i = j e.g A
= 1 if i = j-1 AND a[i] != a[j] e.g AB
= 2 if i = j-1 AND a[i] == a[j] e.g AA
= LP(i+1 , j-1) + 2 if i != j-1 AND a[i] == a[j] e.g: ABCBA i =0 and j=4
= max{ LP[i+1,j], LP[i,j-1]} if i != j-1 AND a[i] != a[j] e.g MNOPQ i=0 and j=4

Note: copied from the wiki

- om July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution. The DP solution can provide you the longest palindrome present in the given string. However, I wonder, how you would trace the DP table to print ALL the palindromes available.

There are 2 cool solutions available for this problem at:
stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree

The solution using suffix arrays is complete and is very well explained.

- Murali Mohan July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i may be wrong but i think this algo takes O(n^2) time right??? is there a DP algo that will run in O(n) time?

- oakley July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For any palindrome you can consider the cases:
a. If start and end index are same in a string that is i==j then return 1.
b. if at any position i and j string[i]==string[j] and i+1==j then return 2.
c. if at any position i and j string[i]==string[j] then
return longestPalindrome(string,i+1,j-1)+2 //this is the case for 2 length palindromes.
return max(longestPalindrome(string,i,j-1),longestPalindrome(string,i+1,j))

- vgeek July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using DP, my code is based on Java. The time complexity is O(n^2)

public static int[] getLongest(String str){
		char[] data = str.toCharArray();
		int[] index = new int[data.length];
		int[] buffer = new int[256]; //store pre index
		int max = 0;
		int[] span = new int[2];
		
		for(int i = data.length - 1; i >= 0; i--){
			index[i] = buffer[data[i]] == 0 ? -1 : buffer[data[i]];
			buffer[data[i]] = i;
		}
			
		for(int i = 0; i < index.length && index[i] != -1 ; i++){
			int cur = i;
			int j = index[i];
			while(j != -1){
				for(; j != -1; j = index[j]){
					if(isPaloindromes(data,cur,j) == true){
						if(max < j - cur + 1){
							max = j - cur + 1;
							span[0] = cur;
							span[1] = j;
						}
					}
				}
				int tmp = cur;
				index[tmp] = -1;
				cur = index[cur];
				j = cur == -1 ? -1 : index[cur];
			}
		}
		return span;
	}
	
	public static boolean isPaloindromes(char[] data, int i, int j){
		int mid = (i + j) / 2;
		for(int k = 0; k < mid; k++){
			if(data[i + k] != data[j - k])
				return false;
		}
		return true;
	}

- jialiang.bao August 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Manacher's algorithm

- alex August 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution with O(n^2) worst case.

static void MaxPalindrome(string str)
        {
            int n = str.Length;
            int max = 1;
            for (int i = 0; i < n-1; i++)
            {
                int s = 0;
                int e = 0;
                int cnt = 0;
                if (i>0 && str[i - 1] == str[i + 1]) // odd palindrome
                {
                    s = i - 2;
                    e = i + 2;
                    cnt = 3;
                }
                else if (str[i] == str[i + 1]) //even palindrome
                {
                    s = i - 1;
                    e = i + 2;
                    cnt = 2;
                }
                else 
                {
                    continue;
                }
                while (s >= 0 && e < n)
                {
                    if (str[s] != str[e])
                        break;
                    s--;
                    e++;
                    cnt = cnt + 2;
                }

                Console.WriteLine("\n Palindrome:");
                for (int k = s + 1; k <= e - 1; k++)
                    Console.Write(str[k] + "\t");
                
                if (cnt > max)
                    max = cnt;
                

            }
            Console.WriteLine("\n Max Palindrome Length:" + max);
        }

- vamsi September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#find a way to separate this into chunks
def palindromes(string):
    #smallest palindrome, 2 letters spelled the same when interchanged, e.g aa bb etc, 
    #so compare chars one by one till you get a palindrome or till you get to the end 
    # of list
    string = string.lower()
    word =''
    longest=''
    for i in range(len(string)-1):
        word+=string[i]
        j=i+1
        while not palindrome(word) and j<len(string)-1:
            word+=string[j]
            j+=1
        
        if palindrome(word) and (len(longest) < len(word)):
            longest = word
        word=''

    return longest

#function to determine palindrome
def palindrome(word):
    if len(word) <= 1 :
        return False
    
    for i in range(len(word)):
        if word[i] == word[(len(word)-1) - i]:
            flag = True
        else:
            return False
    return flag
if __name__=='__main__':
	print (palindromes('abfdRacecaRAbAorTITabcdef'))

- SA July 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1]Take the string as an input
2] split it into odd and even numbered characters
3] create a even char string half of count of even characters(this would help in generating a smaller permutation subset)
4] Generate all possible permutations of an even number subset(using dynamic programming)
5] use this list to generate the pallindrome by reversing each string and appending at the end(use odd number characters in the middle of the string).
Below is the implemented code for the same.

#include "stdafx.h"
#include <string>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString);
typedef vector<string> stringVect;
stringVect GenerateSubSets(string setVals,int nIdx);
void GeneratePallindromes(string strEvenCharString,string strOddCharString);

int _tmain(int argc, _TCHAR* argv[])
{
	string strInput = "abfdRacecaRAbAorTITabcdef";
	string strEvenCharString, strOddCharString;
	FindEvenAndOddNumberedCharacters(strInput,strEvenCharString,strOddCharString);
	cout << "Odd Characters: " <<strOddCharString <<endl <<"Even Characters : "<<strEvenCharString << endl;
	cout << "Max Len Pallindrome : "<< strEvenCharString.length()*2 +1 << endl;

	GeneratePallindromes(strEvenCharString,strOddCharString);
	std::getchar();
	return 0;
}
/*
	spit out the pallindromes 
*/
void GeneratePallindromes(string strEvenCharString,string strOddCharString)
{
	int nTotPallinCount=0;
	stringVect vOnesidePallindromes = GenerateSubSets(strEvenCharString,0);
	for(auto strOneSidePallin:vOnesidePallindromes)
	{
		string strReversePallin(strOneSidePallin);
		std::reverse(strReversePallin.begin(), strReversePallin.end());
		cout << strOneSidePallin<<strReversePallin<<endl;
		nTotPallinCount++;
		// take into condsideration the odd characaters use them at the center of the string to pivot around the same.
		for(auto iter= strOddCharString.begin();iter != strOddCharString.end();iter++) 
		{
			cout << strOneSidePallin<<*iter<<strReversePallin<<endl;
			nTotPallinCount++;
		}
	}
	cout << "Total Pallin Drome Count : " <<nTotPallinCount<< endl;
}
/*
	Find out all the odd and even characaters so that they can be used to generate a pallin drome

*/
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString){

	map<char,int> charNoMap;
	// get to each character and get a count of each of the characters
	for(auto iter= strInput.begin();iter != strInput.end();iter++)
	{
		charNoMap[*iter]++;
	}

	// count the characters if they are odd or even if even pick the even stream and push to pallindrome list
	// if odd then just pick 1 character in odd list and push the rest into the even list.
	for (auto iter : charNoMap)
	{
		int nCount = iter.second ;
		if(nCount % 2 != 0) // if odd count
		{
			strOddCharString+=iter.first;
			nCount--;
		}
		if(nCount>0)
		{
			// just spit out half of the even characters to help create pallindromes
			for(auto i=0 ;i<nCount/2;i++) strEvenCharString+=iter.first;
		}
	}
}

/*
	Use dynamic programming to generate the string subsets which can then be used to generate pallindromes
*/
stringVect GenerateSubSets(string setVals,int nIdx){
	stringVect retStringVect;
	if(setVals.length() == nIdx){
		retStringVect.push_back(string()); // pushing empty vector
	}
	else{
		retStringVect = GenerateSubSets(setVals,nIdx+1);
		auto nItem = setVals[nIdx];
		stringVect tempvect;
		for(auto vect:retStringVect)
			tempvect.push_back(vect);
		for(auto iter = tempvect.begin();iter != tempvect.end();iter++){
			iter->push_back(nItem);
		}
		for(auto vect:tempvect)
			retStringVect.push_back(std::move(vect));
	}
	return retStringVect;
}

- shyamal.pandya July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

namespace StringExamples
{
class Program
{
public static void Main(string[] args)
{
FindLongestPalindrome();
}

public static void FindLongestPalindrome()
{
string couldbePalindromes = "abdfRacecaRAbAorTITabcdef";
int palinLength = 2;
int longestPalin = 2;
string longestPalindrome = null;
bool isPalin = false;
while (palinLength < couldbePalindromes.Length / 2)
{
for (int j = 0; j < couldbePalindromes.Length - palinLength; j++)
{
char[] arrayforPalin = new char[palinLength + 1];
for (int i = j, k = 0; i <= palinLength + j; i++, k++)
{
arrayforPalin[k] = couldbePalindromes[i];
}
string couldbePalin = new string(arrayforPalin);
isPalin = CheckForPalindrome(couldbePalin);
if (isPalin == true)
{
Console.WriteLine("We found one palindrome {0} with length {1}", couldbePalin, couldbePalin.Length);
if (couldbePalin.Length > longestPalin)
{
longestPalin = couldbePalin.Length;
longestPalindrome = couldbePalin;
}
}
}
palinLength = palinLength + 1;
}
Console.WriteLine("Longest Palin was of length {0}, {1}", longestPalin, longestPalindrome);
Console.ReadLine();
}

public static bool CheckForPalindrome(string checkforPalin)
{
Stack<char> testPalin = new Stack<char>();
bool isPalin = false;
int i = 0;
if (checkforPalin.Length % 2 == 1)
{
while (i < checkforPalin.Length / 2)
{
testPalin.Push(checkforPalin[i]);
i++;
}
i = (checkforPalin.Length / 2) + 1;
while (i < checkforPalin.Length)
{
char charCompare = testPalin.Pop();
if (charCompare == checkforPalin[i])
{
i++;
isPalin = true;
}
else
{
isPalin = false;
break;
}
}
}

if (checkforPalin.Length % 2 == 0)
{
while (i < checkforPalin.Length / 2)
{
testPalin.Push(checkforPalin[i]);
i++;
}
while (i < checkforPalin.Length)
{
char charCompare = testPalin.Pop();
if (charCompare == checkforPalin[i])
{
i++;
isPalin = true;
}
else
{
isPalin = false;
break;
}
}
}
return isPalin;
}
}
}

- Vaibhav Brid July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I don't have the time to code this now, but I think this can be done in O(N) time by using a stack. Scan each character from the string and push it on to the stack. When you push, just compare the newly scanned char to the top and the second char on the stack. If the new char matches any of the two, it might be the beginning of a palindrome. In which case, pop the top two chars and arrange the newly scanned char and the top two popped chars into a String. Now keep scanning new chars and compare them with the top of the stack. As the palindrome continues, the algo will keep finding matching chars on the top of the stack. Keep popping them and adding them to the beginning and end of the String you have started. The palindrome run ends when a newly scanned char doesn't match the top of the stack, or if the stack is empty. You have just found a palindrome. Put it into a priority queue sorted by string length. Set some flags in your algorithm to indicate that the palindrome run has ended, and empty your stack completely and continue to scan the rest of the chars in the String. Repeat the above process to find more Palindromes. Watch out for even versus odd length palindromes. Once the input string has been scanned, you have found all the palindromes and the priority queue should bring the longest one to the top.

- YK July 26, 2013 | Flag Reply


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