Queue/Stack

Question 1

Design a stack that includes a max operation, in addition to push and pop. The max method should return the maximum value stored in the stack. Time O(1) Space O(n)

Answer 1

private static class ElementWithCachedMax {
public Integer element;
public Integer max;

public ElementWithCachedMax(Integer element, Integer max) {
 this.element = element;
 this.max = max;
 }
 }

public static class Stack {

// Stores (element, cached maximum) pair.
private Deque elementWithCachedMax =
new ArrayDeque<>();

public boolean empty() { return elementWithCachedMax.isEmpty(); }

public Integer max() { return elementWithCachedMax.peek().max; }

public Integer pop() { return elementWithCachedMax.removeFirst().element; }

public void push(Integer x) {

elementWithCachedMax.addFirst(
 new ElementWithCachedMax(x, Math.max(x, empty() ? x : max())));
 }
 }

Question 2

Write a program that takes an arithmetical expression in RPN and returns the number that the expression evaluates to.

Time O(n)

Answer 2

public static int eval(String expression) {

Deque intermediateResults = new ArrayDeque<>();
final String DELIMITER = “,”;
final Map> OPERATORS = Map.of(
“+”,
(y, x)
-> x + y,
“-“, (y, x) -> x - y, “*”, (y, x) -> x * y, “/”, (y, x) -> x / y);
for (String token : expression.split(DELIMITER)) {
if (OPERATORS.get(token) != null) {
intermediateResults.addFirst(
OPERATORS.get(token).applyAsInt(intermediateResults.removeFirst(),
intermediateResults.removeFirst()));
} else { // token is a number.
intermediateResults.addFirst(Integer.parseInt(token));
}
}
return intermediateResults.removeFirst();
}

Question 3

Write a program that takes if a string made up of the characters’(‘,’)’,’[’,’]’,”{‘ and “}’ is well-formed.

Time O(n)

Space O(1)

Answer 3

public static boolean isWellFormed(String s) {

Deque leftChars = new ArrayDeque<>();
final Map LOOKUP =
Map.of(‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’, ‘]’);
for (int i = 0; i < s.length(); ++i) {
if (LOOKUP.get(s.charAt(i)) != null) {
leftChars.addFirst(s.charAt(i));
} else if (leftChars.isEmpty() ||
LOOKUP.get(leftChars.removeFirst()) != s.charAt(i)) {
return false; // Unmatched right char.
}
}
return leftChars.isEmpty();
}

Question 4

Write a program which takes a pathname, and return the shortest equivalent pathname. Assume individual directories and files have names that use only alphanumeric characters. Subdirectory names may be combined using forward slashes (/), the current directory (.) and parent directory (..).

Time O(n)

Answer 4

public static String shortestEquivalentPath(String path) {

if (path.equals("")) {
 throw new IllegalArgumentException("Empty string is not a legal path.");
 }

Deque pathNames = new ArrayDeque\<\>();
 // Special case: starts with "/", which is an absolute path.
 if (path.startsWith("/")) {
 pathNames.addFirst("/");
 }

for (String token : path.split("/")) {
 if (token.equals("..")) {
 if (pathNames.isEmpty() || pathNames.peekFirst().equals("..")) {
 pathNames.addFirst(token);
 } else {
 if (pathNames.peekFirst().equals("/")) {
 throw new IllegalArgumentException(
 "Path error, trying to go up root " + path);
 }
 pathNames.removeFirst();
 }
 } else if (!token.equals(".") && !token.isEmpty()) { // Must be a name.
 pathNames.addFirst(token);
 }
 }

StringBuilder result = new StringBuilder();
 if (!pathNames.isEmpty()) {
 Iterator it = pathNames.descendingIterator();
 String prev = it.next();
 result.append(prev);
 while (it.hasNext()) {
 if (!prev.equals("/")) {
 result.append("/");
 }
 prev = it.next();
 result.append(prev);
 }
 }
 return result.toString();
 }

Question 5

Design an algorithm that processes building in east-to-west order and returns the set of buildings which view the sunset. Each building is specified by its hight.

Time O(n)

Space O(n) but could be O(1) for best case.

Answer 5

private static class BuildingWithHeight {
public Integer id;
public Integer height;

public BuildingWithHeight(Integer id, Integer height) {
 this.id = id;
 this.height = height;
 }
 }

public static List
examineBuildingsWithSunset(Iterator sequence) {

int buildingIdx = 0;
Deque candidates = new ArrayDeque<>();
while (sequence.hasNext()) {
Integer buildingHeight = sequence.next();
while (!candidates.isEmpty() &&
(Integer.compare(buildingHeight, candidates.peekFirst().height) >=
0)) {
candidates.removeFirst();
}
candidates.addFirst(
new BuildingWithHeight(buildingIdx++, buildingHeight));
}
return candidates.stream().map(c -> c.id).collect(Collectors.toList());
}

Question 6

queue related methods

Answer 6

• addLast
• removeFirst
• getFirst
• offerLast
• pollFirst
• peekFIrst

Question 7

Given a binary tree, return an array consisting of the leys at the same level. Keys should appear in the order of the corresponding nodes’ depths, breaking ties from left to right.

Time O(n)

Space O(m), where m is the maximum number of nodes at any single depth.

Answer 7

public static List>
binaryTreeDepthOrder(BinaryTreeNode tree) {

List> result = new ArrayList<>();
if (tree == null) {
return result;
}

List> currDepthNodes = List.of(tree);
while (!currDepthNodes.isEmpty()) {
result.add(currDepthNodes.stream()
.map(curr -> curr.data)
.collect(Collectors.toList()));
currDepthNodes = currDepthNodes.stream()
.map(curr -> Arrays.asList(curr.left, curr.right))
.flatMap(List::stream)
.filter(child -> child != null)
.collect(Collectors.toList());
}
return result;
}

Question 8

implement a queue API using an array for storing elements. Your API should include a constructor function, which takes as argument the initial capacity of the queue, enqueue and dequeue functions, and a function which returns the number of elements stored. Implement dynamic resizing to support storing an arbitrarily large number of elements.

Time O(1) dequeue and enqueue

Answer 8

public static class Queue {

private int head = 0, tail = 0, numQueueElements = 0;
private static final int SCALE_FACTOR = 2;
private Integer[] entries;

public Queue(int capacity) { entries = new Integer[capacity]; }

public void enqueue(Integer x) {

if (numQueueElements == entries.length) { // Need to resize.
 // Makes the queue elements appear consecutively.
 Collections.rotate(Arrays.asList(entries), -head);
 // Resets head and tail.
 head = 0;
 tail = numQueueElements;
 entries = Arrays.copyOf(entries, numQueueElements \* SCALE\_FACTOR);
 }

entries[tail] = x;
tail = (tail + 1) % entries.length;
++numQueueElements;
}

public Integer dequeue() {

–numQueueElements;
Integer result = entries[head];
head = (head + 1) % entries.length;
return result;
}

public int size() { return numQueueElements; }

@Override
public String toString() {

return “Queue{“
+ “head=” + head + “, tail=” + tail +
“, entries=” + Arrays.toString(entries) + ‘}’;
}
}

Question 9

How would you implement a queue given a library implementing stacks?

Time O(m)

Answer 9

public static class Queue {

private Deque enqueue = new ArrayDeque<>();
private Deque dequeue = new ArrayDeque<>();

public void enqueue(Integer x) { enqueue.addFirst(x); }

public Integer dequeue() {

if (dequeue.isEmpty()) {
 // Transfers the elements from enqueue to dequeue.
 while (!enqueue.isEmpty()) {
 dequeue.addFirst(enqueue.removeFirst());
 }
 }
 return dequeue.removeFirst();
 }
 }

Question 10

Implement a queue with enqueue, dequeue, and max operations. The max operation returns the maximum element currently stored in the queue.

O(1) for equeue, dequeue, and max

Answer 10

private StackWithMax.Stack enqueue = new StackWithMax.Stack();
private StackWithMax.Stack dequeue = new StackWithMax.Stack();

public void enqueue(Integer x) { enqueue.push(x); }

public Integer dequeue() {

if (dequeue.empty()) {
while (!enqueue.empty()) {
dequeue.push(enqueue.pop());
}
}
return dequeue.pop();
}

public Integer max() {

if (!enqueue.empty()) { return dequeue.empty() ? enqueue.max()
: Math.max(enqueue.max(), dequeue.max());
}
return dequeue.max();
}