McAfee Interview Question
SDETsCountry: India
Interview Type: Written Test
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.
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;
}
SOLUTION-1:
Time Complexity = O(n)
Space Complexity = O(n)
Steps:
Code:
SOLUTION-2:
Time Complexity = O(n)
Space Complexity = O(1)
Steps:
Code:
- R@M3$H.N January 22, 2015