Wstaw Usuń GetRandom

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W przypadku problemu Insert Delete GetRandom musimy zaprojektować strukturę danych obsługującą wszystkie kolejne operacje w średni O (1) czas.

1. insert (val): Wstawia wartość pozycji do zestawu, jeśli jeszcze nie istnieje.
2. remove (val): Usuwa wartość pozycji z zestawu, jeśli jest obecna.
3. getRandom: Zwraca losowy element z bieżącego zestawu elementów. Każdy element musi mieć rozszerzenie to samo prawdopodobieństwo powrotu.

Ponieważ pytanie wymaga operacji wstawiania i usuwania w O (1), potrzebujemy mapy. Ale w przypadku metody getRandom () potrzebujemy struktury danych opartej na indeksach, takiej jak tablica, abyśmy mogli losowo wybrać dowolny element indeksu do zwrócenia.

Stąd, aby uzyskać wszystkie trzy funkcje, możemy używać jednocześnie mapy i tablicy. Zobaczmy, jak to zrobić

Ważne punkty

1. Wstawienie do szyk jest O (1), jeśli jest zrobiony z tyłu.
2. Usunięcie w tablicy to O (1), jeśli element zostanie usunięty z tyłu.

Wykorzystywane struktury danych

Mapa M (do przechowywania wartości, para indeksów)

Wektor V do przechowywania obecnych elementów

Algorytm wstawiania

1. Sprawdź, czy dany element jest obecny na mapie:
   • Jeśli jest obecny, zwróć false
   • Jeszcze:
     • Wstaw podany element na koniec wektora V.
     • Wstaw podany element i jest to indeks do mapowania M.
     • Zwróć prawdę

Algorytm usuwania

1. Sprawdź, czy dany element jest obecny na mapie:
   • Jeśli jest obecny, to:
     • Zamień wartości danego elementu i ostatniego elementu w wektorze (indeks można znaleźć za pomocą mapy M)
     • Zaktualizuj mapę jako M [last_element] = M [dany_element]
     • Usuń ostatni element wektora.
     • Usuń podany element z mapy
     • Zwróć prawdę.
   • W przeciwnym razie zwróć false.

Algorytm dla getRandom

1. Wybierz dowolny losowy indeks i
2. n zakres od 0 do rozmiaru wektora.
3. Zwróć element obecny w tym indeksie w wektorze V.

Implementacja Wstaw Usuń GetRandom

Program C ++ do wstawiania i usuwania GetRandom

#include<bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    vector<int> v;
    map<int,int> m;
    RandomizedSet() {
    }
    
    //function for insertion of given value
    bool insert(int val) {
        if(m.find(val)==m.end()){
            v.push_back(val);
            m.insert({val,v.size()-1});
            return true;
        }
        
        return false;
    }
    
    //function for removal of given value
    bool remove(int val) {
        if(m.find(val)!=m.end()){
            int last = v.back();
            m[last]=m[val];
            v[m[val]]=last;
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    //function to get a random element 
    int getRandom() {
        int ran = rand()%v.size();
        return v[ran];
    }
};

int main()
{
    RandomizedSet* r = new RandomizedSet();
    r->insert(4);
    r->insert(5);
    cout<<r->getRandom()<<" ";
    r->remove(5);
    cout<<r->getRandom()<<" ";
    return 0;
}

5 4

Program JAVA do wstawiania Usuń GetRandom

import java.util.*;
public class Main
{
    public static class RandomizedSet {
    
        HashMap<Integer, Integer> m;
        List<Integer> v;
        
        //constructor
        public RandomizedSet() {
            m = new HashMap<>();
            v = new ArrayList<>();
        }
        
        //function for insertion of given value
        public boolean insert(int val) {
            if(m.containsKey(val)) 
                return false;
            v.add(val);
            m.put(val,v.size()-1);
            return true;
        }
        
        //function for removal of given value
        public boolean remove(int val) {
            if(m.containsKey(val)){
                int last = v.get(v.size()-1);
                m.put(last,m.get(val));
                v.set(m.get(val),last);
                v.remove(v.size()-1);
                m.remove(val);
                return true;
            }
            return false;
        }
        
        //function to get a random element 
        public int getRandom() {
            int ran = (int)(Math.random()%v.size());
            return v.get(ran);
        }
    }
  public static void main(String[] args) {
      RandomizedSet obj = new RandomizedSet();
        obj.insert(6);
        obj.insert(5);
        obj.insert(3);
        System.out.print(obj.getRandom()+" ");
        obj.remove(5);
        System.out.print(obj.getRandom()+" ");
        System.out.print(obj.getRandom()+" ");
  }
}

6 6 6

Referencje