Amazon Interview Question
1. Implement a method that verifies if one string can be constructed by another. E.g: "aaabc" can be constructed by "aaabbbccd" 2. Given a linked list containing numbers (Node element), implement a method that returns two lists: one containing even numbers and one odd numbers - without allocating new list elements.
Interview Answers
Anonymous
void segregateEvenOdd() { Node end = head; Node prev = null; Node curr = head; /* Get pointer to last Node */ while (end.next != null) end = end.next; Node new_end = end; // Consider all odd nodes before getting first eve node while (curr.data %2 !=0 && curr != end) { new_end.next = curr; curr = curr.next; new_end.next.next = null; new_end = new_end.next; } // do following steps only if there is an even node if (curr.data %2 ==0) { head = curr; // now curr points to first even node while (curr != end) { if (curr.data % 2 == 0) { prev = curr; curr = curr.next; } else { /* Break the link between prev and curr*/ prev.next = curr.next; /* Make next of curr as null */ curr.next = null; /*Move curr to end */ new_end.next = curr; /*Make curr as new end of list */ new_end = curr; /*Update curr pointer */ curr = prev.next; } } } /* We have to set prev before executing rest of this code */ else prev = curr; if (new_end != end && end.data %2 != 0) { prev.next = end.next; end.next = null; new_end.next = end; } }