## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
10
of 16 vote

Here is O(N^2) solution.
1. Count all even length palindromes.
2. Count all odd length palindromes.
3.return count.

``````int countPalindrome(char *str)
{
int i,j,k,count=0;
for(i=0;str[i];i++)
{
k=i-1;j=i+1;  //count odd length palindromes
while(k>=0 && str[j] && str[k]==str[j])
{
++count;
k--;j++;
}

k=i;j=i+1; //count even length palindrome
while(k>=0 && str[j] && str[k]==str[j])
{
++count;
k--;j++;
}
}
return count;
}``````

Can someone post the implementation of suffix array?

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

I think Manacher algo can solve this in O(n):
(I treat single character as palindrome)

``````int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();

int ret = 0;

vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}

return ret;
}``````

Comment hidden because of low score. Click to expand.
0

Above implementation will not give correct output for

``abbb``

Comment hidden because of low score. Click to expand.
0

above will not work if input is

``abbb``

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

``codes-to-problem.blogspot.in/``

Comment hidden because of low score. Click to expand.
0

codes-to-problem.blogspot.in/2012/07/find-number-of-substrings-of-string.html

Comment hidden because of low score. Click to expand.
0

Your solution is of what complexity? I think it is O(n^3). If it is ..it sucks.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think this is the correct answer :
akalin.cx/longest-palindrome-linear-time

Comment hidden because of low score. Click to expand.
0

That's longest palindrome. This questions asks to count the number of palindromes.

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

Create a suffix tree of the word and also the word formed by reversing the word. Then simply count all the suffixes that occur in both tree that are palindromes.

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

I have tried it with O(n^2) the best I could get..

``````#include <stdio.h

/*
*
*/
void main()
{
char test[] = "xzyabcbaty";
//first check where the possible palindrom exists
int i, counter=0, j;
int start[10], end[10], possible_candidates=0;
for ( i=0 ; i<sizeof(test)-1 ; i++)
{
for (j=i+1 ; j < sizeof(test) ; j++)
{
if (test[i] == test[j])
{
start[counter] = i;
end[counter] = j;
possible_candidates++;
counter++;
}
}
}

//check if we have any possibility of palindrom
if (counter)
{
int num_of_substring = 0;
for (i=0 ; i < possible_candidates ; i++)
{
if (is_palindrom(test, start[i], end[i]))
{
num_of_substring++;
}
}
printf("Total number of substrings %d", num_of_substring);
}
else
{
printf("Nothing found");
}
}

/*
* palidrom checking function with O(n/2)
*/
int is_palindrom(char* string, int start, int end)
{
int i, j=0;
for (i=start ; i < end ; i++)
{
if (string[i] != string[end-j])
{
return 0;
}
j++;
}
return 1;
}``````

The complexity is O(n^2) + O(n^2) which is 2(O(n^2) => O(n^2)

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

1. Reverse the string and add it to the original string. For eg if the string given is 'banana' take is as 'banana#ananab'
2. Make a suffix array of this string.
3. Put all the suffixes in a hashmap and sort the hashmap to avoid duplicate entries, you can even use arrays.
4. Now find the common prefix in the adjacent strings. Iterate through the hasmap or array created in last point. If you want youcan store this common prefix in a seperate array p. The array p contains all the palindrome string. You can count all the palindrome greater than any length or the longest palindrome.

Comment hidden because of low score. Click to expand.
0

@lucifier your method wont work see the example here
stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
it doesn't find palindrome "ana" and "nan" in banana

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

My idea is to use DP.

s[i,j]= 1 if s[i+1,j-1]=1 && A[i]=A[j], where i+1<=j-1
if A[i]=A[i+1] if i=j-1
0 otherwise

sum=0;
for(i=n; i>=0;i--)
{
for(j>=n;j>=i;j--)
{
if(i==j)
S[i,j]=1;
else
{
if(j=i+1)
{
if(A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
else
{
if(s[i+1,j-1]==1 && A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
}
sum += s[i,j];
}
}

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

#include<stdio.h>
int checkpalindrom(char *s,char *s1)
{
while(s<s1)
if(*s++!=*s1--)
return 0;
return 1;
}

void main()
{
char string[30],c;
int i=0,j=0,n=0;

printf("\n Enter the Msg :- ");
gets(string);

printf("\n Palindram substring are as follow \n\n");

for(i=0,j=0;string[i];i++)
{
if(string[i]==' ' || string[i]=='\t')

{ c=*(string+i);

*(string+i)='\0';

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

*(string+i)=c;

j=i+1;
}

}

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

}
input and output as follow ....

Enter the Msg :- hi madam and mom gud day

Palindram substring are as follow

2) mom

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

``````#include "stdio.h"
#include "string.h"

int main() {
char * str = "abababbaa";
printf("hello world from panindrom!\n");
printf("%s has %d panindrom\n",str, getNumberOfPanindrom(str));
}

int getNumberOfPanindrom(char * str) {
return center_in_even_position(str) + center_in_odd_position(str);
}

int center_in_odd_position(char * str) {
int i,j = 0;
int count = 0;
int size = strlen(str);
for( i = 0; i < size; i++)
{
for( j = 1; j <= min(i, size - i - 1); j++)
{
if(str[i-j] == str[i+j])
count ++;
else
break;
}
}
return count;
}

int center_in_even_position(char * str) {
int i, j = 0;
int count = 0;
int size = strlen(str);
for( i = 0; i < size; i ++)
{
for (j = 0; j < size - i - 1; j++)
{
if(str[i-j] == str[i+j+1])
count ++;
else
break;
}
}
return count;
}

int min(int a, int b) {
return ((a > b) ? b : a);
}``````

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

This solution works in O(n+p) where n is the length of string and p is the length of palindrom patterns. In worst case it would be O(n^2)
check it:

/a.out "baab check aa abc zxz it adda hhh "
./a.out " baab check aa abc zxz it adda hhh "
./a.out

``````#include <iostream>
using namespace std;

int palindromesCount(char *input)
{
int countpalindromes=0;
int wordStart=0,wordEnd=0;
int charStart,charEnd;
while(input[wordStart] != '\0') {
if(input[wordStart] != ' ') {
for(wordEnd = wordStart; input[wordEnd] != ' ' & input[wordEnd] != '\0'; wordEnd++); wordEnd--;
charStart = wordStart;
charEnd = wordEnd;
while( ((charEnd-charStart) > 0) & (input[charEnd]==input[charStart]) ) { charStart++; charEnd--;};
if( (charEnd-charStart) <=0 ) countpalindromes ++;
wordStart = wordEnd+1;
}
else wordStart++;
}
return countpalindromes;
};

main(int argc, char *argv[])
{
if(argc>1) cout << palindromesCount(argv[1]) << endl;
}``````

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

you can use a suffix array to get a O(nlogn) algorithm
first construct a new string S+'#'+S' which # is not in char set of S and S' is the reversion of S. Then build a suffix array and calculate the longest common prefix.
sum up each i < len(S) , LCP(Rank[i],Rank[2n-i]) you got the final answer.
if the LCP use a segment tree then each query take O(lgn) time. so the total complexity of the algorithm is O(nlogn)

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

Calculate polinomial hash function for each prefix with O(n) complexity. Next we can calculate hash for some substring in O(1). Next fix center and parity of length and iterate length using binary search to find longest palindrome with fixed center. So we will get O(n log n) complexity.

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

``````int countPalindromes(const string& str)
{
int N = str.size();
vector< vector<int> > dp(N, vector<int>(N, 0));
int cnt = 0;
for (int i=0; i < N; i++)  {
cnt += (dp[i][i] = 1);
}
for (int k=1; k < N; k++)
for (int j=k, i=0; j < N; j++, i++)
cnt += (dp[i][j] = str[i] == str[j] & dp[i+1][j-1];
return cnt;
}``````

Comment hidden because of low score. Click to expand.
0

not working.

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

#include<bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int sz = s.length();
int count=0;
for(int i=0;i<sz;i++) {
for(int j=i;j<sz;j++)
{
string t = s.substr(i,j-i+1);
string rev = t;
reverse(rev.begin(),rev.end());
if(rev==t)
count++;
}
}
cout<<count<<endl;
}

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

{
#include<bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int sz = s.length();
int count=0;
for(int i=0;i<sz;i++) {
for(int j=i;j<sz;j++)
{
string t = s.substr(i,j-i+1);
string rev = t;
reverse(rev.begin(),rev.end());
if(rev==t)
count++;
}
}
cout<<count<<endl;
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
About Program: Finding all the possible substrings of a given string as well as finding the palindrome substrings in it.
Date: 19/07/2012
*/
#include<stdio.h>
#include<conio.h>
#include<string.h>
main()
{
int i,j,k,flag=0,c=0,num=0,num2=0;
char str[200],strcopy[200]={"\0"},stringconcat[200]={"\0"},temp[2]={"\0"},temp2[2]={"\0"};
printf("Enter the string : ");
gets(str);
for(i=0;i<strlen(str)-1;i++)
{
temp[0]=str[i];
strcat(stringconcat,temp);
for(j=i+1;j<strlen(str);j++)
{
temp2[0]=str[j];
strcat(stringconcat,temp2);
printf("%s\n",stringconcat);
num2++;
strcpy(strcopy,stringconcat);
strrev(strcopy);
flag=strcmp(stringconcat,strcopy);
if(flag==0)
{
printf("Palindrome string = %s\n",strcopy);
c=1;
num++;
}
}
for(k=0;k<200;k++)
{
stringconcat[k]='\0';
strcopy[k]='\0';
}
}
if(c==0)
printf("CANNOT FIND A PALINDROME SUBSTRING");
printf("\nTotal number of palindromes of the main string and its substring = %d\nTotal number of substrings possible=%d",num,num2);
getch();
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

using dynamic programming.

``````int Dp(std::string & str) {
int n = str.size();
std::vector<std::vector<int> > dp(n, std::vector<int>(n, 0));
int rs = 0;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n - k; i++) {
if (k == 0) dp[i][i + k] = 1;
else if (k == 1) dp[i][i + k] = str[i] == str[i + k] ? 1 : 0;
else {
if (dp[i + 1][i + k - 1] && str[i] == str[i + k]) dp[i][i + k] = 1;
}
if (dp[i][i + k] == 1) rs++;
}
}
return rs;
}``````

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

O(n^2) algo:

``````require 'pp'

str = "and";
res = []
count = 0

pp str.length
(0..(str.length-1)).each{|i|
res[i] = []
(0..(str.length-1)).each{|j|
if i>j
res[i][j] = -1
elsif i == j
res[i][j] = 1
count += 1
else
if ((res[i][j-1] == 1) and (str[j] == str[i]))
res[i][j] = 1
count += 1
else
res[i][j] = 0
end
end
}
}

pp res
pp count``````

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

if(a[i][j]&&str[i-1]==str[j+1])
a[i-1][j+1]=1

does it work? but i think the time is O(n^2)...

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

tag. O(n) solution is not intuitive.

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

Here is my O(n) solution. The code uses extra storage to track the number of characters matched at the current position based on the number of characters matched at the previous position. The matching logic simply compares the current position to the even & odd offsets based on the number of matches seen in each case previously. The insights I had were
1. It seemed very similar to the KMP substring problem
2. Each palindrome of length n had n/2 smaller palindromes
3. Once characters start matching, the palindrome will continue to expand until it stops at which point a new palindrome starts from that index

Please comment if you find bugs.

Thanks

``````#define array_elements(_a) (sizeof((_a)) / sizeof((_a)[0]))

#define MAX_LENGTH 4096

#define PRINT_PALINDROME_SUBSTRINGS 1

void
print_palindrome_substring(
char *s, int start, int end, char *message, int count
)
{
printf("%s [%d]: ", message, count);

while (start <= end) {
printf("%c", s[start]);
start++;
}

printf(".\n");
}

int
count_palindrome_substrings(
char *s
)
{
int pred_even[MAX_LENGTH];
int pred_odd[MAX_LENGTH];
int i;
int count;
int off;

pred_even[0] = 0;
pred_odd[0] = 0;
i = 1;
count = 0;

while (s[i] != 0) {
off = i - 1 - 2 * pred_even[i - 1];

if (off >= 0 && s[off] == s[i]) {
pred_even[i] = pred_even[i - 1] + 1;
count++;

#if PRINT_PALINDROME_SUBSTRINGS
print_palindrome_substring(s, off, i, "even", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS

} else {
pred_even[i] = 0;
}

off = i - 1 - 2 * pred_odd[i - 1] - 1;
if (off >= 0 && s[off] == s[i]) {
pred_odd[i] = pred_odd[i - 1] + 1;
count++;

#if PRINT_PALINDROME_SUBSTRINGS
print_palindrome_substring(s, off, i, "odd", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS

} else {
pred_odd[i] = 0;
}

i++;
}

return count;
}

int
main(
int argc,
char **argv
)
{
int i;
char *palindrome_substrings_test[] = {
"abbba",
"abbabcddcbaefghihgfe" };

for (i = 0; i < array_elements(palindrome_substrings_test); i++) {

printf(
"count_palindrome_substrings(%s) = %d.\n",
palindrome_substrings_test[i],
count_palindrome_substrings(palindrome_substrings_test[i]));
}
}``````

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

int palidrome_count(const char *a, int n)
{
int i;
int len;
int count = n;

int **p = (int **)malloc(sizeof(int *) * n);
for (i = 0; i < n; ++i) {
p[i] = (int *)malloc(sizeof(int) * (n+1));
memset(p[i], 0, sizeof(int) * (n+1));
p[i][0] = p[i][1] = 1;
}

for (len = 2; len <= n; ++len) {
for (i = 0; i + len < n; ++i) {
p[i][len] = ((a[i] == a[i + len - 1]) ? 1 : 0) & p[i+1][len-2];
count += p[i][len];
}
}

for (i = 0; i < n; ++i) {
free(p[i]);
}
free(p);

return count;
}

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

I think Manacher algo can solve this in O(n), I implement two algos:
1. longestPalindrome is O(n) using Manacher
2. partition is O(n^2) using 2-order DP

``````#include <stdio.h>
#include <iostream>
#include "climits"
#include "vector"
#include "cstring"
#include <sstream>
#include "cstdlib"
#include "map"
#include "algorithm"
#include "cmath"
#include "queue"
#include "stack"

using namespace std;

class Solution {
public:
int longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
stringstream ss;
int n = s.size();
ss << "#";
for(int i = 0; i < n; i++){
ss << s[i] << "#";
}
string ns = ss.str();

int ret = 0;

vector<int> arr(ns.size(), 0);
int cm = 0;
int ci = 0;
for(int i = 0; i < ns.size(); i++){
int pi = 2 * ci - i;
int pl = 0;
if(pi >= 0){
pl = arr[pi];
}
if(i + pl < cm){
arr[i] = pl;
}else{
while(i + pl < ns.size() && i - pl >= 0){
if(ns[i + pl] != ns[i - pl]) break;
else pl++;
}
pl -= 1;
arr[i] = pl;
if(pl > cm) cm = pl;
}
ret += (arr[i] + 1) / 2;
}

return ret;
}

int partition(string s) {
int n =  s.size();
vector< vector< bool > > palindromeMatrix(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
palindromeMatrix[i][i] = true;
}
int ret = n;
for (int margin = 1; margin < n; margin++) {
for (int i = 0; i < n - margin; i++) {
int j = i + margin;
if ((i + 1 > j - 1 || palindromeMatrix[i + 1][j - 1])
&& s[i] == s[j]) {
palindromeMatrix[i][j] = true;
palindromeMatrix[j][i] = true;
ret += 1;
}
}
}
return ret;
}

};

int main(int argc, char** argv) {
Solution ss;
string s = "abaaba";
cout << ss.longestPalindrome(s) << endl;
cout << ss.partition(s) << endl;
}``````

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

I did it by getting all substrings and checking them for palindromes, O(n^3). Interviewer said, it can be done better in time.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Its is very boring actually :) ....
akalin.cx/longest-palindrome-linear-time

Comment hidden because of low score. Click to expand.
0

I'd like to see some explanation of how an O(n) algorthm for this problem follows from an O(n) solution for longest palindrome. I don't think it does, given that there can be multiple palindromes having different centers.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

#include<stdio.h>
int checkpalindrom(char *s,char *s1)
{
while(s<s1)
if(*s++!=*s1--)
return 0;
return 1;
}

void main()
{
char string[30],c;
int i=0,j=0,n=0;

printf("\n Enter the Msg :- ");
gets(string);

printf("\n Palindram substring are as follow \n\n");

for(i=0,j=0;string[i];i++)
{
if(string[i]==' ' || string[i]=='\t')

{ c=*(string+i);

*(string+i)='\0';

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

*(string+i)=c;

j=i+1;
}

}

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

}

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.

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