Największa suma mniejsza niż K
Dzisiaj zajmiemy się następującym problemem rekrutacyjnym: Mamy daną tablicę A[1..N] oraz wartość K. Chcemy znaleźć spójną podtablicę A[i..j] o jak największej sumie, ale mniejszej od K. Zacznijmy od pytania do rekrutera: Kandydat: Czy tablica może zawierać elementy ujemne?Rekruter: Tak. To pytanie wynika z tego, że istnieje algorytm rozwiązujący problem w czasie liniowym dla tablic z […]
Turniej szachowy
Dzisiaj rozwiążemy następujące zadanie rekrutacyjne: W turnieju szachowym gra n graczy. Turniej będzie trwał n-1 dni i w każdym dniu, każdy szachista będzie rozgrywał jedną partię. Każdy z zawodników powinien zagrać z każdym innym dokładnie raz. Napisz program, który stworzy rozpiskę rozgrywek. Zaczniemy jak zawsze od pytań do rekrutera. Kandydat: Czy możemy założyć, że n […]
Algorytm żółwia i zająca
Dana jest tablica A[0..n] zawierająca liczby {1..n}. Napisz algorytm, który znajdzie dowolną liczbę występującą w tablicy więcej niż raz. Algorytm powinien działać w czasie liniowym i zużywać jedynie stałą ilość dodatkowej pamięci. Kandydat: Czy można modyfikować tablicę wejściową?Rekruter: Nie. Zadanie to pojawia się czasem na rozmowach kwalifikacyjnych w pewnej firmie (kod trzydzieści trzy – dziesięć), […]
Fioletowe żabki
Pewna czarownica omyłkowo odstawiła fiolkę z bardzo silną trucizną na półkę z innymi fiolkami i teraz nie pamięta, która z nich zawiera niebezpieczną substancję. Postanowiła ona przetestować fiolki za pomocą żabek, które są na truciznę odporne, ale u których po wypiciu trucizny następuje efekt uboczny w postaci zmiany koloru na fioletowy. Zmiana koloru następuje w […]
Pionek na planszy
Podczas rekrutacji, moglibyśmy trafić na następujące zadanie: W linii prostej znajduje się n pól. Na każdym polu znajduje się pewna liczba całkowita. Na polu z numerem pierwszym znajduje się pionek. Pionek może poruszać się po planszy w prawą stronę, ale w każdym kroku nie może poruszyć się o więcej niż k pól. Jaka jest możliwie […]