Round 1 was the shopping cart problem that other interview reports have also mentioned, but part 2 seemed a bit different.
You're building a shopping cart for a cooking app. Users can add recipes to their cart. Each recipe has a list of ingredients (e.g., Chicken, Garlic). When the same ingredient appears across multiple recipes, the total count qualifies for bulk discounts.
Part 1 was the same as other reports: add_recipe, remove_recipe, get_total_discounts.
Part 2 asked about checkout and get_version. Every cart operation creates a new version, and once you check out a specific version, everything newer than it gets thrown away.
Version 0: {}
add A
Version 1: {A}
add B
Version 2: {A, B}
checkout(1) — now version 2 gets discarded.
My first instinct was to brute-force it and just store the entire version history, but the interviewer said it needed to be space efficient. So instead the history stores (add, a), (remove, a) pairs, and at checkout time you replay them from the start according to the version number. Then I added a _discard_future_versions.
Round 2 was a tic-tac-toe question.
Given an empty 3x3 tic-tac-toe board, X always moves first. Calculate the total number of legal tic-tac-toe games. The game ends immediately as soon as someone wins or the board fills up. Different move orders count as different games, even if the final board looks the same.
I solved it with backtracking DFS.
The round 1 interviewer was really nice and gave a lot of hints. The round 2 interviewer was really quiet — I got stuck on the backtracking part for a while. I did finish it in the end, but I still got rejected.
Discussion
Loading comments…