Practice after the lessons, not instead of them. Lesson 6 and lesson 7 teach every move these use; the banks give you problems you have not seen worked, which is what the round gives you.
Ten transfer problems for the coding round
Context. Every listing so far was solved in front of you, so writing one cleanly proves recall, not transfer. The round itself gives you a problem you have not seen worked, so some practice has to as well (author's reading). These ten are standard problem types that lesson 6 has not solved. Each one yields to a pattern from the selector, and none is named here. The statements are the author's wording, and every example and limit in the table is invented. The solutions are in the Solutions appendix; do not open one until you have scored your own attempt.
The targets are the author's estimate (not measured). Do them after the lesson 6 drill set, one per sitting on the 45-minute clock of Figure 6.1; T8 is the hard one. The ten problems, with an example and limits for each:
Table: #, Problem, Invented example, Limits, Target (10 rows)
| # | Problem | Invented example | Limits | Target |
|---|---|---|---|---|
| T1 | Rearrange an array of integers, in place, into the next larger arrangement in dictionary order. If it is already the largest, rearrange it into the smallest. Extra space must be O(1). | [1, 3, 5, 4, 2] becomes [1, 4, 2, 3, 5]; [3, 2, 1] becomes [1, 2, 3]. | n up to 105; values may repeat. | 15 min |
| T2 | An array holds only the values 0, 1 and 2 (three colours of ticket). Sort it in place in a single pass, without counting the values first. | [2, 0, 1, 2, 1, 0] becomes [0, 0, 1, 1, 2, 2]. | n up to 105; O(1) extra space. | 10 min |
| T3 | Return the smallest positive integer that does not appear in an unsorted array. You may change the array. | [3, -1, 4, 1] gives 2; [7, 8, 9] gives 1; [] gives 1. | n up to 105; any int values, with repeats; O(n) time, O(1) extra space. | 18 min |
| T4 | Return the longest contiguous part of a string that reads the same in both directions. If several tie, return any one. | "cabbad" gives "abba". | Length up to 1,000; lowercase letters. | 18 min |
| T5 | Say whether a string can be made to read the same in both directions by deleting at most one character. | "radkar" gives true (delete k: "radar"); "abcda" gives false. | Length up to 105. | 12 min |
| T6 | A message of capital letters was coded as numbers, A as 1 up to Z as 26, and the separators were lost. Given the digit string, count the ways to read it back. | "2263" gives 3 (2 2 6 3, 22 6 3, 2 26 3); "1020" gives 1; "100" gives 0. | Length up to 90; the count can pass 231. | 15 min |
| T7 | Given a string and a dictionary of words, say whether the string can be cut into a sequence of dictionary words. A word may be used more than once. | "loopready" with {loop, re, ad, y} gives true; "loopread" with {loop, ready} gives false. | String length up to 300; up to 1,000 words, each up to 20 letters. | 18 min |
| T8 (hard) | Count the ways to place n queens on an n by n chessboard so that no two share a row, a column or a diagonal. | n = 6 gives 4; n = 8 gives 92. | n from 1 to 10. | 30 min |
| T9 | A grid holds 0 (empty), 1 (a working machine) and 2 (an infected machine). Each minute, every infected machine infects the working machines directly above, below, left and right of it. Return the minutes until no working machine is left, or -1 if some never get infected. | {{2, 1, 1}, {0, 1, 0}, {1, 1, 2}} gives 2; {{1, 0, 2}} gives -1; {{0, 2}} gives 0. | Up to 300 by 300. | 13 min |
| T10 | Parcels with weights w must leave in the given order over at most D days. Each day the van takes the next parcels in line until the next one would take it over its capacity. Return the least capacity that ships every parcel within D days. | w = [4, 2, 7, 3, 5, 1] and D = 3 gives 9 (capacity 8 needs 4 days). | n up to 5 × 104; weights 1 to 500. | 20 min |
How to run them: a partner holds this table and the solutions, and reads you only the problem and the example. Each solution carries the one hint a partner may give, which counts as a lost point as on the drill set, and the follow-up the partner asks once you are done. Working alone, cover the solutions, set a timer to the target, and score yourself as on the drill set before you look.
Gave up / revisit when / signal (transfer set). Gave up: problems taken from a company's own list; no printed problem stays unseen once it is printed, so these are standard types this lesson has not worked. Revisit when: you have done all ten. Take fresh ones from a list you have not studied, and keep the rule that nobody names the pattern. Signal: you named the right pattern within five minutes on at least seven of the ten, with no hint.
Next stop: Fifteen machine-coding prompts, 2 min
Fifteen machine-coding prompts
These prompts are the author's own, written for practice. None is taken from any company, and the author does not claim any is asked anywhere. Each row is a drill, not a model answer. Use it in three passes: cover the last two columns and predict the follow-up and the technique yourself; pick two and spend five minutes each writing only the interface the follow-up would touch; build one on the 90-minute plan of lesson 7 and count the files the follow-up edits. Rows marked with threads need the concurrency section of lesson 7.
Table: #, Prompt, Entities, A follow-up an interviewer might add, Technique exercised (15 rows)
| # | Prompt | Entities | A follow-up an interviewer might add | Technique exercised |
|---|---|---|---|---|
| 1 | Parking lot (lesson 7 builds it) | Spot, Ticket, Gate, pricing rule | "Add a monthly pass." Then "two gates, one last spot." (threads) | Strategy, decorator, repository; lock around check and act |
| 2 | Expense splitter | User, Group, Expense, split rule, Balance | "Split 100 rupees three ways so the shares sum to 100." Then "split by percent." | Strategy; integer paise with an explicit remainder rule |
| 3 | Rate limiter | Limiter, Rule, Clock, Bucket | "Different limits per user." Then "two requests at once." (threads) Then "no burst at the window edge." | Strategy, injected clock; atomic check-and-decrement; sliding log |
| 4 | Elevator | Car, Request, Scheduler, Door | "Add a scheduling policy." Then "a request arrives while moving." | State, strategy; deterministic ticks in tests |
| 5 | LRU cache with expiry | Cache, Entry, Clock, EvictionPolicy | "Add LFU." Then "entries expire." Then "make get thread-safe." (threads) | Strategy; map plus linked list; a get is a write |
| 6 | Notification broker | Topic, Subscriber, Message, Channel | "A slow subscriber must not block the others." Then "retry a failed delivery." (threads) | Observer with one bounded queue per subscriber |
| 7 | Seat booking | Show, Seat, Hold, Booking | "A hold expires after five minutes." Then "two users, one seat." (threads) | State per seat; atomic check-then-act; sorted locks for several seats |
| 8 | Vending machine | Machine, Slot, Coin, State | "Refund on cancel." Then "add card payment." | State as classes with a transition table; strategy for payment |
| 9 | Food ordering | Restaurant, Menu, Cart, Order, Rider | "Add a coupon." Then "stack two." Then "reassign the rider if one drops." | Strategy for discounts; all-or-nothing hold; idempotency key; state |
| 10 | Logger framework | Logger, Level, Appender, Formatter | "Add a file sink." Then "a level per package." Then "the disk is slow." | Fan-out to sinks; bounded queue with a drop policy |
| 11 | Task scheduler | Task, Entry, Clock, Queue | "Run every 10 seconds." Then "the machine slept for a minute." | Priority queue with a tie-break; injected time; late-run policy |
| 12 | Snake and ladder | Board, Jump, Player, Dice | "Bounce back from 100." Then "a six gives another turn." | One jump type for both; injected dice |
| 13 | Tic-tac-toe | Board, Move, Status | "Add undo and redo." Then "make it n by n." | Command with an exact inverse; line counters |
| 14 | Meeting-room booking | Room, Employee, Booking, Calendar | "Add recurring bookings." Then "two people book at once." (threads) | Overlap test with a sorted map; validate before write |
| 15 | Wallet transfer | Account, Transfer, Entry, idempotency key | "The client retries with the same key." Then "two transfers in opposite directions at once." (threads) | putIfAbsent on the key; double entry; locks in id order |