## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

just use mancher algorithm..complexity O(n)

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

Please noe that this algorithm require space complexity as well, which is O(N)

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

The following code does it. Not sure about the complexity though

``````static int lengthLargestPalindrome(String x){
StringBuilder sb = new StringBuilder(x);
String orig = sb.toString();
String rev = sb.reverse().toString();
if(orig.equals(rev)){
return orig.length();
}
return Math.max(lengthLargestPalindrome(x.substring(1)), lengthLargestPalindrome(x.substring(0,x.length()-1)));
}``````

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

Manacher algorithm is what you are looking for. Here is the link: http://en.wikipedia.org/wiki/Longest_palindromic_substring

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

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”. for this string it wont work as your rsult will give abacd but that should not be the case.

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

You did not even understand Sachin. Did you

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

Does anybody have a better solution than O(n^2) in time

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

Unfortunately it is O(n^2) even with a lot of optimizations but at least the memory cost is O(1):

``````public String largestPalen(String str){
String largest = "";
char[] chars = str.getChars();
for(int left = 0; left < str.length(); left++){
for(int right = str.length()-1; right >= left; right--){
if(isPalen(chars, left, right)){
if(right - left > largest.length){
largest = str.subString(left, right);
}
break;
}
}
if(largest.length() >= str.length() - left){
break;
}
}
return largest;
}

private boolean isPalen(char[] chars, int lo, int hi){
while(lo < hi){
if(chars[lo++] != chars[hi--]){
return false;
}
}
return true;
}``````

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

It is O(n^3). Because "isPalen" is O(n)

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

``````{ 1 if i=j
L(i,j)= { L(i+1,j-1) +2  if s[i]=s[j]
{ max { L(i+1,j), L(i,j-1) } otherwise

find L(0,n-1)``````

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

``````public class Palindrome {

/**
* Returns the longest palindrome.
* @param str the string to check
* @return the longest palindrome
*/
public static String findMaxPalindrome(String str) {
String max = "";
int maxLength = 0;
for (int i = 0; i < str.length(); i++) {
// palindrome only starts with a letter.
if (!Character.isLetter(str.charAt(i))) continue;
for (int j = i + maxLength; j < str.length(); j++) {
// palindrome only ends with a letter.
if (!Character.isLetter(str.charAt(j))) continue;
// get substring length without space
int count =  getSubstringLength(str, i, j);
if (count > maxLength && isPalindrome(str, i, j)) {
max = str.substring(i, j+1);
maxLength = count;
}
}
}
return max;
}

/**
* returns the number of letter chars in the sub string from the index i
* to the index j.
* @param str the string to checl
* @param i the start index
* @param j the end index
* @return the number of letters.
*/
private static int getSubstringLength(String str, int i, int j) {
int count = 0;
for (int k = i; k < j; k++) {
if (Character.isLetter(str.charAt(k))) count++;
}
return count;
}

/**
* Check if the substring (from i to j) is a palindrome.
* Use recurcivity.
* @param str the string to check
* @param i the start index
* @param j the end index
* @return true if it is a palindrome, false otherwise.
*/
private static boolean isPalindrome(String str, int i, int j) {
if (j <= i) return true;
if (!Character.isLetter(str.charAt(i))) return isPalindrome(str, i+1, j);
if (!Character.isLetter(str.charAt(j))) return isPalindrome(str, i, j-1);
return Character.toLowerCase(str.charAt(i)) == Character.toLowerCase(str.charAt(j))
&& isPalindrome(str, i+1, j-1);
}

/**
* Main
* @param args
*/
public static void main(String[] args) {
String str = "Hi Anna! A Toyota’s a Toyota. Do you agree?";
String palindrome = findMaxPalindrome(str);
System.out.println(palindrome); // => A Toyota’s a Toyota
}
}``````

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

``````String longestPalindrome(String given) {
if(given == null || given.equals("")) {
return "empty";
}

int[][] lengthMatrix = new int[given.length()][given.length()];
for(int i=0; i< given.length(); i++) {
for(int j=0; j< given.length(); j++) {
if(i==j) {
lengthMatrix[i][j] = 1;
}
else {
lengthMatrix[i][j] = 0;
}
}
}

int max=1, startIndex=0, endIndex=0;
String normalize = given.toLowerCase();
for(int len= 2; len<= given.length(); len++) {
for(int j=0; j<= given.length() - len; j++) {
if(normalize.charAt(j) == normalize.charAt(j+len-1)) {
if(len == 2) {// boundary case
lengthMatrix[j][j+len-1] = 2;
max = len; startIndex = j; endIndex = j+len-1;
}
else if(lengthMatrix[j+1][j+len-2] != 0) {
lengthMatrix[j][j+len-1] = len;
max = len; startIndex = j; endIndex = j+len-1;
}
}
}
}
return given.substring(startIndex, endIndex+1);
}``````

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

dynamic programming

optimal substructure:
abcba is a palindrome if and only if bcb is a palindrome.

overlapping sub problems
checking index 0-4 is a palindrome and checking index 1-3 is a palindrome both involve common checks

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

Javascript code - Can we do it better than O(n2)?

``````function isPlaindrome(str) {
var i = 0;
var j = str.length - 1;
while (i < j) {
if (str[i] === str[j]) {
i++;
j--;
} else {
return false;
}
}
return true;
}

function getAllPossibleSubstrings(str, subStringLength) {
if (str.length < subStringLength) {
return [];
}

var substrings = [];
if (str.length === subStringLength) {
return substrings.push(str);
}

for (var i = 0; i < (str.length - subStringLength); i++) {
substrings.push(str.substring(i, i + subStringLength));
}
return substrings;
}

function findLargestPalindrome(str) {
if (isPlaindrome(str)) {
return str;
}

var length = str.length - 1;
for (var i = length; i >= 2; i--) {
var subStrings = getAllPossibleSubstrings(str, i);

for (var j = 0; j < subStrings.length; j++) {
if (isPlaindrome(subStrings[j])) {
return subStrings[j];
}
}
}

return '';

}``````

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

Approach:

-Have 3 pointer (or three char var in case Java String) prev, char and next
-Move pointer one by one and check whether prev and next are same
-In case prev and next are not same keep moving
-In case prev and next are same, save char in MaxPalindromeMid, check prev's prev and next's next and keep checking, increase counter util not same not occurs
-Resume moving step by step and check all the palindrome and update counter and MaxPalindromeMid only in case got bigger then prev palindrome.

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

``````//l and r are centers of palindrom
//returns max palindrom size arouns l and r centers
//let call palindrom centers index's around palindrom center
{
int sz=0;
int rr=r;
int ll=l;
if(s.length()==0)return 0;
while(ll>=0&&rr<s.size())
{
if(s[l]==s[r])sz++;
else break;
++rr;--ll;
}
if(r-l==1)return 2*sz;
else if(r-l==2)return 2*sz+1;
else return 0;//error case
}

std::string largest_palindrom(std::string s)
{
int max_sz=0;
int c=0;
for(int i=0;i<s.length()+1;++i)
{
int e=max_palindrom(s,i-1,i);//for even size palindroms
int o=max_palindrom(s,i-1,i+1);//for odd size palindroms
if(std::max(o,e)>max_sz)
{
max_sz=std::max(o,e);
c=i;
}
}
//sz is a largest palindrom size
//but I return largest palindrom
return s.substr(c-max_sz/2,max_sz);
}``````

in worst case it works in O(n^2) time
but average time is O(n)
use O(1) memory
algorithm is simply don't use hard techniques

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

In java:

``````import java.lang.*;

class HelloWorld{

public static int size(String str){
for(int j = 0;j < str.length() / 2;j++){
if(str.charAt(j) != str.charAt(str.length() - 1 - j)) return 0;
}
return str.length();
}

public static void main(String []args){
String str = "anna atoyota atoyota !";
int size = 0;
int count = 0;
for(int i = 0;i < str.length();i++){
if(str.charAt(i) == ' '){
if(size(str.substring(count, i)) > size) size = size(str.substring(count, i));
//System.out.println(str.substring(count, i));
count = i + 1;
}
}
System.out.println(size);
}
}``````

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

Here is dynamic programming solution...
Let R[i][j] = {0} ... stores the computation results of (i, j) frame.
Let is_pal(A, i, j): returns palindrome length of substring A[i...j], if its a palindrome, 0 otherwise.

``````mpal(A, i, j) {
if(R[i][j])
return R[i][j];
else
return (R[i][j] = max{mpal(A, i+1, j-1), mpal(A, i, j-1), mpal(A, i+1, j), is_pal(A, i, j)});
}``````

(A, i,j):

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

java code to print maximum palindrome

import java.io.IOException;

public class largetpalindrome {

/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
String path = "C:\\Users\\Administrator\\Desktop\\test\\test\\src\\input.txt";
String line;

// input array one
char[] c = line.toCharArray();
int max=0,result=0;
boolean sucess=true;
for(int i = 1;i<c.length-1;i++)
{
int pre=i-1,next=i+1;
while(sucess){
if(c[pre]==c[next])
{
max++;
if(pre!=0)
{
--pre;

}else
break;
if(next!=(c.length-1))
++next;
else
break;
}
else
sucess=false;
}
sucess =true;
if(result<max)
result=max;
max=0;
}
result=result*2+1;
System.out.print(result+" ");

}

}

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

This solution provides algorithm complexity of O(N) and space complexity of O(1). The reasoning, code and test are explained here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find.html

Pseudo-code
1. If the string is empty, then return -1.
2. If the string has only one character, then return 1.
4. If the string has two characters,
return 2, if two characters are equal,
return 1, if they are not
5. Assign tempIndex = 0; curIndex = 1; foundPalindrome = false and palindromeLength = 1
6. If str[curIndex] is equal to str[curIndex - 1], then set tempIndex = curIndex -1 and foundPalindrome = true. Increment curIndex until str[curIndex] is equal to str[tempIndex] and str[curIndex + 1] is not euqal to str[tempIndex], Go to Step 8,
7. If str[curIndex] is equal to str[curInex - 2] (only if curIndex - 2 is valid index), then set tempIndex = curIndex - 2 and foundPalindrome = true.
8. Increment curIndex anyway, If str[curIndex] is euqal to str[tempIndex - 1] (only if tempIndex -1 is a valid Index), decrement tempIndex.
9. Repeat Step 8 until
9. 1 curIndex reaches the end of str: then save the result if (curIndex - tempIndex) > palindromeLength and return.
9.2 tempIndex - 1 reaches beyond the start of str or str[curIndex] != str[tempIndex - 1]: then clear foundPalindrome and save the result if (curIndex - tempIndex) > palindromeLength. Then go to Step 6.

``````#include <string>

struct PalindromeInString
{
int pos;    // start position in string
int len;    // length of palindrome
};

PalindromeInString FindLargestPalindromeInString(const std::string& str)
{
if (str.empty()) {
return PalindromeInString{ -1, -1 };
}

if (str.length() == 1) {
return PalindromeInString{ 0, 1 };
}

if (str.length() == 2) {
if (str[0] == str[1]) {
return PalindromeInString{ 0, 2 };
}
else {
return PalindromeInString{ 0, 1 };
}
}

PalindromeInString result = { 0, 1 };
bool found = false;
size_t tempIndex;
size_t curIndex;
for (tempIndex = 0, curIndex = 1; curIndex < str.length(); ++curIndex) {
if (!found) {
if (str[curIndex] == str[curIndex - 1]) {
// Step 6
found = true;
tempIndex = curIndex - 1;
while ((curIndex + 1) < str.length()) {
if (str[curIndex + 1] != str[tempIndex]) {
break;
}
else {
++curIndex;
}
}
}
else if (curIndex > 1 && str[curIndex] == str[curIndex - 2]) {
// Step 7
found = true;
tempIndex = curIndex - 2;
}
else {
continue;
}
}
else {
// Step 9
if (tempIndex > 0 && str[curIndex] == str[tempIndex - 1]) {
--tempIndex;
}
else {
found = false;
// save the palindrome with max length found so far
if (result.len < (curIndex - tempIndex)) {
result = { tempIndex, curIndex - tempIndex };
}
}
}
}

if (found && result.len < (curIndex - tempIndex)) {
result = { tempIndex, curIndex - tempIndex };
}

return result;
}``````

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

what if there are two palindromes and they overlap each other, and the longer palindrome's center point locates within the other one? will this case work?

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

Idea is simple: find largest odd palindrome and even one and then find largest among two.

``````size_t StrLen(char *s)
{
size_t length = 0;

if (s)
{
for (; *s; length++, s++);
}

return length;
}

bool FindLongestPalindrome(char *s, int *piBegin, int *piEnd)
{
bool fFound = false;
size_t length = 0;
int i = -1;
int j = -1;

if (s && piBegin && piEnd)
{
length = StrLen(s);
*piEnd = 0;
*piBegin = 1;

// find longest odd palindrome
for (int k = 0; k < length; k++)
{
i = k;
j = k;

while (i >= 0 && j < length)
{
if (s[i] != s[j])
{
break;
}
else
{
if (j - i > *piEnd - *piBegin)
{
fFound = true;
*piEnd = j;
*piBegin = i;
}
i--;
j++;
}
}
}

// find longest even palindrome
for (int k = 0; k < length - 1; k++)
{
i = k;
j = k + 1;

while (i >= 0 && j < length)
{
if (s[i] != s[j])
{
break;
}
else
{
if (j - i > *piEnd - *piBegin)
{
fFound = true;
*piEnd = j;
*piBegin = i;
}
i--;
j++;
}
}
}
}

return fFound;
}``````

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

I haven't coded it but I have a approach. Get to the middle of string. Check its left index of middle and right one. If both are same , then keep on incrementing right index and decrement left index. Once difference is found , we have the currently available longest palindrome string. Pass this length recursively for two sub strings - Left and Right.

As per static analysis, it's complexity will be O(nlogn)..

Thoughts....

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

I am confused, is the question asking for longest length palindromic substring in a string or longest length palindromic subsequence in a string?

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

class Program
{
static void Main(string[] args)
{
string data="knammans";
bool check;
int[] arr=new int[data.Length];
int counter = 0;
for (int i = 0; i < data.Length-2;++i )
{
for(int j=i+1;j<data.Length-1;++j)
{
if(data[i]==data[j])
{
check = palindrome(data.Substring(i, j - i + 1));
if(check)
{
arr[counter++] = j - i + 1;

}
}

}
}
Console.WriteLine("max substring is:{0}",arr.Max());
}
static public bool palindrome(string data)
{
int i, f;
i = 0; f = data.Length - 1;
while(i<f)
{
if (data[i] == data[f])
{
i++;
f--;
continue;
}
else
return false;
}
return true;

}
}

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

``````public static int findLargestPalindrome(String text){
String[] strings = text.split(" ");
int largest = 0;
for (int i = 0; i < strings.length; i++) {
if (isPalindrome(strings[i])) {
if (largest<strings[i].length()) {
largest = strings[i].length();
}
}
}
return largest;
}
public static boolean isPalindrome(String s){
int i=0,j=s.length()-1;
boolean isPalindrome = true;
while (i<j) {
if (s.charAt(i) != s.charAt(j)) {
isPalindrome = false;
break;
}
i++;j--;
}
return isPalindrome;
}``````

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

this cannot handle this string, `abac'. it will consider it is not palindrome. actually, `aba' is the longest palindrome.

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.