Google Interview Question Developer Program Engineers
Country: United States
First, we should read the file into a string and find the longest palindrome in this string.
The best method is to use Manacher's algorithm which runs in O(N) time with extra O(N) space. I don't think an interviewer can possibly expect this in a 45min interview, i suppose a standard O(N^2) solution is expected by checking all possible centers.
My implementation of Manacher's algorithm is the following:
// More details on akalin.cx/longest-palindrome-linear-time
const int MAXLEN = 1000000;
int p[2*MAXLEN+10], np; // size of palindromes with even and odd length
void ManacherAlgorithm(char* str) {
int i, s, e, j, d, pal_len, len = strlen(str);
np = 0;
i = 0;
pal_len = 0;
// Loop invariant: str[(i - pal_len)..i] is a palindrome.
// Loop invariant: np >= 2 * i - pal_len. The code path that
// increments pal_len skips the l-filling inner-loop.
// Loop invariant: np < 2 * i + 1. Any code path that increments
// i past seqLen - 1 exits the loop early and so skips
// the l-filling inner loop.
while (i < len) {
// First, see if we can extend the current palindrome.
// Note that the center of the palindrome remains fixed.
if (i > pal_len && str[i-pal_len-1] == str[i]) {
pal_len += 2;
++i;
continue;
}
// The current palindrome is as large as it gets,so we append it
p[np++] = pal_len;
// Now to make further progress, we look for a smaller palindrome sharing
// the right edge with the current palindrome. If we find one, we can try
// to expand it and see where that takes us. At the same time, we can fill
// the values for l that we neglected during the loop above. We make use of
// our knowledge of the length of the previous palindrome (pal_len) and the
// fact that the values of l for positions on the right half of the
// palindrome are closely related to the values of the corresponding
// positions on the left half of the palindrome.
//
// Traverse backwards starting from the second-to-last index up to the
// edge of the last palindrome.
s = np - 2;
e = s - pal_len;
for (j = s; j > e; --j) {
d = j - e - 1;
// We check to see if the palindrome at p[j] shares a left edge
// with the last palindrome. If so, the corresponding palindrome
// on the right half must share the right edge with the last
// palindrome, and so we have a new value for pal_len.
if (p[j] == d) {
pal_len = d;
break;
}
p[np++] = min(d, p[j]);
}
if (j == e) {
i++;
pal_len = 1;
}
}
p[np++] = pal_len;
// Traverse backwards starting from the second-to-last index up until we
// get p to size 2 * seqLen + 1.
// We can deduce from the loop invariants we have enough elements.
s = np - 2;
e = s - (2*len + 1 - np);
for (j = s; j > e ; --j) {
// The d here uses the same formula as the d in the inner loop above.
// (Computes distance to left edge of the last palindrome.)
d = j - e - 1;
// We bound p[i] with min for the same reason as in the inner loop above.
p[np++] = min(d, p[j]);
}
pal_len = -1;
for (i = 0; i < np; i++)
if (p[i] > pal_len) {
pal_len = p[i];
j = i;
}
s = j / 2 - pal_len / 2;
e = s + pal_len - 1;
printf("max palindrome size = %d indices [%d, %d]\n", pal_len, s, e);
}
Sample Program In java with manacher's algorithm
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class LongestFromFile {
public LongestFromFile() {
super();
}
private int line_number;
private String line;
private String palin_string;
public static void main(String[] args) throws IOException {
LongestFromFile longestFromFile = new LongestFromFile();
BufferedReader br = new BufferedReader(new FileReader(new File("C:\\temp.txt\\abc.txt")));
String source = br.readLine();
longestFromFile.setPalin_string("");
int i = 0;
while (source != null) {
i++;
if (source.trim() != "" && source.length() > 0) {
String palin = longestFromFile.palin(source);
if (longestFromFile.getPalin_string().length() < palin.length()) {
longestFromFile.setLine_number(i);
longestFromFile.setPalin_string(palin);
longestFromFile.setLine(source);
}
}
source = br.readLine();
}
System.out.println(longestFromFile);
}
public String palin(String source) {
StringBuilder sb = new StringBuilder(source);
sb.insert(0, "^");
sb.insert(sb.length(), "$");
int j = 0;
for (int i = 1; i < sb.length(); i++) {
sb.insert(i + j, "#");
j++;
if (i + j > 2 * source.length())
break;
}
int[] p = new int[sb.length()];
int C = 0;
int R = 0;
int M_R = 0;
char[] t = sb.toString().toCharArray();
for (int i = 1; i < t.length - 1; i++) {
M_R = 2 * C - i;
p[i] = R > i ? Math.min(p[M_R], R - i) : 0;
while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
p[i] += 1;
}
if (i + p[i] > R) {
C = i;
R = i + p[i];
}
}
int max = 0;
for (int i = 0; i < p.length; i++) {
if (max < p[i]) {
M_R = i;
max = p[i];
}
}
return source.substring((M_R - max - 1) / 2, ((M_R - max - 1) / 2) + max);
}
public void setLine_number(int line_number) {
this.line_number = line_number;
}
public int getLine_number() {
return line_number;
}
public void setLine(String line) {
this.line = line;
}
public String getLine() {
return line;
}
public void setPalin_string(String palin_string) {
this.palin_string = palin_string;
}
public String getPalin_string() {
return palin_string;
}
public String toString() {
return +this.getLine_number() + "\n" +
this.getLine() + "\n" +
this.getPalin_string();
}
}
i think you're supposed to consider the whole file as a string, not check palindromes on a line-by-line basis
Revised Code
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class LongestFromFile {
public LongestFromFile() {
super();
}
public static void main(String[] args) {
LongestFromFile longestFromFile = new LongestFromFile();
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(new File("C:\\temp.txt\\abc.txt")));
String source = br.readLine();
int i = 0;
String target = "";
while (source != null) {
target += source;
source = br.readLine();
}
source = longestFromFile.palin(target);
System.out.println(source);
} catch (IOException e) {
e.printStackTrace();
} finally {
if (br != null) {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
public String palin(String source) {
StringBuilder sb = new StringBuilder(source);
sb.insert(0, "^");
sb.insert(sb.length(), "$");
int j = 0;
for (int i = 1; i < sb.length(); i++) {
sb.insert(i + j, "#");
j++;
if (i + j > 2 * source.length())
break;
}
int[] p = new int[sb.length()];
int C = 0;
int R = 0;
int M_R = 0;
char[] t = sb.toString().toCharArray();
for (int i = 1; i < t.length - 1; i++) {
M_R = 2 * C - i;
p[i] = R > i ? Math.min(p[M_R], R - i) : 0;
while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
p[i] += 1;
}
if (i + p[i] > R) {
C = i;
R = i + p[i];
}
}
int max = 0;
for (int i = 0; i < p.length; i++) {
if (max < p[i]) {
M_R = i;
max = p[i];
}
}
return source.substring((M_R - max - 1) / 2, ((M_R - max - 1) / 2) + max);
}
}
Unless I'm missing something, use a Stack datastruction:
palindrome(File f) {
s = new Stack();
max = 0; curr_size = 0;
while (c = f.hasNext()) {
if (isSpace(c))
continue;
if (s.size() == 0) {
s.push(c);
continue;
}
if (c == s.peek()) {
s.pop();
curr_size++;
} else {
max = MAX(curr_size, max);
curr_size = 0;
s.push(c);
}
}
in C++ code, dynamic programming
int LongestPalindrome(string file)
{
int length = file.length();
vector<vector<int>> start;
for(int i = 0; i < length; i++)
{
start.push_back(vector<int>());
}
start[0].push_back(0);
int maxLength = 1;
for(int i = 1; i < length; i++)
{
start[i].push_back(i);
if(file[i-1] == file[i])
start[i].push_back(i-1);
for(int j = 0; j < start[i-1].size(); j++)
{
int preS = start[i-1][j]-1;
if(preS>=0)
{
if(file[preS] == file[i])
{
start[i].push_back(preS);
}
}
}
int temp = *max_element(start[i].begin(), start[i].end());
if( temp > maxLength)
maxLength = temp;
}
return maxLength;
}
Here is O(n) solution in C++ (manacher's algorithm)
int* findPalin(char *seq) {
seq = spaceRemovedSequence(seq);
int seqLen = strlen(seq); // length of the given sequence of letters
int lLen = 2 * seqLen + 1; // length of the needed to be formed
int *list = new int(lLen); // creating a array of 2*n+1 times
int ignoreChar=0; // characters to be ignored from the pivot point
for(int i = 0; i < lLen;i++) {
int s = i / 2 - ignoreChar; // start of the palindrome i
int e = i / 2 + i % 2 + ignoreChar; // end of the palindrome i
while (s > 0 and e < seqLen and seq[s - 1] == seq[e])
s -= 1, e += 1; // try matching one left of start and one right of end ans update 's' and 'e'
list[i] = (e - s); // insert in the list about the maximum palindrome from current pivot
int leftEdge = i-list[i]+1; // It is the left edge of the current palindrome foun
ignoreChar = 0; // initially number of character to be ignored in next loop is 0
// it will be updated if any sequence will be found
// between left edge and pivot having its left pivot same as
// left pivot of current palindrome
if(i-1 <= leftEdge) // if current palindrome is 2 or 1 length then dont search
continue;
for (int k = i-1; k > leftEdge; --k) {
if(k - list[k] + 1 <= leftEdge) { // If biggest possible mirror sequence whose left edge is same
// as left edge of the current p[alindrome then
ignoreChar = (k-leftEdge+1)/2; // update charater to be ignored in next loop
break; // goto to the outer for loop
}
list[++i] = list[k]; // else copy the same left part into right part of current pivot
}
}
return list; //return the list in the end
}
Question is find longest palindrome with ignoring white space in the text.
For this, I modify the Manacher's algorithm for ignoring the white space.
For example:
This is the book koob eh te is had
Output:
the book koob eh t
- Adnan Ahmad October 01, 2013public class LongestPalindromeFromFile { public String findLongestPalindrome(String filePath) { String data = null; // Read data from file try { data = readDataFromFile(filePath); if(data == null){ System.out.println("Unable to get file contents"); return null; } } catch (Exception e) { return null; } // Transform file data char []transformData = transformData(data); int center = 0, right = 0, mirror = 0; int []lengthPal = new int[transformData.length]; for(int index = 1; index < transformData.length - 1; index++){ mirror = (2*center) - index; if(right > index){ lengthPal[index] = Math.min(right - index, lengthPal[mirror]); } // Ignore white spaces on right and left sides int leftSpaces = 0, rightSpaces = 0; int leftIndex = index - (1 + lengthPal[index]); int rightIndex = index + (1+lengthPal[index]); while(leftIndex >=0 && rightIndex < transformData.length){ if (transformData[leftIndex] == ' '){ leftSpaces++; leftIndex = index - (2 + lengthPal[index]); } else if (transformData[rightIndex] == ' '){ rightSpaces++; rightIndex = index + (2 + lengthPal[index]); } else if (transformData[leftIndex] == transformData[rightIndex]){ lengthPal[index]++; leftIndex = index - (1 + lengthPal[index]); rightIndex = index + (1 + lengthPal[index]); } else{ break; } } lengthPal[index] += leftSpaces + rightSpaces; if((index+lengthPal[index])> right){ center = index + (rightSpaces - leftSpaces); right = center + lengthPal[index]; } } return printPalindrome(data, lengthPal); } private String readDataFromFile(String filePath) throws FileNotFoundException, IOException{ try{ BufferedReader reader = new BufferedReader(new FileReader(filePath)); StringBuilder builder = new StringBuilder(); String line; while((line = reader.readLine()) !=null){ builder.append(line); } return builder.toString(); } catch(FileNotFoundException ex){ throw ex; } catch (IOException e) { throw e; } } private char[] transformData(String data){ char[] transformData = new char[2*data.length() + 3]; transformData[0] = '$'; transformData[2*data.length() + 2] = '$'; transformData[2*data.length() + 1] = '#'; for(int index = 0; index < data.length(); index++){ transformData[2 * index + 1] = '#'; transformData[2 * index + 2] = data.charAt(index); } return transformData; } private String printPalindrome(String data, int[]lengthPal){ int center = 0, length = 0; for(int index = 1; index < lengthPal.length - 1; index++){ if(lengthPal[index] > length){ length = lengthPal[index]; center = index; } } int leftSpaces = 0, rightSpaces = 0; String leftSide = data.substring((center - 1 - length) >> 1, center >> 1); String rightSide = data.substring((center + 1) >> 1, (center - 1 + length) >> 1); for(char ch : leftSide.toCharArray()){ if(ch == ' '){ leftSpaces++; } } for(char ch : rightSide.toCharArray()){ if(ch == ' '){ rightSpaces++; } } center += (leftSpaces - rightSpaces); return data.substring((center - 1 - length) >> 1, (center - 1 + length) >> 1); } }