Allowed R6 · Within policy
{
"slug": "nim-game",
"title": "Nim Game",
"difficulty": "easy",
"tags": [
"coding",
"algorithms-theory",
"technical",
"swe",
"intern"
],
"is_free": true,
"locked": false,
"frequency": 0.333,
"last_reported_at": "2025-07-21T17:12:58.568788Z",
"url": "https://www.mokabla.com/en/c/incorta/nim-game",
"agent": {
"page": "https://www.mokabla.com/agent/en/c/incorta/nim-game",
"question": "https://www.mokabla.com/agent/_call/get_question?company=incorta&question=nim-game"
},
"company": {
"slug": "incorta",
"name_en": "Incorta"
},
"body_md": "## What they ask\n\nA heap holds `n` stones. You and the interviewer take turns, and on every turn a player must remove 1, 2 or 3 stones. Whoever removes the last stone wins. You always move first, and both sides play perfectly. Write a function that returns `true` if you can force a win for a given `n`.\n\nThey usually let you brute-force it first with recursion or a small DP table, then ask you to look at the table and find the pattern.\n\n## Examples\n\n- `n = 4` returns `false`: whatever you take (1, 2 or 3), the opponent takes the rest and wins.\n- `n = 1`, `n = 2`, `n = 3` all return `true`: you just take everything.\n- `n = 7` returns `true`: take 3, leave 4, and now the opponent is in the losing position above.\n\n## Constraints\n\n- `1 <= n <= 2^31 - 1`, so an O(n) table will not pass the largest inputs.\n\n## What they look for\n\n- Noticing that every multiple of 4 is a losing position and being able to say why (from any non-multiple of 4 you can always hand the opponent a multiple of 4, and from a multiple of 4 you cannot).\n- A one-line O(1) answer after the reasoning, not before it.\n- Clean explanation out loud; this was a 30-minute intern round and the interviewer cared more about the argument than the code.",
"follow_ups_md": "- What changes if a player may take 1 to `k` stones instead of 1 to 3?\n- What if the player who takes the last stone loses instead of wins?\n- Prove the multiple-of-4 rule by induction on `n`.",
"access": "Question bodies are paid content: a person buys 30 days of access per company (200 EGP or 200 points) in the human app. Agents get titles, tags and difficulty; bodies only for free questions."
}