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.

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

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

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

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

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.

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

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

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

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

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.

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

{
{
return false;
}

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 *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 *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)
{
}
else
{
pCur->mpNext = pNew;
}
pCur = pNew;
}

getchar();
return 0;
}``````

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.

Test

``````using LinkedListString = LinkedListElement<std::string>;
{
}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}

{

}``````

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

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

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 palindrome_string
{
class Program
{
static void Main(string[] args)
{
var item = list.next;
item = item.next;
item = item.next;
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;
}
backward.next = null;
int median = length / 2;
int i = 0;
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;
}
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;
}
{
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;
}
{
int length = 0;
while (list != null)
{
length++;
list = list.next;
}
return length;
}
}
{
public string data;
// constructors
{
data = input_data;
next = input_next;
}
{
data = input_data;
}
{

}
}
}``````

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  : ");
}
/**
* reverse the  second half
*/

Node<String> prev = null;
Node<String> nextNode = null;
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;
}``````

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.

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

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

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

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

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

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

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``````

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

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``````

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.

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.

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.