Cosa c'è di sbagliato in questa mia soluzione algoritmica che controlla se una determinata funzione restituisce un array ordinato quando un array viene fornito come input?

Come già detto da @Dipstick, il passaggio 3 può fallire se ci sono duplicati nell'array di input. Per risolvere questo problema e migliorare la complessità temporale, è possibile utilizzare un dizionario con gli elementi dell'array come chiavi e il loro numero di occorrenza come valori. Un tale dizionario può essere creato anche dalla matrice ordinata e non ordinata in O(n) , e devi testare se i dizionari risultanti sono identici, cosa che può essere fatta anche in O(n) .

Si può combinare questo usando un solo dizionario contando il numero totale di occorrenze nell'array non ordinato meno il numero di occorrenze nell'array ordinato. In pseudo codice (presupponendo un valore predefinito di 0 per i valori nel dizionario quando la chiave viene utilizzata la prima volta):

 for(e in ar)
     noOfOccurence[e]+=1; 
 for(e in ars)
     noOfOccurence[e]-=1;

 for(e in noOfOccurence.Keys)
     if(noOfOccurence[e] != 0)
         return false;

 return true;

Il tuo metodo verifica solo che gli array originali e ordinati contengano gli stessi valori, non che contengano lo stesso numero di ciascun valore; per esempio. 1112 passerebbe per 1221

Nel passaggio 3 è possibile, ad esempio, contrassegnare che un determinato valore nell'array ordinato è già stato abbinato (la rimozione dall'array richiederebbe troppo tempo), ma la ricerca non sarebbe più una ricerca binaria come si farebbe premi i valori già utilizzati.

[Ovviamente questo non è un problema se i valori sono univoci ma ciò non è indicato]

Per i miglioramenti della velocità è possibile testare con array noti con risposte preimpostate da controllare o semplicemente eseguire l'array restituito ra controllando ra[n] =< ra[n+1] per tutto n nell'intervallo 0..len(ra-1) complessità di cui è molto basso . È possibile determinare se ogni elemento è presente in ogni matrice contando le istanze di ciascun valore e quindi confrontando i conteggi.

Il tuo test dovrebbe includere anche casi d'angolo come ar=[1] e ar=[] e per un'intervista menzionerei almeno il test per input non validi come array di valori non interi, non-array, ecc., lo so che il comportamento in questi casi è indefinito nel caso in cui è stato fornito, ma una parte del lavoro di un tester è quella di evidenziare omissioni e ambiguità delle specifiche, come ad esempio la gestione degli errori. Se esegui il solo test per ciò che è specificamente nelle specifiche non farai un buon tester e questo tipo di problema è una delle cose che l'intervistatore cercherà.

Mentre dici che l'intervistatore non ha fornito altre informazioni, è stato possibile fare domande? Poiché esiste un solo argomento per la funzione, sarei nel presupposto che la funzione restituisca sempre l'array in ordine di una directory, molto probabilmente in ordine crescente. cioè.

fn([4,1,5]) -> [1,4,5]

Ma ovviamente è una cosa che l'intervistatore dovrebbe confermare per te in quanto influisce sulla risposta. (Inoltre sarebbe molto strano che la funzione restituisca asc OR desc , senza alcun modo di specificare).

Pertanto, l'approccio di mio laico consisterebbe nel passare una matrice non ordinata alla funzione, e quindi confrontarla con un secondo array che sapevo già essere stato ordinato -

expected = [1,4,5]
sorted = fn([4,1,5])
// compare expected and sorted...

Per quanto riguarda i test di base, il processo di confronto di ogni elemento l'uno contro l'altro e anche il confronto di ogni singolo elemento con l'array sorgente sembra contorto - rispetto al confronto con un elenco corretto noto.

  > But to my surprise the interviewer said that this solution is not correct

Se fossi un intervistatore di lavoro mi aspetterei di ottenere la risposta: scrivi un semplice unittest per il metodo di ordinamento con un campione di input non ordinato e l'output previsto (vedere la risposta di @USD Matt)

  > time complexity can be improved.

La tua soluzione sembra a prima vista più completa / complicata del semplice esempio.

Se fossi alla ricerca di uno sviluppatore esperto mi aspetterei che il candidato conosca le unittests e non sia più necessario.

Suppongo che il test automatizzato complesso / completo sia eccessivo e non necessario per lo sviluppo testdriven. Un semplice esempio dovrebbe essere sufficiente.

Se tieni traccia del minimo e del massimo di un array di dimensioni max - min + 1 funzionerà se l'intervallo non è ampio.

Sottrai min da ogni valore, quindi inizia da 0

for(e in input)
     ar[e - min] +=1; 
for(e in sorter)
     ar[e - min] -=1;

for(e in ar)
     if(e != 0)
         return false;

return true;

È possibile verificare la presenza di duplicati mentre si esegue il test per l'ordinamento
Sì binario sarebbe O (n logn) ma potrebbe essere più veloce del dizionario

Fai un passo indietro e guarda questo da un punto di vista semplicistico. Stai facendo il tuo primo passo per essere il test più impegnativo di tempo e di calcolo. Vorrei iniziare con una serie di controlli di integrità che catturano i problemi più evidenti ed evitare di dover (ri) ordinare l'array e confrontare elemento per elemento.

Metti il tuo test per assicurarti che il numero di elementi nel risultato sia uguale al numero di elementi inseriti perché se il numero di elementi non corrisponde a te puoi fallire il test e non andare oltre.

Successivamente verifica che il primo elemento sia inferiore all'elemento precedente.

Se ciò dovesse accadere, controlla tra gli elementi alcuni elementi, ad esempio il primo e l'ultimo, e gli elementi a 1/4 ° segno, 1/2 segno e 3/4 ° segno e assicurati che prima < articolo a 1/4 < oggetto a 1/2 < articolo a 3/4 < scorso.

Supponendo che quei test passino, quindi scaverò nel iterare tutti gli elementi per testare l'integrità del genere. Ma non vorrei ricorrere all'input per confrontare, ma semplicemente iterare i risultati in ordine, confrontando questo elemento con quello precedente e assicurandoti che questo elemento sia più grande di quello precedente. Esegui il bail con un test fallito non appena ne colpisci uno più piccolo del suo predecessore.

Il tempo di esecuzione del test sarà uguale al tempo necessario per ordinare l'elenco ma solo se l'ordinamento è buono. Se l'ordinamento non è buono, il tempo di esecuzione sarà in qualche misura inferiore a quello che sarebbe stato necessario per riordinare e testare. Quanto più piccolo dipende se il valore non riuscito è sul front end dei dati o sul back-end del gruppo di dati.

In genere, c'è qualcosa sui dati che vengono ordinati, e specialmente da dove provengono i dati, che possono indicare i casi in cui è più probabile che si verifichino errori di ordinamento. Se hai il lusso di avere una visione approfondita di queste cose, allora crea dei controlli di sanità per catturare quei casi e metterli in evidenza prima della visita di ogni oggetto per verificare l'ordinamento.