Interview Question

Financial Software Developer Interview New York, NY

1. Find out the longest palindrome in a given string in

  less than O(n*n) time. 2. Design a system that can deliver the newest price of stocks to users.
Answer

Interview Answer

1 Answer

0

public String longestPalindrome(String s) {
   int start = 0, end = 0;
   for (int i = 0; i < s.length(); i++) {
      int len1 = expandAroundCenter(s, i, i);
      int len2 = expandAroundCenter(s, i, i + 1);
      int len = Math.max(len1, len2);
      if (len > end - start) {
         start = i - (len - 1) / 2;
         end = i + len / 2;
      }
   }
   return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
   int L = left, R = right;
   while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
      L--;
      R++;
   }
   return R - L - 1;
}

Anonymous on Apr 6, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.