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

Мне рассказали об этой задаче в интервью. Как бы вы ответили?

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

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

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

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

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

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

По сравнению:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• HashMap
• ArrayList / Массив / Двойной связанный список.

Шаги: -

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

Вот решение этой проблемы на C #, которое я придумал недавно, когда мне задали тот же вопрос. Он реализует функции «Добавить», «Удалить», «Содержит» и «Случайно» вместе с другими стандартными интерфейсами .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;

        }
    }
}

Мы можем использовать хеширование для поддержки операций за время Θ (1).

insert (x) 1) Проверьте, присутствует ли x, выполнив поиск по хэш-карте. 2) Если нет, вставьте его в конец массива. 3) Добавьте также в хеш-таблицу, x добавляется как ключ, а последний индекс массива как индекс.

remove (x) 1) Проверьте, присутствует ли x, выполнив поиск по хэш-карте. 2) Если присутствует, найдите его индекс и удалите его из хеш-карты. 3) Поменяйте местами последний элемент с этим элементом в массиве и удалите последний элемент. Замена выполняется, потому что последний элемент может быть удален за O (1) раз. 4) Обновить индекс последнего элемента в хеш-карте.

getRandom () 1) Сгенерировать случайное число от 0 до последнего индекса. 2) Вернуть элемент массива по случайно сгенерированному индексу.

search (x) Выполните поиск x в хэш-карте.

Хотя это и устарело, но поскольку на 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;
}

В C # 3.0 + .NET Framework 4 универсальный Dictionary<TKey,TValue>вариант даже лучше, чем Hashtable, потому что вы можете использовать System.Linqметод расширения ElementAt()для индексации в базовый динамический массив, в котором KeyValuePair<TKey,TValue>хранятся элементы:

using System.Linq;

Random _generator = new Random((int)DateTime.Now.Ticks);

Dictionary<string,object> _elements = new Dictionary<string,object>();

....

Public object GetRandom()
{
     return _elements.ElementAt(_generator.Next(_elements.Count)).Value;
}

Однако, насколько мне известно, Hashtable (или его потомок Dictionary) не является реальным решением этой проблемы, потому что Put () может амортизироваться только O (1), а не истинным O (1), потому что это O (N ) на границе динамического изменения размера.

Есть ли реальное решение этой проблемы? Все, о чем я могу думать, - это если вы укажете начальную емкость Dictionary / Hashtable на порядок больше того, что вы ожидаете когда-либо, тогда вы получите операции O (1), потому что вам никогда не нужно изменять размер.

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

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

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

/* 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`
    }
}

Почему бы нам не использовать epoch% arrayysize для поиска случайного элемента. Определение размера массива составляет O (n), но амортизированная сложность будет O (1).

Я думаю, что мы можем использовать список двойных ссылок с хеш-таблицей. ключ будет элементом, а связанное с ним значение будет узлом в двойном списке ссылок.

1. insert (H, E): вставить узел в список двойных ссылок и сделать запись как H [E] = node; О (1)
2. delete (H, E): получить адрес узла с помощью H (E), перейти к предыдущему узлу и удалить и сделать H (E) как NULL, поэтому O (1)
3. содержит (H, E) и getRandom (H), очевидно, O (1)