«

mar 23

Quesiti da colloquio (2)

Quesiti da colloquio (2)

Runaround

runaround [ˈrʌnəˌraʊnd] n(fam) to give sb the runaround far girare a vuoto qn

Runaround

Questo è un quesito posto a un mio collega durante un colloquio.

Una stringa runaround ha le seguenti caratteristiche

  • E’ composta da N<10 elementi nell’alfabeto [1-9]
  • Ogni elemento dell’alfabeto può comparire una sola volta
  • Ogni elemento della lista può essere usato una sola volta
  • Il primo elemento della sequenza è detto testa.
  • Gli elementi successivi alla testa rappresentano la posizione del prossimo elemento nella lista di output ( la lista viene considerata come un anello)
  • Percorrendo tutta la stringa secondo i salti contenuti nella stringa stessa si ritorna alla posizione iniziale

Analizziamo per esempio il runaround 81362

Cifra Posizione
Testa 8 1362
8 813 6 2
6 8136 2
2 8 1 362
1 81 3 62
3 8 1362

Si richiede un algoritmo per verificare se una data stringa rappresenta un runaround.

Allego dati per il test

Validi Non Validi
13 12
147 123
1263 1234
81236 81111
83491 82222
913425 7654321
8124956 911111

Soluzione

Per verificare che una stringa sia un runaround semplicemente proviamo a percorrerla


def check_runaround(runaround)
  disponibili=("1".."9").to_set
  k=0
  runaround.size.times{
    return false if not disponibili.include?(runaround[k])
    salto=(k+runaround[k].to_i) % runaround.size
    disponibili.delete(runaround[k])
    k=salto
  }
  return true if k==0
  false
end

Share Button