1. Problem Description
This is an Amazon Interview Question Inerns from careercup. Here is the original description of this thread.
"Write a code to find if a link list is palindrome . Linklist consists variable string at each node. for eg
a->bcd->ef->g->f->ed->c->ba
The above given linklist is palindrome and func shd return - True"
2. Solution
I have discussed one solution to detect palindrome in the data structure of linked list on Data Structure and Algorithm - Linked List: Palindrome, where has the data type of a single char and provides a solution of computation complexity of O(N) and space complexity of O(1). Comparing with this problem the difference is the data type (in this problem std::string) that contains varying number of chars.
The solution should be similar with with the one on Data Structure and Algorithm - Linked List: Palindrome, except the way to partition the linked list into two halves.
Here is the pseudo
- Traverse the list to find the total number of chars
- Traverse the list again to find the linked list node that contains the mid character
- Split the linked to two
*) The left half: from the head to the linked list node that has the mid character
*) The right half: the rest of the linked list
- Reverse the left half.
- Compare two lists if they are holding the same data and capture the result
- Reverse the left half
- combine the two lists together
- Return the result of comparison
The solution has computation complexity of O(N) and space complexity of O(1). Keep in mind that this solution should be working for the problem on Data Structure and Algorithm - Linked List: Palindrome as well only a bit of less efficiently to find the node to split into two halves.
3. C++ Implementation
Based on the implementation of Data Structure and Algorithm - Linked List: Palindrome, a template specialization function of type "std::string" is defined and implemented as the solution of this interview question.
// ********************************************************************************
// IMPLEMENTATION
// ********************************************************************************
class LinkedListPalindromeDetector
{
public:
// ......
template<typename T>
static bool IsPalindrome(LinkedListElement<T>* head)
{
// ......
}
//http://www.careercup.com/question?id=4826931360956416
template<>
static bool IsPalindrome(LinkedListElement<std::string>* head)
{
// 1. empty list
if (head == nullptr) {
return false;
}
using LinkedListString = LinkedListElement<std::string>*;
LinkedListString cur = head;
// 2. not empty list
size_t totalCharacters = 0;
while (cur != nullptr) {
totalCharacters += cur->data.size();
cur = cur->next;
}
cur = head;
LinkedListString prev = cur;
size_t numOfCharactersToPrev = 0;
size_t numOfCharactersToCur = 0;
auto oddNumOfCharacters = (totalCharacters & 1) > 0;
size_t halfSize = oddNumOfCharacters?
((totalCharacters >> 1) + 1) : (totalCharacters >> 1);
while (numOfCharactersToCur < halfSize) {
numOfCharactersToPrev = numOfCharactersToCur;
numOfCharactersToCur += cur->data.size();
prev = cur;
cur = cur->next;
}
// split the LinkedList
prev->next = nullptr;
auto leftHalf = head;
auto rightHalf = cur;
// reverse the 2nd half
LL_Reverse(&leftHalf);
std::string* leftStr = &(leftHalf->data);
leftHalf = leftHalf->next;
std::string* rightStr = leftStr;
size_t leftStrIndex = halfSize - numOfCharactersToPrev;
size_t rightStrIndex = leftStrIndex;
oddNumOfCharacters ? leftStrIndex -= 1 : leftStrIndex = leftStrIndex;
bool match = true;
do{
if (rightStrIndex >= rightStr->size()) {
if (rightHalf == nullptr) {
match = false;
break;
}
rightStr = &(rightHalf->data);
rightHalf = rightHalf->next;
rightStrIndex = 0;
}
if (leftStrIndex == 0) {
if (leftHalf == nullptr) {
match = false;
break;
}
leftStr = &(leftHalf->data);
leftHalf = leftHalf->next;
leftStrIndex = leftStr->size();
}
while (leftStrIndex > 0 && rightStrIndex < rightStr->size()) {
if ((*leftStr)[leftStrIndex - 1] != (*rightStr)[rightStrIndex]) {
match = false;
break;
}
--leftStrIndex;
++rightStrIndex;
}
if (!match) {
break;
}
} while (leftHalf != nullptr || rightHalf != nullptr);
// reverse first half
auto prevCopy = prev;
LL_Reverse(&prev);
// merge two halfs
prevCopy->next = cur;
return match;
}
};
#endif
// ********************************************************************************
// 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);
}
// ********************************************************************************
Nice post, more questions@ www.codeitt.com
ReplyDelete