Google Interview Question
Software Engineer / DevelopersCountry: United States
function findNextTargetChar (target, S, from) {
for (var i = from; i < S.length; ++i) {
if (S[i] === target) {
return i
}
}
return -1
}
function chunkedPalindrome (S) {
var midpoint = Math.ceil(S.length / 2)
if (S.length === 1) {
return '(' + S + ')'
}
var a, b
a = 0
var p, q
p = midpoint
var done = false
while (!done) {
p = findNextTargetChar(S[a], S, p)
if (p === -1) {
return '(' + S + ')'
}
b = a
q = p
var l = S.length - q
var match = true
for (var i = 0; i < l; ++i) {
if (S[b+i] === S[q+i]) {
} else {
match = false
p++
break
}
}
if (match) {
done = true
}
}
return [
'(',
S.slice(a,b + i),
')',
chunkedPalindrome(S.slice(b + i, q)),
'(',
S.slice(p, q + i),
')'
].join('')
}
console.log(chunkedPalindrome('merchant'))
console.log(chunkedPalindrome('volvo'))
console.log(chunkedPalindrome('ghiabcdefhelloadamhelloabcdefghi'))
console.log(chunkedPalindrome('ghighiabcdefhelloadamhelloabcdefghighi'))
in C#
static void Main(string[] args)
{
// string str = "VOLVO";
string str = "merchant";
int cnt= checkLongestPalindrom(str);
Console.WriteLine(cnt);
//for (int i = 0; i <= allPolicies.Length; i++)
//{
//}
Console.ReadLine();
}
public static int checkLongestPalindrom(String s)
{
char[] strArray = s.ToArray();
int left = 0, right = s.Length - 1, count = 1;
String leftStr = "", rightStr = "";
while (left < right)
{
leftStr += strArray[left];
rightStr = strArray[right] + rightStr;
if (leftStr.Equals(rightStr))
{
count += 2;
leftStr = rightStr = "";
}
left++;
right--;
}
return count;
}
jsk1016, Your algorithm is not finding "LONGEST" Palindrome.
for the case, "antaprezatepzapreanta", your algorithm will return 3, (a)(ntaprezatepzapreant)(a). But the LONGEST palindrome is 7, (anta)(pre)(za)(tpe)(za)(pre)(anta).
O(n^2) time and O(n) space recursive solution with Dynamic Programming.
function f(S, DP){
if (S.length <= 1){
return S.length;
}
else {
if (!DP[S]){
var best = 1;
var limit = Math.floor(S.length / 2);
for (var len = 1; len <= limit; len++){
var left = S.substr(0, len);
var middle = S.substr(len, S.length - 2 * len);
var right = S.substr(S.length - len, len);
//console.log(left);
//console.log(middle);
//console.log(right);
if (left === right){
best = Math.max(best, f(middle, DP) + 2);
}
}
DP[S] = best;
}
return DP[S];
}
}
console.log(f('volvo', {})); //3
console.log(f('merchant', {})); //1
console.log(f('ghiabcdefhelloadamhelloabcdefghi', {})); //7
console.log(f('antaprezatepzapreanta', {})); //11
public class ChunkedPalindrome {
static int length = 0;
public static void main(String[] args) {
calculate("antaprezatepzapreanta", 0, "");
System.out.println(length);
}
public static void calculate(String str, int count, String s) {
if(str.length() == 0) {
// error handling
// System.out.println(str+" "+s);
// System.out.println(count*2);
if(length < count*2) length = count*2;
} else {
int i = 0;
int size = str.length()/2;
String temp = "";
while(i < size) {
if(str.charAt(i) == str.charAt(str.length()-1)) {
if(str.substring(0, i+1).equals(str.substring(str.length()-1-i, str.length()))) {
calculate(str.substring(i+1, str.length()-1-i), count+1, s+"-"+str.substring(0, i+1));
}
}
i++;
}
// error handling
// System.out.println(str+" "+s);
// System.out.println(count*2+1);
if(length < count*2+1) length = count*2+1;
}
}
}
//(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)
Recursive Implementation
def findChunkPalindrome(s):
print s
if len(s) < 1:
return 1
count = 0
start = 0
end = len(s)-1
while(1):
if s[0:start+1] != s[end:]:
start = start+1
end = end-1
if start>=end:
count = 1
break
else:
print('start = '+str(start)+'|end = '+str(end))
count = count+2+findChunkPalindrome(s[start+1:end])
break
return count
Recursive as well as iterative Solution:
def findChunkPalindrome(s):
print s
if len(s) < 1:
return 1
count = 0
start = 0
end = len(s)-1
while(1):
if s[0:start+1] != s[end:]:
start = start+1
end = end-1
if start>=end:
count = 1
break
else:
#print('start = '+str(start)+'|end = '+str(end))
count = count+2+findChunkPalindrome(s[start+1:end])
break
return count
def findChunkPalindrome2(s):
count = 0
while(len(s)>=1):
start = 0
end = len(s)-1
#print(s)
if len(s)==1:
count = count+1
s = ''
else:
for i in range(len(s)/2+1):
#print(i)
if s[0:start+i+1] == s[end-i:]:
count = count+2
s = s[start+i+1:end-i]
#print(s)
break
elif (start+i+1)>=(end-i):
s = ''
count = count+1
break
return count
s = 'ghiabcdehelloadamhelloabcdeghi'
#s = 'volvo'
print(findChunkPalindrome(s))
print(findChunkPalindrome2(s))
public class LongestPalindrome {
public int longestPalindrome(String s){
if(s.length()==0){
return 0;
}
int start=0;
int end=s.length();
int length=1;
if(end%2==0)
length=0;
int flag=0;
char[] charString=s.toCharArray();
for(int i=1; i<=s.length()/2;i++){
if(charString[i-1]==charString[end-1]){
length=length+2;
}
else if(s.substring(start,i).equals(s.substring(end-i, end))){
flag=s.substring(start,i).length();
}
}
length=length+flag*2;
return length;
}
public static void main(String args[]){
LongestPalindrome l = new LongestPalindrome();
System.out.println(l.longestPalindrome("antaprezatepzapreanta"));
}
}
public class LongestPalindrome {
public int longestPalindrome(String s){
if(s.length()==0){
return 0;
}
int start=0;
int end=s.length();
int length=1;
if(end%2==0)
length=0;
int flag=0;
char[] charString=s.toCharArray();
for(int i=1; i<=s.length()/2;i++){
if(charString[i-1]==charString[end-1]){
length=length+2;
}
else if(s.substring(start,i).equals(s.substring(end-i, end))){
flag=s.substring(start,i).length();
}
}
length=length+flag*2;
return length;
}
public static void main(String args[]){
LongestPalindrome l = new LongestPalindrome();
System.out.println(l.longestPalindrome("antaprezatepzapreanta"));
}
}
public class LongestPalindrome {
public int longestPalindrome(String s){
if(s.length()==0){
return 0;
}
int start=0;
int end=s.length();
int length=1;
if(end%2==0)
length=0;
int flag=0;
char[] charString=s.toCharArray();
for(int i=1; i<=s.length()/2;i++){
if(charString[i-1]==charString[end-1]){
length=length+2;
}
else if(s.substring(start,i).equals(s.substring(end-i, end))){
flag=s.substring(start,i).length();
}
}
length=length+flag*2;
return length;
}
public static void main(String args[]){
LongestPalindrome l = new LongestPalindrome();
System.out.println(l.longestPalindrome("antaprezatepzapreanta"));
}
}
I believe this should run in O(n) time since it simply starts at each end and works it way toward the middle once. Here is my java implementation.
public int countChunks(String str) {
int startPtr = 0;
int endStart = 0;
int endPtr = str.length() - 1;
int startEnd = str.length() - 1;
int matchCount = 1;
while(startPtr < endPtr) {
char startChar = str.charAt(startPtr);
for(int i = endPtr; i >= startPtr; i--) {
startEnd = i;
if(startChar == str.charAt(i)) break;
}
if(startEnd <= startPtr) break;
endStart = startPtr + (endPtr - startEnd);
String lStr = str.substring(startPtr, endStart + 1);
String rStr = str.substring(startEnd, endPtr + 1);
if(lStr.equals(rStr)) matchCount += 2;
startPtr = endStart + 1;
endPtr = startEnd - 1;
}
return matchCount;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FindLongChunkedPalindorme {
public static void main(String args[]) {
String inputString = "eaepaveae";
Map<Integer, List<String>> result = new HashMap<>();
longest(inputString, 0, result, 1);
}
private static boolean longest(String inputString, int pos, Map<Integer, List<String>> result, Integer id) {
if (inputString == null || inputString.length() == 0)
return false;
for (int start = pos + 1; start < inputString.length() / 2; start++) {
String beg = inputString.substring(pos, start);
String end = inputString.substring(inputString.length() - start, inputString.length() - pos);
if (beg.equals(end)) {
List<String> can = result.get(id);
if (can == null) {
can = new ArrayList<>();
}
can.add(beg);
result.put(id, can);
longest(inputString, start, result, id + 1);
}
}
// TODO: before adding +1 validate
if(id.intValue() == 1) {
System.out.println(result.size() * 2 + 1);
return true;
}
return false;
}
}
A solution in Javascript with O(N^2) time
//Returns true if the first i chars of the string match the last i chars of the string
function matchesFirstAndLastChars(S,i){
return S.slice(0, i+1) === S.slice(-1*(i+1));
}
//Removes one chunk at beginning and end of S
function removeLeadingAndTrailingChunk(S){
for (var i = 0; i < Math.floor(S.length/2); i++){
if (matchesFirstAndLastChars(S, i)){
return S.slice(i+1,S.length - 1 - i);
}
}
return S;
}
// Solution recursive function O(N^2)
function ChunkedPalindromeLength(S){
if (S.length === 0) return 0;
var shortened = removeLeadingAndTrailingChunk(S);
if (shortened === S) return 1;
return ChunkedPalindromeLength(shortened) + 2;
}
Complexity: O(n)
public class PalindromicChunk {
private static int call(String s, int count, int lenth, String s2) {
if (s == null || s.isEmpty()) {
return (0);
}
if (s.length() <= 1) {
if (count != 0 && s2.length() - lenth <= 1) {
return (count + 1);
} else {
return (1);
}
}
int n = s.length();
for (int i = 0; i < n / 2; i++) {
if (s.substring(0, i + 1).equals(s.substring(n - 1 - i, n))) {
return call(s.substring(i + 1, n - 1 - i), count + 2, lenth + (i + 1) * 2, s2);
}
}
return count + 1;
}
public static void main(String[] args) {
System.out.println(call(null, 0, 0, null));
System.out.println(call("", 0, 0, ""));
System.out.println(call("V", 0, 0, "V"));
System.out.println(call("VOLVO", 0, 0, "VOLVO"));
System.out.println(call("VOLVOV", 0, 0, "VOLVOV"));
System.out.println(call("ghiabcdefhelloadamhelloabcdefghi", 0, 0, "ghiabcdefhelloadamhelloabcdefghi"));
System.out.println(call("ghiabcdefhelloadamhelloabcdefghik", 0, 0, "ghiabcdefhelloadamhelloabcdefghik"));
System.out.println(call("antaprezatepzapreanta",0,0,"antaprezatepzapreanta"));
}
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long mod = 1000000007;
int mul = 26;
string s("ghiabcdefhelloadamhelloabcdefghi");
long long l(0), r(0), i(0), j(s.size() - 1);
int count(0);
int powi(1);
while(i < j)
{
l = (l*mul + (s[i++] - 'a'))%mod;
r = (r + (s[j--] - 'a')*powi)%mod;
powi = (mul*powi) % mod;
// cout<<l<<" "<<r<<endl;
if(l == r)
{
l = r = 0;
powi = 1;
count += 2;
}
}
if((l != 0 and r != 0) or l == r)
count += 1;
cout<<count<<endl;
return 0;
}
public class LongestPalindrome {
public static void main(String[] args) {
String input = "aaabbaaacdjhsdjheuiwaeaaccddbbddccaa";
String result = findLongestPalindrome(input);
System.out.println("Longest palindrome: " + result);
}
private static String findLongestPalindrome(String input) {
String longestPalindrome = "";
int lengthOfLongestPalindrome = 0;
for(int i=0; i<input.length(); i++) {
String middle = String.valueOf(input.charAt(i));
boolean isPalindrome = true;
int count = 1;
int leftMiddle = i;
int rightMiddle = i;
while(isPalindrome) {
String left = leftMiddle - count >= 0? String.valueOf(input.charAt(leftMiddle - count)) : "";
String right = rightMiddle + count <= input.length() - 1? String.valueOf(input.charAt(rightMiddle + count)) : "";
if(!left.equals(right)) {
if(!right.equals(middle)) {
isPalindrome = false;
} else {
rightMiddle++;
}
} else {
String currentPalindrome = input.substring(leftMiddle - count, rightMiddle + count + 1);
if(currentPalindrome.length() > lengthOfLongestPalindrome) {
longestPalindrome = currentPalindrome;
lengthOfLongestPalindrome = currentPalindrome.length();
}
}
count++;
}
}
return longestPalindrome;
}
}
public class LongestPalindrome {
public static void main(String[] args) {
String input = "aaabbaaacdjhsdjheuiwaeaaccddbbddccaa";
String result = findLongestPalindrome(input);
System.out.println("Longest palindrome: " + result);
}
private static String findLongestPalindrome(String input) {
String longestPalindrome = "";
int lengthOfLongestPalindrome = 0;
for(int i=0; i<input.length(); i++) {
String middle = String.valueOf(input.charAt(i));
boolean isPalindrome = true;
int count = 1;
int leftMiddle = i;
int rightMiddle = i;
while(isPalindrome) {
String left = leftMiddle - count >= 0? String.valueOf(input.charAt(leftMiddle - count)) : "";
String right = rightMiddle + count <= input.length() - 1? String.valueOf(input.charAt(rightMiddle + count)) : "";
if(!left.equals(right)) {
if(!right.equals(middle)) {
isPalindrome = false;
} else {
rightMiddle++;
}
} else {
String currentPalindrome = input.substring(leftMiddle - count, rightMiddle + count + 1);
if(currentPalindrome.length() > lengthOfLongestPalindrome) {
longestPalindrome = currentPalindrome;
lengthOfLongestPalindrome = currentPalindrome.length();
}
}
count++;
}
}
return longestPalindrome;
}
}
static int count_chunks(char *str) {
int chunks = 0;
int len = strlen(str);
while (len) {
int o_idx;
int idx;
for (o_idx = len - 1; o_idx >= 0; o_idx--)
if(str[o_idx] == str[0])
break;
if (o_idx == 0) {
return ++chunks;
}
for (idx = 1, o_idx++; o_idx < len; idx++, o_idx++) {
if(str[idx] != str[o_idx])
return ++chunks;
}
chunks += 2;
len -= idx * 2;
str += idx;
}
return chunks;
}
static int count_chunked_pal(char *str) {
int chunks = 0;
int len = strlen(str);
while (len) {
int o_idx;
int idx;
for (o_idx = len - 1; o_idx >= 0; o_idx--)
if(str[o_idx] == str[0])
break;
if (o_idx == 0) {
return ++chunks;
}
for (idx = 1, o_idx++; o_idx < len; idx++, o_idx++) {
if(str[idx] != str[o_idx])
return ++chunks;
}
chunks += 2;
len -= idx * 2;
str += idx;
}
return chunks;
}
my solution is as follows:
Start from the middle and compare the substring on the right and on the left
if equal then count 1 otherwise take a shorter string on the left and a shorter string on the right. by shorter i mean, drop the last char on each substring. keeps doing it until you reach two equal strings. then drop them from the main string, count them as 1 and solve the same problem for a shorter string. here is the code:
package helloworld;
import java.util.ArrayList;
import java.util.HashMap;
public class LongestPalindrom{
public Integer countPalindroms(String str){
//System.out.println("Solving for " + str);
if(str.length() <=1){
return str.length();
}
if(str.length() == 2 && str.charAt(0) == str.charAt(1)){
return 2;
}else{
if(str.length() == 2 && str.charAt(0) != str.charAt(1))
return 1;
}
int middle = (str.length())/2;
for(int i=0;i<middle; i++){
//System.out.println("comparing:" + str.substring(0,middle - i) + " and:"+str.substring(middle + i+1) + " middle=" + middle + " str=" + str );
if(str.substring(0,middle - i).equals(str.substring(middle + i+1))){
return 1 + countPalindroms(str.substring(middle - i , str.length() - (middle-i)));
}
}
return 1;
}
public static void main(String[] args){
String pal1 = "VOLVO";
System.out.printf("The pals for %s is:%d. expected 2%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLkZLab";
System.out.printf("The pals for %s is:%d. expected 3%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLffkjhffZLab";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "LLaZOkaLL";
System.out.printf("The pals for %s is:%d. expected 3%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abZLfkjhfZLab";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "abaaolk";
System.out.printf("The pals for %s is:%d. expected 1%n",pal1,new LongestPalindrom().countPalindroms(pal1));
pal1 = "antaprezatpezapreanta";
System.out.printf("The pals for %s is:%d. expected 4%n",pal1,new LongestPalindrom().countPalindroms(pal1));
}
}
int getLP(string s)
{
string rBuff="";
string lBuff="";
int count=0;
for (int rInd=s.length()-1, lInd=0;lInd<rInd;lInd++,rInd--)
{
lBuff=lBuff+s[lInd];
rBuff=s[rInd]+rBuff;
if (lBuff!=rBuff)
continue;
rBuff="";
lBuff="";
count+=2;
}
if (lBuff.size()>0 || s.length()%2) count++;
return count;
}
int getLP(string s)
{
string rBuff="";
string lBuff="";
int count=0;
for (int rInd=s.length()-1, lInd=0;lInd<rInd;lInd++,rInd--)
{
lBuff=lBuff+s[lInd];
rBuff=s[rInd]+rBuff;
if (lBuff!=rBuff)
continue;
rBuff="";
lBuff="";
count+=2;
}
if (lBuff.size()>0 || s.length()%2) count++;
return count;
}
In which case, the following code wouldn't work..
int count(string str) {
int i = 0, n = str.length();
if (n < 2) {
return n;
}
for (i = 1; i <= n / 2; i++) {
string str1 = str.substr(0, i);
string str2 = str.substr(n - i);
if (str1 == str2) {
return 2 + count(str.substr(i, n - 2 * i));
}
}
return 1;
}
public class Test {
public static void main(String[] args) {
findMaxChunkCount("volvo");
}
private static void findMaxChunkCount(String s) {
int len = s.length();
int index = len - 1;
int count = 0;
int lastIndex = -1;
boolean matched = false;
for (int i = 0; i < (len + 1) / 2; i++) {
String s1 = s.substring(lastIndex + 1, i + 1);
// System.out.println(s1);
String s2 = s.substring(index, len - (lastIndex + 1));
// System.out.println(s2);
if (s1.equals(s2)) {
if (s.indexOf(s2, (len) / 2) - s.indexOf(s1) == 0) {
count++;
} else
count = count + 2;
// System.out.println("count is " + count);
lastIndex = i;
matched = true;
} else {
matched = false;
}
index--;
}
if (matched == false) {
count++;
}
System.out.println("max chunk count is for" + s + " is " + count);
}
}
public class Test {
public static void main(String[] args) {
findMaxChunkCount("volvo");
}
private static void findMaxChunkCount(String s) {
int len = s.length();
int index = len - 1;
int count = 0;
int lastIndex = -1;
boolean matched = false;
for (int i = 0; i < (len + 1) / 2; i++) {
String s1 = s.substring(lastIndex + 1, i + 1);
// System.out.println(s1);
String s2 = s.substring(index, len - (lastIndex + 1));
// System.out.println(s2);
if (s1.equals(s2)) {
if (s.indexOf(s2, (len) / 2) - s.indexOf(s1) == 0) {
count++;
} else
count = count + 2;
// System.out.println("count is " + count);
lastIndex = i;
matched = true;
} else {
matched = false;
}
index--;
}
if (matched == false) {
count++;
}
System.out.println("max chunk count is for" + s + " is " + count);
}
}
public class Test {
public static void main(String[] args) {
findMaxChunkCount("volvo");
}
private static void findMaxChunkCount(String s) {
int len = s.length();
int index = len - 1;
int count = 0;
int lastIndex = -1;
boolean matched = false;
for (int i = 0; i < (len + 1) / 2; i++) {
String s1 = s.substring(lastIndex + 1, i + 1);
// System.out.println(s1);
String s2 = s.substring(index, len - (lastIndex + 1));
// System.out.println(s2);
if (s1.equals(s2)) {
if (s.indexOf(s2, (len) / 2) - s.indexOf(s1) == 0) {
count++;
} else
count = count + 2;
// System.out.println("count is " + count);
lastIndex = i;
matched = true;
} else {
matched = false;
}
index--;
}
if (matched == false) {
count++;
}
System.out.println("max chunk count is for" + s + " is " + count);
}
}
Time: O(n)
Space: O(n)
public class PalindromeChunks {
static int longestChunkedPalindrome(String s) {
int chunkCount = 0;
String left = "", right = "";
int i = 0, j = s.length() - 1;
while (i < j) {
left = left + s.substring(i, i+1);
right = right + s.substring(j, j+1);
if (left.equals(new StringBuilder(right).reverse().toString())) {
chunkCount += 2;
left = "";
right = "";
}
++i;
--j;
}
if ( (!left.equals("") && !right.equals("")) || i == j) // middle chunk left over
++chunkCount;
return chunkCount;
}
public static void main(String[] args ) {
System.out.println("VOLVO: "+longestChunkedPalindrome("VOLVO")); // 3
System.out.println("merchant: "+longestChunkedPalindrome("merchant")); // 1
System.out.println("ghiabcdefhelloadamhelloabcdefghi: "+longestChunkedPalindrome("ghiabcdefhelloadamhelloabcdefghi")); // 7
}
}
The easiest way to do it is.
public int checkLongestPalindrom(String s)
{
int left = 0,right=s.length()-1,count=1;
String leftStr="",rightStr="";
while(left < right)
{
leftStr += s.charAt(left);
rightStr = s.charAt(right) + rightStr;
if(leftStr.equals(rightStr))
{
count+=2;
leftStr=rightStr="";
}
left++;
right--;
}
return count;
}
The complexity is O(n/2)
//Time: O(N) space: O(N)
//Test cases to try: "aaa"=> 3, mkmk=>2, akem=>1
public int countChunks(String str){
if(str == null || str.length() == 0){
throw new IllegalArgumentException();
}
int s = 0;
int e = str.length();
int i = 1;
int j = e - 1;
int chunks = 0;
while(i <= j){
String left = str.substring(s,i);
String right = str.substring(j,e);
if(left.equals(right)){
chunks += 2;
s = i++;
e = j--;
}else{
i++;
j--;
}
}
if(s != e){
chunks++;
}
return chunks;
}
- PR December 10, 2016