Структура данных: вставить, удалить, содержать, получить случайный элемент, все в O (1)

Question

Мне дали эту проблему в интервью. Как бы вы ответили?

Разработка структуры данных, которая предлагает следующие операции за время O (1):

• вставить
• удалить
• 1010 * содержит *
• получить случайный элемент

Answer 1

Рассмотрим структуру данных, состоящую из хеш-таблицы H и массива A. Ключами хеш-таблицы являются элементы в структуре данных, а значения - их позиции в массиве.

1. insert (value): добавить значение в массив, и пусть i будет его индексом в A. Установите H [value] = i.
2. remove (value): мы собираемся заменить ячейку, содержащую значение в A, последним элементом в A. пусть d будет последним элементом в массиве A с индексом m. пусть я будет H [значение], индекс в массиве значения, которое будет удалено. Установите A [i] = d, H [d] = i, уменьшите размер массива на единицу и удалите значение из H.
3. содержит (значение): возврат H.contains (значение)
4. getRandomElement (): let r = random (текущий размер A). вернуть A [r].

, так как массив должен автоматически увеличиваться в размере, он будет амортизировать O (1), чтобы добавить элемент, но я думаю, что все в порядке.

Answer 2

O (1) поиск подразумевает хешированную структуру данных .

Для сравнения:

• O (1) вставка / удаление с поиском O (N) подразумевает связанный список.
• O (1) вставка, O (N) удаление и O (N) поиск подразумевает список с поддержкой массива
• O (logN) вставка / удаление / поиск подразумевает дерево или кучу.

Answer 3

Возможно, вам это не понравится, потому что они, вероятно, ищут умное решение, но иногда стоит придерживаться ваших оружий ... хеш-таблица уже удовлетворяет требованиям - возможно, в целом лучше, чем все остальное будет (хотя, очевидно, в амортизированном постоянном времени и с другими компромиссами для других решений).

Хитрым требованием является выбор "случайного элемента": в хэш-таблице вам нужно будет отсканировать или исследовать такой элемент.

Для закрытой хеширования / открытой адресации вероятность того, что любой данный сегмент будет занят, составляет size() / capacity(), но, что важно, это обычно поддерживается в постоянном мультипликативном диапазоне реализацией хэш-таблицы (например, таблица может быть больше, чем ее текущее содержание, скажем, от 1,2x до ~ 10x в зависимости от производительности / настройки памяти). Это означает, что в среднем мы можем ожидать поиск от 1,2 до 10 сегментов - полностью независимо от общего размера контейнера; амортизированный O (1).

Я могу представить два простых подхода (и еще много более причудливых):

• линейный поиск по случайному интервалу

  • рассмотрим пустые / сохраняющие значение сегменты ala "--AC ----- B - D": вы можете сказать, что первый "случайный" выбор справедлив, даже если он благоприятствует B, потому что B имел больше вероятности быть предпочтительным, чем другие элементы, но если вы делаете повторный «случайный» выбор, используя те же значения, то ясно, что B многократно предпочтительным может быть нежелательным (хотя ничто в вопросе не требует даже вероятностей)

• неоднократно пробовать случайные группы, пока не найдете заполненный

  • «только» емкость () / размер () в среднем посещенных сегментов (как указано выше) - но в практическом плане дороже, потому что генерация случайных чисел относительно дорога, и бесконечно плоха, если бесконечно невероятно наихудший случай поведение...
    • более быстрым компромиссом будет использование списка предварительно сгенерированных случайных смещений из начального случайно выбранного сегмента,% -ное их включение в счетчик сегментов

Не очень хорошее решение, но все же может быть лучшим компромиссом, чем затраты памяти и производительности на поддержание второго индексного массива в любое время.

Answer 4

Для этого вопроса я буду использовать две структуры данных

• HashMap
• ArrayList / Array / Double LinkedList.

Шаги: -

1. Вставка: - Проверить, присутствует ли X в HashMap - Сложность времени O (1). если нет, то добавьте в конец ArrayList - сложность времени O (1). добавить его в HashMap также x в качестве ключа и последний индекс в качестве значения - сложность времени O (1).
2. Удалить: - Проверить, присутствует ли X в HashMap - Сложность времени O (1). Если он присутствует, найдите его индекс и удалите его из HashMap - сложность O (1). поменяйте местами этот элемент с последним элементом в ArrayList и удалите последний элемент - сложность Времени O (1). Обновление индекса последнего элемента в HashMap - сложность времени O (1).
3. GetRandom: - Создать случайное число от 0 до последнего индекса ArrayList. вернуть элемент ArrayList при сгенерированном случайном индексе - Временная сложность O (1).
4. Поиск: - См. В HashMap для х в качестве ключа. - Сложность времени O (1).

код: -

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class JavaApplication1 {

    public static void main(String args[]){
       Scanner sc = new Scanner(System.in);
        ArrayList<Integer> al =new ArrayList<Integer>();
        HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();  
        while(true){
            System.out.println("**menu**");
            System.out.println("1.insert");
            System.out.println("2.remove");
            System.out.println("3.search");
            System.out.println("4.rendom");
            int ch = sc.nextInt();
            switch(ch){
                case 1 : System.out.println("Enter the Element ");
                        int a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println("Element is already present ");
                        }
                        else{
                            al.add(a);
                            mp.put(a, al.size()-1);

                        }
                        break;
                case 2 : System.out.println("Enter the Element Which u want to remove");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){

                            int size = al.size();
                            int index = mp.get(a);

                            int last = al.get(size-1);
                            Collections.swap(al, index,  size-1);

                            al.remove(size-1);
                            mp.put(last, index);

                            System.out.println("Data Deleted");

                        }
                        else{
                            System.out.println("Data Not found");
                        }
                        break;
                case 3 : System.out.println("Enter the Element to Search");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println(mp.get(a));
                        }
                        else{
                            System.out.println("Data Not Found");
                        }
                        break;
                case 4 : Random rm = new Random();
                        int index = rm.nextInt(al.size());
                        System.out.println(al.get(index));
                        break;

            }
        }
    }

}

- Временная сложность O (1). - Пространственная сложность O (N).

Answer 5

Лучшим решением, вероятно, является хеш-таблица + массив, он очень быстрый и детерминированный.

Но ответ с наименьшим рейтингом (просто используйте хеш-таблицу!) На самом деле тоже хорош!

• хеш-таблица с повторным хешированием или выбором нового сегмента (т. Е. Один элемент на сегмент, без связанных списков)
• getRandom () неоднократно пытается выбрать случайный сегмент, пока он не станет пустым.
• как отказоустойчивый, возможно, getRandom (), после N (количество элементов) неудачных попыток, выбирает случайный индекс i в [0, N-1], а затем линейно проходит через хэш-таблицу и выбирает # i-йelement.

Людям это может не понравиться из-за «возможных бесконечных петель», и я видел, что очень умные люди тоже имеют такую ​​реакцию, но это неправильно!Бесконечно маловероятные события, которые просто не происходят.

Предполагая хорошее поведение вашего псевдослучайного источника - что нетрудно установить для этого конкретного поведения - и что хеш-таблицывсегда заполнено по крайней мере на 20%, легко увидеть, что:

Не будет никогда случиться так, что getRandom () будет пытаться выполнить более 1000 раз.Просто никогда .Действительно, вероятность такого события составляет 0,8 ^ 1000, что составляет 10 ^ -97 - поэтому нам пришлось бы повторить это 10 ^ 88 раз, чтобы один шанс из миллиарда случался когда-либо один раз.Даже если эта программа работала полный рабочий день на всех компьютерах человечества до тех пор, пока Солнце не умрет, это никогда не произойдет.

Answer 6

Хотя это уже давно, но в C ++ нет ответа, вот мои два цента.

#include <vector>
#include <unordered_map>
#include <stdlib.h>

template <typename T> class bucket{
    int size;
    std::vector<T> v;
    std::unordered_map<T, int> m;
public:
    bucket(){
        size = 0;
        std::vector<T>* v = new std::vector<T>();
        std::unordered_map<T, int>* m = new std::unordered_map<T, int>();
    }
    void insert(const T& item){
        //prevent insertion of duplicates
        if(m.find(item) != m.end()){
            exit(-1);
        }
        v.push_back(item);
        m.emplace(item, size);
        size++;

    }
    void remove(const T& item){
        //exits if the item is not present in the list
        if(m[item] == -1){
            exit(-1);
        }else if(m.find(item) == m.end()){
            exit(-1);
        }

        int idx = m[item];
        m[v.back()] = idx;
        T itm = v[idx];
        v.insert(v.begin()+idx, v.back());
        v.erase(v.begin()+idx+1);
        v.insert(v.begin()+size, itm);
        v.erase(v.begin()+size);
        m[item] = -1;
        v.pop_back();
        size--;

    }

     T& getRandom(){
      int idx = rand()%size;
      return v[idx];

     }

     bool lookup(const T& item){
       if(m.find(item) == m.end()) return false;
       return true;

     }
    //method to check that remove has worked
    void print(){
        for(auto it = v.begin(); it != v.end(); it++){
            std::cout<<*it<<" ";
        }
    }
};

Вот фрагмент кода клиента для тестирования решения.

int main() {

    bucket<char>* b = new bucket<char>();
    b->insert('d');
    b->insert('k');
    b->insert('l');
    b->insert('h');
    b->insert('j');
    b->insert('z');
    b->insert('p');

    std::cout<<b->random()<<std::endl;
    b->print();
    std::cout<<std::endl;
    b->remove('h');
    b->print();

    return 0;
}

Answer 7

Вот решение C # для этой проблемы, которое я придумал некоторое время назад, когда мне задавали тот же вопрос.Он реализует Add, Remove, Contains и Random вместе с другими стандартными интерфейсами .NET.Не то, чтобы вам когда-нибудь понадобилось так подробно это реализовывать во время собеседования, но приятно иметь конкретное решение, на которое можно посмотреть ...

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

/// <summary>
/// This class represents an unordered bag of items with the
/// the capability to get a random item.  All operations are O(1).
/// </summary>
/// <typeparam name="T">The type of the item.</typeparam>
public class Bag<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
{
    private Dictionary<T, int> index;
    private List<T> items;
    private Random rand;
    private object syncRoot;

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    public Bag()
        : this(0)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="capacity">The capacity.</param>
    public Bag(int capacity)
    {
        this.index = new Dictionary<T, int>(capacity);
        this.items = new List<T>(capacity);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="collection">The collection.</param>
    public Bag(IEnumerable<T> collection)
    {
        this.items = new List<T>(collection);
        this.index = this.items
            .Select((value, index) => new { value, index })
            .ToDictionary(pair => pair.value, pair => pair.index);
    }

    /// <summary>
    /// Get random item from bag.
    /// </summary>
    /// <returns>Random item from bag.</returns>
    /// <exception cref="System.InvalidOperationException">
    /// The bag is empty.
    /// </exception>
    public T Random()
    {
        if (this.items.Count == 0)
        {
            throw new InvalidOperationException();
        }

        if (this.rand == null)
        {
            this.rand = new Random();
        }

        int randomIndex = this.rand.Next(0, this.items.Count);
        return this.items[randomIndex];
    }

    /// <summary>
    /// Adds the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    public void Add(T item)
    {
        this.index.Add(item, this.items.Count);
        this.items.Add(item);
    }

    /// <summary>
    /// Removes the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    public bool Remove(T item)
    {
        // Replace index of value to remove with last item in values list
        int keyIndex = this.index[item];
        T lastItem = this.items[this.items.Count - 1];
        this.items[keyIndex] = lastItem;

        // Update index in dictionary for last item that was just moved
        this.index[lastItem] = keyIndex;

        // Remove old value
        this.index.Remove(item);
        this.items.RemoveAt(this.items.Count - 1);

        return true;
    }

    /// <inheritdoc />
    public bool Contains(T item)
    {
        return this.index.ContainsKey(item);
    }

    /// <inheritdoc />
    public void Clear()
    {
        this.index.Clear();
        this.items.Clear();
    }

    /// <inheritdoc />
    public int Count
    {
        get { return this.items.Count; }
    }

    /// <inheritdoc />
    public void CopyTo(T[] array, int arrayIndex)
    {
        this.items.CopyTo(array, arrayIndex);
    }

    /// <inheritdoc />
    public bool IsReadOnly
    {
        get { return false; }
    }

    /// <inheritdoc />
    public IEnumerator<T> GetEnumerator()
    {
        foreach (var value in this.items)
        {
            yield return value;
        }
    }

    /// <inheritdoc />
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    /// <inheritdoc />
    public void CopyTo(Array array, int index)
    {
        this.CopyTo(array as T[], index);
    }

    /// <inheritdoc />
    public bool IsSynchronized
    {
        get { return false; }
    }

    /// <inheritdoc />
    public object SyncRoot
    {
        get
        {
            if (this.syncRoot == null)
            {
                Interlocked.CompareExchange<object>(
                    ref this.syncRoot,
                    new object(),
                    null);
            }

            return this.syncRoot;

        }
    }
}

Answer 8

/* Java program to design a data structure that support folloiwng operations
   in Theta(n) time
   a) Insert
   b) Delete
   c) Search
   d) getRandom */
import java.util.*;

// class to represent the required data structure
class MyDS
{
   ArrayList<Integer> arr;   // A resizable array

   // A hash where keys are array elements and vlaues are
   // indexes in arr[]
   HashMap<Integer, Integer>  hash;

   // Constructor (creates arr[] and hash)
   public MyDS()
   {
       arr = new ArrayList<Integer>();
       hash = new HashMap<Integer, Integer>();
   }

   // A Theta(1) function to add an element to MyDS
   // data structure
   void add(int x)
   {
      // If ekement is already present, then noting to do
      if (hash.get(x) != null)
          return;

      // Else put element at the end of arr[]
      int s = arr.size();
      arr.add(x);

      // And put in hash also
      hash.put(x, s);
   }

   // A Theta(1) function to remove an element from MyDS
   // data structure
   void remove(int x)
   {
       // Check if element is present
       Integer index = hash.get(x);
       if (index == null)
          return;

       // If present, then remove element from hash
       hash.remove(x);

       // Swap element with last element so that remove from
       // arr[] can be done in O(1) time
       int size = arr.size();
       Integer last = arr.get(size-1);
       Collections.swap(arr, index,  size-1);

       // Remove last element (This is O(1))
       arr.remove(size-1);

       // Update hash table for new index of last element
       hash.put(last, index);
    }

    // Returns a random element from MyDS
    int getRandom()
    {
       // Find a random index from 0 to size - 1
       Random rand = new Random();  // Choose a different seed
       int index = rand.nextInt(arr.size());

       // Return element at randomly picked index
       return arr.get(index);
    }

    // Returns index of element if element is present, otherwise null
    Integer search(int x)
    {
       return hash.get(x);
    }
}

// Driver class
class Main
{
    public static void main (String[] args)
    {
        MyDS ds = new MyDS();
        ds.add(10);
        ds.add(20);
        ds.add(30);
        ds.add(40);
        System.out.println(ds.search(30));
        ds.remove(20);
        ds.add(50);
        System.out.println(ds.search(50));
        System.out.println(ds.getRandom());`enter code here`
    }
}

Answer 9

Не можем ли мы сделать это с помощью HashSet из Java?Он обеспечивает вставку, del, поиск всех в O (1) по умолчанию.Для getRandom мы можем использовать итератор Set, который в любом случае дает случайное поведение.Мы можем просто перебрать первый элемент из набора, не беспокоясь об остальных элементах

public void getRandom(){
    Iterator<integer> sitr = s.iterator();
    Integer x = sitr.next();    
    return x;
}

Answer 10

Я согласен с Аноном. За исключением последнего требования, где требуется получение случайного элемента с равной справедливостью, все остальные требования могут быть выполнены только с использованием одного DS на основе хеша. Я выберу HashSet для этого в Java. Модуль хеш-кода элемента даст мне индекс no базового массива за O (1) раз. Я могу использовать это для добавления, удаления и содержит операции.