1. Problem Description
This is a a Microsoft interview question for software developer engineer from careercup. Here is the original thread,
"Given a singly connected linked list, find the largest palindrome in the list in O(1) space.
".
2. Algorithm
This is a more difficult question than Data Structure and Algorithm - Linked List: Palindrome and Data Structure and Algorithm - Linked List: Palindrome II, which require to use O(1) space to find out if a linked list is a palindrome. In order to achieve O(1) space the technique of splitting the linked list is still applicable for this question as well.
Pseudo-code:
- Initialize startPtr as nullptr - points to the starting node of palindrome
- Initialize len as the length of palindrome of 0
- Return empty startPtr and zero len, if linked list is empty
- Point startPtr to head and initialize len as 1
- Split the linked list as two equal parts and count the size
* If linked list has even number of nodes as S, then
> middleNode point to the (S/2)th node
> firstHalfCount as S/2 and totalCount as S
* If odd number of node(s), then
> middleNode points to (S/2+1)th node
> firstHalfCount as S/2+1 and totalCount as S
- Reverse the 1st half linked list and keep the 2nd half as firstHalfHead, secondHalfHead
- If potential maximal palindrome size is greater than len
(2*firstHalfCount + 1) > len, and firstHalfHead and secondHalfHead are valid, then
- Compare firstHalfHead and secondHalfHead until the first difference appearing
- The length is greater than len
> Point startPtr to the last node of firstHalfHead that have the same value in both
> Update len as the current length
- Compare firstHalfHead and secondHalfHead->next until the first difference appears
- If the length+1 is greater than len
> Point startPtr to the last node of firstHalfHead that have the same value in both
> Update len as the current length+1
- Update:
> firstHalfCount = firstHalfCount - 1;
> Push front the head of firstHalfHead to secondHalfHead
> Point firstHalfHead into its next
- Keep loop this step until any of the condition does not hold
- Recover the linked list
- Split the linked list into two again and count the size
- Reverse the 1st half and keep the 2nd half as firstHalfHead and secondHalfHead
- Assign secondHalfCount = totalCount - firstHalfCount
- If potential maximal palindrome size is greater than len,
(2*secondHalfCount + 1) > len, and firstHalfHead and secondHalfHead are valid, then
- Compare firstHalfHead and secondHalfHead until the first difference appearing
- If the length is greater than len
> Point startPtr to the last node of firstHalfHead that have the same value in both
> Update len as the current length
- Compare firstHalfHead->next with secondHalfHead until the first difference appears
- If the length+1 is greater than len
> Point startPtr to the last node of firstHalfHead that have the same value in both
> Update len as the current length+1
- Update:
> secondHalfCount = secondHalfCount - 1
> Push front the head of secondHalfHead to firstHalfHead
> Point secondHalfHead into its next
- Keep loop this step until any of the condition does not hold
- Recover the linked list
- Return startPtr and len
3. C++ Solution
// ********************************************************************************
// Implementation
// ********************************************************************************
#pragma once
#include "LinkedListAlgo.h"
#include "LinkedListElement.h"
#include <vector>
#include <cassert>
template<typename T>
class LinkedListLongestPalindrome
{
public:
LinkedListLongestPalindrome() = default;
LinkedListLongestPalindrome(LinkedListLongestPalindrome&) = delete;
LinkedListLongestPalindrome(LinkedListLongestPalindrome&&) = delete;
LinkedListLongestPalindrome& operator=(LinkedListLongestPalindrome&) = delete;
LinkedListLongestPalindrome& operator=(LinkedListLongestPalindrome&&) = delete;
~LinkedListLongestPalindrome() = default;
struct LL_PalindromeResult
{
LL_PalindromeResult()
: LL_PalindromeResult(nullptr, 0)
{}
LL_PalindromeResult(LinkedListElement<T> *ptr, size_t l)
: startPtr(ptr), len(l)
{
}
LL_PalindromeResult(LL_PalindromeResult&) = default;
~LL_PalindromeResult() = default;
LinkedListElement<T> *startPtr;
size_t len;
};
LL_PalindromeResult operator()(LinkedListElement<T>* head)
{
LL_PalindromeResult result;
if (head == nullptr) {
return result;
}
result = LL_PalindromeResult(head, 1);
if (head->next == nullptr) {
return result;
}
// find the middle node
LinkedListElement<T> *middleNode;
size_t firstHalfCount;
size_t totalCount;
SplitLinkedListIntoTwo(head, middleNode, firstHalfCount, totalCount);
// split the node
LinkedListElement<T> *firstHalf;
LinkedListElement<T> *secondHalf;
SplitAndReverseTheFirstHalf(head, middleNode, firstHalf, secondHalf);
// find the longest palindrome in the 1st run
LL_PalindromeResult tempResult = FindLongestPalindrome(firstHalf,
secondHalf,
result.len,
firstHalfCount,
false);
if (tempResult.len > result.len) {
result = tempResult;
}
// recover the linked list
RecoverFromSplitting(firstHalf, secondHalf);
assert(firstHalf == head);
// split the node again
SplitAndReverseTheFirstHalf(head, middleNode, firstHalf, secondHalf);
// find the longest palindrome in the 2nd run
tempResult = FindLongestPalindrome(firstHalf,
secondHalf,
result.len,
totalCount - firstHalfCount,
true);
if (tempResult.len > result.len) {
result = tempResult;
}
// recover the linked list
RecoverFromSplitting(firstHalf, secondHalf);
return result;
}
private:
LL_PalindromeResult FindLongestPalindrome(LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf,
size_t curMax,
size_t halfCount,
bool reversed)
{
LinkedListElement<T> *temp;
LL_PalindromeResult result(nullptr, curMax);
LL_PalindromeResult tempResult;
while ((halfCount * 2 + 1) > result.len && firstHalf != nullptr && secondHalf != nullptr) {
tempResult = GetCommon(firstHalf, secondHalf, reversed);
// track the longest palindrome
if (tempResult.len > result.len) {
result = tempResult;
}
// update the node and count for the next loop
if (reversed) {
temp = secondHalf->next;
secondHalf->next = firstHalf;
firstHalf = secondHalf;
secondHalf = temp;
}
else {
temp = firstHalf->next;
firstHalf->next = secondHalf;
secondHalf = firstHalf;
firstHalf = temp;
}
--halfCount;
}
return result;
}
LL_PalindromeResult GetCommon(LinkedListElement<T> *x,
LinkedListElement<T> *y,
bool reversed)
{
if (x == nullptr || y == nullptr) {
return LL_PalindromeResult();
}
// compare firstHalf with secondHalf
LL_PalindromeResult result1 = CompareCommon(x, y, 0);
// depends on which run
// - compare firstHalf->next with secondHalf
// - compare firstHalf with secondHalf->next
LL_PalindromeResult result2 = reversed ?
CompareCommon(x->next, y, 1) : CompareCommon(x, y->next, 1);
// return the longer palindrome
return result1.len > result2.len ? result1 : result2;
}
LL_PalindromeResult CompareCommon(LinkedListElement<T> *x,
LinkedListElement<T> *y,
size_t curLongestLen)
{
// compare two nodes until the first diverge appears
LL_PalindromeResult result(nullptr, curLongestLen);
while (x != nullptr && y != nullptr) {
if (x->data == y->data) {
result.len += 2;
result.startPtr = x;
x = x->next;
y = y->next;
}
else {
break;
}
}
return result;
}
void SplitLinkedListIntoTwo(LinkedListElement<T>* head,
LinkedListElement<T>* &middleNode,
size_t &firstHalfCount,
size_t &totalCount)
{
if (head == nullptr) {
middleNode = nullptr;
firstHalfCount = totalCount = 0;
return;
}
// a, b, c, d, e, f, g, h
// a, a
// b, c
// c, e
// d, g
// d, nullptr
// a, b, c, d, e, f, g, h, i
// a, a
// b, c
// c, e
// d, g
// e, i
// e, nullptr
LinkedListElement<T> *slowPtr = head;
{
LinkedListElement<T> *fasterX2 = head;
while (fasterX2 != nullptr) {
if (fasterX2->next != nullptr) {
++totalCount;
fasterX2 = fasterX2->next;
if (fasterX2->next != nullptr) {
++totalCount;
++firstHalfCount;
slowPtr = slowPtr->next;
}
}
fasterX2 = fasterX2->next;
}
}
middleNode = slowPtr;
}
void SplitAndReverseTheFirstHalf(LinkedListElement<T> *head,
LinkedListElement<T> *middleNode,
LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf)
{
if (middleNode == nullptr) {
firstHalf = secondHalf = nullptr;
return;
}
secondHalf = middleNode->next;
middleNode->next = nullptr;
firstHalf = head;
LL_Reverse(&firstHalf);
}
void RecoverFromSplitting(LinkedListElement<T>* &firstHalf,
LinkedListElement<T>* &secondHalf)
{
LinkedListElement<T>* temp;
if (firstHalf != nullptr) {
temp = firstHalf;
LL_Reverse(&firstHalf);
temp->next = secondHalf;
}
else {
firstHalf = secondHalf;
}
}
};
// ********************************************************************************
// Test
// ********************************************************************************
void TestLinkedListLongestPalindrome()
{
using Result = LinkedListLongestPalindrome<char>::LL_PalindromeResult;
{
LinkedListElement<char> *inputLL = nullptr;
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 0);
assert(r.startPtr == nullptr);
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
LinkedListElement<char> *inputLL = nullptr;
LL_PushFront(&inputLL, 'B');
LL_PushFront(&inputLL, 'A');
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("ABCDEFGHIJKLMN");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
assert(r.len == 1);
assert(r.startPtr->data == 'A');
}
{
const std::string input("AAAAAAAAAAAAAAAAAAAAA");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == input);
}
{
const std::string input("ABABCDEFGFEDCBAXY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("ABABCDEFGFEDCBAXYZUVWXYZ");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("UVWXYZABABCDEFGFEDCBAXYZ");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "ABCDEFGFEDCBA");
}
{
const std::string input("AB01234567899876543210XY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("asfdasdfasAB01234567899876543210XY");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210XYkljfkajsdkfasd");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
{
const std::string input("AB01234567899876543210ABCDDCBAxyx");
LinkedListElement<char> *inputLL = nullptr;
auto iterREnd = input.rend();
for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
LL_PushFront(&inputLL, *iterR);
}
Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
std::string palindrome;
while (r.len) {
palindrome.push_back(r.startPtr->data);
r.startPtr = r.startPtr->next;
--r.len;
}
assert(palindrome == "01234567899876543210");
}
}
No comments:
Post a Comment