1) Three points are given A(x1, y1), B(x2, y2), C(x3, y3). Write a method returning an array of points (x, y) inside the triangle ABC. 2) Implement Stack that also has method that returns maxumum element on stack. Faster solution for more points. 3) Implement Iterator to walk through files in a directory and all subdirectories. Interface of an API to be used was given. 4) a) In-order visit of nodes of binary search tree is forming string (in-order visit: visit node, than visit in-order left son, the visit in-order right son). Based on the output string for the in-order visit, reconstruct the binary tree. Example: String 5214768 reconstructs binary search tree 5 2 7 1 4 6 8 b) Can you reconstruct the binary search tree based on string for pre-order visit (pre-order visit left son, then visit the node, then pre-order visit right son)? Why, or why not? 5) a) In the game of battleships, ten 1-square ships are placed on 10X10 board. What’s the probability that two 1-square ships on opponents’ boards are in the same spot. b) In the game of battleships, eight 1-square ships and also one 2-square ship are placed on 10X10 board. What is the probability that two ships intersect? 6) On the chess board a rook is placed in the corner. Two squares on the board are occupied. Write a method to return all possible 3 moves for the rook to go from its corner to the opposite corner, but it cannot go through occupied squares. 7) Give an example of function f(x) with no breaks knowing the following: * f(-2) = -1 * f(2) = 1 * f(6) = -1 * the surface under f(x) above x axis is less than 1.99 Solution by segments don’t give max points. Solution should be the same expression for the whole range [-2, 6]. Tip: function doesn’t have to be differentiable, just continuous. 1. Osmisliti sto efikasniji algoritam koji ce za dati niz brojeva naci tri clana cija suma je jednaka nuli. Objasniti realizaciju nad nizom {7, -5, 2, 3, -4, -4, 2, 0, 1, -6}. 2.Dat je niz od N stringova jednake dužine L. Potrebno je proveriti da li zadati string postoji u tom nizu. Na koje načine se ovo sve može obaviti? Koje su prekalkulacije potrebne? Koje su složenosti svakog od pristupa? Koji je najbolji? Osmisliti test primere za koje su ovi algoritmi najsporiji. 3. Data je sortirana skip lista. Koliko je potrebno provera da bi se utvrdilo da li sadrži zadati element. Koje još strukture imaju 2n pokazivača (što je slučaj kod skip liste)? 4. Dato je K sortiranih nizova različitih dužina sa ukupno N elemenata. Potrebno je formirati jedan sortirani niz dužine N koji bi sadržao sve elemente gde je složenost Θ(n*logk) 5. Data su dva realna intervala. Iz oba intervala se bira po jedan nasumičan broj, sa uniformnom raspodelom. Potrebno je odabrati jedan od ova dva intervala tako da je veći od ona dva nasumična broja češće baš iz tog intervala. Tačnije, potrebno je odrediti interval za koji je veća verovatnoća da je veći od dva broja generisan iz tog intervala. 6. U komunikaciji sa serverom klijent dobija neki niz objekata nepoznate dužine. Jedina metoda dostupna klijentu jeste dobavljanje sledećeg objekta, koja vraća null u slučaju dolaska do kraja niza. Nakon što se dođe do kraja niza, potrebno je da klijent nasumično vrati jedan od primljenih objekata, sa uniformnom raspodelom. Ne postoje resursi za čuvanje svih objekata. 7. Dato je binarno stablo i dva pokazivača na elemente iz tog stabla. Potrebno je odrediti njihovog prvog zajedničkog pretka. Kako bi izgledao algoritam ako čvor osim pokazivača na svoju decu ima i pokazivač na roditelja? 8.Dato je binarno stablo. Svaki čvor osim pokazivača na decu ima i pokazivač na sledeći čvor u tom nivou (prvi desno od njega), koji nije inicijalizovan. Potrebno je inicijalizovati ove pokazivače za sve čvorove. 9. Potrebno je osmisliti chat sistem za veliku kompaniju sa puno zaposlenih. Kako bi on bio organizovan? Šta bi se nalazilo sa serverske, a šta sa klijentske strane? Facebook intervju 1. Datu jednostruko povezanu listu potrebno je obrnuti tako da njeni članovi budu u obrnutom redosledu. (1 4 5 6 2 -> 2 6 5 4 1) 2. Potrebno je implementirati komandu cd (change directory). Funkcija prima dva parametra: apsolutnu putanju do trenutnog foldera i apsolutnu ili relativnu putanju do željenog foldera. Imena foldera se sastoje samo od slova, putanje su ispravno formatirane, a putanja do željenog foldera može sadržati i tačku ili dve tačke (trenutni, odnosno prethodni folder). 3. Dat je niz brojeva. Potrebno je proveriti da li neka tri broja iz tog niza imaju zbir 0. 4. Potrebno je generisati partitivni skup za zadati skup brojeva. 5. Potrebno je izračunati koren broja bez korišćenja funkcije sqrt(). Kvadrat dobijene vrednosti može da odstupa od vrednosti zadatog broja za određenu toleranciju. 6. Data je funkcija bool fair_coin() koja u 50% slučajeva vraća true. Potrebno je napisati funkciju koja će u N procenata slučajeva vraćati true (zadato je dozvoljeno odstupanje). 1.Dat je skup rimskih cifara (I, V, X, L, C, D, M). Potrebno je formirati rimske brojeve od svih ovih cifara tako da zbih brojeva bude minimalan. Za maksimalan broj bodova traži se linearna složenost. 2.Dato je binarno stablo. Potrebno je obeležiti čvorove čiji je broj elemenata u njihovom podstablu (računajući i koren) manji od dubine tog čvora. Traži se linearna složenost. 3.Na raspolaganju vam je N kutija i dozvoljeno je M bacanja. Kutije se bacaju sa nekog od spratova zgrade beskonačne visine. Ukoliko se kutija baci sa nekog sprata iznad sprata X, ona će se razbiti. Potrebno je sa najviše M bacanja kutija odrediti najviši sprat (tj. najveću vrednost koju algoritam uspe da pronađe) sa kojeg je moguće baciti kutiju a da se ne razbije. 4.Dat je pravilno formiran logički izraz koji se sastoji od karaktera T, F, &, |, !, (, ) i razmaka. Potrebno je odrediti njegovu vrednost u linearnom vremenu. 5.Dat je neki tekst i željeni broj linija teksta. Potrebno je odrediti minimalnu širinu ekrana (u karakterima) takvu da tekst može da stane u željeni (ili manji) broj linija, bez prelamanja reči. Traži se nlogn složenost.