Quali sono i puzzle standard chiesti nelle interviste di programmazione?

Ho dato un bel po' di interviste durante l'anno scorso, soprattutto per la posizione di stagista in ingegneria del software. Cercherò di suddividere le domande poste in due sezioni di base, problemi algoritmici e puzzle.

Tuttavia, la maggior parte delle interviste di programmazione raramente consiste in puzzle. Quasi tutte le interviste che ho fatto erano per aziende "Tier-1" e non mi è stato chiesto un puzzle in nessuna di esse. La maggior parte degli intervistatori vi chiederà problemi algoritmici e a volte qualche problema di progettazione.

Puzzles

• Si gioca un gioco in cui vi sono concessi 3 lanci di dadi. Se in qualsiasi fase si decide di terminare il gioco, si ottiene un numero di monete pari al valore dell'ultimo lancio di dadi. Qual è il numero massimo di monete che si può ottenere?
• Gettando un uovo da un numero di piano maggiore di [math]N[/math] di un edificio di 100 piani lo si rompe. Devi trovare [math]N[/math], minimizzando il numero di cadute per il caso peggiore, se hai 2 uova con te.
  
• Quanti punti ci sono sul globo dove camminando un miglio a sud, un miglio a est e un miglio a nord raggiungi il luogo da cui sei partito?
  
• Dato un insieme di cifre, trova la somma di tutti gli [math]N[/math] numeri di cui ogni cifra appartiene all'insieme di cifre dato.
  

Problemi algoritmici

• Trova se un numero è presente in un array ordinato che è stato ruotato circolarmente.
• Data una sequenza, trovare se la sua traversata pre-ordinata di un albero di ricerca binario valido.
• Data una matrice [math]N*M[/math] di numeri da [math]1[/math] a [math]N*M[/math] (ogni numero ricorre solo una volta), trovare il percorso lessico-graficamente più piccolo dall'alto a sinistra al basso a destra spostandosi solo a destra o in basso.
• Dato un float [math]N[/math], trovare [math]\sqrt{N}[/math].
• Dato un insieme di tagli, trovare il numero minimo di monete richiesto per formare una somma. Una moneta di qualsiasi taglio può essere usata più tipi.
• Dato l'insieme dei tagli, trova il numero minimo di tagli distinti richiesti per formare una somma. Una moneta di qualsiasi taglio può essere usata più tipi.
• Dati [math]N[/math] palloncini, se si fa scoppiare [math]i^{th}[/math] palloncino si ottiene [math]A_{i-1}*A_i*A_{i+1}[/math] monete e quindi [math]i^{th}[/math] e [math](i+1)^{th}[/math] palloncini diventano adiacenti. Trova il numero massimo di monete che puoi raccogliere.
• Data una stringa [math]S[/math] e un insieme di caratteri, trova la più piccola finestra in [math]S[/math] che contiene il dato insieme di caratteri.
• Data una matrice non ordinata dove ogni elemento è alla distanza massima di [math]K[/math] dalla sua posizione corretta (cioè la posizione nell'array ordinato).Cioè la posizione nella matrice ordinata), ordinare la matrice.
• Dato un albero binario, controllare se è un albero di ricerca binario.
• Trovare il numero di componenti connesse nere in una matrice bianca e nera. Un'altra versione è se la matrice è tridimensionale.
• Ordina un array memorizzato su un nastro, dove esiste un puntatore che punta ad un elemento ad un indice e le operazioni permesse sul puntatore sono lettura, scrittura, avanzamento, goto beginning. Avete 5 nastri vuoti ciascuno di dimensione 100 che potete usare.
• Dati [math]N[/math] array ordinati, trovate il [math]K^{th}[/math] elemento più piccolo se tutti gli array sono fusi.
• Avete 4 stringhe, potete riordinarle in qualsiasi modo vogliate. Devi massimizzare il prefisso comune più lungo di tutte e 4 le stringhe dopo la riorganizzazione.
• Ci sono [math]N[/math] punti nel piano 2-D. Ogni punto ha un colore R, B, G. Trova un triangolo di area maggiore con questi punti tale che uno dei lati del triangolo sia parallelo a uno dei due assi e ogni vertice abbia un punto di colore diverso.
• Trova le terzine in un dato array che sommano a zero.
• Una stringa come a2b3c5 si decomprime in aabbbccccc. Comprimere una data stringa.
• Clonare una lista collegata.
• Clonare un grafo dato in forma di lista di adiacenza.
• Invertire una lista collegata.
• Dato un programma python determinare la linea in cui si verifica un errore di compilazione dovuto all'indentazione.
• Dato un dizionario e varie query di stringhe, per ogni query restituire le stringhe presenti nel dizionario anagrammate alla stringa della query.
• Trova la mediana di un flusso di numeri interi in corso ogni volta che un nuovo numero viene aggiunto al flusso.

Anche se avrei potuto risolvere ognuno di essi, ho fatto schifo in alcuni di essi nei miei colloqui e non sono riuscito a passare in nessuna azienda d'oltreoceano. Di tutte le aziende indiane a cui avevo fatto domanda, ho eliminato tutti i loro processi di intervista, però.

Suppongo che il tuo motivo dietro questa domanda potrebbe essere la preparazione per le interviste tecniche e anche se ho risposto alla domanda, non mi dispiace darti qualche consiglio non richiesto. Il tuo approccio attuale deve essere qualcosa come visitare siti web come glassdoor, geeksforgeeks ecc. e risolvere attraverso problemi e puzzle o probabilmente andare a caso attraverso i blog sparsi su tutta l'internet. C'è molto poca struttura al contenuto che si sta preparando in questo modo.

Considerando lo scenario, uno dei miei anziani ha iniziato InterviewBit.com. Tutti i contenuti sono ben strutturati; vi sembrerà di avere un allenatore personale. Ci sono varie caratteristiche che si possono sentire dal co-fondatore stesso. Anshuman Singh'risposta a Come posso ottenere un lavoro a Facebook o Google in 6 mesi? Ho bisogno di un piano di lavoro conciso per costruire un set di abilità abbastanza buono. Dovrei unirmi a qualche altra start-up o costruire i miei progetti/start-up? Dovrei concentrarmi solo sulla pratica di strutture dati e algoritmi?