Мне дали эту проблему в интервью. Как бы вы ответили?
Создайте структуру данных, которая предлагает следующие операции в O (1):
- Вставка
- удалить
- содержит
- получить случайный элемент
Структура данных: вставка, удаление, содержит, получение случайного элемента, все в точке O (1)
Ответ 1
Рассмотрим структуру данных, состоящую из хэш-таблицы H и массива A. Клавиши hashtable - это элементы в структуре данных, а значения - их позиции в массиве.
- insert (value): добавьте значение в массив и пусть я будет его индексом в A. Установите H [значение] = i.
- remove (value): Мы заменим ячейку, содержащую значение в A, с последним элементом в A. Пусть d - последний элемент в массиве A с индексом m. пусть я будет H [значение], индексом в массиве значения, которое нужно удалить. Установите A [i] = d, H [d] = i, уменьшите размер массива на единицу и удалите значение из H.
- содержит (значение): return H.contains(значение)
- getRandomElement(): пусть r = random (текущий размер A). return A [r].
так как массив должен автоматически увеличивать размер, он будет амортизировать O (1), чтобы добавить элемент, но я думаю, что ОК.
Ответ 2
O (1) поиск подразумевает хешированную структуру данных.
Для сравнения:
- O (1) вставка/удаление с помощью O (N) поиска подразумевает связанный список.
- O (1) insert, O (N) delete и O (N) lookup подразумевает список с поддержкой массива
- O (logN) insert/delete/lookup подразумевает дерево или кучу.
Ответ 3
Вам может не понравиться это, потому что они, вероятно, ищут умное решение, но иногда оно платит, чтобы придерживаться ваших пистолетов... Хэш-таблица уже удовлетворяет требованиям - возможно, лучше всего чем все остальное (хотя, очевидно, в амортизированном постоянном времени и с различными компромиссами с другими решениями).
Требование, что сложным является выбор "случайный элемент": в хеш-таблице вам нужно будет сканировать или зондировать такой элемент.
Для закрытой хеширования/открытой адресации вероятность того, что какой-либо данный ковш будет занята, равна size() / capacity(), но, как правило, это обычно сохраняется в постоянном мультипликативном диапазоне с помощью реализации хэш-таблицы (например, таблица может храниться больше, чем ее текущее содержимое, скажем, от 1.2x до ~ 10x в зависимости от производительности/настройки памяти). Это означает, что в среднем мы можем ожидать поиска от 1,2 до 10 ведер - полностью независимо от общего размера контейнера; амортизируется O (1).
Я могу представить два простых подхода (и еще много других):
-
искать линейно из случайного ведра
- рассмотрим пустые ведомые ведомости ala "-AC ----- B-D": вы можете сказать, что первый "случайный" выбор справедлив, хотя он благоприятствует B, потому что у B не было больше вероятности предпочтительнее других элементов, но если вы делаете повторные "случайные" выборки с использованием тех же значений, то ясно, что B, которые часто предпочитают, может быть нежелательным (ничто в вопросе не требует даже вероятности)
-
повторяйте случайные буферы, пока не найдете заполненный файл
- "только" емкость()/размер() средние посещенные ковши (как указано выше) - но на практике более дорогими, потому что генерация случайных чисел относительно дорога и бесконечно плоха, если бесконечно маловероятно худшее поведение...
- более быстрый компромисс заключался бы в том, чтобы использовать список предварительно сгенерированных случайных смещений из начального случайно выбранного ковша,% -в их в подсчет веток
- "только" емкость()/размер() средние посещенные ковши (как указано выше) - но на практике более дорогими, потому что генерация случайных чисел относительно дорога и бесконечно плоха, если бесконечно маловероятно худшее поведение...
Не отличное решение, но все же может быть лучшим общим компромиссом, чем накладные расходы на память и производительность для поддержания второго массива индексов в любое время.
Ответ 4
Лучшим решением, вероятно, является хэш-таблица + массив, он очень быстрый и детерминированный.
Но самый низкий рейтинг (просто используйте хеш-таблицу!) на самом деле тоже классно!
- хэш-таблица с повторным хешированием или новый выбор ковша (т.е. один элемент на каждый ковш, без связанных списков)
- getRandom() неоднократно пытается выбрать случайное ведро до тех пор, пока оно не будет пустым.
- как отказоустойчивый, возможно, getRandom(), после неудачных попыток N (количество элементов) выбирает случайный индекс я в [0, N-1], а затем линейно проходит хэш-таблицу и выбирает #i -й элемент.
Люди могут не нравиться это из-за "возможных бесконечных циклов", и я видел, что у очень умных людей тоже есть эта реакция, но это неправильно! Бесконечно маловероятных событий просто не бывает.
Предполагая хорошее поведение вашего псевдослучайного источника - что нетрудно установить для этого конкретного поведения - и что хэш-таблицы всегда заполнены не менее чем на 20%, легко увидеть, что:
Никогда не произойдет, что getRandom() должен попробовать более 1000 раз. Просто никогда. В самом деле, вероятность такого события составляет 0,8 ^ 1000, что составляет 10 ^ -97, поэтому нам пришлось бы повторить его 10 ^ 88 раз, чтобы иметь один шанс в миллиард из когда-либо происходящего один раз. Даже если эта программа работала полный рабочий день на всех компьютерах человечества до тех пор, пока Солнце не умрет, этого никогда не произойдет.
Ответ 5
Вот решение С# для этой проблемы, я придумал немного назад, когда задал тот же вопрос. Он реализует 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<T>"/> class.
/// </summary>
public Bag()
: this(0)
{
}
/// <summary>
/// Initializes a new instance of the <see cref="Bag<T>"/> 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<T>"/> 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;
}
}
}
Ответ 6
Хотя это уже старо, но поскольку на С++ нет ответа, здесь мои два цента.
#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;
}
Ответ 7
Для этого вопроса я буду использовать две структуры данных
- HashMap
- ArrayList/Array/Double LinkedList.
Шаги: -
- Вставка: - Проверьте, присутствует ли X в HashMap - сложность времени O (1). if not Present Then Добавить в конец ArrayList - Сложность времени O (1). добавьте его в HashMap также в качестве ключа и последнего индекса как значение - сложность времени O (1).
- Удалить: - проверить, присутствует ли X в HashMap - сложность времени O (1). Если присутствует, то найдите его индекс и удалите его из HashMap - сложность времени O (1). замените этот элемент последним элементом в ArrayList и удалите последний элемент - сложность времени O (1). Обновите индекс последнего элемента в HashMap - сложность времени O (1).
- GetRandom: - Генерировать случайное число от 0 до последнего индекса ArrayList. вернуть элемент ArrayList произвольно созданный индекс - сложность времени O (1).
- Поиск: - См. в 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).
Ответ 8
В С# 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 (или его потомство) не является реальным решением этой проблемы, потому что Put() можно амортизировать только O (1), а не true O (1), поскольку это O (N) на границе динамического изменения размера.
Есть ли реальное решение этой проблемы? Все, о чем я могу думать, это если вы указали начальную емкость Dictionary/Hashtable на порядок выше того, чего вы ожидаете от необходимости, тогда вы получите операции O (1), потому что вам никогда не нужно изменять размер.
Ответ 9
Мы можем использовать хеширование для поддержки операций в течение Θ (1).
вставка (х) 1) Проверьте, присутствует ли x, выполнив поиск в хэш-карте. 2) Если нет, тогда вставьте его в конец массива. 3) Добавьте также в хэш-таблицу, x добавляется как индекс ключа и последнего массива в качестве индекса.
удалить (х) 1) Проверьте наличие x, выполнив поиск в хэш-карте. 2) Если есть, то найдите его индекс и удалите его из хэш-карты. 3) Смените последний элемент с этим элементом в массиве и удалите последний элемент. Перестановка выполняется, потому что последний элемент можно удалить в O (1) раз. 4) Обновить индекс последнего элемента в хэш-карте.
getRandom() 1) Создайте случайное число от 0 до последнего индекса. 2) Верните элемент массива в случайно сгенерированный индекс.
поиск (х) Сделайте поиск х в хэш-карте.
Ответ 10
Я согласен с Аноном. За исключением последнего требования, при котором требуется получение случайного элемента с равной честностью, все остальные требования могут быть решены только с использованием единственного DS на основе Hash. Я выберу HashSet для этого в Java. По модулю хеш-кода элемента я получаю индекс no базового массива в O (1) раз. Я могу использовать это для добавления, удаления и содержит операции.
Ответ 11
Не можем ли мы сделать это с помощью HashSet Java? Он предоставляет insert, del, поиск по O (1) по умолчанию. Для getRandom мы можем использовать итератор Set, который в любом случае дает случайное поведение. Мы можем просто перебрать первый элемент из набора, не беспокоясь об остальных элементах
public void getRandom(){
Iterator<integer> sitr = s.iterator();
Integer x = sitr.next();
return x;
}
Ответ 12
/* 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`
}
}
Ответ 13
Я думаю, мы можем использовать двойной список ссылок с хэш-таблицей. ключ будет элементом, и его связанное значение будет node в двойном списке ссылок.
- insert (H, E): вставьте node в двойной список ссылок и введите запись как H [E] = node; O (1)
- удалить (H, E): получить адрес node по H (E), перейти к предыдущему из этого node и удалить и сделать H (E) как NULL, поэтому O (1)
- содержит (H, E) и getRandom (H) obviuosly O (1)