Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
1. find the middle node
2. reverse the first half linked list
3. starting from mid-node, traverse forward and backward to test palindrome
What if we have such structure: “aba” -> “cd” -> “ef” -> “ed” -> “ca” -> "ba" ? How to find the middle node?
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.
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
#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;
}
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);
}
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()
{
}
}
}
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;
}
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.
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.)
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
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
I think may be you can traverse once keep count of the length of the whole string.
- hkunited November 30, 2015Then 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.