Amazon Interview Question


Country: United States




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

With O(n) this is possible using suffix tree. Search for previous posts of this questions you'll find it there.

- Grr1967 November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

No sane interview will insist on a better than quadratic complexity for this problem.

Is the "must be better" your own interpretation?

- Anonymous November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a method called suffix array to solve this problem.

Idea is:
For each position i, find the longest continuous common part in two side (before i and after i). like
cbabc
for position 2 (count from 0), the left and right longest common part is 2.

Then the problem is actually to find the longest common part of suffix(i) and prefix(i).

Example:
s1 : aababcbabb

For position 2, we should find the longest common prefix of
babcbabb
baa
which is ba, so the longest palindrome centered at position 2 would be aba.

To find this longest prefix, we cannot use a naive enumeration, we should sort all of suffix and reverted prefix together.

Now the problem is how to sort all suffix and reverted prefix, actually we can first revert the original string (refer as s1'), and append it to s1, like following:

s1#s1' (the # is used as a separator)
then we just sort the suffix in this converted string (because suffix in s1' is reverted prefix of s1), the separator is used to judge whether suffix belongs to s1 or s1'.

To sort the suffix of this appended string, there is a technique called doubling, and it could be found by searching Suffix array.

- Phil November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use Manacher's algorithm for this :

String getLargestPalString(String S) {
 int T = preProcess(S); // Method arranges '#' in between the char in S, before and after the string
 int C = 0;
 int R = 0;

 int n = T.length();
 int[] P = new int[n];

 for(int i = 1; i < n-1; ++i) {
  int i_mirror = 2*C-i;

  P[i] = (R > i) ? (max(P[i_mirror], R-i)) : 0;
 
  while(T.charAt(i+P[i]+1) == T.charAt(i-P[i]-1))
   P[i]++;

 if(R-i < P[i]) { 
   R = i+P[i];
   C = i;
 }
 }

 //Finding max from P to get largest Pal substring
  int max  = -1;
  int index = -1;

  for(int i = 0; i < n; ++i) {
   if(max < P[i]) {
    max = P[i];
    index = i;
   }
  }

 int C = i/2;
 int start = C-max/2;
 int end = C+max/2-(i&1);
 return S.substring(start, end);
}

- srikantaggarwal November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can implement Manacher's algorithm

- USTChucat November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be related with finding all palindromes in a string . O(n^2) tracking the length of palindrome ...

- Anonymous November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala:

def rmDuplicates(s: String): String = s.toList match {
 case Nil => ""
 case c :: rest => c + rmDuplicates(rest.filterNot(e => e == c).mkString)
}


def uniqueSubstr(s: String, xs:List[String]):List[String] = s.toList match {
 case Nil => xs
 case c :: rest  => uniqueSubstr(rest.mkString, (c::(rest.takeWhile(x => x != c))).mkString :: xs)
}

scala> val v = uniqueSubstr("dabcade", Nil).map(s => rmDuplicates(s)).sortWith((x,y) => x.length > y.length)(0)
v: String = bcade

- rbsomeg February 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public string largestPalindrome(string input)
{
int i, j, k, len = input.Length, maxLengthTillNow = 0;
string palindromeString = string.Empty;

for (i = 1; i < len; ++i)
{
// for even length palindrome
if (input[i - 1] == input[i])
{
j = i - 2;
k = i + 1;

//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--;
k++;
}

//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}

// for odd length palindrome
if ((i + 1 < len) && input[i - 1] == input[i + 1])
{

j = i - 2;
k = i + 2;

//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--; k++;
}

//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
}

return palindromeString;
}

- siva November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I expect a valid comment when I see down vote.

- siva November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

do longest common subsequence as per CLRS but reverse either the column or row of characters..

- supermonk247 November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

create another string reverse of original and find LCS of two.

- Arulmozhi November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

{
this is the solution
}

- its me November 29, 2012 | 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