Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Lunedì quiz - 1

Periodo di colloqui, domande e rompicapo. Questo è interessante, fonte Amazon.com

Data una matrice binaria (n x m), individuare la grandezza del blocco di ‘uni’ contigui (N, S, O ed E) più grande. Ad esempio nella matrice qui sotto

0011000000
0011000100
0011001100
0001111100
0000000001
1111111111
0011110010
0000001111
0000000010

il blocco più grande è quello evidenziato con 21 uni.

-quack

Potrebbero interessarti anche:
Commenti (43): [ Pagina 1 di 2  - più vecchi ]
14. suc
martedì 12 ottobre 2010 alle 2:28 PM - IE 8.0 Windows Vista
   

e se sommiamo gli uni nelle colonne o nelle righe? si riesce a trovare un dato importante? boh

   
15. Miki28
martedì 12 ottobre 2010 alle 3:03 PM - chrome 6.0.472.63 Windows 7
   

@neronotte: sorry, letto troppo in fretta

   
16. lol
martedì 12 ottobre 2010 alle 4:48 PM - chrome 6.0.472.63 Windows 7
   

avevo già incontrato questo problema ma non mi ricordo la soluzione lol.

 

 

   
17. Edward
martedì 12 ottobre 2010 alle 6:42 PM - firefox 4.0 Windows 7
   

<puffo brontolone>Io odio i pattern!</puffo brontolone>

 

Edward

   
18. il nonno
martedì 12 ottobre 2010 alle 6:51 PM - IE 7.0 Windows 7
   

e' equivalente ad un algoritmo di fill, una volta trovato un 1 si inizia a "riempire" la matrice di zeri ricorsivamente... poi sicuramente ci sono algoritmi piu' efficienti, ma questo funziona in modo semplicissimo.

   
19. Paperino
martedì 12 ottobre 2010 alle 7:40 PM - chrome 6.0.472.63 Windows 7
   

@Edward: senza scomodare le matrici

@nonno: è simile, ma se usi il flood fill non puoi ottimizzare

@Mario: no, è che ci scambiamo queste domande come le figurine Panini.

   
20. neronotte
mercoledì 13 ottobre 2010 alle 12:02 AM - chrome 6.0.472.63 Windows 7
   

Una possibile ottimizzazione del mio algoritmo potrebbe essere quella di eseguire il flood degli considerando la direzione di spostamento. Es., considerando che ci si muove sempre dall'angolo in alto a sx verso l'angolo in basso a dx, una volta incontrato il primo 1 è inutile verificare le caselle [row-1, col] e [row, col-1], perchè sicuramente sono state già visitate. Nelle mosse susccessive si può considerare allo stesso modo il gradiente di spostamento ed evitare di eseguire la verifica su caselle sicuramente già visitate.

   
21. Blackstorm
mercoledì 13 ottobre 2010 alle 12:19 AM - firefox 3.6.10 Windows 7
   

Ma sbattere la matrice in un array e calcolare la somma? si trova un 1, nello spazio di m bit si contano i contingui e poi si somma m al primo bit trovatoe via dicendo... tanto se possono essere solo contigui si parte da un 1 e si controlla solo quello a dx, e poi quello sotto e via dicendo...

   
22. lol
mercoledì 13 ottobre 2010 alle 12:02 PM - chrome 6.0.472.63 Windows 7
   

paperino, ci dici l'algoritmo utilizzato in campo minato?

   
23. Giuseppe
mercoledì 13 ottobre 2010 alle 12:31 PM - IE 9.0 Windows 7
   

mia follia mattiniera... backtracking a partire da (x0,y0) finché c'è un "sottografo" connesso. conteggio quindi gli "uni" (equivalente al conteggio dei passi utili del backtracking). Al termine spostarsi al primo uno non visitato.

Al passo 0 ovviamente x0=y0=0

 

   
24. il nonno
giovedì 14 ottobre 2010 alle 10:23 AM - chrome 7.0.517.24 Windows 7
   

Penso di aver trovato la soluzione e credo che abbia la complessita' minima possibile.

[SPOILER ALERT]

Se qualcuno vuole cimentarsi non continui a leggere questo commento

Premetto che il problema mi pare non proprio banale e come domanda da interview direi che va bene se il candidato ha gia' risposto in modo brillante a domande precedenti e si vuole cercare di vedere quali sono i suoi limiti.

Ma veniamo alla soluzione che richiede di tenere un array monodimensionale per i conteggi parziali.

Si inizia a percorrere la matrice in alto a sinistra e la prima casella che contiene un 1 lo si cambia in 2 e si incremente il contatore  che teniamo nell'array monodimensionale alla posizione 2. Si controlla se ci sono 1 adiacenti e li si cambia in 2 e si incrementa il contatore dell'array di conseguenza. Si prosegue e al prossimo 1 lo si rimpiazza con un 3 e cosi' via.

Ad esempio se le prime due righe fossero

0 1 1 0 1 0 1 1 0

0 0 1 1 0 1 1 0 1

dopo aver persorso la prima riga diventerebbero

0 2 2 0 3 0 4 4 0 

0 0 2 1 0 1 4 0 1

Quando si passa alla seconda riga l'algoritmo cambia leggermente nel senso che se si trova un 1 prima di cambiarlo si controlla il valore della cella successiva, se e' > 1 allora si usa qual valore altrimenti si usa un nuovo valore.

Quando in una cella si trova ad esempio 2 e nella successiva si trova 4 allora si cambiano tutti i 4 di quella riga in 2 e si azzera il contatore parziale del 4 dopo averlo sommato al contatore del 2.

Alla fine si percorre l'array monodimensionale e si cerca il valore massimo.

Bazinga!

   
25. Paperino
giovedì 14 ottobre 2010 alle 7:21 PM - chrome 6.0.472.63 Windows 7
   

@nonno: si può fare di meglio.

   
26. il nonno
giovedì 14 ottobre 2010 alle 7:40 PM - IE 7.0 Windows 7
   

ecchecasso! quanto meglio, che ordine di complessita'?

 

   
27. Paperino
giovedì 14 ottobre 2010 alle 8:45 PM - chrome 6.0.472.63 Windows 7
   

Scorrimento della matrice una volta sola con occupazione minima di spazio aggiuntivo.

   
28. il nonno
giovedì 14 ottobre 2010 alle 9:02 PM - IE 7.0 Windows 7
   

non capisco come tu possa scorrerla una sola volta... quando trovi un 1 devi controllare se ha altri 1 attorno e quindi gia' li' ti sei giocato la possibilita' di accedere ad ogni posizione una sola volta... mah mi sfugge qualcosa...

   
29. Phenix
giovedì 14 ottobre 2010 alle 9:04 PM - chrome 6.0.472.63 Windows 7
   

Scorri la matrice originale una sola volta e ti crei una gemella che scorri quanto e come vuoi

Della seria fatta la legge creato l'inganno

   
30. Paperino
giovedì 14 ottobre 2010 alle 9:11 PM - chrome 6.0.472.63 Windows 7
   

hint: hai bisogno di guardare solo la 'riga' precedente mentre processi la riga corrente.

   
31. il nonno
giovedì 14 ottobre 2010 alle 9:22 PM - IE 7.0 Windows 7
   

hint buono!

   
32. il nonno
giovedì 14 ottobre 2010 alle 9:30 PM - IE 7.0 Windows 7
   

ma anche no... che cambia rispetto al mio algoritmo? io guardo solo la riga successiva quando scorro una riga... sono identici nella complessita'.

   
33. Paperino
giovedì 14 ottobre 2010 alle 11:42 PM - chrome 6.0.472.63 Windows 7
   

non so, forse sono la stessa cosa.

La mia soluzione.

   
34. il nonno
venerdì 15 ottobre 2010 alle 2:30 AM - chrome 7.0.517.24 Windows 7
   

Paperino,

l'implementazione della tua soluzione e' sicuramente elegante (un trionfo di operazioni binarie ), ma diventa gia' piu' incasinata se la matrice ha righe e colonne > 64 mentre la mia non e' affetta da questo problema.

Inoltre tu per ogni bit block della riga precedente che ha ottenuto un match fai un controllo con tutti i bitblock della riga corrente, cosa che invece il mio algoritmo non ha bisogno di fare, quindi sospetto (ma potrei benissimo sbagliarmi) che la tua implementazione abbia una complessita' maggiore.

Inoltre la mia credo usi pure meno memoria oltre al fatto che non deve eseguire la conversione iniziale in UInt64.

Insomma, magari non e' detto che la mia sia effettivamente meno complessa, ma ho una discreta certezza che sia per lo meno alla pari della tua

E di sicuro la mia e' piu' bella da vedere rappresentata graficamente mentre "perlustra" la matrice, anche l'occhio vuole la sua parte!

 

 

   
35. Paperino
venerdì 15 ottobre 2010 alle 2:43 AM - chrome 6.0.472.63 Windows 7
   

l'implementazione della tua soluzione e' sicuramente elegante (un trionfo di operazioni binarie  ), ma diventa gia' piu' incasinata se la matrice ha righe e colonne > 64 mentre la mia non e' affetta da questo problema.

In realtà è un problema limitato, in quanto ci sono diverse implementazioni di BigInt in giro.

Inoltre tu per ogni bit block della riga precedente che ha ottenuto un match fai un controllo con tutti i bitblock della riga corrente, cosa che invece il mio algoritmo non ha bisogno di fare, quindi sospetto (ma potrei benissimo sbagliarmi) che la tua implementazione abbia una complessita' maggiore.

In ogni riga hai al massimo col/2 blocchi. Ovviamente trasponi la matrice in modo da minimizzare il numero di colonne. Ad occhio e croce non dovrebbero essere tante, però si potrebbero contare le operazioni di confronto e vedere.

Inoltre la mia credo usi pure meno memoria oltre al fatto che non deve eseguire la conversione iniziale in UInt64.

Dettaglio trascurabile in quanto la rappresentazione in stringa l'ho usata solo per comodità 'visiva'.

   
36. il nonno
venerdì 15 ottobre 2010 alle 9:43 AM - chrome 7.0.517.24 Windows 7
   

In ogni riga hai al massimo col/2 blocchi. Ovviamente trasponi la matrice in modo da minimizzare il numero di colonne. Ad occhio e croce non dovrebbero essere tante, però si potrebbero contare le operazioni di confronto e vedere. 

Sono comunque (col/2 + 1) * col/4 confronti per ogni riga mentre il mio algoritmo ne fa col * 2 dato che per ogni cella confronta la successiva e quella della riga sottostante.

Ci sarebbero poi le operazioni della funzione Break che genera tutti i bit block, anche quella fa dei confronti.

Ho il dubbio che il tuo algoritmo in realta' percorra ogni cella piu' volte del mio, l'operazione di XOR che fai nel ciclo while (data != 0) di fatto dovrebbe venir calcolata come un percorrere le singole celle coinvolte, ma sul calcolo della complessita' degli algoritmi sono sempre stato una frana

 

   
37. Paperino
venerdì 15 ottobre 2010 alle 6:33 PM - chrome 6.0.472.63 Windows 7
   

Ci sarebbero poi le operazioni della funzione Break che genera tutti i bit block, anche quella fa dei confronti.

Ho il dubbio che il tuo algoritmo in realta' percorra ogni cella piu' volte del mio, l'operazione di XOR che fai nel ciclo while (data != 0) di fatto dovrebbe venir calcolata come un percorrere le singole celle coinvolte[...]

Yes, è uno scorrere ma limitato al numero di uni. Poi sarebbe da capire se e quanto le operazioni matematiche costano più o meno di quelle di swap, ecc.

Se scrivi il tuo in codice gli passo una amatriciona gigantesca e vediamo cosa ne esce fuori. Se i risultati divergono poi cerchiamo un volontario che li verifichi

   
38. il nonno
venerdì 15 ottobre 2010 alle 7:39 PM - chrome 7.0.517.24 Windows 7
   

per ora non l'ho ancora scritto... adesso che mi metti pressione mi tocca impegnarmi!

   
39. Paperino
venerdì 15 ottobre 2010 alle 8:32 PM - chrome 6.0.472.63 Windows 7
   

Forza, forza!

   
40. wac
lunedì 18 ottobre 2010 alle 11:48 PM - firefox 3.6.10 Windows 7
   

mi sono permesso di implementare l'algoritmo del nonno.

non sapevo dove uploadarlo, e l'ho messo quà

www.megafileupload.com/.../UniNonno-txt.html

E' scritto da cani(non sono ai livelli dei frequentatori di questo blog, ho fatto del mio meglio XD) ma in quei pochi test che ho fatto funziona

 

 

 

   
41. il nonno
martedì 19 ottobre 2010 alle 12:00 AM - IE 7.0 Windows 7
   

@wac

bravo, l'hai implementato meglio di me!

Io per pigrizia c'ho messo un bordo di zeri intorno alla matrice originale per non gestire come caso diverso le celle del bordo.

   
42. Paperino
martedì 19 ottobre 2010 alle 12:52 AM - chrome 6.0.472.63 Windows 7
   

Domani li faccio girare

   
43. wac
martedì 19 ottobre 2010 alle 12:19 PM - firefox 3.6.10 Windows 7
   

@ il nonno

grazie del complimento

 

cmq la mia implementazione, per "sopperire" ad un piccolo difettuccio di natura grafica, fa un confronto di troppo, che ai fini del risultato finale(in termini di conteggio blocchi) è superfluo ^_^

   
[ Pagina 1 di 2  - più vecchi ]
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)