Amazon Interview Question
Country: India
Interview Type: Written Test
I think there are numbers of '0' and '1' in each node of linked list...like 1001,1010, 1111011
all the solutions given here are assuming that only '0' and '1' are present as data of node. :P
if the node has 1001 or 1111011 then this is a value it represents a number... so whats the speciality?? do you think this is in the form of string "100010" like?
yaa it will represent a number...but in that case how your algorithm will work.?
your algo will work only in the case if node contains '0' or '1'(single digit).
it will not work for any number formed by combination of '0''s and '1''s
Very impressive algorithm .. Below is the working code for your algorithm
typedef struct node
{
int data;
struct node* prev;
struct node* next;
}Node;
void Sort(Node* doubleLinkedList)
{
int numberOfOnes=0;
while(doubleLinkedList->next!=NULL)
{
if(doubleLinkedList->data==1)
{
numberOfOnes++;
doubleLinkedList->data=0;
}
doubleLinkedList=doubleLinkedList->next;
}
if(doubleLinkedList->next==NULL&&doubleLinkedList->data==1)
numberOfOnes++;
while(numberOfOnes>0)
{
doubleLinkedList->data=1;
doubleLinkedList=doubleLinkedList->prev;
numberOfOnes--;
}
}
void insert(Node* n, int data)
{
Node* newNode=new Node();
newNode->data=data;
//travere to the end
for(;n->next!=NULL;n=n->next);
n->next=newNode;
newNode->prev=n;
newNode->next=NULL;
}
void print(Node* n)
{
printf("\n Printing the double linked list:");
while(n!=NULL)
{
printf("%d\t",n->data);
n=n->next;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Node* n=new Node();
n->prev=NULL;
n->next=NULL;
insert(n,1);
insert(n,0);
insert(n,1);
insert(n,0);
//save this n somewhere else too
Node* backup=n;
Sort(n);
print(backup);
int dummy;
scanf("%d",&dummy);
return 0;
}
below is just one pass algorithm:
i=0, j=n-1... start traversing both ends... if
i j
0 0 then increment i++
0 1 then increment i++ and j--
1 0 then swap a[i] & a[j] and i++, j--
1 1 then decrement j--...
do this until i<j
@algos: To get n, we need to do one pass. While coming back, (using j), we need to traverse back. So it is not really one pass. Please let me know if I have misunderstood your solution.
this is double linked list, so you will have tail pointer... to traverse tail to head use tail->prev... to traverse head to tail use head->next...
How will we have the tail pointer without traversing the list? It is a doubly linked list, not a circular doubly linked list. It will look something like this:
null-<-[1]-><-[2]-><-[3]->null
1 is the head, 3 is the tail. How do we get from head to tail without traversing?
@algos: Hate to nitpick - but you are assuming that the implementation of Insert gives you a tail pointer. That is not a correct assumption to make. That way, for a different problem, I might also have an implementation of a doubly linked list which has a pointer to the middle node, which might be helpful in some cases - but is hardly a reasonable expectation. I agree yours is a O(n) solution - all I'm saying is that it is not single pass as you have mentioned in your comment "below is just one pass algorithm:
i=0, j=n-1... start traversing both ends... if
i j"
As you traverse through the doubly linked list, separate out the nodes for 0 and 1 (maintain sublists). Finally, append the 1 sublist to the tail of the zero-sublist. Single traversal, constant space
// Sort a Doubly Linked List consisting of only 0 and 1
Node* GetSortedBinaryDLL(Node* pHead)
{
if ((nullptr == pHead) ||
(nullptr == pHead->next))
{
return pHead;
}
Node *pZerosHead = nullptr, *pZeroesTail = nullptr;
Node *pOnesHead = nullptr, *pOnesTail = nullptr;
Node *pCur = pHead;
while (nullptr != pCur)
{
Node *pNext = pCur->next;
pCur->next = nullptr;
pCur->prev = nullptr;
if (0 == pCur->val)
{
if (nullptr != pZeroesTail)
{
ASSERT(nullptr != pZerosHead);
pZeroesTail->next = pCur;
pCur->prev = pZeroesTail;
pZeroesTail = pCur;
}
else
{
ASSERT(nullptr == pZerosHead);
pZerosHead = pZeroesTail = pCur;
}
}
else
{
ASSERT(1 == pCur->val);
if (nullptr != pOnesTail)
{
ASSERT(nullptr != pOnesHead);
pOnesTail->next = pCur;
pCur->prev = pOnesTail;
pOnesTail = pCur;
}
else
{
ASSERT(nullptr == pOnesHead);
pOnesHead = pOnesTail = pCur;
}
}
pCur = pNext;
}
if (nullptr != pZerosHead)
{
pZeroesTail->next = pOnesHead;
if (nullptr != pOnesHead)
{
pOnesHead->prev = pZeroesTail;
}
return pZerosHead;
}
return pOnesHead;
}
If i count the number of 0s(say m) and number of 1s(say n) and then make last m nodes as 1 and remaining as 0s. That too solves my problem with O(N) time complexity
Minimum number of memory access with 0(n)
Put a pointer on head and one pointer in tail.
while ( head != tail ) {
If head == 0 then head go ahead. (increment)
else if tail == 1 then tail move to previous node. (decrement)
else if ( head == 1 && tail == 0 ) {
swap the values of head and tail
move head forward (increment)
if ( head == tail )
break ;
move tail to previous node (decrement)
}
}
I don't quite understand this question...but I'm thinking maybe we can traverse the list...when it see's a one it just remove from the list and add to tail...so eventually all the 1's will be at the end of the list. I'm not sure if we are allow to do this so please correct me if I'm wrong.
I agree with you but we don't have a tail pointer here. We can just keep accumulating 0s and 1s together since we have next and prev pointers.
For ex: 0,1,0,0,0,1,1,1,1,0,1,0,0,1,0,1,0
Found first 1 at pos = 1 (save its address in temp)
Keep traversing until you find next 1
Once you do change pointers such that the 1 found in the beginning is pulled from its original position and prepended to this next 1 found.
Such that: 0,0,0,0,1,1,1,1,1,0,1,0,0,1,0,1,0
Now we have the pointer to last 0 found (prev of first 1 in list)
and pointer to first 1
Keep changing links
O(n) - single traversal
Max n swaps
In single pass.
///
void SortList(TNode *node)
{
TNode *head = root;
TNode *Onode = NULL;
TNode *link = NULL;
while(head != NULL)
{
TNode *node=head;
if ( head->next == NULL)
link=head;
head=head->next;
if (node->value == 1)
{
if (node->prev != NULL)
node->prev->next= node->next;
if (node->next != NULL)
node->next->prev= node->prev;
if (onode == NULL)
{
onode = node;
node->next = null;
node->prev = null;
}
else
{
node->next = onode;
node->prev = NULL;
onode->prev = node;
onode=node;
}
}
else if ( node-> value != 0
{
ASSERT;
}
}
if (onode != NULL && link != NULL)
{
link->next=onode;
onode->prev=link;
}
}
///
No additional memory allocation besides linked list, and O(n) running time. There's no need here to swap the references, only the values, since the Nodes hold only an int(value exchange is cheap in this circumstance)...
static class Node {
Node left;
int bit;
public Node(int bit, Node left) {
this.bit = bit;
this.left = left;
}
public Node(int bit) {
this.bit = bit;
}
public String toString() {
return bit + "";
}
}
static void swap(Node a, Node b) {
a.bit = a.bit ^ b.bit;
b.bit = a.bit ^ b.bit;
a.bit = a.bit ^ b.bit;
}
static LinkedList<Node> sort(LinkedList<Node> list) {
Node tail = list.get(list.size() - 1);
Iterator<Node> headIter = list.iterator();
Node head = null;
while (headIter.hasNext() && (head != tail)) {
System.out.println("Current list: " + list);
head = headIter.next();
if (head.bit == 1) {
while ((tail.bit == 1) && (head != tail)) {
tail = tail.left;
}
if (head != tail) {
swap(head, tail);
tail = tail.left;
}
}
}
return list;
}
traverse the double linked list from head to tail... while traversing make all nodes as 0 and count how many 1's are there... after reaching the tail again traverse from tail to head and make each node 1 and decrement count...do this until count becomes 0... can u plz elaborate i m not able to get it
Since there are only two values presented in this list, instead of thinking it's a sorting problem, you can think of it as moving elements around in the linked list. First, traverse the list to get the total number of element in the list. O(n). Then we can start swap element with head/tail. For example, when encounter element 0, make it as the head element of the list; if the element is 1, move it to the tail. O(n). The total run time will be O(n) + O(n) = O(n)
traverse the double linked list from head to tail... while traversing make all nodes as 0 and count how many 1's are there... after reaching the tail again traverse from tail to head and make each node 1 and decrement count...do this until count becomes 0...
- algos August 13, 2012