Amazon Interview Question Software Engineer / Developers
What about traverse the list twice? In first traverse, count how many 1's, 2's and 3's in the list, and in the second traverse, just sets nodes to 1 0r 2 or 3 in order according the their counts. It's O(n).
Definitely the dutch flag problem.
Something like this would sort the list inplace. O(n) complexity.
Where
pEnd = End of list
pIndex = pBeg = root
// Condition where the pointers surpass each other
while(pEnd->pNext != pIndex )
{
// putting 1's in the begining
if(pIndex->nData == 1 && pIndex != pBeg)
{
swap(pBeg->nData, pIndex->nData);
pBeg = pBeg->pNext;
}
// putting 3's at the end
else if (pIndex->nData == 3 && pIndex != pEnd)
{
swap(pEnd->nData, pIndex->nData);
pEnd = pEnd->pPrev;
}
else
pIndex = pIndex->pNext;
}
find the last index of 1 in the list from the beginning
find the last index of 3 in the list from the end
Then keep on traversing the list.
if 1 found, swap with the node next to last index of 1,
if 3 found, swap with node in front of last index of 3.
so at the end we get, all 1's in the front, all 3's at the end and all 2's in between.
no need to find any index of one or two or three. Simply head and tail solve the problem as follows:
0. save tail ptr (T) in another variable V.
traverse the list-
1. if node 1 then add to head dont increase head pointer until reach T
2. else if node 3 add to tail dont increase tail pointer to new node.
final list is sorted.
AJ,
I think there are only 3 nodes ( fixed ) in the linked list.
Always atleast 1 node will be at right place, and need to swap remaining 2.
Step 1:
find the right nodes to be swapped.
Step 2 - Swap:
simple trick is swap the values ( check if it is ok )
else, ask interviewer if it is single linked list / double linked list
and set the links appropriately.
"Always atleast 1 node will be at right place" - How can you explain further. What about the case where the order is 3 -> 1 -> 2.
I think it can be anything..its like a problem where we are to sort the array containing only three elements.1,2,3.
we will take three pointer.
start,mid and last pointer.
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;
while(mid <= hi)
{
switch(a[mid])
{
case 0:
swap(&a[lo++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[hi--]);
break;
}
}
}
for pointers it will look like
void SortList(struct node* head)
{
node* low = head;
node* mid = low;
node* hi = end(head);
while(mid != hi)
{
switch(mid->data)
{
case 1:
swap(low->data, mid->data);
low = low-next;
mid = mid->next;
break;
case 2:
mid = mid->next;
break;
case 3:
swap(mid->data, hi->data);
hi = hi->prev;
break;
}
}
1, 2 & 3 combination is another variant of dutch national flag problem where 0, 1 & 2 are given in unsorted order. We can achieve this in O(n) time complexity. No extra space is required.
void Sorting012sDutchFlagProblem(int A[], int n)
{
int i=0, pos0 =0, pos2=n-1;
while ( i < n )
{
if (A[i]==0)
{
A[i] = A[pos0];
A[pos0] = 0;
pos0++;
}
if (A[i]==2) && i < pos2)
{
A[i] = A[pos2];
A[pos2] = 2;
pos2--;
i--;
}
i++;
}
}
Time Complexity: O(n)
Space Complexity: O(1).
it evaluates level of node while moving in BFS order. For even levels it enters the item in a Stack and empties it when size of stack =2^level. For odd levels it simply prints in normal level order.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class LevelOrderPrint <T extends Comparable<T>> {
//BFS method
public static void BFS(BTreeNode root){
Queue<BTreeNode> queue = new LinkedList<BTreeNode>();
Stack<Integer > st =new Stack<Integer>();
if(root!=null)
queue.add((BTreeNode) root);
while(!queue.isEmpty()){
root=queue.remove();
if(root.mark==false)
{
root.mark=true;
if(root.level%2==0){
st.push(root.val);
if(st!=null&&st.size()==Math.pow(2,root.level)){
while(st.size()>0)
System.out.print(st.pop()+" ");
}
}
else
{System.out.print(root.val+" ");
}
}
if(root.left!=null)
{root.left.level=root.level+1;
queue.add(root.left);
}
if(root.right!=null)
{root.right.level=root.level+1;
queue.add(root.right);
}
}
public void sortList(){
Element current = root;
Element value3= new Element(0);
Element value1=new Element(0);;
Element value2= new Element(0);;
Element parent = null;
Element next = null;
while(current.next != null){
parent = current;
current = current.next;
next = current.next;
if(current.data == 3){
current.next=value3.next;
value3.next= current;
current.previous=value3;
if(current.next !=null){
current.next.previous=current;
}
if (value3.previous==null){
value3.previous=current;
}
parent.next=next;
if(next != null){
next.previous=parent;
}
current = parent;
}else
if(current.data == 2){
current.next=value2.next;
value2.next= current;
current.previous=value2;
if(current.next !=null){
current.next.previous=current;
}
if (value2.previous==null){
value2.previous=current;
}
parent.next=next;
if(next != null){
next.previous=parent;
}
current = parent;
}else
if(current.data == 1){
current.next=value1.next;
value1.next= current;
current.previous=value1;
if(current.next !=null){
current.next.previous=current;
}
if (value1.previous==null){
value1.previous=current;
}
parent.next=next;
if(next != null){
next.previous=parent;
}
current = parent;
}
}
if(value3.next != null){
value2.previous.next=value3.next;
value3.next.previous=value2.previous;
value1.previous.next=value2.next;
value2.next.previous=value1.previous;
root.next=value1.next;
value1.next.previous=root;
}
displayList();
}
Take 3 different pntrs, one, two, three. Traverse the list. If 1 is the value of the curent node, take the node out of the list and add it to the end of list represented by pntr "one", same for "two", "three". at the end u ll have 3 lists just point last ptr of "one" to "two" and of "two" to "three".
- Ishant May 22, 2011