Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Nice approach.
An O(N) time and O(N) auxillary space solution, would be to::
1) Scan the original list and create the copy list, one node at a time, populating ONLY the "next" pointers in each node. Also, while scanning the original list create a map between the addresses of corresponding nodes in original and copied list.
2) Now, scan the original list once again and for each "arbitrary" pointer in each node of the original list, get the corresponding value from the map, and copy that value in "arbitrary" field of the node of the copied list.
It seems that you are duplicating every node in the list, if it's so, how the space complexity is O(1), isn't it O(n)?
Could you please elaborate on the space complexity?
Node* f(Node* h)
{
if (h==null) return null;
Hash<int, int> *ht = new Hash<int, int>();
Node *hp = h;
Node *nh = null;
Node *nt = null;
while (hp!=null)
{
Node *n = new Node(hp->value);
if (nh == null)
{
nh = nt = n;
}
else
{
nt->next = n;
nt = nt->next;
}
ht.Add(hp, n);
hp = hp->next;
};
hp = h;
while (hp != null)
{
if (hp->random == null)
{
ht[hp]->random = null;
}
else
{
ht[hp]->random = ht[hp->random];
}
hp = hp->next;
}
delete ht;
return nh;
}
// Initial value of source is head of original list
public Node copyList(Node source)
{
// base case
if(source == null)
return null;
// create new node for new list
Node newNode = new Node();
newNode.setData(source.getData());
// set new node's next to copy of original's next
newNode.setNext(copyList(source.getNext()));
return newNode;
}
You are in effect copying a graph, which may be circular, say a node points to one of its predecessors in the list.
The one thing notable is that you have a path with covers every node in the graph for only once.So if the nodes aren't many, you can traverse the old linked list or the new "graph" to check what you have already copied(the latter presumably better for it has less nodes, yet the pointers may overlap each other and point to the same nodes multiple times,the overlapping being proportional to the number of pointers of each node, plus you need to deal with the possibility of circling) instead of using a full-blown hash table; I leave out the implementation.
i don't understand what is meaning of randomly pointing does it make a graph?or it follow the meaning of single link list where each node point to one node and that node not points it back or multiple nodes can point to one node m confused if it is graph then i think we have to use dfs which is of o(n2) any better and simple solution??
node* copy_list( node* original )
{
node* original_h=original;
store( original_h );
vector<node*> v;
node* copy_h=new node;
node* prev;
copy_h->data=original_h->data;
copy_h->next=NULL;
copy_h->random=original_h;
v.push_back(originl_h);
node* t=copy_h;
prev=original_h;
original_h=original_h->next;
prev->next=copy_h;
while(original_h)
{
node* tmp=new node;
tmp->data=original_h->data;
tmp->next=NULL;
tmp->random=original_h;
t->next=tmp;
t=t->next;
v.push_back(original_h);
prev=original_h;
original_h=original_h->next;
prev->next=tmp;
}
t=copy_h;
while(t)
{
t->random=t->random->random->next;
t=t->next;
}
node* restore= original;
for(int i=1;i<v.size();i++)
{
restore->next=v[i];
restore=restore->next;
}
return copy_h;
}
#include<stdlib.h>
#include<stdio.h>
typedef struct node_s{
int data;
struct node_s *next;
struct node_s *arbit;
} Node_s;
void free_list(Node_s * head){
if(!head) return;
Node_s * temp = head;
Node_s * next = head;
while(temp){
next = temp->next;
free(temp);
temp = next;
}
}
void push_1(Node_s **head, int value){
if(*head == NULL){
(*head) = (Node_s *)malloc(sizeof(Node_s));
(*head)->data = value;
(*head)->next = NULL;
}
else{
Node_s * temp = (Node_s *)malloc(sizeof(Node_s));
if(temp){
temp->data = value;
temp->next = (*head);
*head = temp;
}
}
}
void add_arbit(Node_s *L1, int a, int b){
Node_s * first = L1;
Node_s * second = L1;
while(first){
if(first->data == a)
break;
first = first->next;
}
while(second){
if(second->data == b)
break;
second = second->next;
}
if(first)
first->arbit = second;
}
Node_s * create_node(int val){
Node_s * temp = (Node_s *)malloc(sizeof(Node_s));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}
Node_s * clone(Node_s * node){
if(!node) return NULL;
Node_s * current = node;
//First insert clone nodes in original linked list.
while(current){
Node_s * current_next = current->next;
current->next = create_node(current->data);
current->next->next = current_next;
current = current_next;
}
current = node;
//Now copy arbit pointer of each node to cloned list
Node_s * clone_head = current->next;
while(current){
Node_s * clone = current->next;
if(current->arbit){
clone->arbit = current->arbit->next;
}
current = clone->next;
}
current = node;
//Segregate two linked list
while(current){
Node_s * clone = current->next;
current->next = clone->next;
if(clone->next){
clone->next = clone->next->next;
}
current = current->next;
}
//return head pointer to the calling function
return clone_head;
}
int main(){
Node_s * L1 = NULL;
push_1(&L1,1);
push_1(&L1,2);
push_1(&L1,3);
push_1(&L1,4);
push_1(&L1,5);
push_1(&L1,6);
add_arbit(L1,1,6);
add_arbit(L1,2,5);
add_arbit(L1,3,1);
add_arbit(L1,4,2);
add_arbit(L1,5,4);
add_arbit(L1,6,3);
print_list_1(L1);
Node_s *clone_head = clone(L1);
free_list(L1);
print_list_1(clone_head);
return 0;
}
I like the solution
- santosh July 30, 20121) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node
2) Now copy the arbitrary link in this fashion
original->next->arbitrary = original->arbitrary->next; /*TRAVERSE
TWO NODES*/
This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
3) Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;
4) Make sure that last element of original->next is NULL.
Time Complexity: O(n)
Auxiliary Space: O(1)