Amazon Lab126

www.lab126.com
Employer Engaged

Interview Question

Software Development Test Engineer Interview Sunnyvale, CA

I was asked a question about finding the longest palendrome

  in a string. I discovered a naive algorithm relatively quickly, and then was asked to handle all corner cases. Took about 10 minutes.
Answer

Interview Answer

2 Answers

0

It's fairly complex; you would start from center characters and expand to the left and right, looking for palendromatic substrings a character at a time. Worst case complexity is n^2.

Interview Candidate on May 9, 2014
0

public class LongestPalindrome {
    public static String longest(String s, int i, int j) {
        if(i > j) {
            return "";
        }
        if (i == j) {
            return s.substring(i, j + 1);
        }
        if (s.charAt(i) == s.charAt(j)) {
            String intermediate = longest(s, i + 1, j - 1);
            if (intermediate.length() == j - i - 1) {
                return s.charAt(i) + intermediate + s.charAt(j);
            }
            String c1 = longest(s, i, j - 1);
            String c2 = longest(s, i + 1, j);
            return (c1.length() > c2.length()) ? c1 : c2;
        } else {
            String c1 = longest(s, i, j - 1);
            String c2 = longest(s, i + 1, j);
            return (c1.length() > c2.length()) ? c1 : c2;
        }
    }

    public static void main(String[] args) {
        String str = "abcdcbeabba";
        System.out.println(longest(str, 0, str.length() - 1));
    }
}

Khogen on May 17, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.