Rahul
BAN USER- 0of 0 votes
AnswersThe dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and
- Rahul in India for Kindle
it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The
sets S1 and S2 are usually destroyed by the operation. Show how to support UNION
in O(1) time using a suitable list data structure.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersThere is a sorted array of infinite numbers (can contain duplicates). Given a number. Find the last occurring instance of that number in the array.
- Rahul in India for Kindle
Ex., i/p: 12344445566667789...
search number: 6
o/p: 12 (index)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
- 1 Answer Implement Doubly linked list using single pointer...
Explain how to implement doubly linked lists using only one pointer value x.np per
- Rahul December 10, 2012
item instead of the usual two (next and prev). Assume that all pointer values can be
interpreted as k-bit integers, and define x.np to be x:np D x:next XOR x:pre,
the k-bit “exclusive-or” of x.next and x.prev. (The value NIL is represented by 0.)
Be sure to describe what information you need to access the head of the list. Show
how to implement the SEARCH, INSERT, and DELETE operations on such a list.
Also show how to reverse such a list in O(1) time.| Flag | PURGE
void insert(int n, node* random)
{
if(random==NULL)
{
node* newNode = getNode(n);
head = newNode;
return;
}
if(random==random->next)
{
node* newNode = getNode(n);
random->next = newNode;
if(newNode->data<random->data)
head = newNode;
return;
}
node* current = random;
node* nextNode = random->next;
node* newNode = NULL;
while()
{
if((n>=current->data && n<nextNode->data) ||
(n<current->data && n>nextNode->data))
{
newNode = getNode(n);
newNode->next=nextNode;
current->next=newNode;
break;
}
current=nextNode;
nextNode=nextNode->next;
}
if(n<current->data && n<nextNode->data)
head = newNode;
return;
}
Is this really Google's question?
- Rahul December 15, 2012