Amazon Interview Question for SDE1s


Country: United States
Interview Type: Written Test




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

Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand

for # a # b # a # a # b # a#

P[] 0 1 0

which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #

for # a # b # a # a # b # a #

P[] 0 1 0 3 0 1 6 1 0 3 0 1 0

which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center

So it shows that at P6 we have longest palindrome. of length 6

'abaaba'

- jerry June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

We can solve this using Dynamic Programming which will take O(n^2) space and will have time complexity of O(n^2) where n is length of string.

However, it can be solved without Dynamic Programming. So, time complexity will be O(n^2) but in constant space.

int longestPalindromicSubstring(char* str)
{
	int len = strlen(str);
	int maxLength = 1;
	int start = 0;
	int low, high;
	
	for(int i = 1; i < len; i++)
	{
		// Find longest even length palindrome with
		// center points as i-1 and i
		low = i-1;
		high = i;
		while(low >= 0 && high < len && str[low] == str[high])
		{
			if(high - low + 1 > maxLength)
			{
				start = low;
				maxLength = high - low + 1;
			}
			low--;
			high++;
		}
		
		// Find longest odd length palindrom with
		// center point as i
		low = i-1;
		high = i+1;
		while(low >= 0 && high < len && str[low] == str[high])
		{
			if(high - low + 1 > maxLength)
			{
				start = low;
				maxLength = high - low + 1;
			}
			low--;
			high++;
		}
	}
	
	printf("Longest Palindromic Substring is: ");
	for(int i = start; i <= start + maxLength - 1; i++)
	{
		printf("%c", str[i]);
	}
	
	return maxLength;
}

- Nitin Gupta June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String is of 'n' length. Palindrome is same around a center, thus there are (2n-3) centers. Taken odd and even length strings and removed the centers at index 0 and (n-1), since they cant be the centers. If they are centers, the palindrome will be a single length character.

Start from the start of the string and for each center, check whether it's a palindrome. If it's a palindrome, expand the center by one index both side.

Time complexity O(n^2) and space is O(1)..

e.g. input : hhgabcbaj, output: abcba..

There are 15 centers, after removing the centers at first and last characters.

center 1: hh (no further expansion), so answer is 'hh'
center 2: hhg - X
center 3: hg - X
center 4: hga - X
center 5: ga - X
center 6: gab - X
center 7: ab - X
center 8: abc - X
center 9: bc - X
center 10: bcb (expand it), abcba (expand it), no further expansion.. answer: 'abcba'
center 11: cb - X
center 12: cba - X
center 13: ba - X
center 14: baj - X
center 15: aj - X

Thus the answer is abcba....

Space complexity O(1) and time complexity O(n^2) worst case.. average case, it's O(n).. But the average case complexity is arguable, so I am keeping it O(n^2) for safe.

- shekhar2010us June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like your solution. But what makes you think average case time complexity might be O(n). We generally don't talk about the average case time complexity for deterministic algorithms.

- Epic_coder June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Manacher’s Algorithm can solve the longest possible substring in linear time

- jerry June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think that this will work, Its not an optimal solution but it will give the desired output.

char* give_longest_palindrome(char* str,int size)	
	{
		char* longest_palindrome;
		int longest_palindrome_size=0;
		for(int i=0;str[i]!='\0';i++)
		{
			for(int j=i;str[j]!='\0';j++)
			{
				if(check_if_palindrome(str,i,j))
				{
					if((j-i)>=longest_palindrome_size)
					{
						longest_palindrome_size=j-i;
						longest_palindrome=new char[longest_palindrome_size+2];
						for(int k=i;k<=j;k++)
						{
							longest_palindrome[k-i]=str[k];
						}
						longest_palindrome[longest_palindrome_size+1]='\0';
					}
				}
			}
		}
			
		return longest_palindrome;
	}

	bool check_if_palindrome(char* str,int left,int right)
	{
		
		while(left<=right)
		{ 
			if(str[left]!=str[right]) return false;
			left++;
			right--;
		}
		return true;
	}

- Omer Kahoot June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The interviewer is always looking for best possible solution. Manachers Algorithm is work optimal and can do it in linear time

- jerry June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah, the best solution will be Manachers Algorithm..

- Omer Kahoot June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is a problem of longest palindrome sub-string.

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int max(int x,int y){
return (x>y)?x:y;
}
int lps(char* seq,int i,int j){
if(i==j)
return 1;
if(seq[i]==seq[j]&&i+1==j)
return 2;
if(seq[i]==seq[j])
return lps(seq,i+1,j-1)+2;
return max(lps(seq,i,j-1),lps(seq,i+1,j));
}
int main()
{ char arr[]="BBABCBCAB";
 int n=strlen(arr);
 printf("the length of the longest substring is %d ",lps(arr,0,n-1));
    return 0;
}

- vgeek June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No..substring and subsequence have different meaning..please google it

- Amit June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry i wrote it sub-sequence but it finds a sub-string you can test it.

- vgeek June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my java implementation. If there are any optimizations that can be done, feel free to let me know. If all of the characters in the array are unique (no duplicates), then the function returns the first letter of the string (as all of the palindrome ranks are 1 in the string).

public class longestPalindromicSubstring {
	
	public static String processString(String s){
		// pads every character in the string with '#'
		// example: string aba -> #a#b#a#, abba -> #a#b#b#a#
		String t = new String("");
		char[] s_c = s.toCharArray();
		int left, right;
		for (int i = 0; i < s_c.length; ++i){
			t += "#" + s_c[i];
		}
		if (s_c[s_c.length-1] != '#')
			t+= "#";
		
		return t;
		
	}

	public static String longestPalindrome(String s){
		String t = processString(s);
		char[] t_array = t.toCharArray();
		int max_size = t.length();
		int[] memo = new int[max_size];
		memo[0] = memo[max_size-1] = 0;
		
		
		for (int i = 1; i < max_size-1;++i){
			int offset = 1;
			int count;
			memo[i] = -1; // value will always be > -1 for the palindrome rank
			if (t_array[i] == '#')
				count = 0;
			else
				count = 1;
			
			while (i + offset < max_size && i - offset > 0){
				if (t_array[i+offset] != t_array[i-offset])
					break;
				if (t_array[i+offset] != '#')
					count += 2;
				
				// if they are part of the palindrome currently being viewed, they will have the same palindrome
				// rank as their counterpart
				memo[i+offset-1] = memo[i-offset+1];
				++offset;
			}
			memo[i] = Math.max(count, memo[i]);
			
		}
		displayArrays(t_array, memo);
		
		// find maximum palindrome rank
		int max, center;
		max = center = 0;
		for (int j = 0; j < max_size; ++j){
			if (memo[j] > max){
				center = j;
				max = memo[j];
			}
		}
		//purely for debugging
		//System.out.println("Max: " + max + " Center: " + center);
		
		return s.substring((center-max)/2, (center+max)/2);
		
	}
	public static void displayArrays(char[] c, int[] v){
		// function purely for the display of the arrays
		// to easier understand what is going on with the algorithm
		System.out.println("Character array: ");
		System.out.print("{" + c[0]);
		for (int i = 1; i < c.length;++i)
			System.out.print(", " + c[i]);
		System.out.println("}");
		
		
		System.out.println("Palindrome value array: ");
		System.out.print("{"+ v[0]);
		for (int i = 1; i < v.length;++i)
			System.out.print(", "+ v[i]);
		System.out.println("}");
	}
	
	
	
	public static void main(String[] args) {
		System.out.println(longestPalindrome("werqrewqaaaabbcbbaaaaadfafde"));
		
		

	}

}

- braaap June 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Pal
{
public static int one;
public static int zero;
	
	public static void setIndex(int z0,int o1)
	{
       one=o1;
	   zero=z0;
	}


public static void main(String ... args)
{
	longpallin();
}
public static int ispallindrome(String s)
	{
boolean status=true;int st=0,ed=0;
ed=s.length()-1;
while(st<=ed)
	{
	if(s.charAt(st)==s.charAt(ed))
		{
		st++;
		ed--;
		}
		else
		{
          status=false;
		  break;
		}
	}
	if(status)
		{
		return (s.length());
//System.out.println("pallindrome");
		}
		else
		{
//System.out.println("not pallindrome");
		return 0;
		}
	}
public static void longpallin()
	{
	String d="racecar";
int max=0;
int len=d.length();
--len;
for(int i=0;i<=len;i++)
	{
	for(int j=i+1;j<=len+1;j++)
	{
		System.out.println(d.substring(i,j));
	int x=ispallindrome(""+d.substring(i,j));
	if(x>0)
		{
		    if(max>x);
			else
				{
				max=x;
                setIndex(i,j);
				}
		}
	
	}
}
System.out.println("Biggest pallindrome String is:");
for(int x=zero;x<one;x++)
System.out.println(d.charAt(x));
System.out.println("length of pallindrome is:"+(one-zero)+"\n with starting index:"
+zero+" and ending index:"+one);
}
}

- Vaibhav Agarwal July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if you use brute force then it will take o(n^2) time i.e. taking two loops and for each substring checking as if it is palindrome or not and finally return the longest substring.
but for optimal solution use manchester method.(linear time complexity)

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

how it will take n^2 time..did you forget to test palindrome which will take one extra iteration ? it means o(n^3) . please don't write only algorithm name like manchester, explain it fully and how it is linear ? Give code snippet.

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

package com.bala.logical;

public class Polindrome {
	public static void main(String[] args) {
		String bigString = "aaabbaaaccdeqjncsdddmmmkkkmmmddd";
		String bigPoli = "";
		for (int i = 0; i < bigString.length(); i++) {
			for (int j = i + 1; j < bigString.length(); j++) {
				String s = bigString.substring(i, j);
				if (isPolindrome1(s)) {
					if (s.length() > bigPoli.length()) {
						bigPoli = s;
					}
				}
			}
		}
		System.out.println(bigPoli);
	}
	
	public static boolean isPolindrome1(String s) {
		int i = 0;
		while (i < s.length()) {
			if (s.charAt(i) != s.charAt(s.length() - i)) {
				return false;
			}
			i++;
		}
		return true;
	}
}

- Balakrishna Konduri July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DP solution
1) Maintain a 2D (N*N) binary hash for a string of size N and initialize to -1.
2) Iterate recursively such that at a particular iteration for two indexes p and q, if str[p]==str[q] refer/compute
hash if str[p+1]...str[q-1] is palindrome.
3) handle edge cases (like q<p).

bool func(char *str,char **hash,int i,int j,int *max,int *I)
{
	if(i>j) return 1;
	if(hash[i][j]!=-1) return hash[i][j];
	if(str[i]==str[j] && func(str,hash,i+1,j-1,max,I)==1)
	{
		hash[i][j]=1;
		if(j-i>*max)
		{
			*max=j-i;
			*I=i;
		}
		return hash[i][j];
    }
	else 
	{
		hash[i][j]=0;
		return (func(str,hash,i+1,j-1,max,I)|| func(str,hash,i,j-1,max,I));		
	}

}

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

#include<iostream>
using namespace std;
int findLongest(string s)
{
    char *elements=new char[s.length()];
    int top=-1;
    int tempLong=0,maxLong=0;
    for(int i=0;i<s.length();i++)
    {
            if((top>=0&&elements[top]==s[i])||(top>0&&elements[top-1]==s[i]))
            {
                 tempLong=0;                                                            
                 if(top>0&&elements[top-1]==s[i])//for palindrome of odd length
                 {
                     top--;
                     tempLong++;
                 }
                 while(top>=0&&elements[top]==s[i])
                 {
                     top--;
                     i++;
                     tempLong+=2;
                 }
                 if(tempLong>maxLong)
                 maxLong=tempLong;
                 top=-1;
            }
            elements[++top]=s[i];
    }
    delete [] elements;
    return maxLong;
}
int main()
{
    string s;
    cout<<"Enter the string:";
    getline(cin,s);
    cout<<"The longest palindrome in the string is of the length: "<<findLongest(s)<<endl;
    system("pause");
    return 0;
}

In this code all the characters in the string are pushed onto a stack and as soon a character is encountered which is the same as the element on the top of the stack, then the elements in the stack are popped until the successive characters of the string match the characters on the top of the stack. There is a counter which counts the number of times the stack is popped. The value of this counter is the length of palindrome. And when a character in the string which is other than what is on the top of stack, then the stack is made empty. The max value of palindrome is checked against the temporary value and the largest value is returned. The worst case order complexity of this algorithm is O(n^2), where n is the length of the string.

- Abhay Gupta October 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Update: This code has O(n) complexity.

- Abhay Gupta October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Manacher algorithm..linear time complexity

- Amit June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/**
	 * time: O(N*N)
	 * space: O(N)
	 */
	private String longestPalindromeSubstring(String str){
		
		String reverted = revert( str );		
			
		int[] maxSub = new int[ str.length() ];	
		
		int maxStrLength = 1;
		int maxStrEnd = 0;

		for( int i = 0; i < str.length(); i++ ){
			
			int[] newSub = new int[ str.length() ];	
			
			char baseCh = str.charAt(i);
			
			newSub[0] = (baseCh == reverted.charAt(0) ?  1 : 0);
			
			for( int j = 1; j < reverted.length(); j++ ){
				
				char revCh = reverted.charAt(j);
				
				if( revCh == baseCh ){
					
					newSub[j] = 1 + maxSub[j-1];
					
					if( newSub[j] > maxStrLength ){
						maxStrEnd = j;
						maxStrLength = newSub[j];
					}					
				}		
			}
			
			maxSub = newSub;			
		}
		
		
		StringBuilder maxStrBuf = new StringBuilder( maxStrLength );
		
		int index = maxStrEnd;
		
		while( maxStrLength > 0 ){			
			maxStrBuf.append( reverted.charAt(index) );			
			--maxStrLength;
			--index;
		}
	
		return maxStrBuf.toString();
	}

- m@}{ June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<iostream>
#include<string>
using namespace std;
void print(string s,int p,int max)
{
	for(int i=0;i<max;i++)
	{
		cout<<s[p+i];
	}
}

void l_palindrome(string s)
{
	int max=0;
	int start,p;
	int end;
	int l=s.length();
	for(int i=1;i<l;i++)
	{
		start=i-1;
		end=i;
		while(start>=0&&end<l&&s[start]==s[end])
		{
			if(end-start+1>max)
			{
				max=end-start+1;
			    p=start;	
			}
			--start;
			++end;
		}
		start=i-1;
		start=i+1;
		while(start>=0&&end<l&&s[start]==s[end])
		{
			if(end-start+1>max)
			{
				max=end-start+1;
				p=start;
			}
			--start;
			++end;
		}
	}
	print(s,p,max);
}

int main()
{
	string s;
	cin>>s;
	l_palindrome(s);
	return 0;
}

- chaitanya June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand

for # a # b # a # a # b # a#

P[] 0 1 0

which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #

for # a # b # a # a # b # a #

P[] 0 1 0 3 0 1 6 1 0 3 0 1 0

which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center and the longest palindrome is at P6

- jerry June 27, 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