## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

It is called Manacher algorithm. For excellent explanation of Manacher algorithm see,

leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Also visit wiki page,

en.wikipedia.org/wiki/Longest_palindromic_substring

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

this one makes sense! it uses O(n) time and O(n) space

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

Which makes it wrong? The needed one is O(1) space complexity. I don't think that's possible.

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

``````public static int pal(String s) {
char[] array = s.toCharArray();
int maxCounter = 1;
for (int i = 1; i < array.length - 1; i++) {
int counter = 1;
int l = i - 1;
int r = i + 1;
while ( l > 0 && r < array.length - 1 ) {
if (array[l] == array[r]) {
counter++;
r++;
l--;
} else {
break;
}
}
if (counter > maxCounter) {
maxCounter = counter;
}
}
return maxCounter;
}``````

Not entirely sure this is O(n) time. It is def O(1) space.

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

It is called Manacher algorithm. For excellent explanation of Manacher algorithm see,

leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

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

It is surely not O(N). You are checking for palindrome for every possible position. Checking palindrome takes O(N) time and there are O(N) such positions. So, it is O(N^2) algorithm.

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

this is the first solution i gave, but you need to give O(n) + O(1) complexity solution, I finally gave the solution of required bound

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

I am 100% sure that finding a longest palindrome in a given string is not possible in O(n) & O(1). There is only one best case when the string itself is palindrome. Can u post yr solution here?

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

I fixed a few bugs in panos' answer. It wasn't handling cases such as "madamyracecarxzyjj" correctly. Also, pal() was returning a counter instead of the number of characters in the palindrome. Finally, I adapted it to C++.

``````int pal(string s)
{
int maxCounter = 1;
for (int i = 1; i < s.length() - 1; i++) {
int counter = 1;
int l = i - 1;
int r = i + 1;
while ( l >= 0 && r <= s.length() - 1 )
{
//cout << "s[l] :" << s[l] << "  s[r]: " << s[r] << endl;
if (s[l] == s[r]) {
counter++;
//cout << "counter: " << counter << endl;
r++;
l--;
}
else
{
if (counter > maxCounter)
{
maxCounter = ((counter * 2) - 1);
}

break;
}
}

}
return maxCounter;
}``````

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

Also, this solution still does not quite meet the requirements since it runs in O(n^2) time

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

you sure it can be done in O(n)? basically you don't know the start point and end point of the palindrome, so I think you need at least O(n^2). Let me know if I was wrong.

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

Actually when you run your o(n*n) solution, look the algorithm's step very carefully, you will realize that we are doing many recalculations, which are not required, and when you are able to remove those recalculations, you will get the required solution.

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

You can use this recursion formulae

P(crawlerFromBeginning,crawlerFromEnd) =
if(word[crawlerFromBeginning]== word[crawlerFromEnd]){
2 + P(crawlerFromBeginning+1,crawlerFromEnd-1) // if the characters at the position
are equal
}
else{
max(P(crawlerFromBeginning+1,crawlerFromEnd) ,P(crawlerFromBeginning,crawlerFromEnd-1) )
}

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

Sorry for previous comment ...the above code is right.

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

I realize above algo doesn't taking care of Even cases (like: cdeedc, aaaa ) & what about string length 2 (aa) .
So i am fixing the code now.

public int pal(String s) {
// null pointer check for s and length of s if 0
if (s == null)
return 0;

int len = s.length();

if (len < 2) {
return len;
}

char[] array = s.toCharArray();

// the algorithm will fail for strings of length 2

if (len == 2) {
if (array[0] == array[1])
return len;
else
return 0;
}

int maxCount = 1;

for (int center = 1; center < len - 1; center++) {
int palinLen = 1;
int l = center - 1;
int r = center + 1;
// Even Case handled here
// in case of aaa center + 2 (where center=1) = 3 < 3 means this case will not land in
// Even case;
if (array[center] == array[center + 1] && (center + 2 < len)) {
r = center + 2;
palinLen++;
}

while (l >= 0 && r <= len - 1) {
if (array[l] == array[r]) {
r++;
l--;
palinLen += 2;
}

}
if (l < 0 || r == len) {
if (palinLen > maxCount) {
maxCount = palinLen;
}
}
}
return maxCount;
}

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

There are a few fixes the above code required:-
1. the while loop while (l >= 0 && r <= len - 1) required to check for l<=r as well.

2. Inside this loop if if (array[l] != array[r]) we had to break out of this loop.

3. The last if clause if (l < 0 || r == len) is not required.

``````public static void main(String args[]) {
String str = "ABCDMNPPNMDCBAOPOABCDMPNSSNPM";
System.out.println(pal(str));

}

static public int pal(String s) {
// null pointer check for s and length of s if 0
if (s == null)
return 0;

int len = s.length();

if (len < 2) {
return len;
}

char[] array = s.toCharArray();

// the algorithm will fail for strings of length 2

if (len == 2) {
if (array[0] == array[1])
return len;
else
return 0;
}

int maxCount = 1;

for (int center = 1; center < len - 1; center++) {

int palinLen = 1;
int l = center - 1;
int r = center + 1;
// Even Case handled here
// in case of aaa center + 2 (where center=1) = 3 < 3 means this
// case will not land in
// Even case;
if (array[center] == array[center + 1] && (center + 2 < len)) {
r = center + 2;
palinLen++;
}

while (l >= 0 && r <= len - 1 && l<=r) {
if (array[l] == array[r]) {
r++;
l--;
palinLen += 2;
}
else
{
break;
}

}
if (palinLen > maxCount) {
maxCount = palinLen;
}
}
return maxCount;
}``````

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

I fixed panos's code a little bit. But it's still not O(n). C# code.

``````static int ReturnMaxPalindromeLength(string value)
{
if (string.IsNullOrEmpty(value) || value.Length < 2)
return 0;
int currentlength = 0;
int maxLength = 0;
for (int i = 0; i < value.Length; i++)
{
int left = i - 1;
int right = i + 1;
if (left < 0 || right > value.Length - 1 || !value[left].Equals(value[right]))
continue;
while(left >= 0 && right <= value.Length - 1)
{
if (value[left].Equals(value[right]))
{
currentlength++;
left--;
right++;
}
else
{
break;
}
}
if (currentlength > maxLength)
maxLength = currentlength;
currentlength = 0;
}
return maxLength*2 + 1;
}``````

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

leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

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

The question is incorrect - Manacher's algorithm uses O(n) space, not constant space.

So the best solution takes O(n) time and O(n) space.

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

``````string longest_around(const string& str, int i, int j)
{
string longest;
int left = i, right = j;
while(str[left] == str[right])
{
longest = str[left] + longest + str[right];
++left; ++right;
}

return longest;
}

string longest_palindrome(const string& str)
{
string result;
for(int i = 0; i < str.length() - 1; ++i)
{
string pal = longest_around(str, i, i);
if(pal.length() > result.length())
{
result = pal;
}

pal = longest_around(str, i, i + 1);
if(pal.length() > result.length())
{
result = pal;
}
}

return result;
}``````

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

``````public class LongestPalindrome {

public static void main(String[] args){

System.out.println("Enter the string");
String str1=new String();
//String str1=new String();
Scanner s=new Scanner(System.in);
str1=s.nextLine();
char[] s1 = str1.toCharArray();
char [] s2 = new char[2*str1.length()+1];
int l,r,count,maxcount=1;
for(int j=0;j<2*str1.length()+1;j++)
{

if(j%2==0) {

s2[j]='#' ;

}

else{

s2[j] = s1[j/2];

}

}

/* for(int k=0;k<2*str1.length()+1;k++)
System.out.print(s2[k]);  */

for(int i=1;i<2*str1.length()+1;i++){
count=0;
l=i-1;
r=i+1;

while(l>=0 && r<=2*str1.length() && s2[l]==s2[r])
{
count++;
l--;
r++;

}

if(count>maxcount){

maxcount=count;

}

}

System.out.println("");

System.out.println("the maximum sized palindrome is  " + maxcount);

}

}``````

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

I do not see any point in asking such complex code for interview ..This is wrong method to select people who have just mugged up things ...This is not knowledge at all.

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

The question makes no sense.

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

In order to find the Longest Palindromic Substring in O(n) we need to apply the Manacher's Algorithm. It works like this:
Let's say that we have the input string S:

``S = ccacaacaba``

First Step: Preprocess input string by inserting special Character '#' between each char in the string:

``T = ^#c#c#a#c#a#a#c#a#b#a#\$``

Characters ^ and \$ are used just to avoid bounds checking. Let's call this preprocessed String T.
Then we need to create an Array (P) with the same size of the preprocessed String T. This array will have at each position i the size of the longest Palindrome centered in i.

``````T = ^ # c # c # a # c # a # a # c # a # b # a # \$
P = 0 0 1 2 1 0 3 0 3 0 1 6 1 0 3 0 1 0 3 0 1 0``````

In order to compute all the value of P efficiently, we can use the simmetric property of P, for example if we take into account the palindrome centered at position i=11, T[11] ("acaaca"), we can see that the value of P at position i+1 is equal at the value of P at position i-1 (T[i-1]==T[i+1]) and T[i-2]==T[i+2], T[i-3]==T[i+3] ... T[i]==T[i_mirror].
The problem is that this property is not always valid. Let's take into account i+5 and i-5. Note T[i+5]==1 and T[i-5]==3. This happens because the Palindrome centered at i-5 expands beyond the left limit of the simmetric center that we took into account P[11], with palindromic length of 6. This means that the simmetric property is guaranteed only if P[i_mirror] <= R-i, where R is the Right limit of the Palindrome centered at the simmetric center C that we are taking into account (in this case P[11]). If R-i<P[i_mirror] then we only know that P[i]>=R-i. Thus we need to expand the palindrome size centered at i char by char:

``````while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;``````

the last step is to know when to move the simmetric center C and the right limit R to the right with i. This happens when i past the right limit R of C:

``````if(R<i+P[i]) {
C=i;
R=i+P[i];
}``````

Expanding a palindrome take at most O(n) and moving the center also at most O(n), therefore this algorithm performs with O(2n) complexity, thus this is a linear algorithm to find the longest Palindrome substring.

In my code you can use

``String stringGenerator(int n)``

to generate a random String from the alphabet (first var in the method) of length n;
the method

``String manacherizeString(String s)``

preprocess the input string by inserting special characters and the longest palindromic substring is retrieved by the method

``String manacher(String s)``

Here is the complete code implementing the Manacher Algorithm in java:

``````import java.util.Random;

public class LongestPalindromicSubstring {
public static String manacherizeString(String s) {
if(s.length()==0) return "^\$";
String p = "^#";
for(int i=0;i<s.length();i++) {
p+=s.charAt(i)+"#";
}
p+="\$";
return p;
}
public static String manacher(String s) {
String T = manacherizeString(s);
System.out.println(T);
int R = 0;
int C = 0;
int imirror;
int[] P = new int[T.length()];
for(int i=1;i<T.length()-1;i++) {
imirror = C-(i-C);
if(R>i) {
P[i] = Math.min(P[imirror],R-i);
}
else {
P[i] = 0;
}
while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;
if(R<i+P[i]) {
C=i;
R=i+P[i];
}
}
int maxLength = 0;
int maxCenter = 0;
for(int i=0;i<P.length-1;i++) {
System.out.print(P[i]+" ");
if(P[i]>maxLength) {
maxLength = P[i];
maxCenter = i;
}
}
System.out.println("\nMaxLength: "+maxLength+" MaxCenter: "+maxCenter);
return s.substring((maxCenter-1-maxLength)/2,((maxCenter-1-maxLength)/2)+maxLength);
}
public static String stringGenerator(int n) {
//String alphabet = "abcdefghiklmnopqrstuvxyz";
String alphabet = "abc";
String s = "";
Random r = new Random();
for(int i=0;i<n;i++) {
s+=alphabet.charAt(r.nextInt(alphabet.length()));
}
return s;
}
public static void main(String[] args) {
String s = stringGenerator(10);
System.out.println(s);
System.out.println("Longest Palindromic Substring:\n"+manacher(s));
}
}``````

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

Hey All,

it should be r-- and l++ instead of r++ and l--

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

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.