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;
	RandomList newHead = root.next;
	while (ptr != null) {
		RandomList temp = ptr.next;
		ptr.next = temp.next;
		if (temp.next != null)
			temp.next = temp.next.next;
		ptr = ptr.next;
	}
 
	return newHead;
}

Complexity: O(n)

- R@M3$H.N October 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Megha Maheshwari December 08, 2015 | Flag
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...

- undefined October 02, 2015 | Flag Reply
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...

- undrai October 02, 2015 | Flag Reply
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 ?

- Amogh Huilgol January 05, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More