W wywiadzie otrzymałem następujący problem (którego już nie udało mi się rozwiązać, nie próbując oszukać mojej przeszłości): Gra rozpoczyna się od dodatniej liczby całkowitej . (Np. ) Liczba ta jest konwertowana na reprezentację binarną, a jest liczbą bitów ustawioną na . (Np. , )A 0 = 1234 N 1 A 0 = b 100 1101 0010 N = 5.
Gracz 1 wybiera liczbę mniejszą niż . musi mieć tylko jeden bit ustawiony na 1. (Np. ). Niech . (Np a_1 = 1234-512 = = 722 B10 1101 0010 ). Ruch jest ważny jeśli B_0 spełnia poprzednich ograniczeń, a liczba bitów ustawionych w A_1 nadal równa n .A 0 B 0 B 0 = b 10 0000 0000 = 512 A 1 = A 0 - B 0 A 1 = 1234 - 512 = 722 = b 10 1101 0010A 1
Gracz 2 kontynuuje od , wybierając prawidłowy , następnie gracz 1 kontynuuje od i tak dalej. Gracz przegrywa, jeśli nie ma już żadnych ważnych ruchów.
Zakładając, że obaj gracze grają optymalnie, określ zwycięskiego gracza za pomocą dość wydajnej metody. (W mojej definicji problemu ograniczeniem było to, że program musi być w stanie dostarczyć rozwiązanie dla kilku milionów liczb wejściowych, które pasują do 32-bitowej liczby całkowitej ze znakiem). Oznacza to, że rozwiązaniem nie musi być w pełni analityczny.
Moim osobistym zainteresowaniem jest ustalenie, czy oczekiwanie ode mnie znalezienia i wdrożenia prawidłowego rozwiązania bez opinii zwrotnej na temat poprawności w ciągu 120 minut, które otrzymałem, było uzasadnione; lub jeśli było to jedno z tych pytań „zobaczmy, czy widzieli już tę zagadkę”.
Nie udało mi się, ponieważ zdecydowałem się wdrożyć coś, co wydawało się rozsądną strategią, która dała mi prawidłowe wyniki dla kilku przypadków testowych, które otrzymałem z góry, zmarnowałam zbyt dużo czasu na szybkie uruchomienie i skończyła się niepoprawnym podawaniem pełna wydajność, gdy mój czas się skończył.
Z perspektywy czasu powinienem był zastosować wyszukiwanie siłowe i zapamiętać częściowe rozwiązania dla małych liczb początkowych, ale z perspektywy czasu zawsze jest 20/20. Jestem jednak ciekawy, czy istnieje inne wspólne podejście, które wymknęło mi się z tropu.