Chicago Software Engineer Interview Experience — Three Rounds Ending in a Deep C++ Concurrency Grill

Round 1: Dual Behavioral Interview — Communication & Continuous Improvement

Round 2: C++ Data Structures & Algorithms

Question 1

Simple Moving Average (Sliding Window)

Implement a class that computes the Simple Moving Average (SMA) over a fixed-size sliding window. The class should support the following APIs:

class SMA {
public:
    SMA(int windowSize);
    void add(int sample);
    double getAvg() const;
};

Requirements:

• The constructor takes the window size N.
• Calling add(int sample) inserts a new integer sample into the window.
• If the number of samples exceeds N, only the most recent N samples should be retained.
• getAvg() returns the arithmetic mean of the values currently in the window as a double.
• Before the window is full, the average should be computed using all samples received so far.

Example:

SMA sma(3);
add(1)
getAvg() -> 1.0
add(2)
getAvg() -> 1.5
add(3)
getAvg() -> 2.0
add(4)      // window becomes [2,3,4]
getAvg() -> 3.0

Expected complexity: add() is O(1), getAvg() is O(1).

What it's testing: sliding window, queue/deque, running sum, stream processing, data structure design (maintain O(1) update and O(1) query).

Question 2

Smart Queue / Stock Quote Container

Implement a container that stores incoming stock quotes as they arrive. Each Quote consists of:

struct Quote {
    string symbol;
    int bid;
    int ask;
};

Implement the following APIs:

void push(const Quote& quote);
bool pop(Quote& quote);
// Returns false if the container is empty.
// Otherwise removes the oldest valid quote and returns it via reference.
int size() const;

The container must satisfy the following requirements:

• Preserve insertion order.
• If a quote for symbol ABC is received before a quote for symbol XYZ, then the latest quote for ABC should be popped before the latest quote for XYZ (unless ABC is updated later).
• Only keep the most recent quote for each symbol.
• If a new quote arrives for a symbol that already exists in the container, the old quote should be removed and replaced with the new one.
• At any time, there should be at most one quote per symbol in the container.

Example:

push({AAPL, 95, 97})
push({GOOG, 500, 540})
push({MSFT, 30, 34})
push({GOOG, 501, 520})   // replaces previous GOOG quote
push({AAPL, 94, 98})     // replaces previous AAPL quote
size() -> 3
pop() -> {AAPL, 94, 98}
push({MSFT, 32, 35})     // replaces previous MSFT quote
pop() -> {GOOG, 501, 520}
pop() -> {MSFT, 32, 35}
pop() -> false
size() -> 0

What it's testing: data structure design, using an unordered_map plus a doubly linked list (std::list) to get O(1) push/pop/size. This is essentially a variant of the LRU cache data structure.

Round 3: C++ Concurrency & Memory

A simplified Producer-Consumer system. The system has three classes: Storage, Factory, Consumer.

Storage is a shared store with a fixed capacity, holding int items internally, and provides:

bool store(int item);
bool retrieve(int& result);

Requirements:

• When storage isn't full, store() inserts the item and returns true.
• When storage is full, store() doesn't insert and returns false.
• When storage isn't empty, retrieve() takes out an item, writes it into result, and returns true.
• When storage is empty, retrieve() returns false.
• Storage will be accessed by both the factory and consumer threads at the same time, so it needs to be thread-safe.

Factory produces items at a specified rate:

Factory(unsigned itemsPerSec, Storage& storage);
void work();

For example, itemsPerSec = 10 means producing 10 items per second. Each item produced should increment: 0, 1, 2, 3, ... If storage is full, the item just produced is simply dropped, and the next attempt should move on to the next item rather than retrying the same one — e.g. if item 5 fails to write because storage is full, the next attempt should try to write 6.

Consumer consumes items at a specified rate:

Consumer(unsigned itemsPerSec, Storage& storage);
void work();

If storage is empty, that consumption attempt fails, and it tries again on the next cycle.

Thread control: in test(), create a Factory thread, create a Consumer thread, let both threads run for a while, have test() actively request both threads to stop, then wait for both threads to exit. The stop timing should not be hardcoded inside Factory::work() or Consumer::work().

Main things being tested:

1. Producer-Consumer model — whether you can recognize this as a classic producer-consumer problem: Factory is the producer, Consumer is the consumer, Storage is the bounded buffer.

2. Thread-safe queue — std::queue itself is not thread-safe. All of size(), empty(), push(), front(), pop() need synchronization. The key is that the check and the mutation must happen inside the same critical section, e.g.:

std::lock_guard<std::mutex> lock(m_mutex);
if (m_queue.empty()) {
    return false;
}
result = m_queue.front();
m_queue.pop();

You can't check empty(), release the lock, and then pop() afterward — that produces a TOCTOU race.

3. Using a mutex — a basic implementation can use std::mutex and std::lock_guard to protect the whole queue. What this is testing: data race, critical section, mutual exclusion, exception-safe locking, mutex contention.

4. Bounded queue semantics — you need to correctly distinguish store() == false (full) from retrieve() == false (empty). The API here is non-blocking — it doesn't require the producer to wait when full, or the consumer to wait when empty.

5. Production and consumption rate — controlled via interval = 1000ms / itemsPerSec to control call frequency. For example: Factory at 10 items/sec, Consumer at 5 items/sec, capacity 2 — the producer is faster than the consumer, so storage is often full and some items get dropped.

6. External stop mechanism — don't hardcode the run duration inside the worker:

while (now - start < 10s)

A better design lets the caller control the lifetime:

std::atomic<bool> m_stop{false};

worker:

while (!m_stop.load()) {
    // work
}

main thread:

sleep_for(10s);
factory.requestStop();
consumer.requestStop();
factoryThread.join();
consumerThread.join();

What this is testing: separation of concerns, decoupling worker logic from lifetime management, graceful shutdown, thread join.

7. Why the stop flag has to be atomic — the main thread writes m_stop.store(true); the worker thread reads m_stop.load(). If you use a plain bool, one thread reading while another writes with no synchronization is a data race and undefined behavior. Using std::atomic<bool> guarantees the access is well-defined.

8. Atomic memory ordering — by default, load()/store() use std::memory_order_seq_cst. But for a plain stop flag, you can use:

m_stop.store(true, std::memory_order_relaxed);
m_stop.load(std::memory_order_relaxed);

because all you need here is atomicity for reading this one flag's value — you're not using this flag to publish any other shared data. Related follow-ups: relaxed / acquire / release / acq_rel / seq_cst / consume. You only need release-store and acquire-load when the stop flag is also being used to publish other shared state.

9. Stop response latency — even though the stop flag is atomic, if the worker is currently inside sleep_for(interval), it can't stop immediately. It has to wait for the sleep to return before it checks the flag again, so the maximum stop delay is roughly one interval. You can use a condition_variable to improve stop responsiveness further.

10. Downsides of a mutex — a mutex-based approach is simple and correct, but it can bring lock contention, blocking, context switches, scheduling overhead, lock convoys, higher tail latency, and deadlock risk. Even though this problem only has one producer and one consumer so contention isn't severe, the interviewer kept asking whether the mutex could be removed.

11. Lock-free SPSC ring buffer — since this problem is single producer, single consumer, you can use a fixed-size ring buffer: the producer only modifies tail, the consumer only modifies head, both indices are atomic, and no mutex is needed. The core synchronization pattern:

buffer[tail] = item;
tail.store(next, std::memory_order_release);

consumer:

tail.load(std::memory_order_acquire);
result = buffer[head];

release/acquire guarantees that when the consumer observes the new tail, it also observes the item the producer wrote into the buffer earlier. Similarly, only after the consumer updates head can the producer safely reuse that slot.

12. Difference between SPSC and MPMC — the lock-free ring buffer above only works for one producer plus one consumer. With multiple producers or multiple consumers, multiple threads would be modifying the same head or tail simultaneously, which requires CAS, slot-ownership handling, and a more complex sequence-number or concurrent-queue algorithm. This is a common follow-up.

Interviewer's step-by-step follow-up path:

1. Implement thread-safe bounded storage
2. Add producer and consumer rates
3. Fix item generation semantics
4. Move stop control outside the worker
5. Explain why atomic<bool> is required
6. Discuss memory ordering
7. Explain mutex downsides
8. Replace the mutex-based queue with an SPSC lock-free ring buffer

Overall this round leaned heavily on: C++ concurrency, mutex, atomic, memory ordering, producer-consumer, graceful shutdown, lock-free SPSC queue.