Domanda intervista classifica FizzBuzz (1), implementando malloc (10) [chiuso]

10

Mi piacerebbe avere la tua opinione sulla difficoltà della seguente domanda di intervista:

Trova il sottoarray contiguo con la somma massima in un array di numeri interi nel tempo O (n).

Questo banale problema sonoro è stato reso famoso da Jon Bentley nelle sue Perle di programmazione in cui lo utilizza per dimostrare tecniche di progettazione dell'algoritmo.

Su una scala da 1 a 10, 1 è il test FizzBuzz (o HoppityHop ) e 10 che implementa la funzione C di stdlib malloc (), come classificherebbe il problema precedente?

Penso che le persone che possono rispondere al meglio a questa domanda siano quelli che hanno letto Perle di programmazione e che hanno provato a risolvere questo problema da soli. Per motivare coloro che non lo hanno fatto, "Programming Pearls" viene presentato più volte nell'elenco dei "Top 10 dei libri di programmazione".

Un paio di commenti potrebbero aiutare a ottenere una valutazione migliore:

  • L'implementazione di malloc () non è così formidabile come sembra. Ad esempio, vedi il linguaggio di programmazione C di K & R. A volte diventa chiesto a Microsoft .

  • CLRS osservazione sulla risoluzione dei problemi: spesso è più difficile risolvere un problema da zero piuttosto che verificare una soluzione presentata in modo chiaro, specialmente quando si lavora sotto vincoli di tempo .

posta blrs 27.02.2011 - 00:21
fonte

4 risposte

17

Questo dipende molto dallo sviluppatore.

Se malloc avesse 10 anni, avrei valutato questo problema come 20. Ma poi di nuovo ho fatto malloc prima e probabilmente potrei rifarlo.

Qualcuno che ha fatto questo problema o conosce l'algoritmo appropriato della parte superiore della propria testa ne farà un 5 e malloc () a 10.

Il problema con questo tipo di domande è che se le hai già fatte prima sono facili e questo è davvero un test per vedere se hai già visto questo algoritmo. Quindi non mi piacciono per le interviste.

Ora per i test in cui si concede allo sviluppatore un paio di giorni è un test perfettamente valido perché se non conoscono l'algoritmo, allora gli dai la possibilità di fare la ricerca e di ottenere la massima velocità ed è un test non solo delle tue conoscenze ma della tua capacità di acquisire nuove conoscenze.

    
risposta data 27.02.2011 - 05:43
fonte
9

Suppongo che la valutazione dovrebbe essere bidimensionale, almeno. FizzBuzz- malloc descrive l'intervallo su un asse, lo chiamerei "complessità tecnologica". Ma questa singola dimensione non è certamente sufficiente per descrivere il problema. Per risolvere il problema in questione, lo sviluppatore dovrebbe pensare più del codice , mentre implementare malloc richiede più disciplina di codifica che creare algoritmi complessi.

Quindi ecco come sistemerei questi problemi:

Perillustrareilmiopunto,hoaggiuntoa sort di fusione parallela alla trama, come, immagino, è un buon esempio di attività sia tecnologicamente che algoritmicamente sofisticate.

    
risposta data 27.02.2011 - 12:38
fonte
2

Penso che sia considerevolmente più difficile di FizzBuzz o HoppityHop: quei due non sono altro che un semplice if-else o un interruttore in un ciclo.

Il sub-array massimo richiederà un'analisi più approfondita del problema sottostante - non è qualcosa che ci si aspetterebbe di vedere in una classe di programmazione per principianti poiché richiede competenze matematiche più elevate rispetto a un problema di tipo FizzBuzz. Questo problema ha una sensazione simile al problema del percorso più breve, che è risolto dall'algoritmo di Dijkstra - forse è una specializzazione del problema del percorso più lungo .

Sulla tua scala da 1 a 10 probabilmente lo classificherei tra 3 e 5.

* Mentre il server non funzionava, ho scoperto che il problema massimo di sottoarray ha una sua pagina su wikipedia.

    
risposta data 27.02.2011 - 01:45
fonte
1

Ne ho dato un 3. Oltre la maggior parte dei programmatori che ho intervistato, ma un problema facile per quelli che ho consigliato per il noleggio.

    
risposta data 27.02.2011 - 01:45
fonte

Leggi altre domande sui tag