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):
    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

- palindromeemordnilap December 06, 2015 | Flag Reply
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 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;
}

- shoumikhin November 30, 2015 | Flag Reply
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).

- damluar November 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- damluar November 30, 2015 | Flag
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.

- zr.roman December 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- shoumikhin December 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman December 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- vsounda1@binghamton.edu January 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can u please explain approach

- sameer November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- damluar November 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Shoumikhin can u please explain approach

- sameer November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ankushbindlish November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

// 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;
}

- ankushbindlish November 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- rishab99999 November 30, 2015 | Flag Reply
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)

- Nenad Banfic November 30, 2015 | Flag Reply
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.

- Hello December 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- palindromeemordnilap December 06, 2015 | Flag Reply
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.

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");
    }
}

- peter tang December 09, 2015 | Flag Reply
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)
        {
            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();
        }
    }
}

- Anonymous December 16, 2015 | Flag Reply
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                                                                                                                                                                                                                     
                                                                                                                                                                                                                                              
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)

- NK January 08, 2016 | Flag Reply
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:

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)

- vCillusion November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

copy paste from stackoverflow

- damluar November 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shoumikhin November 30, 2015 | Flag
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:

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)

- vCillusion November 30, 2015 | Flag Reply
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;
	}
}

- Akhil December 04, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More