Mani intervijas jautājumi: apgriez masīvu otrādi, un pazudušās monētas

Kaut kur ap 2010.–2011. gadu es sāku piedalīties darba intervijās ar jauniem cilvēkiem. Sākumā mēs vienkārši runājām, un daudzi uz jautājumiem atbildēja pieklājīgi, pat labi.

Skaitļi, kas dalās ar 5. Reiz atnāca cilvēks, kurš iepriekš bija strādājis valsts iestādē. Es palūdzu viņam uzrakstīt vienkāršu funkciju: ir skaitļu masīvs, izvadi visus, kas dalās ar 5. Elementārs uzdevums. Es gaidīju kaut ko glītu C# ar LINQ:

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

Tā vietā viņš sāka iet cauri visiem skaitļiem no nulles līdz int.MaxValue ar soli 5 un katram pārbaudīt, vai tas ir masīvā:

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

Tas ir ne tikai cikls pāri diviem miljardiem skaitļu — tas arī nekad nebeidzas. int.MaxValue ir 2 147 483 647, kas nedalās ar 5, tāpēc i vienkārši tam pārkāpj pāri. Tad notiek pārpilde, i kļūst negatīvs, un meklēšana sākas no jauna. Viņam nebija ne jausmas, ko viņš raksta.

Tad es sapratu: cilvēkiem obligāti jādod kaut kas, ko uzrakstīt uz papīra. Kaut kas vienkāršs.

Apgriez masīvu otrādi. Pēc tam mans mīļākais uzdevums kļuva masīva apgriešana otrādi. Un cilvēki uzķērās uzreiz.

Pirmā kļūda ir standarta: cikls iet no pirmā elementa līdz pēdējam, un masīvs tiek apgriezts divreiz.

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;
}

Es viņus pakaitināju: „Nu, palaižam — ko mēs redzam?” Tieši to pašu, ar ko sākām, un viņi lauzīja galvu, kāpēc. Tālāk es viņus noķēru uz vidējā elementa: ja garums ir nepāra, tas tiek samainīts pats ar sevi — „ak, velns, tiešām”. Un klasika ar indeksu: a[a.Length - i] nevis a[a.Length - 1 - i], kas jau pašā pirmajā solī iziet ārpus masīva robežām.

Reiz atnāca kandidāts, kurš bija gandrīz CTO vai arhitekta līmenī. Es teicu: uzraksti nelielu programmu. Viņš teica: „Nerakstīšu.” Es teicu: „Tad uz redzēšanos.” Viņš teica: „Uz redzēšanos,” un aizgāja.

Cilvēki bieži jautāja: kāpēc uz papīra, nevis datorā? Tāpēc, ka uzdevums ir elementārs. Datorā es dotu kaut ko lielu, uz visu vakaru. Šeit mēs kopā pasēžam piecas vai desmit minūtes un pa ceļam apspriežam teoriju. Manuprāt, kārtīgs programmētājs vispirms precizē uzdevumu: cik liels ir masīvs, kādi skaitļi, kāda tipa, kādi ierobežojumi.

Divi pavedieni un viens maks. Vēlāk, kad mēs veidojām Blockchain Cuties, mums bija vairāki serveri, katrā vairāki pavedieni, un dati datubāzē pazuda. Tas bija mans pirmais gads ar Java: pirms tam es pārsvarā biju rakstījis klienta puses lietas, vienpavediena translatorus vai Unity, kur daudzpavedienu gandrīz nav, toties ir daudz 3D un optimizācijas. Un es ar izbrīnu sapratu, ka mani paša kolēģi, kas strādāja ar serveriem, nesaprata konkurento piekļuvi.

Tā radās mans klasiskais uzdevums. Divi pavedieni vienlaikus caur ORM — Hibernate — nolasa no datubāzes vienu un to pašu objektu: spēlētāja maku ar 10 monētām. Vienā pavedienā spēlētājs kaut ko nopērk par 5, paliek 5. Otrā kāds no viņa kaut ko ir nopircis, tāpēc jāpieskaita 3, sanāk 13. Abi saglabā. Kas galu galā nonāk datubāzē?

Cilvēks kasa pakausi: „Nu, 13.” — „Un kas nav kārtībā?” — „Velns, nezinu. Laikam transakcijas.” — „Un kā transakcijas palīdzētu?” Un viņš sāk apjukt.

Transakcijas vienas pašas te neglābj. Transakcija garantē, ka tās ieraksti vai nu visi tiek izpildīti, vai neviens, bet pēc noklusējuma izolācijas līmenī abas transakcijas mierīgi nolasa 10, un katra ieraksta savu vērtību. Stingrāki izolācijas līmeņi gan palīdz — tad datubāze atceļ vienu no transakcijām, un tā ir jāatkārto, — tāpat kā skaidra rindas bloķēšana. Bet zem slodzes bloķēšana ir lēnāka.

Es uzdevumu nolaidu uz zemes: „Pieņemsim, tu raksti biļešu pārdošanas programmu. Kā sanāk, ka tev dažreiz pazudīs dati?” — „Velns, tiešām, pazudīs.” — „Labi, piedāvā variantus, un es došu mājienus.” Un cilvēki sāka kraut vienu uz otra: mērīsim laiku, pārbaudīsim, vai ierakstījās vai ne. — „Jā, bet šīs pārbaudes vidū atkal var iespraukties cits process.” — „Ak nē, tad kā to dara?”

Patiesībā ir četri vai pieci labi risinājumi, un nevienam no tiem nav jāzina Hibernate īpatnības:

• Atomārs atjauninājums SQL: UPDATE wallet SET coins = coins - 5 WHERE id = ? AND coins >= 5 — datubāze pati rēķina no pašreizējās vērtības, un mīnusos nonākt nevar.
• Serializēt: viens worker serviss, kas apstrādā maka operācijas pa vienai.
• Virsgrāmata (ledger): glabāt nevis bilanci, bet katru izmaiņu, un bilanci rēķināt no tām.
• Pesimistiskā bloķēšana: nobloķēt rindu uz operācijas laiku.
• Optimistiskā bloķēšana: versijas numurs ierakstam. To mēs parasti arī izmantojām: 99% gadījumu konflikta nav, un viss iziet cauri. Bet, ja ierakstīšana neizdodas, mēs pārrēķinām un palaižam transakciju no jauna.

Ko es no tā paņēmu: man nepatīk jautāt par ietvaru iekšējo uzbūvi. Mani vairāk interesē, kā cilvēks ir gatavs domāt un mācīties tieši tagad, kopā ar mani: es dodu mājienus uz vietas un vēroju, kā viņš spriež. Un neliels piecu minūšu uzdevums uz papīra pastāsta par programmētāju vairāk nekā stunda runāšanas.