StackAdapt Software Engineer Interview Experience — Windowed Map Coding Question, Rude Interviewer

The question was to implement a Windowed Map — a KV store with a time window. Data arrives at irregular intervals, and only the data within the most recent window size / time window is kept; anything outside the window is expired and no longer visible to the user.

You need to implement 3 methods (as efficiently as possible):

• Get(key): if the key exists and hasn't expired, return the value; otherwise return null / throw. O(1)
• Put(key, value): write/update the key-value pair; every put updates that key's timestamp. O(1)
• GetAverage(): return the average of the values that are still valid within the window (optimize as much as possible)

Constraints: at any given moment, the valid data within the window fits in memory, but all the data over the entire lifetime does not (so you need eviction for expired data). Assume single-threaded for now. Get does not update the timestamp; Put does.

Example: Put("a", 10) at t=0, Put("b", 20) at t=1, GetAverage() -> 15.0. After waiting 11 seconds: Get("a") -> null (expired), GetAverage() only counts the data that's still valid.

I asked about the O(1) — it's not amortized O(1), they wanted worst-case O(1). I used an ArrayDeque and got dinged for it. I honestly don't know how you'd achieve worst-case O(1) here (and honestly I don't think it's even possible, given this is a sliding window based on a base timestamp). For the timestamp, the interviewer said something like System.currentTimeMillis() would be fine.

The interviewer's attitude was extremely, extremely rude, and they didn't want to answer my questions either. Before I'd even written any code, they kept circling around when hash collisions happen, the time complexity of hash collisions, and the time complexity of rebalancing in Java after a hash collision.

The team is the Ingestion team, and after the manager interview I really felt like it was a great team.

But this interviewer was just way over the line — I don't want to work with them. While I was writing code they interrupted me several times asking why I wrote it this way, and I explained each time. Honestly it felt like the interviewer wasn't there to help me, they were there to make things difficult for me.

I've interviewed at a bunch of companies now, and this was the one round where the experience was really, really bad.

In the end, interviewing is a two-way street. Wishing everyone good luck.