An SDET interview asked me to implement a stack and a queue (for example, for navigation history and a queue of test steps) and to test them. How should I approach both parts?
Asked by The SDET Playbook
Asked Sep 28, 2026Viewed 0 times
An SDET interview asked me to implement a stack and a queue (for example, for navigation history and a queue of test steps) and to test them. How should I approach both parts?
Asked by The SDET Playbook
Sign in to answer and to vote.
A stack is last in, first out (browser back history); a queue is first in, first out (steps waiting to run). An array is a fine stack, but Array.prototype.shift() moves every remaining element, so a queue built on it takes O(n) per dequeue. Keeping a head index makes it O(1):
export class Stack<T> {
private items: T[] = [];
push(item: T): void { this.items.push(item); }
pop(): T | undefined { return this.items.pop(); }
peek(): T | undefined { return this.items.at(-1); }
get size(): number { return this.items.length; }
}
export class Queue<T> {
private items: T[] = [];
private head = 0;
enqueue(item: T): void { this.items.push(item); }
dequeue(): T | undefined {
if (this.head === this.items.length) return undefined;
const item = this.items[this.head++];
if (this.head > 1024 && this.head * 2 > this.items.length) {
this.items = this.items.slice(this.head); // drop consumed slots now and then
this.head = 0;
}
return item;
}
get size(): number { return this.items.length - this.head; }
}
Test the behavior that defines each structure, not just one happy path:
import { describe, expect, it } from 'vitest';
import { Queue, Stack } from './collections';
describe('Stack', () => {
it('returns items in reverse order', () => {
const s = new Stack<number>();
[1, 2, 3].forEach((n) => s.push(n));
expect([s.pop(), s.pop(), s.pop()]).toEqual([3, 2, 1]);
});
it('is safe when empty', () => {
const s = new Stack<number>();
expect(s.pop()).toBeUndefined();
expect(s.size).toBe(0);
});
});
describe('Queue', () => {
it('returns items in insertion order across interleaved calls', () => {
const q = new Queue<string>();
q.enqueue('a'); q.enqueue('b');
expect(q.dequeue()).toBe('a');
q.enqueue('c');
expect([q.dequeue(), q.dequeue(), q.dequeue()]).toEqual(['b', 'c', undefined]);
});
it('keeps order and size through compaction', () => {
const q = new Queue<number>();
for (let i = 0; i < 5000; i++) q.enqueue(i);
for (let i = 0; i < 4000; i++) expect(q.dequeue()).toBe(i);
expect(q.size).toBe(1000);
expect(q.dequeue()).toBe(4000);
});
});
The second queue test targets the one tricky branch, compaction, which a small happy-path test never reaches. Point that out: choosing tests from the code's risky paths is the skill being assessed.
Sources: MDN: Array.prototype.shift(), Vitest