## Amazon Interview Question for SDE-2s

• 0

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;
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].front();
dictionary[pattern].pop_front();
counter--;

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
}``````

}

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

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.

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

Why do we need priority queue?

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>>>();

// 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;
}

// 2) Build the actual "ordering" list according to the input pattern Colors
List<CircularListNode<T>> sortedArray = new ArrayList<CircularListNode<T>>();
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) {
}
// 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> 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
}

}``````

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

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;
}``````

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

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

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

@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.

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;
Node[] pointerToCurrent = new Node;
int elementCount = 0;

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

bool firstExecution = true;
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++;
}

current = null;
while(elementCount > 0) {

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

}

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?

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...

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.
}

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.