Two-Spike Order Rail
A small diner keeps order tickets on spikes: you push a ticket down onto the spike, and you can only take the ticket on top. A spike is a stack. The cooks, though, must cook orders in the order they came in, oldest first.
The diner has exactly two spikes and nothing else. With a bit of care, the two spikes together can hand out tickets in arrival order.
Your task
Write a class TicketRail with these methods:
pin(ticket): a new order arrives with this ticket number.serve(): remove and return the oldest ticket still waiting.peek(): return the oldest ticket without removing it.isEmpty(): returntrueif no tickets are waiting.
Store tickets only in two stacks, using only push, pop, look at the top, and check if empty (an array with push / pop in JavaScript, a list with append / pop in Python). Each method should take O(1) time on average over many calls.
class TicketRail
Examples
new TicketRail() .pin(12) .pin(15) .serve() .pin(18) .peek() .serve() .serve() .isEmpty()
[null, null, null, 12, null, 15, 15, 18, true]
Tickets 12 and 15 are pinned. The oldest, 12, is served first. Then 18 arrives. The oldest left is 15, so peek shows 15 and serve hands out 15, then 18. Now the rail is empty.
Constraints
- 1 ≤ number of method calls ≤ 1,000
- 1 ≤ ticket ≤ 1,000,000; ticket numbers may repeat.
- serve and peek are only called when at least one ticket is waiting.
Start with brute force
Use one spike. To serve, lift every ticket off onto the second spike, take the bottom one, then put all the others back.
That moves every waiting ticket twice for every single serve, so with n tickets waiting each serve is O(n), and a busy shift costs O(n²). The better design moves each ticket across at most once in its whole life.
Hints
0 of 4 shown- Hint 1
Pin tickets 1, 2, 3 on one spike. Now lift them off one by one and push each onto the second spike. Which ticket is on top of the second spike?
- Hint 2
Moving a whole spike onto another reverses the order, so the oldest ticket ends up on top. One spike can receive new tickets while the other hands out old ones.
- Hint 3
When is it safe to move tickets from the receiving spike to the serving spike? Try: pin 1, pin 2, serve, pin 3, serve. What goes wrong if you move ticket 3 across while ticket 2 is still on the serving spike?
- Hint 4
Keep an
inboxstack forpinand anoutboxstack forserveandpeek. Only when the outbox is empty, pop everything from the inbox and push it onto the outbox. Then the outbox top is always the oldest ticket.isEmptychecks both.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Pouring one stack onto another reverses it. So if new tickets go onto an inbox spike, pouring that spike onto an outbox spike puts the oldest ticket on top, ready to serve.
Trace the example: pin 12, pin 15, serve, pin 18, peek, serve, serve.
- pin 12, pin 15. inbox =
[12, 15](15 on top), outbox =[]. - serve: the outbox is empty, so pour. outbox =
[15, 12](12 on top). Pop 12. - pin 18. inbox =
[18], outbox =[15]. - peek: the outbox is not empty, so do not pour. Its top is 15, the oldest. Return 15.
- serve: pop 15. serve again: the outbox is empty, pour 18 across, pop 18.
Step 4 is the key rule. If you had poured 18 on top of 15, the next serve would wrongly return 18. Pour only when the outbox is empty.
One pour can move many tickets, so a single serve can be slow. But each ticket is pushed onto the inbox once, poured once, and popped once. Spread over all calls, that is O(1) per call on average (amortized).
class TicketRail {
constructor() {
this.inbox = []; // new tickets, newest on top
this.outbox = []; // reversed, oldest on top
}
pin(ticket) {
this.inbox.push(ticket);
}
refill() {
// only pour when the outbox is empty, or the order breaks
if (this.outbox.length === 0) {
while (this.inbox.length > 0) this.outbox.push(this.inbox.pop());
}
}
serve() {
this.refill();
return this.outbox.pop();
}
peek() {
this.refill();
return this.outbox[this.outbox.length - 1];
}
isEmpty() {
return this.inbox.length === 0 && this.outbox.length === 0;
}
}class TicketRail:
def __init__(self):
self.inbox = [] # new tickets, newest on top
self.outbox = [] # reversed, oldest on top
def pin(self, ticket):
self.inbox.append(ticket)
def _refill(self):
# only pour when the outbox is empty, or the order breaks
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def serve(self):
self._refill()
return self.outbox.pop()
def peek(self):
self._refill()
return self.outbox[-1]
def is_empty(self):
return not self.inbox and not self.outboxRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.