Microsoft Interview Question
SDE-2sCountry: United States
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 max_palindrome(ListNode *head)
{
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()
{
auto head = new ListNode({.data = 1}), p = head;
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;
}
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).
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).
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.
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.
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.
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.
Considering "madam", in a list as "amadamosel".
here "ama","ada","madam" are the palindromes, only Madam is the answer.
bool IsPallindrom(Node head){
return head != null && IsPallindrom(head,head->next) != null;
}
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;
}
// Handling Odd/Even length pallindrom
bool IsPallindrom(Node head){
return head != null && IsPallindrom(head,head->next) != null;
}
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;
}
#include <iostream>
using namespace std;
struct LinkList
{
LinkList(char ch) : mCh(ch), mpNext(NULL) {}
char mCh;
LinkList *mpNext;
};
int Count(LinkList *p1, LinkList *p2)
{
int count = 0;
while((p1 && p2) && (p1->mCh == p2->mCh))
{
count++;
p1 = p1->mpNext;
p2 = p2->mpNext;
}
return count;
}
int GetMaxPalindrome(LinkList *pHead)
{
if(pHead == NULL)
{
return 0;
}
int count = 0;
LinkList *p1 = pHead;
LinkList *pPrev = NULL;
while(p1)
{
LinkList *p2 = p1->mpNext;
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)
{
LinkList *p2 = p1->mpNext;
p1->mpNext = pPrev;
pPrev = p1;
p1 = p2;
}
return count;
}
int main()
{
string sample = "12121213";
LinkList *pHead = NULL;
LinkList *pCur = NULL;
for(int i = 0; i < sample.size(); ++i)
{
LinkList *pTemp = new LinkList(sample[i]);
if(pCur != NULL)
{
pCur->mpNext = pTemp;
}
else
{
pHead = pTemp;
}
pCur = pTemp;
}
cout << GetMaxPalindrome(pHead);
return 0;
}
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)
def max_palindrome(head):
def compare_linked_lists(n1, n2):
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
if not head.next:
return 1
cur_node = head
prev_node = None
max_p = 1
while cur_node:
next_node = cur_node.next
cur_node.next = prev_node
if next_node:
max_p = max(max_p, compare_linked_lists(cur_node, next_node),
compare_linked_lists(cur_node, next_node.next) + 1)
prev_node = cur_node
cur_node = next_node
return max_p
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.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/linkedlist-find-longest-palindrome.html
Test
void TestLinkedListLongestPalindrome()
{
using Result = LinkedListLongestPalindrome<char>::LL_PalindromeResult;
{
LinkedListElement<char> *inputLL = nullptr;
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 0);
assert(r.startPtr == nullptr);
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'B');
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("ABCDEFGHIJKLMN");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("AAAAAAAAAAAAAAAAAAAAA");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
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");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
LinkedList<string> myList = new LinkedList<string>();
myList.AddLast("mom");
myList.AddLast("dad");
myList.AddLast("microsoft");
myList.AddLast("Moooooooooooooom");
myList.AddLast("moooooooooooooor");
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);
Console.ReadKey();
}
}
}
This was my shot at it...
class Node(object):
def __init__(self, val, next=None):
self._val = val
self._next = next
def reverseList(head):
newHead = None
while head:
newHead = Node(head._val, newHead)
head = head._next
return newHead
def maxPallindrom(head):
maxPal = []
listItr = head
revListItr = head
while listItr:
revList = reverseList(listItr)
currentPal = checkPal(listItr, revList)
if len(currentPal) > len(maxPal):
maxPal = currentPal
listItr = listItr._next
return maxPal
def checkPal(head1, head2):
currentPal = []
itr1 = head1
itr2 = head2
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))))))
print maxPallindrom(head)
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:
Walk through the list reversing the links while visiting. Start with x=f and y=f.next:
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)
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:
Walk through the list reversing the links while visiting. Start with x=f and y=f.next:
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)
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;
}
}
- palindromeemordnilap December 06, 2015