## Microsoft Interview Question for SDE-2s

Country: United States

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

``````def max_palindrome(head):
num_eq = 0

while n1 and n2:
if n1.value != n2.value:
break

n1 = n1.next
n2 = n2.next

num_eq += 2

return num_eq

return 1

prev_node = None
max_p = 1

while cur_node:
next_node = cur_node.next
cur_node.next = prev_node

if next_node:

prev_node = cur_node
cur_node = next_node

return max_p``````

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

``````struct ListNode
{
int data;
ListNode *next;
};

int count_common(ListNode *a, ListNode *b)
{
int ret = 0;

for (; a && b; a = a->next, b = b->next)
if (a->data == b->data)
++ret;
else
break;

return ret;
}

{
int ret = 0;
ListNode *p = nullptr, *q = head;

while (q)
{
auto t = q->next;

q->next = p;

ret = max(ret, 2 * count_common(p, t) + 1);
ret = max(ret, 2 * count_common(q, t));

p = q;
q = t;
}

return ret;
}

int main()
{
p->next = new ListNode({.data = 2}); p = p->next;
p->next = new ListNode({.data = 1}); p = p->next;
p->next = new ListNode({.data = 2}); p = p->next;
p->next = new ListNode({.data = 1}); p = p->next;
p->next = nullptr;

cout << max_palindrome(head) << endl;  //5

return 0;
}``````

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

This algorithm reverses a list as it goes through it. For example, let's say we have a list e -> b -> c -> b -> a -> b -> c -> h. When we reach 'a', the list will look something like this e <- b <- c <- b <- a -> b -> c -> h. Now we just go in both directions from `a` and compare characters.
We check for both cases: if palindrome is even (aabb) and odd (abcba).

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

In the end you can restore the original list, reversing it once more.

The algorithm is O(n^2) running time, since it can happen that we traverse the list multiple times in both directions (for example, 'aaaaaaa' will trigger multiple traversals).

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

the solution does not work.
Input list: 0->1->2->3->4->5->1->2->2->1->9.
The output is 5. But it should be 4.
Moreover, the answer should be "1221", but not just the length of the largest palindrome.

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

Thank you.
There is a bug which I corrected but the post did not update for some reason.
In count_common in for loop with inner if condition there should be an else branch doing simple break when elements are not equal.

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

And one more: your solution is specific and sharpened to integer data in list.
But the task does not limit the data type of nodes' data to int.
So, your solution will not work for list of strings, “aba” -> “cd” -> “efe” -> “d” -> “caba”, etc.

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

So How does the algorithm decide where to stop reversing the list before checking for palindrome?
If it is exactly halfway through then the solution wouldn't work if the palindrome is not the entire list.

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

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

I'm not shoumikhin, but I tried to explain the code, see my comment to his answer.

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

Shoumikhin can u please explain approach

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

``````bool IsPallindrom(Node head){
}

Node IsPallindrom(Node left,Node right)
{
// Boundary condition
if(left == null || right == null) return null;

// Terminating condition
// Recurring condition
var newRight = right->next == null ? left->Next : IsPallindrom(left->Next, right->Next->Next);

// Fail condition
if(newRight == null ) return null;

// Success condition
if( left->data == newRight->data) return newRight->Next;
return null;
}``````

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

``````// Handling Odd/Even length pallindrom
}

Node IsPallindrom(Node left,Node right)
{
// Boundary condition
if(left == null || right == null) return null;

// Terminating condition
// Recurring condition
var newRight = null;
if(right->next == null)
newRight = left->Next;
else if(right->next->Next == null)
newRight = left->Next->Next;
else  {
newRight = IsPallindrom(left->Next, right->Next->Next);
}
// Fail condition
if(newRight == null ) return null;

// Success condition
if( left->data == newRight->data) return newRight->Next;
return null;
}``````

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

``````#include <iostream>

using namespace std;

{
LinkList(char ch) : mCh(ch), mpNext(NULL) {}
char mCh;
};

{
int count = 0;
while((p1 && p2) && (p1->mCh == p2->mCh))
{
count++;
p1 = p1->mpNext;
p2 = p2->mpNext;
}
return count;
}

{
{
return 0;
}

int count = 0;
while(p1)
{
p1->mpNext = pPrev;
count = max(count, max(Count(p1, p2) * 2 ,
Count(p1->mpNext, p2) * 2 + 1));
pPrev = p1;
p1 = p2;
}

p1 = pPrev;
pPrev = NULL;
while(p1)
{
p1->mpNext = pPrev;
pPrev = p1;
p1 = p2;
}

return count;
}

int main()
{
string sample = "12121213";

for(int i = 0; i < sample.size(); ++i)
{
if(pCur != NULL)
{
pCur->mpNext = pTemp;
}
else
{
}
pCur = pTemp;
}

return 0;
}``````

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

The idea could be similar to the idea of finding longest palindrome of an array. First we look at palindromes of odd length and pick each character as the middle character and start expand to both left and right until the word is palindrome. Note it is O(n^2) algorithm so it is best we can do (I dont take manacher algorithm into account).

Similar idea can be applied to lists but here we need to as we change our middle elements also change next pointer to point to the previous item (so basically at the end of algorithm the whole list will be reversed).

After that we do the same thing for even length lists.

Time complexity: O(n^2)

Space complexity: O(1)

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

Am I missing something here? I think the point of this problem is the O(1) storage, which means you are not supposed to store the items of the linked list.

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

``````def max_palindrome(head):
num_eq = 0

while n1 and n2:
if n1.value != n2.value:
break

n1 = n1.next
n2 = n2.next

num_eq += 2

return num_eq

return 1

prev_node = None
max_p = 1

while cur_node:
next_node = cur_node.next
cur_node.next = prev_node

if next_node:

prev_node = cur_node
cur_node = next_node

return max_p``````

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

This is to use technique of splitting/merging the linked list into two and again to one. Directly operate on the linked list rather than copying any of them.

Test

``````void TestLinkedListLongestPalindrome()
{
{
assert(r.len == 0);
assert(r.startPtr == nullptr);
}
{
LL_PushFront(&inputLL, 'A');
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
LL_PushFront(&inputLL, 'B');
LL_PushFront(&inputLL, 'A');
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("ABCDEFGHIJKLMN");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("AAAAAAAAAAAAAAAAAAAAA");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == input);
}
{
const std::string input("ABABCDEFGFEDCBAXY");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("ABABCDEFGFEDCBAXYZUVWXYZ");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("UVWXYZABABCDEFGFEDCBAXYZ");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("AB01234567899876543210XY");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("asfdasdfasAB01234567899876543210XY");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210XYkljfkajsdkfasd");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210ABCDDCBAxyx");
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}

std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
}``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{

string theResult = "";
int longest = 0;

foreach (string item in myList)
{
Char[] tmp = item.ToLower().ToCharArray();
Array.Reverse(tmp);
string backwards = new string(tmp);

if (backwards == item.ToLower())
{
if (item.Length > longest)
{

theResult = item;
longest = item.Length;

}
}

}

Console.WriteLine(theResult);

}
}
}``````

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

This was my shot at it...

``````class Node(object):
def __init__(self, val, next=None):
self._val = val
self._next = next

maxPal = []
while listItr:
revList = reverseList(listItr)
currentPal = checkPal(listItr, revList)
if len(currentPal) > len(maxPal):
maxPal = currentPal
listItr = listItr._next
return maxPal

currentPal = []
while (itr1 and itr2) and itr1._val != itr2._val:
itr2 = itr2._next
while (itr1 and itr2) and itr1._val == itr2._val:
currentPal.append(itr1._val)
itr1 = itr1._next
itr2 = itr2._next
return currentPal

if __name__ == '__main__':
head = Node(1, Node(2, Node(3, Node(2, Node(5, Node(7))))))

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

One could come up with a O(n²)-algorithm with O(1) space complexity as follows:

Consider f→o→b→a→r→r→a→b:

set x.next = null

f o→b→a→r→r→a→b
^ ^
| \
x y

and check for how many links both lists (x and y) are equal.
Now continue. (tmp=y.next, y.next=x, x=y, y=tmp) E.g. in the second step, it will yield f←o b→a→r→r→a→b, with x=o and y=b, now you check again if it's a palindrome and continue:
f←o←b a→r→r→a→b
f←o←b←a r→r→a→b
f←o←b←a←r r→a→b
etc.

If you need to restore the list again, reverse it again in O(n)

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

copy paste from stackoverflow

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

This is not correct enough, since it does not consider a case when a palindrome is formed with an odd number of nodes.

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

One could come up with a O(n²)-algorithm with O(1) space complexity as follows:

Consider f→o→b→a→r→r→a→b:

set x.next = null

f o→b→a→r→r→a→b
^ ^
| \
x y

and check for how many links both lists (x and y) are equal.
Now continue. (tmp=y.next, y.next=x, x=y, y=tmp) E.g. in the second step, it will yield f←o b→a→r→r→a→b, with x=o and y=b, now you check again if it's a palindrome and continue:
f←o←b a→r→r→a→b
f←o←b←a r→r→a→b
f←o←b←a←r r→a→b
etc.

If you need to restore the list again, reverse it again in O(n)

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

O(1) algorithm for this case. Space performance doesn't vary with input.

``````package com.largestpalindromeinlist;

public class Node {

Node next;
String data;

public static boolean isPallindrome(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
}
public static String getLargestPallindrome(Node root) {
String largestPallindrome = "";
while (root!= null) {
if(isPallindrome(root.data) && root.data.length()>largestPallindrome.length()){
largestPallindrome=root.data;
}
root=root.next;
}
return largestPallindrome;
}
}``````

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.