Domande dell'intervista sul mazzo di carte e su quella a matrice sparsa [chiusa]

È un buon inizio con le carte. Ecco la mia idea se vuoi ottenere una modellazione più realistica: dovresti prendere in considerazione il fatto che un mazzo può contenere più o meno di 52 carte (ad esempio se ci sono i jolly, o se è un mazzo euchre, ecc.). Quindi, invece di un array, forse un elenco enumerabile generico (come List<Card> di C #). Ciò renderebbe anche più semplice l'inserimento e la rimozione di singole carte (ad esempio per simulare lo scambio).

Quindi, per mischiare, puoi dividere quella lista in due pile di carte di dimensioni arbitrarie, pop fuori dalla cima e spingerle in una terza lista, selezionando casualmente quale metà scegliere ogni volta. Sarebbe più realistico.

Per quanto riguarda la seconda domanda, mi sembra ragionevole.

Bene, mescolare in modo statisticamente corretto è sorprendentemente difficile . Dato che so che è complicato, cerco semplicemente di farlo correttamente.

Se lo fai da solo, assicurati di farlo funzionare alcune migliaia di volte per vedere se è corretto. E segnalalo al revisore.

Question 1: how would you represent a standard 52 card deck in (basically any language)? How would you shuffle the deck?

In Java, vorrei usare:

1. ArrayList<Card> deck come tipo di dati e nome.
2. Collections.shuffle(deck) o Collections.shuffle(deck, myRnd) per mescolare il mazzo.

Question 2: how to represent a large sparse matrix? the matrix can be very large... like 1000x1000... but only a relatively small number (~20) of the entries are non-zero.

In Java, memorizzerei solo elementi diversi da zero, in:

1. HashMap<TupleN, Data> matrix come tipo di dati in generale, dove TupleN è una classe valore (con una funzione di hash personalizzata) e contiene posizioni di elementi.
2. In caso di 2 dimensioni li combinerei nel tipo lungo HashMap<Long, Data> m e uso m.get(((Long)i1<<32)+i2); , se ho bisogno di un elemento.

Non è la tecnica migliore per ordinare le carte.
Vedi Kneuth per i dettagli.

Un algoritmo migliore è:

 1) Have a deck of all cards (a)
 2) Have a deck with 0 cards (b)
 3) Pick one card at random from (a) and remove it.
 4) Add picked card to top of (b)
 5) While (a) is not empty goto (3)
 6) (b) is now shuffled.

Nota quando si implementa questo è possibile utilizzare un singolo mazzo. Il segreto è che una volta che una carta è stata selezionata, non viene mai più selezionata (cioè una volta spostata sul mazzo mescolato non viene toccata).

Nella seconda domanda, avrei chiesto quali operazioni avremmo voluto ottimizzare sulla matrice. La migliore implementazione di una matrice sparsa sembrerebbe dipendere dalle operazioni eseguite.

Direi di essere onesto, poiché so che ci sono persone più intelligenti di me che hanno già risolto un problema del genere, e dal momento che non ho mai passato molto tempo a pensarci in particolare perché non viene spesso nella programmazione di reti incorporate, vorrei iniziare guardando gli algoritmi pubblicati o le librerie di terze parti. Vuoi che prenda un paio di minuti per fare una ricerca o ti dica solo il meglio che posso inventare da solo?

Il "meglio che posso inventare da solo" è molto simile al tuo, anche se potrei entrare in ulteriori dettagli dell'applicazione come le strutture dati necessarie per garantire che una carta non venga duplicata tra le mani, "vista" di una carta contro "modello", ecc.

La risposta ad entrambe le domande è "Dipende da cosa vuoi fare con esso".

Una carta da gioco può essere considerata come un elemento del prodotto cartesiano di valori e semi e implementata come una coppia che compone due enumerazioni. Ottimo per le lezioni OO a livello di scuola. Ma se stai implementando, per esempio, una valutazione ottimizzata della mano di poker per un sistema con memoria limitata (ad esempio non puoi usare solo un FSM da 2 GB), non è una rappresentazione utile. Quando l'ho fatto (parzialmente per il problema del Project Euler in questione, in parte perché un amico ha espresso interesse) ho usato un int per 64 bit int per scheda con rappresentazione bit 23456789TJQKA00200300400500600700800900T00J00Q00K00A00C00D00H00S perché il bit bepping può ottenere molte proprietà molto velocemente.

Per le matrici sparse devi davvero pensare a quale tipo di matrici stai implementando e cosa vuoi fare con loro. Le matrici diagonali, ad esempio, sono suscettibili di un'implementazione molto specializzata.

Questo non garantirebbe che non tocchi di nuovo un elemento già posizionato?

for (i = 51; i >= 2; i--) {
  swap(arr[i], arr[rand() % i]);
}

swap(arr[0], arr[1]); //just to be safe.

(riferendosi a Watch out per usare la stessa probabilità per ogni carta ... è un trucco in questo algoritmo.)

In pratica significa mischiare, quindi il risultato finale dovrebbe essere il più casuale possibile (nessuno dovrebbe essere in grado di indovinare la sequenza risultante, data la sequenza originale).

Mi piace l'approccio semplice di Martin, l'unica cosa è che la tua funzione rand () dovrebbe essere buona.

Btw, anche se uso swap algo (senza alcun vincolo sulla revisione), anche quello dovrebbe costituire un buon approccio. l'iterazione dovrebbe essere > = 52/2 = 26 volte.