## McAfee Interview Question for SDETs

Country: India
Interview Type: Written Test

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

SOLUTION-1:
Time Complexity = O(n)
Space Complexity = O(n)

Steps:

``````> Use 2 Pointers 'slow' and 'fast'
> As you traverse to the middle of List PUSH the 'slow' pointer's 'value' on to Stack.
> Once in Middle of List, then from there till the end of list, POP value from Stack and compare with 'slow' pointer 'value'.
> If everything matches then its Palindrome, else return false.``````

Code:

``````public boolean isPalindrome(ListNode root) {
Stack<Integer> stack = new Stack<Integer>();
ListNode slow = root;
ListNode fast = root;

while (fast != null && fast.next != null) {
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}

// odd number of elements
if (fast != null) {
slow = slow.next;
}

while (slow != null) {
int top = stack.pop();
if (slow.val != top) {
return false;
}
slow = slow.next;
}
return true;
}``````

SOLUTION-2:
Time Complexity = O(n)
Space Complexity = O(1)

Steps:

``````> Get the middle of the linked list by using the ‘slow’ and ‘fast’ pointers.
> Reverse the second half of the linked list.
> Check if the first half and second half are identical. Else return false.``````

Code:

``````public boolean isPalindrome(ListNode root) {
ListNode slow = root;
ListNode fast = root;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// odd number of elements
if (fast != null) {
slow = slow.next;
}

//Reverse the Second half of list
slow.next = Reverse(slow.next) ;
slow = slow.next ;

fast = root ;
while (slow != null) {
if (slow.val != fast.val) {
return false;
}
slow = slow.next;
fast = fast.next ;
}
return true;
}``````

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

solution 2, are you reversing slow.next in place? If it is not in place, it is not O(1) space; if it is, you need to reverse it back to original, since you should not alter the input.

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

@akiremi - Agree... Missed that part.

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

i think for your first code, the comment should be // even number of elements instead of odd

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

``````public boolean isPalindrome() {
Node<T> current = this.front;
int length = 0;
while (current != null) {
current = current.next;
length++;
}

Stack<T> stack = new Stack<T>();
current = this.front;
for (int i = 0; i < length / 2; i++) {
stack.push(current.data);
current = current.next;
}

if (length % 2 == 1) {
current = current.next;
}
for (int i = 0; i < length / 2; i++) {
T temp = stack.pop();
if (temp.compareTo(current.data) != 0)
return false;
current = current.next;
}
return true;
}``````

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.