Trutgeek
BAN USER- 0of 0 votes
AnswersGiven a list of employees and their bosses as a CSV file , write a function that will print out a hierarchy tree of the employees.
- Trutgeek in United States for Phone Interview| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures
public static Node pointToNextHigherElement(Node head) {
Stack<Node> stack = new Stack<Node>();
Node current = head;
Stack<Node> tempList = new Stack<>();
while ( current != null){
if (stack.isEmpty()) {
current = fillStack(stack, current, tempList);
} else {
Node elementFromStack = stack.pop();
if (elementFromStack.value > current.value) {
stack.push(elementFromStack);
current = fillStack(stack, current, tempList);
} else {
tempList.add(elementFromStack);
}
}
}
while(!stack.isEmpty()) {
Node temp = stack.pop();
if (!stack.isEmpty()) {
Node next = stack.peek();
temp.random = next;
}
}
return head;
}
private static Node fillStack(Stack<Node> stack, Node current, Stack<Node> tempList) {
stack.push(current);
while (!tempList.isEmpty()) {
stack.push(tempList.pop());
}
current = current.next;
return current;
}
public static Node pointToNextHigherElement(Node head) {
Stack<Node> stack = new Stack<Node>();
Node current = head;
stack.push(current);
current = current.next;
while ( current != null){
Node elementFromStack = stack.pop();
if (elementFromStack.value > current.value) {
stack.push(elementFromStack);
stack.push(current);
} else {
stack.push(current);
stack.push(elementFromStack);
}
current = current.next;
}
while(!stack.isEmpty()) {
Node temp = stack.pop();
if (!stack.isEmpty()) {
Node next = stack.peek();
temp.random = next;
}
}
return head;
}
public static Node updateLinkedList(Node head) {
if (head == null) {
return null;
}
Node slow = head;
Node fast = head;
Stack<Node> stack = new Stack<Node>();
while (fast != null){
stack.push(slow);
fast = fast.next;
if (fast != null) {
slow = slow.next;
fast = fast.next;
}
}
while(!stack.isEmpty()) {
Node temp = stack.pop();
slow.value = temp.value + slow.value;
slow = slow.next;
}
return head;
}
Good catch. Added a temp stack to hold values lesser than the current node.
- Trutgeek September 06, 2017