Interview puzzle su un segmento di linea

Question

Interview puzzle su un segmento di linea

#1 da (4 voti)
#2 da (1 voti)
#3 da (0 voti)
#4 da (0 voti)
#5 da (-1 voti)

10

Su una riga numerica di lunghezza M , dove 0 < M <= 1,000,000,000 , hai dato N ( 1 < N <= 100,000 ) coppie di punti interi. In ogni coppia, il primo punto rappresenta dove si trova attualmente un oggetto, e il secondo punto rappresenta dove un oggetto deve essere spostato. (Tieni presente che il second point potrebbe essere più piccolo di first ).

Ora, supponi di iniziare al punto 0 e di avere un carrello che possa contenere 1 oggetto. Si desidera spostare tutti gli oggetti dalle loro posizioni iniziali alle rispettive posizioni finali mentre si percorre la distanza minima lungo la linea del numero (spostamento non ). Devi finire sul punto M .

Ora, ho cercato di ridurre questo problema a un problema più semplice. Ad essere onesti non riesco nemmeno a pensare ad una soluzione di forza bruta ( possibilmente avida). Tuttavia, il mio primo pensiero è stato quello di degenerare un movimento all'indietro verso due movimenti in avanti, ma ciò non sembra funzionare in tutti i casi.

Ho richiamato questi casi di test di esempio 3 qui:

La risposta al primo testcase è 12 . Innanzitutto, raccogli l'elemento red al punto 0 . Quindi vai al punto 6 (distanza = 6 ), rilascia temporaneamente l'elemento red , quindi raccogli l'elemento green . Quindi vai al punto 5 (distanza = 1 ) e rilascia l'elemento green . Quindi torni al punto 6 (distanza = 1 ) e raccogli l'oggetto red che hai lasciato, vai al punto 9 (distanza = 3 ), quindi vai al punto 10 (distanza = 1 ) per terminare la sequenza.

La distanza totale percorsa era 6 + 1 + 1 + 3 + 1 = 12 , che è la distanza minima possibile.

Gli altri due casi hanno risposte di 12 , credo. Tuttavia, non riesco a trovare una regola generale per risolverlo.

Qualcuno ha qualche idea?

algorithms math

posta david 10.02.2013 - 02:47

fonte

5 risposte

Leggi altre domande sui tag algorithms math

Quanta derisione è "giusto?" DDD CQRS - autorizzazione per query e per comando

score 4 · Answer 1

Se sei vuoto, inizia a spostarti a destra.
Ogni volta che raggiungi un oggetto e sei vuoto, prendilo (duh) e vai verso la sua destinazione.
Ogni volta che raggiungi un oggetto a e stai già trasportando b , sempre seleziona quale degli oggetti ha la destinazione numericamente più piccola (il più a sinistra).
Se non sei ancora in M, torna al passaggio 1.

Questo è ottimale: l'unico posto in cui hai una vera scelta è nel passaggio 3. Gestire prima la destinazione più a sinistra per prima cosa assicura che nel momento in cui hai inviato entrambi gli oggetti, sarai il più a destra possibile.

Perché questa domanda è su programmers.sx? Sì, "domanda dell'intervista", ma è solo un bel indovinello.

PS. In termini di implementazione, tutto ciò di cui hai bisogno è l'elenco delle attività (le coppie di punti interi) ordinate per posizione originale.

score 1 · Answer 2

Supponi di avere queste mosse di (a, b), (c, d), (e, f), ... , quindi la distanza minima che devi percorrere è abs(b - a) + abs(d - c) + abs(f - e) + ... e la distanza effettiva che percorri è abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ... .
Fondamentalmente, data una serie di mosse, il punto è minimizzare la funzione "distanza percorsa" scambiando gli elementi intorno. Se consideri una particolare combinazione come un nodo e tutte le combinazioni che puoi raggiungere da essa come spigoli puoi usare uno dei tanti algoritmi di ricerca del grafico attorno ai quali fai uso di un'euristica. Un esempio è la ricerca travi .

score 0 · Answer 3

Potrei essere in grado di capire il problema ma riguardo ai seguenti aspetti:

Ordina le coppie per il primo numero della coppia che è la corrente posizione
Spostati lungo la linea scambiando gli elementi nella posizione corretta (tu avere una variabile temporanea)

Il fatto che sia ordinato garantisce di non andare avanti e indietro sugli elementi per posizionarli nella posizione corretta (indipendentemente dal fatto che la linea sia rappresentata come una matrice o un elenco)

Aggiornamento dopo il commento @templatetypedef: Usa un HashTable per memorizzare tutte le coppie. Usa la posizione corrente di ogni coppia come tasto indice.
Usa un secondo indice sopra le coppie.

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2

score 0 · Answer 4

La mia inclinazione a un algoritmo che è fondamentalmente goloso:

Crea un elenco di punti che devono essere spostati. Poiché l'ottimizzazione non fa parte del problema richiesto, non mi preoccuperò di organizzarlo.

while !Done
    if CartIsEmpty()
        FindClosestObjectToMove()
        MoveToObject()
       LoadCart()
    else
        Destination = Cart.Contains.Target
        CurrentMove = [Location, Destination]
        SubList = List.Where(Move.Within(CurrentMove))
        if !SubList.Empty
            Destination = SubList.FindSmallest(Location, Move.Origin)
        MoveTo(Destination)
        if !Destination.Empty
            SwapCart()
            UpdateTaskList()
        else
            EmptyCart()
            DeleteTask()

Penso che questo copra tutti i casi. In un certo senso è ricorsivo, ma attraverso l'aggiornamento della lista piuttosto che chiamare se stesso.

score -1 · Answer 5

Questo è il problema del venditore ambulante asimmetrico . Puoi pensare a questo come un grafico. I bordi saranno ciascuno (inizio, fine) coppia, uno per ciascuno (0, inizio) e tutte le altre coppie di (fine, inizio).

Assumendo NP! = P, avrà un tempo di esecuzione previsto esponenziale.