Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

C++ approach. The list could be given in any order (i.e. "ybgrrgbyrrggbbyy") as well as the pattern (i.e. "gbyr"). This function will order the list without declaring additional nodes but we will have to use a map. NOTE: the amount of nodes in the list has to be a multiple of the length of the patttern.

{

	void orderList(string pattern)
	{
		map<char, list<node*>> dictionary;
		current = head;
		node * prev;
		int counter = 0;
		
		while(current->next != NULL) 
		{
			dictionary[current->data].push_back(current);
			prev = current;
			current = current->next;
			prev->next = NULL;
			counter++;
		}
		
		prev = dictionary[pattern[0]].front();
		dictionary[pattern[0]].pop_front();
		counter--;
		
		head = prev;
		
		int i = 1;
		while(counter > 0)
		{
			current = dictionary[pattern[i]].front();
			dictionary[pattern[i]].pop_front();
			prev->next = current;
			prev = current;
			
			i++;
			if(i == pattern.length())
				i = 0;
			counter--;
		}
		//current->next = head; //make list circular again
	}

}

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

O(n) to iterate once to select each color
structure 1.) store it in a dictionary or a map of lists for each color
structure 2.) create new lists for individual colors

O(n) to pop each node based from the data structure on rgyb format
this handles uneven spacing of rgyb sub nodes with trailing sequences based on available color selections

O(n) extra space 2*O(n) time

- RT April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Three steps:

1) Build a hashMap<Color, Queue<Node>>, where each bucket will store the nodes of same color using FIFO PriorityQueue.

2) Build a sortedList, ArrayList<Node>, and walk through the color pattern list repeatedly and remove each node from the corresponding bucket (ie same color) to insert into this new list. This is the list that is being asked.

3) Last step is to fix the pointer reference of the nodes in the original list.

- Phi Tran April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do we need priority queue?

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

public <T> CircularListNode<T> reorderList(final CircularListNode<T> head, final Color[] colors) {
		// 1) Put nodes (references) of same color to their own bucket
		Map<Color, Queue<CircularListNode<T>>> colorMap = new HashMap<Color, Queue<CircularListNode<T>>>();
		
		CircularListNode<T> node = head;
		// TODO: Check to make sure no color repeated in the colors list
		while (node != null) {
			Queue<CircularListNode<T>> bucket = colorMap.get(node.color);
			if (bucket == null) { // first time, create the bucket
				bucket = new PriorityQueue<CircularListNode<T>>();
				colorMap.put(node.color, bucket); // add to the map
			}
			bucket.add(node); // store node's reference to original list
			node = node.next;
			if (node == head) break;
		}
		
		// 2) Build the actual "ordering" list according to the input pattern Colors
		List<CircularListNode<T>> sortedArray = new ArrayList<CircularListNode<T>>();
		node = head;
		while (true) {
			// Repeat the pattern until colorMap is exhausted.
			boolean notEmpty = false;
			for (Color c : colors) {
				Queue<CircularListNode<T>> bucket = colorMap.get(c);
				// if this bucket is not yet empty, take 1 from it
				CircularListNode<T> tmpNode = bucket.poll(); // null if bucket is empty
				if (tmpNode != null) { 
					sortedArray.add(tmpNode);
				} 
				// check (not remove) anything left in the bucket
				if (bucket.peek() != null) {
					notEmpty = true; // at least one
				}
			}
			/**
			 * If all buckets are empty, DONE.
			 */
			if (!notEmpty)
				break;
		}
		
		// 3) Fix reference of each node in the sortedArray
		Iterator<CircularListNode<T>> iter = sortedArray.iterator();
		CircularListNode<T> newHead = iter.hasNext()? iter.next() : null;
		 // this head MAY NOT be the same as the original list's head.
		CircularListNode<T> prevNode = newHead;
		CircularListNode<T> curNode = null;
		while (iter.hasNext()) {
			curNode = iter.next();
			prevNode.next = curNode;
			prevNode = curNode;
		}
		// last node to point to the head.
		if (prevNode != newHead) { // avoid case there is only single node
			prevNode.next = newHead;
		}
		
		return newHead;
	}

- Phi Tran April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a kind of sudo-code.
- find the start char of the pattern
- change the head pointer to that node
- Iterate the LL
- Mark the start of a pattern
- iterate the LL till all characters from the pattern are organized in a section
- move the start pointer to the next item of the end of the 1st section
- continue till the start pointer.next is actually the head of the LL

p = pattern[];
find the first char of the pattern in the LL, 
	say, a points to the node containing the 1st char of the pattern
	
while(a.next != head){
	b = a;
	c = b.next;
	foreach(char  in  p){
		if(p[i] == b.val){
			b = c;
			c = c.next;
		} else {
			while(c.val != p[i])
				c = c.next;
			swapNodes(b,c);
		}
	}
	a = c;
}

- Green April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey, I was asked to write the code too. Can you please clarify your algo bit more.

- Nitin April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Green : Should not after swapNodes(b,c); b be pointing to b.next....I mean
b = b.next; should be present after swapNodes(b,c);.....Not sure if I have missed something/ not understood your algo correctly.

- Rakesh Roy April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Queue or stack will work as well. I solved it maintaining two list/Array of each color and also pointer to each element in the list.
Solution is still 2 * O(n).

Step 1: Scan through the list until head == current (circular linked list) and create a list/Array of each color nodes.
Step2: iterate through the pattern "rgyb" until all the elements are used and start populating final list
Step 3: return head of new list


Here is the code in C#:
public class Node {
public char color;
public Node next;
};

enum colors {
r = 0,
g,
y,
b
};

public static Node RearrangeList(Node head, string pattern ) {

Node[] colorArray = new Node[4];
Node[] pointerToCurrent = new Node[4];
int elementCount = 0;

for(int i =0;i<4;i++) {
colorArray[i] = null;
pointerToCurrent[i] = null;
}

Node current = head;
bool firstExecution = true;
while(firstExecution || !Object.Equals(current, head)){
firstExecution = false;
int index = getIndex(current.color);

if(colorArray[index] == null){
colorArray[index] = current;
pointerToCurrent[index] = current;
} else {
pointerToCurrent[index].next = current;
pointerToCurrent[index] = current;
}

current = current.next;
pointerToCurrent[index].next = null;
elementCount++;
}

Node newHead = null;
current = null;
while(elementCount > 0) {

foreach (char c in pattern)
{
int index = getIndex(c);
if(newHead == null) {
newHead = current = colorArray[index];
}
else {
current.next = colorArray[index];
current = current.next;
}
colorArray[index] = colorArray[index].next;
current.next = null;
}
elementCount -= pattern.Length;
}

return newHead;
}

- CodeKaur April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

None of the solutions above are handling circular nature of the linked list.
Nitin, can you please explain what will be the output of the circular nature? Should it remain circular or not? If yes, will the start node of the circle remain the same?

- Victor April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The list represents students standing in a cirle. Hence the final output should also remain circular. The head can change anywhere but the pattern needs to be the same...i.e. rgyb can be gybr or ybrg etc...

- Nitin April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
Take for temp pointers corresponding to r,g,y,b. Set them to the first occurrence of node of that type. one more pointer to track cur_pos.
Pseudo-code:
1) Start condition: cur_pos = head
2) Traverse list to set pointers r,g,y,b to first occurance of node of those types.
3) move 4 nodes corresponding to r,g,y,b to cur_pos.
r->g->y->b->cur_pos->.....
4) repeat 2,3 from starting from cur_pos.
}

- aks June 14, 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