Algoritmo di commutazione per il problema di progettazione del software di parcheggio

Naviga le tue risposte
1

C'è una domanda di intervista comune che sarà una varietà della simulazione del parcheggio - la cui essenza è che hai un parcheggio con posti auto di varie dimensioni (piccolo, medio, grande) e auto di varie dimensioni (piccolo, medio, grande), e il tuo lavoro è simulare l'inserimento di un'auto nel lotto e la rimozione di un'auto specifica dal lotto.

La mia domanda è specificamente correlata a una ruga che viene gettata nel problema; cosa succede se lasci le auto di piccole o medie dimensioni in spazi di parcheggio più grandi delle rispettive dimensioni, e più tardi ti ritrovi con una macchina grande che cerca di entrare molto con solo un piccolo parcheggio?

Ho avuto intervistatori che mi chiedevano come costruire al meglio un algoritmo di commutazione, con strutture dati ottimali, in grado di spostare una piccola auto che occupa un ampio parcheggio nel piccolo spazio aperto, e poi mettere l'auto grande nell'ora. aprire un grande punto. Non ho idea di come fare questo, oltre il semplice iterare attraverso una serie di spazi di parcheggio occupati e fermarsi quando trovi la tua prima auto piccola. Tuttavia, non sono sicuro che O (n) il tempo per l'inserimento sia il momento migliore, ma ho esaurito le idee per migliorare questo runtime.

Quindi chiedo, qual è il più o almeno un algoritmo più ottimale per trovare e cambiare auto da parcheggi di varie dimensioni?

    
posta TheFooh 31.08.2016 - 16:00
fonte

1 risposta

2

Le domande dell'intervista sono tutte informazioni su come conoscerti come persona: come pensi, come comunichi, quali domande fai e così via.

Avere una risposta "perfetta" a qualsiasi enigma della settimana non è utile, perché l'unica interazione che avviene è che l'intervistatore fa una domanda in scatola (indicando così una mancanza di originalità e di sforzo), e tu rispondi con una risposta in scatola (indicando quindi un certo grado di memorizzazione ma non condividendo realmente le intuizioni circa l'idoneità o meno della posizione).

Per questa domanda, prima darei all'intervistatore il "mi stai prendendo in giro - stiamo davvero andando giù per questa strada?" fissi, quindi inizierei a fare domande:
  1. di quanti parcheggi stiamo parlando?
  2. quante macchine possiamo spostare alla volta?
  3. le auto parcheggiate in doppia fila (cioè bloccate da altre auto)?
  4. sono gli accessi più facili da individuare rispetto ad altri (ad esempio, problemi di geografia)
  5. quale è l'arrivo / partenza prevista delle auto?
  6. per quanto tempo le auto rimarranno normalmente lì?
  7. sappiamo in anticipo quando partirà una macchina particolare?

e infine,

  1. definisce "ottimale"

In questo caso definirei "ottimale" come minimizzare il tempo dello sviluppatore. Scrivi il codice più semplice, facile da capire e manutenere e non preoccuparti di alcuna ottimizzazione. Rendere il codice un po 'più veloce non ha importanza, rispetto al tempo necessario per riposizionare le auto.

Vedi anche questo rilevante XKCD - Vale la pena? . Potresti spendere un paio di centinaia di ore per eliminare qualche millisecondo dall'algoritmo, che si ripagherà da solo in pochi decenni.

Come puoi vedere, le domande rivelano all'intervistatore un po 'di più su di me: come penso, cosa considero importante, su quale livello di dettaglio mi concentro, e così via.

Per rispondere alla tua domanda specifica

So I ask, what is the most, or at the very least, a more optimal algorithm, to find and switch cars from parking spots of varying sizes?

Tieni traccia di quali auto sono collocate in spazi sovradimensionati. Speriamo che questa sia l'eccezione, quindi se il tuo lotto ha 200 auto avrai solo 10 o 20 in questa lista.

Quando hai bisogno di cambiare auto, puoi usare questo elenco per andare direttamente alle auto che devono essere spostate.

    
risposta data 31.08.2016 - 17:21
fonte

Leggi altre domande sui tag

Aggiornamento di una best practice per token Quando si progetta un router URL, c'è un motivo per cui alcuni framework scelgono un file di configurazione rispetto a una convenzione di denominazione?