## Tintri Interview Question for Member Technical Staffs

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

> Traverse the linked list and for each node , create a new node.
> Insert the new node in the original linked list right after the original node.
> Once the entire linked list is traversed , we would be having a linked list with each node followed by its duplicate node.

> Now Traversal again, this time only by iterating over the original nodes.
> For each originalNode , we set its duplicate's random pointer to its randomPointer's next.
> Then traverse the link list again & remove all the duplicate nodes from the link list and return the head pointer of the linked list.

``````public RandomList DuplicateRandomList(RandomList root) {

if (!root)
return null;

RandomList ptr = root;

//copy each node and insert to list adjacent to original
while (ptr != null) {
RandomList copy = new RandomList(ptr.label);
copy.next = ptr.next;
ptr.next = copy;
ptr = copy.next;
}

//copying random pointer for each new node
ptr = root;
while (ptr != null) {
if (ptr.random != null)
ptr.next.random = ptr.random.next;
ptr = ptr.next.next;
}

// generate two list by breaking
ptr = root;
while (ptr != null) {
RandomList temp = ptr.next;
ptr.next = temp.next;
if (temp.next != null)
temp.next = temp.next.next;
ptr = ptr.next;
}

}``````

Complexity: O(n)

Comment hidden because of low score. Click to expand.
0

Hi...what is the purpose of creating a duplicate in the existing list and than traverse once again to remove the duplicates. Cant we simply create a new linked list when we are traversing the original one?

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this in O(n) time and O(1) space but involves modifying original list's rnd pointers though they will be reverted back at the end.

Idea is after we do a normal clone of the list with next pointers set, the empty rnd pointers of the clone can be used to temp store original's rnd and original's rnd can store clone as a way to map original and clone. I'll sketch out an algo when I get time...

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this in O(1) space and O(N) time.

After doing the normal clone with next pointers, the empty rnd pointers can be used to temporarily store corresponding original's rnd and original's rnd can store corresponding clone node as a way to keep a map between original -> clone without using extra space.

I'll sketch out something when I get time...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am unable to understand the question even after reading several times . Could someone explain this question in simpler terms ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.