Send a brief
RULV
← All posts
← →
2010–2025

My interview questions: reverse an array, and the lost coins

Somewhere around 2010–2011 I started taking part in interviews for new people. At first we just talked, and many people answered the questions decently, even well.

Numbers divisible by 5. Once a man came who had previously worked at a government office. I asked him to write a simple function: there’s an array of numbers, print all the ones divisible by 5. An elementary task. I expected something neat in C# with LINQ:

numbers.Where(x => x % 5 == 0).ToList().ForEach(Console.WriteLine);

Instead he started going through every number from zero to int.MaxValue in steps of 5 and checking for each whether it was in the array:

for (int i = 0; i != int.MaxValue; i += 5)
    if (numbers.Contains(i))
        Console.WriteLine(i);

Not only is that a loop over two billion numbers — it also never ends. int.MaxValue is 2,147,483,647, which isn’t divisible by 5, so i simply steps over it. Then it overflows, i goes negative, and the search starts all over again. He had no idea what he was writing.

That’s when I understood: people must be given something to write on paper. Something simple.

Reverse an array. After that my favourite task became reversing an array. And people got caught right away.

The first mistake is the standard one: the loop runs from the first element to the last, and the array gets reversed twice.

for (int i = 0; i < a.Length; i++)
{
    int t = a[i];
    a[i] = a[a.Length - 1 - i];
    a[a.Length - 1 - i] = t;
}

I’d tease them: “So, we run it — what do we see?” Exactly what we started with, and they’d rack their brains over why. Next I’d catch them on the middle element: with an odd length it gets swapped with itself — “oh, damn, right.” And the classic with the index: a[a.Length - i] instead of a[a.Length - 1 - i], which runs off the end of the array on the very first step.

Once a candidate came who was almost at the level of a CTO or an architect. I said: write a little program. He said: “I won’t.” I said: “Then goodbye.” He said: “Goodbye,” and left.

People often asked: why on paper and not on a computer? Because the task is elementary. On a computer I’d give something big, for a whole evening. Here we sit together for five or ten minutes and discuss the theory along the way. To my mind, a decent programmer first of all clarifies the task: how big is the array, what numbers, of what type, what constraints.

Two threads and one wallet. Later, when we were making Blockchain Cuties, we had several servers, several threads inside each, and data in the database was getting lost. It was my first year of Java: before that I had mostly written client-side things, single-threaded translators or Unity, where there’s hardly any multithreading but plenty of 3D and optimisation. And I realised to my surprise that my own colleagues who worked on the servers didn’t understand concurrent access.

That’s how my classic task came about. Two threads read the same object from the database at the same time through an ORM — Hibernate: a player’s wallet with 10 coins. In one thread the player buys something for 5, leaving 5. In the other someone has bought something from him, so 3 must be added, giving 13. Both save. What ends up in the database?

The person scratches their head: “Well, 13.” — “And what’s wrong?” — “Damn, I don’t know. Transactions, probably.” — “And how would transactions help?” And they start getting confused.

Transactions alone don’t save you here. A transaction guarantees that its writes either all go through or none do, but at the default isolation level both transactions happily read 10 and each writes its own value. Stricter isolation levels do help — the database then aborts one of the transactions and it has to be retried — and so does an explicit row lock. But under load, locks are slower.

I’d bring the task down to earth: “Say you’re writing a ticket-selling program. How come you’ll sometimes lose data?” — “Damn, right, I will.” — “Fine, suggest some options, and I’ll give hints.” And people would start piling things up: we’ll time it, we’ll check whether it was written or not. — “Yes, but in the middle of that check another process can squeeze in again.” — “Oh no, so how do you do it?”

Actually there are four or five good solutions, and none of them requires knowing Hibernate’s quirks:

  • An atomic update in SQL: UPDATE wallet SET coins = coins - 5 WHERE id = ? AND coins >= 5 — the database computes from the current value itself, and you can’t go negative.
  • Serialise: one worker service that handles wallet operations one at a time.
  • A ledger: store not the balance but every delta, and compute the balance from them.
  • A pessimistic lock: lock the row for the duration of the operation.
  • An optimistic lock: a version number on the record. That’s what we usually used: 99% of the time there’s no conflict and everything goes through. And if the write fails, we recompute and rerun the transaction.

What I took from it: I don’t like asking about the internals of frameworks. I’m more interested in how a person is ready to think and learn right now, together with me: I give hints on the spot and watch how they reason. And a small five-minute task on paper tells you more about a programmer than an hour of talk.