Implementazione delle strutture dati di base nelle interviste di programmazione [chiuso]

4

Mi sono preparato a fare la mia prima intervista tecnica tra un mese e ho una domanda sull'implementazione di strutture dati comuni come pile o elenchi collegati. Ho intenzione di fare l'intervista in Python o Java, ma non sono sicuro di quale usare ancora.

Mi stavo esercitando e ho cercato di implementare uno stack in Python, usando già elenchi integrati. Tuttavia, gli elenchi in Python hanno già tutti i metodi di stack, mentre c'è ancora del lavoro da fare quando gli array in Java vengono utilizzati per implementare uno stack.

Se mi viene chiesto di implementare uno stack e il mio linguaggio preferito è Python, cosa dovrei fare? Dovrei definire la classe Node? Non mi sarebbe nemmeno stato chiesto di implementare una tale struttura di dati di basso livello in Python comunque?

    
posta Maximus S 09.10.2013 - 06:02
fonte

1 risposta

1

Probabilmente saranno più interessati se capisci cosa è uno stack / elenco collegato, come funzionano e così via. Fondamentalmente, potresti implementarne uno in C, C ++ se dovessi farlo, assumendo che tu conoscessi la lingua? Se queste cose sono una parte standard delle lingue che hai elencato, probabilmente non ti verrà chiesto di implementarle in modo crudo.

Ma come ho detto, vorranno dimostrare che capisci i concetti logici dietro le strutture di dati se la domanda sta arrivando. Per esempio, nel rispondere alla domanda sugli stack, gli stack sono strutture LIFO, dove quello che aggiungi per ultimo viene tolto per primo. È come una pila di piatti in cui puoi solo aggiungere o rimuovere la piastra superiore. Quindi, se si va in fase di implementazione, si prende semplicemente un array di una certa dimensione, si tiene traccia della capacità e si opera solo al di fuori del valore dell'indice. Ad esempio, implementazione Delphi / Pascal:

const
  maxstacksize = 500;
type
  TIntegerStack = class
  private
    elements: array[1..maxstacksize] of integer;
    capacity: integer;
  public
    procedure place(element: integer);
    function remove: integer;
  end;

procedure TIntegerStack.place(element: integer);
   begin
     if capacity = maxstacksize then
       // error, trying to place element on full stack, i.e. stack overflow
     else
       begin
         inc(capacity);
         elements[capacity] := element;
       end;
   end;

function TIntegerStack.remove: integer;
   begin
     Result := -1;
     if capacity = 0 then
       // error, trying to remove element from empty stack
     else
        begin
          Result := elements[capacity];
          dec(capacity);
        end;
   end;

La maggior parte degli intervistatori probabilmente non avrà bisogno che tu la porti così lontano per dimostrare di sapere quali stack sono e come funzionano, ma ti dà un'idea di ciò che l'intervistatore si aspetta.

    
risposta data 09.10.2013 - 06:34
fonte

Leggi altre domande sui tag