StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is a C# solution to that problem I came up with a little while back when asked the same question. It implements Add, Remove, Contains, and Random along with other standard .NET interfaces. Not that you would ever need to implement it in such detail during an interview but it's nice to have a concrete solution to look at...</p> <pre class="lang-cs prettyprint-override"><code>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; } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload