Microsoft Interview Question Software Engineer / Developers
Print Palindromes(char[] ar, int left, int right)
{
if((left<right)&&(left!=-1)&&(right<ar.length))
{
if(((right-left)>2)&&(ar[right]==ar[left]))
{
Print(ar,left,right);
}
if(ar[left-1]==ar[right+1])
{
Palindromes(ar,left-1,right+1);
}
Palindromes(ar,left,left+2);
Palindromes(ar,out,left-1,left+1);
}
}
<pre lang="c++" line="1" title="CodeMonkey59208" class="run-this">//To print all palindromes of length >2
#include<iostream>
#include<string.h>
using namespace std;
void palindrome_oddlength(char* a,char c,int p,int size)
{
int count=0;
char present;int prev,next;
if(p==size)return;
palindrome_oddlength(a,a[p+1],p+1,size);//Go till the last char of string
present=c;prev=p-1;next=p+1;//Treat that present char as center of the palindrome
while(prev!=-1||next!=size)
{
if(a[prev--]==a[next++]){count++;}
else break;
}
if(count>0)
{
for(int i=p-count;i<=p+count;i++)
cout<<a[i];
cout<<endl;
}
return;
}
int main()
{
char b[20];
cin>>b;//take the string as an input
palindrome_oddlength(b,b[0],0,strlen(b));
}
</pre><pre title="CodeMonkey59208" input="yes">abbabaaab</pre>
The above code prints all possible odd length palindromes....
using the same logic try for even length..
Algorithm used is
FOR ODD LENGTH PALINDROMES:
1)Traverse the string from the beginning..
2)Consider the present character we are traversing as "center of the palindrome"...
3)check whether the characters to left and right of present character match..if so move further left and move further right..
4)continue this process till end of the string...
Suffix Tree/Array based solutions would be the choice here. I could come up with a suffix array based approach taking O(n logn) time.
Let, S be the string, T be the reverse of the string.
Let, S = ABC where A,B,C is a substring of length >= 0
then, T = C'B'A' where C', B', A' is reverse of C,B,A respectively
Now, if B and B' is palindrome, they cover same segment of the given string, and B match with B'.
Let, S1 be the set of suffices of S
and, T1 be the set of suffices of S
Sort S1 and T1
Now, for every suffix in S1, check if it's has a prefix match (of length > 2) with some element of T1. Also check the range each prefix match represents. Do, same for for every suffix in T1.
Working with input S = abaabccba. Hence, T = abccbaaba
Hence, S1 = { a, aabccba, abaabccba, abccba, ba, baabccba, bccba, cba, ccba}
and, T1 = { a, aaba, aba, abccbaaba, ba, baaba, bccbaaba, cbaaba, ccbaaba}
Catch any possible flaw in this approach. Thanks.
another correction is that "Do, same for for every suffix in T1" is redundant.
For input = abaabccba, I got 4 palindromes.
For input = abaabaaba, I got 10 palindromes in total: abaabaaba
baabaab
abaaba [starting from 0]
abaaba [starting from 3]
aabaa
baab [starting from 1]
baab [starting from 4]
aba[starting from 0]
aba[starting from 3]
aba[starting from 6]
you have O(n^2) loops and for each loop you could have up to n compares. How it comes to O(nlgn)?
Yes, you are right. Earlier I had a wrong interpretation is that sorting n suffix would take O(n logn), which is indeed O(n^2 log n).
There is no O(n^2) loop, however. Each suffix of S1 would do a (modified) binary search on the sorted suffix array T1. Because if suffix x (for example) have a prefix match of length <= 2, you need not to continue the search in that direction.
Suffix Tree/Array based solutions would be the choice here. I could come up with a suffix array based approach taking O(n logn) time.
Let, S be the string, T be the reverse of the string.
Let, S = ABC where A,B,C is a substring of length >= 0
then, T = C'B'A' where C', B', A' is reverse of C,B,A respectively
Now, if B and B' is palindrome, they cover same segment of the given string, and B match with B'.
Let, S1 be the set of suffices of S
and, T1 be the set of suffices of S
Sort S1 and T1
Now, for every suffix in S1, check if it's has a prefix match (of length > 2) with some element of T1. Also check the range each prefix match represents. Do, same for for every suffix in T1.
Working with input S = abaabccba. Hence, T = abccbaaba
Hence, S1 = { a, aabccba, abaabccba, abccba, ba, baabccba, bccba, cba, ccba}
and, T1 = { a, aaba, aba, abccbaaba, ba, baaba, bccbaaba, cbaaba, ccbaaba}
Catch any possible flaw in this approach. Thanks.
I dont think this problem can be solved in O(nlogn). For a correct algorithm it would take atleast O(palindromes). So it would be O(nlogn) + O(no_palindromes) . number of palindromes can be O(n^2). I usually use a data structure by name dictionary of basic factors which can be built in O(nlogn*logn) and can answer queries like are the 2 substrings same or which is lexicographically smaller than other. Using this also we can solve the problem
If we use hashing this problem can be solved in O(n^2) time, assuming a perfect hash function. We need to compute hash both in original sequence and reverse sequence of the string. As hash is computed incrementally, it'll take O(n) time for getting all hash of substring length k, for 3 <= k <= n-1.
Working Code:
bool flag=0;
char *p, *q, *curr, i=0,j=0;
curr = text,p = text, q = text;
for(i = 1; i< strlen(text);i++)
{
//Case1 //Odd palindromes
p = curr+1;
q = curr-1;
flag = 0;
while(*p == *q){
p++, q--;
flag = 1;
}
if(flag){printf(":Odd:");
printf("%c", *curr);
}
//Case2 //Even palindromes
p = curr;
q = curr-1;
flag = 0;
while(*p == *q){
p++, q--;
flag = 1;
}
if(flag){printf(":Even:");
printf("%c", *curr);
}
curr++;
}
Say n is the position of current element
When we come across n and n+1 th element to be same, there is a possibility for even palindrome.
When we come across n-1 and n+1 th element to be same, there is a possibility for odd palindrome.
If we keep checking these 2 conditions when we parse each character, we can get all the palindromes.
import java.util.Hashtable;
public class StringPalindrome{
private Hashtable hm;
public int checkPalindrome( final String iWord ){
assert( iWord != null );
int length = iWord.length();
hm = new Hashtable();
if( length<3 ) { System.out.println( "No Palindromes in the String" ); return 1; }
for( int i=1; i< length-1; ++i ){
if( iWord.charAt( i ) == iWord.charAt( i + 1 ) )
checkEvenPalindrome( iWord, i );
if( iWord.charAt( i - 1 ) == iWord.charAt( i + 1 ) )
checkOddPalindrome( iWord, i );
}
return 1;
}
private void checkEvenPalindrome( final String iWord, final int iIndex ){
int len = iWord.length();
int count = 0;
String sb = "";
for( int i= iIndex-1, j = iIndex + 2; i>=0 && j< len; ){
if( iWord.charAt( i-- ) == iWord.charAt( j++ ) ){
count++;
sb = iWord.substring( i+1, j ) ;
}
else
break;
}
if( count > 0 ) {
if( !hm.containsKey( sb ) ){
System.out.println( sb );
hm.put( sb, new Integer(1) );
}
}
}
private void checkOddPalindrome( final String iWord, final int iIndex ){
int len = iWord.length();
String sb = "";
for( int i=iIndex-1, j = iIndex+1; i>=0 && j<len; ) {
if( iWord.charAt( i-- ) == iWord.charAt( j++ ) ){
sb = iWord.substring( i+1, j );
}
}
if( !hm.containsKey( sb ) ){
System.out.println( sb );
hm.put( sb, new Integer( 1 ) );
}
}
public static void main( String [] args ) {
StringPalindrome sp = new StringPalindrome();
sp.checkPalindrome( args[ 0 ] );
}
}
// p is the cached results.
bool checkPalindrome(string s, int start, int end, int **p) {
if (p[start][end] == -1) {
if (end - start > 2) {
if (s[start] == s[end]) {
if (checkPalindrome(s, start + 1, end - 1, p)) {
p[start][end] = 1;
return true;
} else {
p[start][end] = 0;
return false;
}
} else {
p[start][end] = 0;
return false;
}
} else {
if (s[start] == s[end]) {
p[start][end] = 1;
return true;
} else {
p[start][end] = 0;
return false;
}
}
}
else return p[start][end] == 1;
}
void printPalindrome(string s) {
int slen = s.length();
int **p = new int *[slen];
for (int i = 0; i < slen; i++) {
p[i] = new int[slen];
}
for (int i = 0; i < slen; i++)
for (int j = 0; j < slen; j++)
p[i][j] = -1; // do not know
for (int i = 0; i < slen - 1; i++) {
for (int j = slen - 1; j > i + 1; j--) {
if (checkPalindrome(s, i, j, p)) {
cout << s.substr(i, j - i + 1) << endl;
}
}
}
for (int i = 0; i < slen; i++) {
delete[] p[i];
}
delete[] p;
}
#include <stdio.h>
#include <string.h>
int is_palindrome(char a[], int left, int right)
{
while (left <= right) {
if (a[left] == a[right]) {
left++;
right--;
} else {
return 0;
}
}
return 1;
}
print_palindrome(char a[], int len)
{
int left, right;
char output[64];
for (left = 0; left < len-1; left++)
{
for (right = left+2; right < len; right++)
{
if (is_palindrome(a, left, right)) {
strncpy(output, a+left, right-left+1);
output[right-left+1] = '\0';
printf("\n the palindrome is %s length is %d", output, strlen(output));
memset(output, '\0', 64);
}
}
}
}
main()
{
char a[] = "abaabccba";
print_palindrome(a, 9);
}
import java.util.Hashtable;
public class StringPalindrome{
private Hashtable hm;
public int checkPalindrome( final String iWord ){
assert( iWord != null );
int length = iWord.length();
hm = new Hashtable();
if( length<;3 ) { System.out.println( "No Palindromes in the String" ); return 1; }
for( int i=1; i< length-1; ++i ){
if( iWord.charAt( i ) == iWord.charAt( i + 1 ) )
checkEvenPalindrome( iWord, i );
if( iWord.charAt( i - 1 ) == iWord.charAt( i + 1 ) )
checkOddPalindrome( iWord, i );
}
return 1;
}
private void checkEvenPalindrome( final String iWord, final int iIndex ){
int len = iWord.length();
int count = 0;
String sb = "";
for( int i= iIndex-1, j = iIndex + 2; i>=0 && j< len; ){
if( iWord.charAt( i-- ) == iWord.charAt( j++ ) ){
count++;
sb = iWord.substring( i+1, j ) ;
}
else
break;
}
if( count > 0 ) {
if( !hm.containsKey( sb ) ){
System.out.println( sb );
hm.put( sb, new Integer(1) );
}
}
}
private void checkOddPalindrome( final String iWord, final int iIndex ){
int len = iWord.length();
String sb = "";
for( int i=iIndex-1, j = iIndex+1; i>=0 && j<len; ) {
if( iWord.charAt( i-- ) == iWord.charAt( j++ ) ){
sb = iWord.substring( i+1, j );
}
}
if( !hm.containsKey( sb ) ){
System.out.println( sb );
hm.put( sb, new Integer( 1 ) );
}
}
public static void main( String [] args ) {
StringPalindrome sp = new StringPalindrome();
sp.checkPalindrome( args[ 0 ] );
}
}
bool checkPalindrome(string s, int start, int end, int **p) {
if (p[start][end] == -1) {
if (end - start > 2) {
if (s[start] == s[end]) {
if (checkPalindrome(s, start + 1, end - 1, p)) {
p[start][end] = 1;
return true;
} else {
p[start][end] = 0;
return false;
}
} else {
p[start][end] = 0;
return false;
}
} else {
if (s[start] == s[end]) {
p[start][end] = 1;
return true;
} else {
p[start][end] = 0;
return false;
}
}
}
else return p[start][end] == 1;
}
void printPalindrome(string s) {
int slen = s.length();
int **p = new int *[slen];
for (int i = 0; i < slen; i++) {
p[i] = new int[slen];
}
for (int i = 0; i < slen; i++)
for (int j = 0; j < slen; j++)
p[i][j] = -1; // do not know
for (int i = 0; i < slen - 1; i++) {
for (int j = slen - 1; j > i + 1; j--) {
if (checkPalindrome(s, i, j, p)) {
cout << s.substr(i, j - i + 1) << endl;
}
}
}
for (int i = 0; i < slen; i++) {
delete[] p[i];
}
delete[] p;
}
- Anonymous July 17, 2013void printPalindromes(string& str) { int N = str.size(); vector<vector<bool> > dp(N,vector<bool>(N)); for (int i=0; i < N; i++) { dp[i][i] = 1; cout << str[i] << endl; } for (int k=1; k < N; k++) { for (int i=0, j=k; j < n; j++, i++) { dp[i][j] = s[i] == s[j] & dp[i+1][j-1]; if (dp[i][j]) cout << str.substr(i, k) << endl; } } }