CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for Software Engineer / Developers


More Questions from This Interview



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

1. Make a copy of original string and reverse it.
2. Find the longest common sub-sequence in both the string.

- Tulley February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That makes it O(N^2). Better way would be to create a combined Suffix tree for S and reverse(S) and find the lowest internal node. This is only O(N).

- vinod. February 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

write code to make suffix tree on interview? he-he)

- Anonymous February 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you mention and explain the suffix tree solution, I think you will make a very nice impression.

- S February 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep! That would be good unless he asks you to code!

- Anonymous February 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain how will you find the largest palindrome using Suffix Tree. I didn't get you. explain it with the name "ALAM" here ALA is the longest palindrome. No need to code it. Just show me how the lowest internal node finds the solution.

- Karthik February 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose the original string is X
the reverse string is Y

find the largest common repetitive string of X#Y$ (suppose #,$ do not exist in X), that would be the result.

how to find the largest common repetitive string?
just check the suffix tree, find out the one that is not leaf (to make sure its count>=2)
and its length is the max.

- AZ February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int start=0;start<st.length;start++){
  prev=start;next=start
  while(prev>=0 && next<st.length && st[prev]==st[next])
        prev--;next++
  if(found string > Max)
      //save string
  if(start<st.length-1)
    if(st[start]==st[start+1]){
      prev=start-1;next=start+2
      while(prev>=0 && next<st.length && st[prev]==st[next])
        prev--;next++
      if(found string > Max)
        //save string
    }  
}

- Sathya February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Adding to the above solution. We can minimize the number of comparisons by checking if the length is greater than the length of longest palindrome till found.

- Karthik February 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Concatenate the string and reverse of the string to a text.
Create a suffix array which stores the index of the strings.
Do a radix sorting on the suffix array.
Search for the longest palindrome using suffix array properties.

- BVarghese May 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{ Have one pointer at one end and another at the other end compare contents of two pointers if there is no match, decrement end pointer till there is a match now increment and decrement beginning and end pointers and compare contents to confirm presence of palindrome if no match, increment beginning pointer by one and take back the end pointer to last position and restart the whole process - Anonymous February 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wt if string is in form of Singly Linked List..!

- PKT February 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this algorithm is incorrect.
suppose the input is DMAM
if u compare D and M, remove M
how can you find the right result, which is MAM.

We cannot do this, because we do not know whether we should remove the final M or the first D.

- AZ February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class MaxPal {
	public static void main(String[] args) {
		String str = "woddooddaqowwoqad";
		System.out.println(pal(str,0,str.length()-1));
	}
	private static int pal(String str, int lo, int hi) {
		if(lo>=hi) return 0;
		if(str.charAt(lo) == str.charAt(hi)) {
			return pal(str,++lo,--hi) + 2;
		}
		return Math.max(pal(str,++lo,hi), pal(str,lo,--hi));
	}
}

- memo February 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This returns the length, but could be altered to return the actual string.

- memo February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the base case should be

if (lo > hi)
			return 0;
		if (lo == hi)
			return 1;

- Anonymous February 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a exponential solution. memoizing this solution gives O(n^2) algo.. More efficient algos are possible..
O(nlogn) using hashing + binary Search

- madhav March 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is an incorrect solution. Fails for DMAM and many others. Suffix Tree is the way to go. Better efficiency too

- Sid March 22, 2011 | 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