Skip to content

Instantly share code, notes, and snippets.

@LuizZak
Last active August 29, 2015 14:18
Show Gist options
  • Save LuizZak/06cf133166cd4bf32f5e to your computer and use it in GitHub Desktop.
Save LuizZak/06cf133166cd4bf32f5e to your computer and use it in GitHub Desktop.
LINQPad runnable resolution to the Fix the Index interview problem (http://ayende.com/blog/170402/interview-question-fix-the-index)
void Main()
{
var tests = new IndexTests();
tests.CanIndexAndQuery();
tests.CanUpdate();
}
// Internal doc class
class Document
{
public readonly string Id; // Let's pretend there is a constructor that initializes this value...
public List<string> Contents; // Probably turn this into a property later...
public Document(string id)
{
Id = id;
}
public override int GetHashCode()
{
return Id.GetHashCode();
}
public override bool Equals(object other)
{
if(ReferenceEquals(other, this)) return true;
if(ReferenceEquals(other, null)) return false;
if(other is Document) return Equals((Document)other);
return false;
}
public bool Equals(Document other)
{
return other.Id == Id;
}
}
// Interface for indexers
interface IIndexer
{
void Index(string docId, string text);
List<string> Query(string term);
void Delete(string docId);
}
// Iterative-implemented hashset indexer, should be clearer than the Linq implementation
class IterativeHashIndexer : IIndexer
{
private HashSet<Document> docs = new HashSet<Document>();
public void Index(string docId, string text)
{
Document doc = new Document(docId);
doc.Contents = new List<string>(text.Split());
docs.Remove(doc);
docs.Add(doc);
}
public List<string> Query(string term)
{
var ret = new List<string>();
foreach(var doc in docs)
{
if(doc.Contents.Any(s => s.Equals(term, StringComparison.OrdinalIgnoreCase)))
{
ret.Add(doc.Id);
}
}
return ret;
}
public void Delete(string docId)
{
docs.RemoveWhere(d => d.Id == docId);
}
}
class LinqHashIndexer : IIndexer
{
private HashSet<Document> docs = new HashSet<Document>();
public void Index(string docId, string text)
{
Document doc = new Document(docId);
doc.Contents = new List<string>(text.Split());
docs.Remove(doc);
docs.Add(doc);
}
public List<string> Query(string term)
{
// This gets a little convoluted, but you can always transform this into a loop
return docs.Where
(
d => d.Contents
.Any
(
s => s.Equals(term, StringComparison.OrdinalIgnoreCase)
)
)
.Select(d => d.Id)
.ToList();
}
public void Delete(string docId)
{
docs.RemoveWhere(d => d.Id == docId);
}
}
class DictionaryIndexer : IIndexer
{
private Dictionary<string, Document> docs = new Dictionary<string, Document>();
public void Index(string docId, string text)
{
Document doc = new Document(docId);
doc.Contents = new List<string>(text.Split());
docs[docId] = doc;
}
public List<string> Query(string term)
{
var ret = new List<string>();
foreach(var kv in docs)
{
if(kv.Value.Contents.Any(s => s.Equals(term, StringComparison.OrdinalIgnoreCase)))
{
ret.Add(kv.Key);
}
}
return ret;
}
public void Delete(string docId)
{
docs.Remove(docId);
}
}
public class IndexTests
{
IIndexer CreateIndexer()
{
// Change with any of the implementations above
return new DictionaryIndexer();
}
[Fact]
public void CanIndexAndQuery()
{
var index = CreateIndexer();
index.Index("users/1", "Oren Eini");
index.Index("users/2", "Hibernating Rhinos");
Assert.Contains("users/1", index.Query("eini"));
Assert.Contains("users/2", index.Query("rhinos"));
}
[Fact]
public void CanUpdate()
{
var index = CreateIndexer();
index.Index("users/1", "Oren Eini");
//updating
index.Index("users/1", "Ayende Rahien");
Assert.Contains("users/1", index.Query("Rahien"));
Assert.Empty(index.Query("eini"));
}
[Fact]
public void CanDelete()
{
var index = CreateIndexer();
index.Index("users/1", "Oren Eini");
index.Index("users/2", "Hibernating Rhinos");
index.Delete("users/1");
Assert.NotContains("users/1", index.Query("eini"));
Assert.Contains("users/2", index.Query("rhinos"));
}
}
// Dummy implementation of the Assert class above, so the code can be executed on LinqPad
static class Assert
{
public static void Contains<T>(T value, IEnumerable<T> values)
{
if(!values.Contains(value))
{
throw new Exception();
}
}
public static void NotContains<T>(T value, IEnumerable<T> values)
{
if(values.Contains(value))
{
throw new Exception();
}
}
public static void Empty<T>(IEnumerable<T> contents)
{
if(contents.Any())
{
throw new Exception();
}
}
}
// Implementing this attribute so the code can run by just removing this FactAttribute and dummy Assert implementation above and running on VisualStudio
class FactAttribute : Attribute { }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment