Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

I think may be you can traverse once keep count of the length of the whole string.
Then traverse the second time and reach the node where the center of the palindrome is.
Now traverse for the 3rd time till that node and strart reversing every connection now from that center node run from that node to left and right and keep checking if the character is the same.

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

1. find the middle node
2. reverse the first half linked list
3. starting from mid-node, traverse forward and backward to test palindrome

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

What if we have such structure: “aba” -> “cd” -> “ef” -> “ed” -> “ca” -> "ba" ? How to find the middle node?

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

zr.roman: In this case the middle node would be the one containing substring "ef".

When we first walk the linked list, total number of chars = 13.
Therefore the middle element of the substring = 13/2 + 1 i.e. at index = 7 which is the char 'f'

We walk the second time, reversing the LL till we reach the node with 7th element and work from there.

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

your solution will not work for list: “ad” -> “bbc” -> “cb” -> “bd” -> “a”.

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

1. find mid-node
2. reverse link of first half
3. from mid-node, traverse back/forward to test palindrome

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

Palindrome normally solved using stack...so maybe we can solve it using recursive function if allowed though stack frame would still consume space :)

1. Cal total length of string
2. Recursively move to next node till we encounter node that has center char of palindome
3. Process current node for palindrome substring and return remaining part of string of current node or next pointer to calling function

I am just simulating stack using recursive call though coding look little hard

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

1. Find length. (Let's call it n)
2. Do a hash for the first n/2 elements
3. Do a revers hash for the next n/2 elements
4. If they match then it's a palindrome.

The list it's not modified at all.

- save.the.w. December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

struct List
{
    List(const string &str) 
    : mStr(str), mpNext(NULL) {}
    string mStr;
    List *mpNext;
};
  
int GetListLen(List *pCur)
{
    int count = 0;
    while(pCur)
    {
        count += pCur->mStr.size();
        pCur = pCur->mpNext;
    }
    return count;
}
    
bool IsPalindrome(List *pHead)
{
    if(pHead == NULL)
    {
        return false;
    }
    
    int len = GetListLen(pHead);
    
    List *pCur = pHead;
    List *pPrev = NULL;
    
    for(int i = 0; i < len;)
    {
        List *pNext = pCur->mpNext;
        int newLen = i + pCur->mStr.size();
        if(newLen > (len / 2)) /* Start reversing the list after len/2 + 1 */
        {
            pCur->mpNext = pPrev;           
        }
        
        i = newLen;
        pPrev = pCur;
        pCur = pNext;
    }
    if(pPrev == NULL)
    {
        return false;
    }
    
    List *pLeft = pHead;
    List *pRight = pPrev;
    
    int leftIndex = 0;
    int rightIndex = pPrev->mStr.size() - 1;
      
    bool isPalin = true;
    for(int i = 1; i <= len / 2; ++i)
    {
        if(pLeft->mStr[leftIndex] != pRight->mStr[rightIndex])
        {
            isPalin = false;
            break;
        }
        leftIndex++;
        rightIndex--;
        
        if(leftIndex == pLeft->mStr.size())
        {
            pLeft = pLeft->mpNext;
            leftIndex = 0;
        }
        
        if(rightIndex == -1)
        {
            pRight = pRight->mpNext;
            rightIndex = pRight->mStr.size() - 1;
        }
    }
    return isPalin;
    
}

int main()
{
    List *pHead = NULL;
    List *pCur = NULL;
    string str[] = {"ab", "c", "de", "eee", "dcb", "a"};
    
    for(int i = 0; i < 6; ++i)
    {
        List *pNew = new List(str[i]);
        if(pCur == NULL)
        {
            pHead = pNew;
        }
        else
        {
            pCur->mpNext = pNew;
        }
        pCur = pNew;
    }
    
    cout << IsPalindrome(pHead) << endl;
    getchar();
    return 0;
}

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

Was an Amazon interview question. Splitting and merging the linked list to achieve this.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/01/data-structure-and-algorithm-linked.html

Test

using LinkedListString = LinkedListElement<std::string>;
void TestLinkedListPalindromWithStringCase1()
{
    LinkedListString* head = nullptr;
    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}

void TestLinkedListPalindromWithStringCase2()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("ABCDEFGFEDCBA"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase3()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("AABCDEFGFEDCBBD"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase4()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("ABCDEFFEDCBA"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase5()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("AABCDEFFEDCBAB"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase6()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("A"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase7()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("B"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}


void TestLinkedListPalindromWithStringCase8()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("A"));
    LL_PushFront(&head, std::string("A"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase9()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase10()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFGFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase11()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("zYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase12()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYz"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFGFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

- peter tang December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Splitting and merging won't help in the given question since we have been asked to solve the question in O(1) space complexity. Merging is space consuming operation and the amount of space consumed will depend on the length of the given linked list, thereby not making it O(1).

- AddyP January 07, 2016 | Flag
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;
using System.Threading.Tasks;

namespace palindrome_string
{
    class Program
    {
        static void Main(string[] args)
        {
            SinglyLinkedList list = new SinglyLinkedList("aba", new SinglyLinkedList("cd"));
            var item = list.next;
            item.next = new SinglyLinkedList("efe");
            item = item.next;
            item.next = new SinglyLinkedList("d");
            item = item.next;
            item.next = new SinglyLinkedList("caba");
            var length = GetListLength(list);
            var is_palindrom = ProcessList(list, length);
        }
        static bool ProcessList(SinglyLinkedList backward, int length)
        {
            bool is_palindrom = false;
            if (backward == null)
            {
                return false;
            }
            SinglyLinkedList forward = backward.next;
            backward.next = null;
            int median = length / 2;
            int i = 0;
            SinglyLinkedList temp;
            bool is_odd = false;
            // median is difrent for even and odd
            if (length % 2 == 0)
            {
                is_odd = false;
                median = length / 2 -1;
            }
            else
            {
                is_odd = true;
                median = length / 2;
            }
            // Get two singly linked list with forward link, and with reverse link
            while (i < median)
            {
                temp = backward;
                backward = forward;
                forward = forward.next;
                backward.next = temp;
                i++;
            }
            // In this method backward and forward will compare
            is_palindrom = CheckPalindrom(backward, forward, is_odd);

            return is_palindrom;
        }
        static bool CheckPalindrom(SinglyLinkedList back, SinglyLinkedList forw, bool is_odd)
        {
            string data_back = back.data;
            string data_forw = forw.data;
            int i = data_back.Length - 1;
            int j = 0;
            // If quantity of item in input data is odd, we have backward longer than forward.
            if (is_odd)
            {
                data_forw = data_back;
                for (int k = 0; k< data_back.Length;k++)
                {
                    int p = data_back.Length - k - 1;
                    if (data_back[k] != data_forw[p])
                    {
                        return false;
                    }
                }
                back = back.next;
                data_back = back.data;
                data_forw = forw.data;
                i = data_back.Length - 1;
            }
            // Compare backward and forward
            while (back != null && forw !=null)
            {
  
                while (i>=0 && j < data_forw.Length)
                {
                    if (data_back[i] != data_forw[j])
                    {
                        return false;
                    }
                    else
                    {
                        i--;
                        j++;
                    }
                }
                //  If current item of back sequence is ended, get next 
                if (i < 0 && back.next !=null)
                {
                    back = back.next;
                    if (back != null)
                    {
                        data_back = back.data;
                        i = data_back.Length - 1;
                    }
                }
                // If current item of forward sequence is ended, get next
                if (j >= data_forw.Length )
                {
                    forw = forw.next;
                    if (forw != null)
                    {
                        data_forw = forw.data;
                        j = 0;
                    }
                }

            }
            return true;
        }
        static int GetListLength(SinglyLinkedList list)
        {
            int length = 0;
            while (list != null)
            {
                length++;
                list = list.next;
            }
            return length;
        }
    }
    class SinglyLinkedList
    {
        public string data;
        public SinglyLinkedList next;
        // constructors
        public SinglyLinkedList(string input_data, SinglyLinkedList input_next)
        {
            data = input_data;
            next = input_next;
        }
        public SinglyLinkedList(string input_data)
        {
            data = input_data;
        }
        public SinglyLinkedList()
        {

        }
    }
}

- Trushnikov.Ivan December 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean checkIfListIsPalindrome(Node<String> first){
		
	StringBuffer firstBuffer = new StringBuffer();
	StringBuffer secBuffer = new StringBuffer();
		Node<String> current = first;
		Node<String> faster = first;
		Node<String> dummy = null;
		while(faster!=null && faster.next!=null){
			dummy = faster.next;
			faster = faster.next.next;
			current = current.next;		
		}
		boolean flag = true;
		System.out.println(" ");
		String middle = current.nData;
		System.out.print(" Middle--->>> "+ current.nData);
		if(faster==null)
		System.out.println(" end is : even case "+ dummy.nData);
		else{
			System.out.println(" end is: odd case  "+ faster.nData);
		   flag = false;	
		}
		System.out.print(" First half  : ");
		Node<String> firstHead = first;
		while(firstHead.nData != current.next.nData){
			firstBuffer.append(firstHead.nData.trim());
			System.out.print(" "+ firstHead.nData);
			firstHead = firstHead.next;
		}
		/**
		 * reverse the  second half
		 */
		
		Node<String> prev = null;
		Node<String> nextNode = null;
		Node<String> newHead = current;
		current = newHead;
		while(current!=null){
		  nextNode = current.next;
		  current.next = prev;
		  prev = current;	
		  current = nextNode;	
		}
		while(current!=null){
			System.out.print(" "+ current.nData);
			secBuffer.append(new StringBuffer(current.nData).reverse().toString());
			current = current.next;
		}
		if(flag){
		secBuffer.append(new StringBuffer(middle).reverse());
		}
		/*
		 * 
		 * compare first and second half
		 */
		if(firstBuffer.toString().equals(secBuffer.toString()))
			return true;
		return false;
	}

- akkhil2012 January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
1. Make the given linked list circular by making the last node point to the head.
2. Iterate from the given head node back to itself. During the iteration, cumulatively concatenate the node values (i.e. strings) such that by the time the iterator returns back to the head node, the cumulated string is the reverse of the actual traversal.
3. In the second iteration, delete the nodes values (i.e. strings) in their order of occurrence from the reversed cumulated string (from step 2) if a match is found. Leave the cumulated string unaltered if a match ain't found.
4. By the time the iterator reaches the head node again, if the cumulated string (from step 2) is an empty string, then its a palindrome, else not.

- AddyP January 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:

1. Make the given linked list circular by making the last node point to the head.

2. Iterate from the given head node back to itself. During the iteration, cumulatively concatenate the node values (i.e. strings) such that by the time the iterator returns back to the head node, the cumulated string is the reverse of the actual traversal.

3. In the second iteration, delete the nodes values (i.e. strings) in their order of occurrence from the reversed cumulated string (from step 2) if a match is found. Leave the cumulated string unaltered if a match ain't found.

4. By the time the iterator reaches the head node again, if the cumulated string (from step 2) is an empty string, then its a palindrome, else not.

(The previous answer posted under the name of AddyP was posted by me only. Reposting it since I had posted the answer without logging in.)

- Aditya P January 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Adithya , could you explain with example, could not understand much what you mentioned

- Manu June 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Adithya , could you explain with example, could not understand much what you mentioned

- Manu June 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
	def __init__(self,value):
		self.value = value
		self.next = None
		
def is_pal_ll_str(head):
	current_node = head
	while current_node.next:
		next_node = current_node.next
		next_node.value = current_node.value + next_node.value
		current_node = next_node
		
	for i in range(len(current_node.value)/2, 0 ,-1):
		if current_node.value[i-1] is current_node.value[len(current_node.value)-i]:
			print current_node.value[i-1], current_node.value[len(current_node.value)-i]
			continue
		else:
			return False
	return True

- montu September 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
	def __init__(self,value):
		self.value = value
		self.next = None
		
def is_pal_ll_str(head):
	current_node = head
	while current_node.next:
		next_node = current_node.next
		next_node.value = current_node.value + next_node.value
		current_node = next_node
		
	for i in range(len(current_node.value)/2, 0 ,-1):
		if current_node.value[i-1] is current_node.value[len(current_node.value)-i]:
			print current_node.value[i-1], current_node.value[len(current_node.value)-i]
			continue
		else:
			return False
	return True

- montu September 01, 2016 | 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