## Amazon Interview Question for Software Engineer / Developers

Team: Chennei
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 4 vote

Reverse second half of the linked list. Then take two pointers one at start and one at centre and check node one-by-one.

Comment hidden because of low score. Click to expand.
0

yeah this should work in O(N) time and constant space.

Comment hidden because of low score. Click to expand.
0

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;

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Actually, you can reverse the list in O(N) time, I apologize.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````bool isPalindrome(SingleLinkList *node)
{
int count; // count the number of elements in the List
count = 0;
{
}
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).

Comment hidden because of low score. Click to expand.
0

Even though the code sucks, this is the only answers that approaches a right answer.

Comment hidden because of low score. Click to expand.
0

I think this is the only way to do it in constant space.

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public boolean checkPalindrome(ListNode 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;
}

private boolean checkPalindrome(ListNode head, int c, ListNode[] ref) {
if (c == 1) {
}
return false;
}
ref[0] = ref[0].next;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````type Node struct {
value string
next  *Node
}

func (n *Node) Next() *Node {
return n.next
}

func (n *Node) Value() string {
return n.value
}

if len(s) == 0 {
return nil
}

for _, v := range s[1:] {
newNode := &Node{string(v), nil}
currentNode.next = newNode
currentNode = newNode
}

}

}
}

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() {

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}

if len(s) == 0 {
return nil
}

for _, v := range s[1:] {
newNode := &Node{string(v), nil}
currentNode.next = newNode
currentNode = newNode
}

}

}
}

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() {

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* null and single element lists are palindromes
*/
public static boolean isPalindrome(Node 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) {
}
else {
}
// 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) {
}
else {
return pal.next;
}
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>
{
return false;
}

if (fast2x == nullptr) {
return true;
}

while (fast2x != nullptr) {
if (fast2x->next != nullptr) {
fast2x = fast2x->next->next;
slow = slow->next;
}
else {
break;
}
}

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
{
{
Item = item;
}
{
this.Item = data[0];
for (int i = 1; i < data.Length; 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();
}
}
{
int i = 0;
while (head != null && i < index)
{
i++;
}
}

{
int count = 0;
while (list != null)
{
list = list.Next;
count++;

}
return count;
}

{
int count = GetSize(list);
int count2 = count >> 1;
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)
{
Console.WriteLine("IsPalindrome? " + word + ": " +isPalindrome(word));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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() {

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;

while(current != null) {

if(count == index)
return current;

current = current.getNext();
count++;
}

return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 same - return TRUE
else return FALSE

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 the sub lists are same then its a palindrome else not

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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");
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````LOL !!
the question is for LinkedList not String``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean isPalindrome(String original){

int i = original.length()-1;
int j=0;
while(i > j){
if(original.charAt(i) != original.charAt(j)){
return false;
}
i--;
j++;
}
return true;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

bool isPalindrome(string s)
{
return equal(s.begin(),s.begin()+ s.size()/2, s.rbegin());
}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

``````bool isPalindrome(string s)
{
return equal(s.begin(),s.begin()+ s.size()/2, s.rbegin());
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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) {

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();
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 ?

Comment hidden because of low score. Click to expand.
1
of 1 vote

As mentioned in question it should be done in constant even though u are using extra space ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.