Expedia Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

Node* Copy(Node* head)
{
	if (head)
		return;
	node* curr = head;
	
	//create a copy of each node and insert it after the node in the original list
	while (curr)
	{
		node* temp = new node();
		temp->Data = curr->Data;
		temp->Next = curr->Next;
		curr->Next = temp;
		curr = temp->Next;
	}

	//Polpulate this->Other and separate out the copy LL
	curr = head;

	node* duplicate = head->next;
	while (curr)
	{
		node* copy = curr->next;
		copy->other = curr->other->next;
		curr->next = copy->next;
		curr = curr->next;
		copy->next = curr->next;
	}
    
	return dulticate;
}

- Brandy May 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good O(n) solution

- iwanna July 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. For each node X in the given list,
1.1 create a corresponding node Y for the new list. Copy X's Data to Y's Data. The Y's
Next and Other both pointing to null.
1.2 Store X as key and Y as value in the map
2. Iterate over each entry in the map.
2.1 For key X , get value Y
2.2 Y-> Next = map.get(X->Next)
2.3 Y->Other = map.get(X->Other)

- Rakesh Roy May 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This so far is the only solution I see that scales

- Anonymous August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice Solution

- popoff August 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You deen to write serialization. I've written something simular in Java. All you need - it is resolve cyclic reference in order to reject infinite cycle copying. In java You can use identityHashCode and identityHashMap to store each node only once. And that build up list from them. You put the node to the identyty hash Map. Then you looks to pointer. If nodes they are referenced to are in the map - then store their hashcode else put theese node to map and store their hash code.
from
Node next -> some other node
to
Node next -> 0xAB23FD133

- glebstepanov1992 May 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node copyList(Node head) {
		if (head == null)	
			return null;

		//Create a new node for each node in the original list.
		//Also, create two index arrays, one for original list, one for new list
		Node curr = head;
		ArrayList<Node> originIndexArray = new ArrayList<Node>();
		ArrayList<Node> newIndexArray = new ArrayList<Node>();
		while (curr != null) {
			Node node = new Node();
			node.data = curr.data;
			newIndexArray.add(node);
			originIndexArray.add(curr);
			curr = curr.next;
		}


		//Set next pointer of each node in the new list
		for (int i = 0; i < newIndexArray.size(); i++) {
			Node node = (Node) newIndexArray.get(i);
			if (i + 1 < newIndexArray.size()) {
				Node nextNode = (Node) newIndexArray.get(i+1);
				node.next = nextNode;
			} else {
				node.next = null;
			}
		}

		//Set other pointer of each node in the new list
		for (int i = 0; i < originIndexArray.size(); i++) {
			Node oNode = (Node) originIndexArray.get(i);
			Node nNode = (Node) newIndexArray.get(i);
			if (oNode.other != null) {
				int k = originIndexArray.indexOf(oNode.other);
				Node otherNode = (Node) newIndexArray.get(k);
				nNode.other = otherNode;
			} else {
				nNode.other = null;
			}
		}

		return (Node) newIndexArray.get(0);
	}

- goldbug1832 May 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We have originalList. Create a DupList with other as null, copy data and next.
Now loop through the Original and Dup lists:
		if orig's other == null then dup's other = null;
		else if orig's other == self then dup's other = self;
		else 
			create another temp1 list = orig's head;
			create another temp2 list = orig's head;
			 loop through temp 1 and 2, and check if temp1's next points to the orig's other
			if yes then put dup's other = temp2's current pos

this will be n^2 solution.

- bhavi February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can we define what is proper for Other?
I don't see any problem with original linkedlist, except for Other, which we just have to set it as null.

- flashzeb March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Java Implementation
// Algorithm of this code is Brandy code.
// Time complexity is O(n) and space is O(n) 
private class Node {
                
                int data;
                Node next, other;
                
                Node(int data) {
                        this.data = data;
                        this.next = this.other = null;
                }
                
        }
        
        Node copyLinkedList(Node head) {

                if (null == head) {
                        return null;
                }

                Node current = head;
                while (null != current) {
                        Node temp = new Node(current.data);
                        temp.next = current.next;
                        current.next = temp;
                        current = temp.next;
                }
                
                current = head;
                Node copiedList = head.next;
                while(null != current) {
                        Node temp = current.next;
                        temp.other = current.other.next;
                        current.next = temp.next;
                        current = current.next;
                        temp = current.next;
                }
                
                return copiedList;
        }

- Kapil July 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

in the given link list make all the nodes pointing to itself by using other pointer
and while copying just put the data of every node by using node->other->data in new linklist

- keshav May 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wouldn't this destroy the original list though?

- Anonymous August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Now I might be under-thinking things here but if all "other" nodes point to only nodes within the same linked list, there is no need to do anything special; just start and head and copy everything

Node* copy(Node* head)
{
    if(head==NULL)
        return NULL;
    
    Node* newHead=new Node(*head);
    while(head->next)
    {
          newHead->next=new Node(*(head->next)); //assume a shallow copy constructor
          head=head->next;
    }
    return newHead;
}

Now if "other" can point to any Node on any list and thus we need to reconstruct that entire sublist as well, then things get interesting. But that is for a another answer

- Anonymous June 26, 2014 | 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