Google Interview Question for Software Engineer / Developers


Country: United States




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

public class LongestChunkedPalindrome {

    public static void main(String[] args) {
        System.out.println(LCP(null));
        System.out.println(LCP(""));
        System.out.println(LCP("V"));
        System.out.println(LCP("VOLVO"));
        System.out.println(LCP("VOLVOV"));
        System.out.println(LCP("ghiabcdefhelloadamhelloabcdefghi"));
        System.out.println(LCP("ghiabcdefhelloadamhelloabcdefghik"));
    }
    
    private static List<String> LCP(String s) {
        List<String> result = new LinkedList<String>();
        
        doLCP(s, result, false);
        
        return result;
    }
    
    private static boolean doLCP(String s, List<String> result, boolean nested) {
        if (s == null || s.length() == 0) return true;
        
        // otherwise
        for (int i = 1; i <= s.length()/2; i++) {
            String candidate = s.substring(0,  i);
            if (candidate.equals(s.substring(s.length()-i, s.length()))) {
                if (doLCP(s.substring(i, s.length()-i), result, true)) {
                    result.add(0, candidate);
                    result.add(candidate);
                    return true;
                }
            }
        }
        
        // otherwise
        if (!nested && s.length() > 1) return false;
        
        // otherwise
        result.add(result.size()/2, s);
        return true;
    }
}

- PR December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'))

- srterpe December 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String "maymaymaymay" should return 2 or 4??

- Anonymous December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

0

- nitinguptaiit April 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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).

- pppz December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
I am not sure, but shouldn't the answer be 11?
(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)

- settyblue December 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My example was wrong, instead of anaprezatepzapreana, please try antaprezatepzapreanta

- pppz December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The result I got from the code above was (a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a) with an answer of 11. Is this still wrong? (It won't let me reply to you so I made a new comment thread).

- jsk1016 December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my python implementation

def longest_chunked(s):
	size = 1; count = 1
	while size * 2 <= len(s):
		s1 = s[:size]; s2 = s[-size:]
		if s1 == s2:
			s = s[size:-size]
			print(s1, s, s2)
			size = 0
			count += 2
		size += 1
	return count

- joesavold December 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- obedtandadjaja December 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vishal Gupta December 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- vishal.gupta4081 December 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def lcpd(s):
    l = s[-1]
    si = 0
    cnt = 1
    while s[:si+1] != s[-si-1:]:
        si = s.find(l, si+1)

    if si != len(s) - 1:
        cnt +=1
        cnt += lcpd(s[si+1:-si-1])
    
    return cnt

- Nitish Garg December 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));
        
    }
}

- ESVEE December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));

}
}

- Anonymous December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));
    }
}

- Anonymous December 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- wheeler.brad December 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- josbimosbi December 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- josemontesp December 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));
    }
}

- hcr January 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Using Rabin Karp O(N) February 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- Anonymous March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- randomuser March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- m June 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- m June 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}

}

- littlefinger August 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- elkon November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    
}

- elkon November 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ram February 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- akhil_gupta_8600049096 July 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- akhil_gupta_8600049096 July 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- gupta.akhil.004 July 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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
	}
}

- jsk1016 December 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is O(n^2) not O(n). Iterating over the characters in the "while (i<j)" loop is O(n). Within the loop you construct a reversed string and compare string equality - both of these operations are O(n). So O(n^2) together.

- chrisb December 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- Sahib.zer December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(n^2). The top level loop is O(n) and within the loop is a string equality check which is O(n).

- chris December 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//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;
}

- divm01986 December 09, 2016 | 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