Priority Crate Management — Problem Statement & Solution Guide
Problem Description
Implement a CrateManager class that utilizes a stack data structure to manage a collection of crates, where each crate is represented by its value.
Examples
Input
addCrate(5), addCrate(3), removeCrate(), peekHighestPriority()
Output
[null, 5, 5]
Explanation: Step 1: Add crate 5 to the stack. The stack is now [5]. Step 2: Add crate 3 to the stack. The stack is now [3, 5]. Step 3: Remove crate 3 from the stack. The stack is now [5]. Step 4: Peek the highest priority crate from the stack. The highest priority crate is 5.
Input
addCrate(5), addCrate(5), removeCrate(), peekHighestPriority()
Output
[null, 5, 5]
Explanation: Step 1: Add crate 5 to the stack. The stack is now [5]. Step 2: Add crate 5 to the stack. The stack is now [5, 5]. Step 3: Remove crate 5 from the stack. The stack is now [5]. Step 4: Peek the highest priority crate from the stack. The highest priority crate is 5.
Constraints
- At most 10^4 crates are added to or removed from the inventory.
- The value of each crate is between 1 and 10^5.
Optimal Approach & Strategy
The optimized approach involves using a stack to manage the inventory and keeping track of the highest priority crate, allowing for efficient retrieval with a time complexity of O(1).
Brute Force Approach
A brute-force approach would involve searching the entire inventory for the highest priority crate every time getHighestPriorityCrates is called, resulting in a time complexity of O(n). This approach is inefficient as the inventory size increases.
Verified Code Solutions
class CrateManager {
constructor() {
this.stack = [];
}
addCrate(crate) {
if (this.stack.length === 0) {
this.stack.push(crate);
} else if (this.stack[this.stack.length - 1] < crate) {
this.stack.push(crate);
}
}
removeCrate() {
if (this.stack.length > 0) {
return this.stack.pop();
} else {
return null;
}
}
peekHighestPriority() {
if (this.stack.length > 0) {
return this.stack[this.stack.length - 1];
} else {
return null;
}
}
}class CrateManager {
constructor() {
this.stack = [];
}
addCrate(crate) {
if (this.stack.length === 0) {
this.stack.push(crate);
} else if (this.stack[this.stack.length - 1] < crate) {
this.stack.push(crate);
}
}
removeCrate() {
if (this.stack.length > 0) {
return this.stack.pop();
} else {
return null;
}
}
peekHighestPriority() {
if (this.stack.length > 0) {
return this.stack[this.stack.length - 1];
} else {
return null;
}
}
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.