Google Interview Question: Define how search keyword sug... | Glassdoor.com.au

Interview Question

Graduate Software Engineer Interview Sydney

Define how search keyword suggestion (such as the

  suggestions in google search) can be implemented.
Answer

Interview Answer

2 Answers

0

Use Trie (or Suffix Tree).
In C++. there is no such data structure, so have to write it.
Build a function named "std::vector GetStringsWithPrefix(std::string prefix)"

xuyan on 27 Jun 2014
0

Here's a trie I wrote in C#

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

public class KeywordSuggester
{
    Trie _trie;

    public KeywordSuggester(Trie trie)
    {
        _trie = trie;
    }

    public IEnumerable Suggestions(string prefix)
    {
        return _trie.HasPrefix(prefix);
    }
}

public class Trie : TrieNode
{
    public Trie() : base()
    {
    }
}

public class TrieNode
{
    public TrieNode()
    {
        Children = new Dictionary();
    }
    public Dictionary Children { get; set; }

    public void Add(string word)
    {
        if (word.Length == 0)
        {
            return;
        }
        char letter = word[0];
        TrieNode node = null;
        if (Children.TryGetValue(letter, out node))
        {
            node.Add(word.Substring(1));
        }
        else
        {
            node = new TrieNode();
            Children.Add(letter, node);
            node.Add(word.Substring(1));
        }
    }
    private IEnumerable GetAllWords()
    {
        foreach (KeyValuePair kv in Children)
        {
            string prefix = kv.Key.ToString();
            TrieNode node = kv.Value;
            if (node.Children.Count == 0)
            {
                yield return prefix;
            }
            else
            {
            IEnumerable words = node.GetAllWords();
            foreach (string word in words)
            {
                yield return prefix + word;
            }
        }
        }
    }

    public IEnumerable HasPrefix(string prefix)
    {
        if (prefix.Length == 0)
        {
            foreach (string word in GetAllWords())
            {
                yield return word;
            }
            yield break;
        }
        char letter = prefix[0];
        TrieNode node = null;
        if (Children.TryGetValue(letter, out node))
        {
            IEnumerable results = node.HasPrefix(prefix.Substring(1));
            foreach (string result in results)
            {
                yield return letter + result;
            }
        }
        yield break;
    }
}

[TestClass]
public class KeywordSuggesterTests
{
    [TestMethod]
    public void Suggestions_SimpleSet_HasCorrectSuggestions()
    {
        var trie = new Trie();
        trie.Add(“dog”);
        trie.Add(“cat”);
        trie.Add(“dot”);
        var suggester = new KeywordSuggester(trie);
        List suggestions = suggester.Suggestions(“do”).ToList();
        Assert.AreEqual(2, suggestions.Count);
        Assert.IsTrue(suggestions.Contains(“dog”));
        Assert.IsTrue(suggestions.Contains(“dot”));
    }
}

Davo on 29 Mar 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.