Amazon Interview

Reversing a Singly Linked List

Introduction Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory. The Idea behind Reversing a Singly Linked List The idea is to iterate through the complete linked list and maintain three pointers as listed below: Pointer to the head of un reversed list headOfUnReversedLL. Pointer to the head of reversed list headOfReversedLL. Pointer to the node to be reversed nodeToReverse. In each iteration we follow the below four steps: The h...
Read More

Find Pair of Numbers in Array with a Given Sum

Problem Definition This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few: Find Pair of Numbers in Array with a Given Sum - The array is unsorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array is sorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array contains unique numbers only. In all the above versions, we have to return the ...
Read More

Spiral Traversal

Spiral Traversal or Zigzag Traversal in a Tree. This is the fourth article in the Tree Traversals - Online Classes. Recently I wrote an article on Level Order Tree Traversal. Another problem on the same lines is to traverse the tree in a zigzag manner. That is also termed as spiral traversal. This question has been asked in many companies during the interview process. Although it is not very specific problem, if you understand the idea behind traversing a tree in breadth first manner, then you can easily solve this. Please read further for more understanding. Defining the problem L...
Read More