Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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
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.
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;
}
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;
}
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;
}
{
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.
}
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.
}
- NL May 05, 2014