Amazon Interview Question Software Engineer / Developers
Team: Chennei
Country: United States
Interview Type: Phone Interview
int length = chkString.Length;
chkString = chkString.ToLower();
if (length%2 == 0)
{
if (chkString[length/2-1] != chkString[length/2])
return false;
}
for (int i=0; i < length/2; i++)
{
if (chkString[i] != chkString[length - i-1])
return false;
}
return true;
You cannot reverse the linked list, since this implies that you either alter the list, or you use variable extra space O(N), both not allowed.
Assuming that reversing in place were allowed, this would take O(N^2) time, not O(N), since the list is single-linked.
bool isPalindrome(SingleLinkList *node)
{
int count; // count the number of elements in the List
count = 0;
head = node;
while (head != null)
{
count++; head = head.next;
}
if (count ==0) return true; // Assume that empty list is a palindrome
left_index = 1;
right_index = count;
left_node = node;
while (left_index < right_index)
{
i = left_index;
right_node = left_node;
while (i < right_index)
{
right_node = right_node.next;
i++;
}
if (left_node.val != right_node.val)
return false;
left_node = left_node.next;
left_index++;
right_index--;
}
return true;
}
Analyze:
- Count the number of elements in the List.
- Keep left_index and right_index to check whether the List is a palindrome. Initialize left_index = 1 (the 1st element in the List) and right_index = the number of elements in the list or the last element in the list.
- In each iteration, increase left_index by one, and decrease right_index by one until left_index >= right_index.
This algorithm uses space O(1).
public boolean checkPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
int c = 0;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
c++;
}
if (c == 0) {
return true;
}
if (fast != null) {
slow = slow.next;
}
ListNode[] ref = new ListNode[1];
ref[0] = slow;
return checkPalindrome(head, c, ref);
}
private boolean checkPalindrome(ListNode head, int c, ListNode[] ref) {
if (c == 1) {
return head.val == ref[0].val;
}
if (!checkPalindrome(head.next, c--, ref)) {
return false;
}
ref[0] = ref[0].next;
return head.val == ref[0].val;
}
Well, the question doesn't clearly explain the restriction "Constant Space". Your solution does not use a Space(N) auxiliary data structure, but it uses the call stack (N/2). My understanding is that if the interviewer meant by "constant space" no extra space that is proportional to N considering the call stack, then this solution would need some tweaks. Otherwise, it looks good.
If the extra space on the call stack is allowed, one can, for each node at position K up to the half of the list (watch out for odd lengths), find the node at position Length - K and compare them. This is O(N^2), but uses no extra space.
type Node struct {
value string
next *Node
}
func (n *Node) Next() *Node {
return n.next
}
func (n *Node) Value() string {
return n.value
}
func NewLinkedList(s string) *Node {
if len(s) == 0 {
return nil
}
headNode := &Node{string(s[0]), nil}
currentNode := headNode
for _, v := range s[1:] {
newNode := &Node{string(v), nil}
currentNode.next = newNode
currentNode = newNode
}
return headNode
}
func PrintLinkedList(linkedList *Node) {
for linkedList != nil {
fmt.Println(linkedList)
linkedList = linkedList.Next()
}
}
func IsPalidrome(linkedList *Node) bool {
startPalidrome, endPalidrome := linkedList, linkedList
for endPalidrome.Next() != nil {
endPalidrome = endPalidrome.Next()
}
for startPalidrome != endPalidrome {
//fmt.Println(startPalidrome, endPalidrome)
if startPalidrome.Value() != endPalidrome.Value() {
return false
}
if startPalidrome.Next() == endPalidrome {
return true
}
startPalidrome = startPalidrome.Next()
middlePalidrome := startPalidrome
for middlePalidrome.Next() != endPalidrome {
middlePalidrome = middlePalidrome.Next()
}
endPalidrome = middlePalidrome
}
return true
}
func main() {
fmt.Println(IsPalidrome(NewLinkedList("ttoott")))
fmt.Println(IsPalidrome(NewLinkedList("ttott")))
fmt.Println(IsPalidrome(NewLinkedList("hello")))
fmt.Println(IsPalidrome(NewLinkedList("ttto")))
fmt.Println(IsPalidrome(NewLinkedList("tt")))
fmt.Println(IsPalidrome(NewLinkedList("t")))
fmt.Println(IsPalidrome(NewLinkedList("tto3tt")))
package main
import "fmt"
type Node struct {
value string
next *Node
}
func (n *Node) Next() *Node {
return n.next
}
func (n *Node) Value() string {
return n.value
}
func NewLinkedList(s string) *Node {
if len(s) == 0 {
return nil
}
headNode := &Node{string(s[0]), nil}
currentNode := headNode
for _, v := range s[1:] {
newNode := &Node{string(v), nil}
currentNode.next = newNode
currentNode = newNode
}
return headNode
}
func PrintLinkedList(linkedList *Node) {
for linkedList != nil {
fmt.Println(linkedList)
linkedList = linkedList.Next()
}
}
func IsPalidrome(linkedList *Node) bool {
startPalidrome, endPalidrome := linkedList, linkedList
for endPalidrome.Next() != nil {
endPalidrome = endPalidrome.Next()
}
for startPalidrome != endPalidrome {
//fmt.Println(startPalidrome, endPalidrome)
if startPalidrome.Value() != endPalidrome.Value() {
return false
}
if startPalidrome.Next() == endPalidrome {
return true
}
startPalidrome = startPalidrome.Next()
middlePalidrome := startPalidrome
for middlePalidrome.Next() != endPalidrome {
middlePalidrome = middlePalidrome.Next()
}
endPalidrome = middlePalidrome
}
return true
}
func main() {
fmt.Println(IsPalidrome(NewLinkedList("ttoott")))
fmt.Println(IsPalidrome(NewLinkedList("ttott")))
fmt.Println(IsPalidrome(NewLinkedList("hello")))
fmt.Println(IsPalidrome(NewLinkedList("ttto")))
fmt.Println(IsPalidrome(NewLinkedList("tt")))
fmt.Println(IsPalidrome(NewLinkedList("t")))
fmt.Println(IsPalidrome(NewLinkedList("tto3tt")))
}
/**
* null and single element lists are palindromes
*/
public static boolean isPalindrome(Node head) {
return null == head || null == head.next || null != getPaldindromicNode(head, head);
}
/**
* Recurses down to find the tail then tests palindrome on the way back up.
* @return null if not a palindrome, else returns next (downward) node to
* test against next (upward) node.
*/
private static Node getPaldindromicNode(Node head, Node node) {
Node pal;
if(null == node.next) {
pal = head; // found the tail, head back up
}
else {
pal = getPaldindromicNode(head, node.next);
}
// we could stop comparing data if(pal == node || pal.next == node),
// but we still have to finish unwinding so what's the point?
if(null != pal && pal.data == node.data) {
if(head == node) {
return head; // finished unwinding
}
else {
return pal.next;
}
}
return null;
}
I did it here with an array, can be easily replaced array with singly linked list. I am using recursion.
public static void main (String [] args) {
char[] carr = new char [] {'s', 'a', 'n', 'd', 'n', 'a', 's'};
System.out.println(isPali(carr, carr[0], 0, true));
}
static boolean isPali (char [] carr, char c, int index, boolean result) {
index ++;
char curChar = c;
if(carr.length / 2 > index) {
result = isPali(carr, carr[index], index, result);
}
System.out.println(curChar + " : " + carr[carr.length - index] + " --> false" + index);
if(result == false) { return result; }
else {
if(curChar != carr[carr.length - index]) {
return false;
} else {
return true;
}
}
}
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
This solution has algorithm complexity of O(N ) and space complexity of O(1). The complete code, test and explanation please refer to: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-linkedlist.html
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;
}
Who told that the input list is allowed for changes, like "reverse second part"? Apparently it can be reversed back, but what if the collection is read-only? What if it is not thread-safe?
When we save place, we have to sacrifice performance and vice-versa. We can apply one optimization though: search chars in the right half from the middle instead of "left" or 0. C# version.
class SingleLinkedList
{
public SingleLinkedList(char item)
{
Item = item;
}
public SingleLinkedList(string data)
{
this.Item = data[0];
SingleLinkedList current = this;
for (int i = 1; i < data.Length; i++)
{
current.Next = new SingleLinkedList(data[i]);
current = current.Next;
}
}
public SingleLinkedList Next { get; private set; }
public char Item { get; private set; }
public override string ToString()
{
StringBuilder sb = new StringBuilder();
var current = this;
while (current != null)
{
sb.Append(current.Item);
current = current.Next;
}
return sb.ToString();
}
}
static SingleLinkedList GetItem(SingleLinkedList head, int index)
{
int i = 0;
while (head != null && i < index)
{
i++;
head = head.Next;
}
return head;
}
static int GetSize(SingleLinkedList list)
{
int count = 0;
while (list != null)
{
list = list.Next;
count++;
}
return count;
}
static bool isPalindrome(SingleLinkedList list)
{
SingleLinkedList head = list;
SingleLinkedList current = list;
int count = GetSize(list);
int count2 = count >> 1;
SingleLinkedList head2 = GetItem(head, count2 + count % 2);
for (int i = 0; i < count2; i++)
{
if (current.Item != GetItem(head2, count2 - i - 1).Item)
return false;
current = current.Next;
}
return true;
}
static void Main(string[] args)
{
SingleLinkedList word = new SingleLinkedList("polyPaAggAaPylop");
Console.WriteLine("IsPalindrome? " + word + ": " +isPalindrome(word));
Console.ReadKey();
}
Assume you have a SinglyLinkedList that keeps track of its size and has the insert and delete methods in O(N) time.
I implemented the following methods (get and isPalindrome) to retrieve whether it is palindrome or not. In constant time I figured there should be no other way to achieve this other than using a O(N^2) time. That's the trade off...
/**
* Interviewer asked for Constant space so no auxiliar linked list could be used!
*
* Only way to do this in constant space is using O(N^2) time.
*
* */
public boolean isPalindrome() {
Node curr = head;
for(int i = 0; i < size; i++) {
if( curr.getData() != get(size - 1 - i).getData() )
return false;
curr = curr.getNext();
}
return true;
}
public Node get(int index) {
if(size == 0)
return null;
if(index > size)
return null;
int count = 0;
Node current = head;
while(current != null) {
if(count == index)
return current;
current = current.getNext();
count++;
}
return null;
}
This could be solved in O(N) order as follows:
Find the mid node of the list - O(N).
Reverse the list starting from mid to end - O(N).
Now compare the sub lists(list 1: from Begin to Mid, List 2: from Mid to End) - O(N).
If these sublists are equal then its a palindrome else not.
Overall complexity is still O(N).
class Node {
char c;
public:
Node()
{
c = 0;
next = NULL;
}
Node *next;
Node(char ch)
{
c = ch;
next = NULL;
}
bool operator != (Node& n)
{
return (c != n.c);
}
};
Node* getNthNode(Node *current, int offset)
{
while ((offset > 0) && (current))
{
--offset;
current = current->next;
}
return current;
}
bool isPalindrome(Node *first) {
Node *forwardCompare = first, *reverseCompare, *last;
int i = 1, stringLength;
if (NULL == first)
return false;
while (forwardCompare->next)
{
forwardCompare = forwardCompare->next;
i++;
}
stringLength = i;
reverseCompare = last = forwardCompare;
forwardCompare->next = first; // create circular linked-list.
forwardCompare = first;
bool isNotPalindrome = false;
for (i = 0; i < (stringLength / 2); ++i)
{
if (*forwardCompare != *reverseCompare)
{
isNotPalindrome = true;
break;
}
forwardCompare = forwardCompare->next;
reverseCompare = getNthNode(reverseCompare, stringLength - 1); // Simulate backward traversal
}
last->next = NULL;
return !isNotPalindrome;
}
int main()
{
Node singlyString[] = { 'a', 's', 'd' };
const int nChars = (sizeof(singlyString) / sizeof(Node));
for (int i = 0; i < (nChars - 1); ++i)
singlyString[i].next = &singlyString[i + 1];
cout << ((isPalindrome(singlyString)) ? "true" : "false");
}
class Node {
char c;
public:
Node()
{
c = 0;
next = NULL;
}
Node *next;
Node(char ch)
{
c = ch;
next = NULL;
}
bool operator != (Node& n)
{
return (c != n.c);
}
};
Node* getNthNode(Node *current, int offset)
{
while ((offset > 0) && (current))
{
--offset;
current = current->next;
}
return current;
}
bool isPalindrome(Node *first) {
Node *forwardCompare = first, *reverseCompare, *last;
int i = 1, stringLength;
if (NULL == first)
return false;
while (forwardCompare->next)
{
forwardCompare = forwardCompare->next;
i++;
}
stringLength = i;
reverseCompare = last = forwardCompare;
forwardCompare->next = first; // create circular linked-list.
forwardCompare = first;
bool isNotPalindrome = false;
for (i = 0; i < (stringLength / 2); ++i)
{
if (*forwardCompare != *reverseCompare)
{
isNotPalindrome = true;
break;
}
forwardCompare = forwardCompare->next;
reverseCompare = getNthNode(reverseCompare, stringLength - 1); // Simulate backward traversal
}
last->next = NULL;
return !isNotPalindrome;
}
int main()
{
Node singlyString[] = { 'a', 's', 'd' };
const int nChars = (sizeof(singlyString) / sizeof(Node));
for (int i = 0; i < (nChars - 1); ++i)
singlyString[i].next = &singlyString[i + 1];
cout << ((isPalindrome(singlyString)) ? "true" : "false");
}
public static boolean iPalindrome(String s) {
int n = s.length();
for (int i = 0; i < (n / 2) + 1; ++i) {
if (s.charAt(i) != s.charAt(n - i - 1)) {
return false;
}
}
return true;
}
It's actually important to note that the input is a linked list, I think the question was asked. "Write a function to test if a singularly linked list is a palindrome using constant space."
The strategy for this is as follows:
1) Create a stack which to hold 1/2 of the first linked list.
2) Create two nodes, one is going 2x as the first and once the faster node reaches end. The slower node should be exactly at middle.
3) Collect the nodes in a stack until the faster node reaches the end.
4) Start popping the stack and match it against the values in the rest of the nodes.
public static boolean isPalindrome(CharNode root) {
// trivial case
if (root == null)
return false;
Stack<CharNode> stack = new Stack<>();
CharNode end = root.next;
CharNode mid = root;
while (true) {
stack.add(mid);
mid = mid.next;
if (end == null) {
// eject the middle element
stack.pop();
break;
}
else if (end.next == null)
break;
end = end.next.next;
}
while (!stack.isEmpty() && mid != null) {
CharNode node = stack.pop();
if (mid.value != node.value)
return false;
mid = mid.next;
}
return mid == null && stack.isEmpty();
}
As you have attended as well it seems , So I just wanted to ask you.. how is the above implementation is correct if it is a constant space ?
You are consuming stack space isn't ?
Reverse second half of the linked list. Then take two pointers one at start and one at centre and check node one-by-one.
- Deepak Mittal October 12, 2014