This is an Amazon Interview Question for Software Engineer/Developers from careercup.
"Implement bool isPalindrome(SingleLinkList *node) in constant Space. "
2. Solution
This solution has O(N) algorithm complexity and O(1) space complexity. The idea is to divide the linked list into two halves. Reverse the second half and compare two halves if they match. If yes, then the list is a palindrome and otherwise not. Afterwards reverse the second half again and restore to the original linked list.
Pseudo-code:
1. Divide the linked list into two parts, as introduced in Section 3 of Linked List: Circle Detection. (1x pointer and 2x pointer, finally the first half will have either the same amount nodes as the second half or have one more.)
2. Reverse the second half
3. Compare the first half and the second half with the length of the second, because the first half may have one more element.
4. Reverse the second half again and restore to the original linked list
5. return the result of the comparison of Step 3
Complexity analysis:
The division and reverse need no or a couple/few temporary node pointer, based on the implementation of Linked List: Circle Detection and Linked List: Common API. The comparison of two linked list will be implemented in this solution and it does not need any extra space. Sot the space complexity is guaranteed to be O(1).
For the algorithm complexity, the division need to go through half of the linked list via 2x pointer, N/2. The reverse of the second half is done twice, N. And the comparison needs to go through the whole of the second list, N/2. In total N/2 + N + N/2 = 2*N, so it is O(N).
3. C++ Implementation
// Implementation
// ********************************************************************************
// LinkedListPalindromeDetector.h
#ifndef LINKED_LIST_PALINDROME_DETECTOR_H
#define LINKED_LIST_PALINDROME_DETECTOR_H
#pragma once
#include "LinkedListAlgo.h"
#include "LinkedListElement.h"
class LinkedListPalindromeDetector
{
public:
LinkedListPalindromeDetector() = default;
~LinkedListPalindromeDetector() = default;
LinkedListPalindromeDetector(
const LinkedListPalindromeDetector& other) = delete;
LinkedListPalindromeDetector(
const LinkedListPalindromeDetector&& other) = delete;
LinkedListPalindromeDetector& operator=(
const LinkedListPalindromeDetector& rhs) = delete;
LinkedListPalindromeDetector& operator=(
const LinkedListPalindromeDetector&& rhs) = delete;
template<typename T>
static bool IsPalindrome(LinkedListElement<T>* head)
{
if (head == nullptr) {
return false;
}
LinkedListElement<T>* slow = head;
LinkedListElement<T>* fast2x = head->next;
if (fast2x == nullptr) {
return true;
}
while (fast2x != nullptr) {
if (fast2x->next != nullptr) {
fast2x = fast2x->next->next;
slow = slow->next;
}
else {
break;
}
}
// split the LinkedList
LinkedListElement<T>* firstHalf = head;
LinkedListElement<T>* secondHalf = slow->next;
slow->next = nullptr;
// reverse the second half and compare with the first half
LL_Reverse(&secondHalf);
// firstHalf shoud have either the amount of elments as secondHalf
// or have one more element.
bool isPalindrome = LL_StartWith(firstHalf, secondHalf);
// recover to the original LinkedList
LL_Reverse(&secondHalf);
slow->next = secondHalf;
return isPalindrome;
}
};
#endif
// Two extra functions are added in LinkedListAlgo.h
// See more about this on Linked List: Common API
/*
* Refer to std::string compare
* Return 0: =
* 1: >
* -1: <
*/
template<typename T>
int LL_Compare(LinkedListElement<T>* lhs, LinkedListElement<T>* rhs)
{
if (lhs == nullptr && rhs == nullptr) {
return true;
}
while (lhs != nullptr) {
if (rhs == nullptr) {
// lhs has more elements
return 1;
}
if (lhs->data > rhs->data) {
return 1;
}
else if (lhs->data < rhs->data) {
return -1;
}
// if the same, compare the next element
lhs = lhs->next;
rhs = rhs->next;
}
if (rhs == nullptr) {
// rhs has the same amount elements as lhs
// and so fare they are all equal
return 0;
}
// rhs has more elements
return -1;
}
template<typename T>
bool LL_StartWith(LinkedListElement<T>* source, LinkedListElement<T>* pattern)
{
if (source == nullptr && pattern == nullptr) {
return true;
}
while (source != nullptr) {
if (pattern == nullptr) {
// source has more elements
return true;
}
if (source->data != pattern->data) {
return false;
}
// if the same, compare the next element
source = source->next;
pattern = pattern->next;
}
// pattern has the same amount elements as source
// and so fare they are all equal, then return true
// pattern has more elements, return false
return pattern == nullptr;
}
// Test
// ********************************************************************************
void TestLinkedListPalindromeDetectorCase1()
{
LinkedListElement<char>* head = nullptr;
assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}
void TestLinkedListPalindromeDetectorCase2()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);
}
void TestLinkedListPalindromeDetectorCase3()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);
}
void TestLinkedListPalindromeDetectorCase4()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'B');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}
void TestLinkedListPalindromeDetectorCase5()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);
}
void TestLinkedListPalindromeDetectorCase6()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'F');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}
void TestLinkedListPalindromeDetectorCase7()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'F');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);
}
void TestLinkedListPalindromeDetectorCase8()
{
LinkedListElement<char>* head = nullptr;
LL_PushFront(&head, 'A');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'E');
LL_PushFront(&head, 'F');
LL_PushFront(&head, 'G');
LL_PushFront(&head, 'D');
LL_PushFront(&head, 'C');
LL_PushFront(&head, 'B');
LL_PushFront(&head, 'A');
assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}
//********************************************************************************
No comments:
Post a Comment