CareerCup

TRIE can used for Auto-Complete.

Here is a simple java implementation:

// Trie.java
public class Trie {

  private TrieNode rootNode;

  public Trie() {
    super();
    rootNode = new TrieNode(' ');
  }

  public void load(String phrase) {
    loadRecursive(rootNode, phrase + "$");
  }

  private void loadRecursive(TrieNode node, String phrase) {
    if (StringUtils.isBlank(phrase)) {
      return;
    }
    char firstChar = phrase.charAt(0);
    node.add(firstChar);
    TrieNode childNode = node.getChildNode(firstChar);
    if (childNode != null) {
      loadRecursive(childNode, phrase.substring(1));
    }
  }

  public boolean matchPrefix(String prefix) {
    TrieNode matchedNode = matchPrefixRecursive(rootNode, prefix);
    return (matchedNode != null);
  }

  private TrieNode matchPrefixRecursive(TrieNode node, String prefix) {
    if (StringUtils.isBlank(prefix)) {
      return node;
    }
    char firstChar = prefix.charAt(0);
    TrieNode childNode = node.getChildNode(firstChar);
    if (childNode == null) {
      // no match at this char, exit
      return null;
    } else {
      // go deeper
      return matchPrefixRecursive(childNode, prefix.substring(1));
    }
  }

  public List<String> findCompletions(String prefix) {
    TrieNode matchedNode = matchPrefixRecursive(rootNode, prefix);
    List<String> completions = new ArrayList<String>();
    findCompletionsRecursive(matchedNode, prefix, completions);
    return completions;
  }

  private void findCompletionsRecursive(TrieNode node, String prefix, List<String> completions) {
    if (node == null) {
      // our prefix did not match anything, just return
      return;
    }
    if (node.getNodeValue() == '$') {
      // end reached, append prefix into completions list. Do not append
      // the trailing $, that is only to distinguish words like ann and anne
      // into separate branches of the tree.
      completions.add(prefix.substring(0, prefix.length() - 1));
      return;
    }
    Collection<TrieNode> childNodes = node.getChildren();
    for (TrieNode childNode : childNodes) {
      char childChar = childNode.getNodeValue();
      findCompletionsRecursive(childNode, prefix + childChar, completions);
    }
  }

  public String toString() {
    return "Trie:" + rootNode.toString();
  }
}

// TrieNode.java
public class TrieNode {

  private Character character;
  private HashMap<Character,TrieNode> children;

  public TrieNode(char c) {
    super();
    this.character = new Character(c);
    children = new HashMap<Character,TrieNode>();
  }

  public char getNodeValue() {
    return character.charValue();
  }

  public Collection<TrieNode> getChildren() {
    return children.values();
  }

  public Set<Character> getChildrenNodeValues() {
    return children.keySet();
  }

  public void add(char c) {
    if (children.get(new Character(c)) == null) {
      // children does not contain c, add a TrieNode
      children.put(new Character(c), new TrieNode(c));
    }
  }

  public TrieNode getChildNode(char c) {
    return children.get(new Character(c));
  }

  public boolean contains(char c) {
    return (children.get(new Character(c)) != null);
  }

  public int hashCode() {
    return character.hashCode();
  }

  public boolean equals(Object obj) {
    if (!(obj instanceof TrieNode)) {
      return false;
    }
    TrieNode that = (TrieNode) obj;
    return (this.getNodeValue() == that.getNodeValue());
  }

  public String toString() {
    return ReflectionToStringBuilder.reflectionToString(this, ToStringStyle.DEFAULT_STYLE);
  }
}

I assume booking.com offers bookings of destinations, hotels, flights, resorts etc.

If so, user can search for any of these 'broad categories'.

One simple approach could be to first have the user pre-select a category (Ex- trying to search for a resort), and internally have multiple tries storing a almost pre-defined list of resorts (using a compressed trie, if memory is not a issue). Also implement a 'LRU cache' mechanism to perform auto-suggest based on 'most recently' used names (under a given category) and remove 'least used ones from cache'.

If we want to give a capability to search for 'anything' (not category specific) then a common trie listing all supported destinations, properties etc can be shown. This could be memory heavy even with a caching logic. So we might have to perform the search in a distributed manner, for instance using a 'map-reduce' algo. Ex-One mapping worker internally crawls for all 'places', one for all 'properties' etc. In order to support such crawling, while storing in trie, we need to 'prefix' each value(atleast leaves) with a category code.

Thanks.

Note :- This is not a scale-able solution.

We can get one restaurant and one flight etc by using the like clause in mysql like "searchString%". Using these we can create the resultant suggestions.

import java.util.*;

public class Trie {
	public static void main(String args[]) {
		Trie trie = new Trie();
		trie.add("William");
		trie.add("williamRoma");
		trie.add("williamRoma");
		trie.add("williamRome");
		System.out.println(trie.calculateCompleteWords());
		Set<String> suggestions = trie.findSuggestions("Wi");
		for (String word : suggestions) {
			System.out.println(word);
		}
	}

	TrieNode root;
	public Trie() {
		root = new TrieNode(new Character(' '));
	}
	public void add(String word) {
		word = word.toLowerCase();
		add(root, word);
	}
	
	public Set<String> findSuggestions(String word) {
		word = word.toLowerCase();
		TrieNode node = isPrefix(word);
		if (node == null)
			return new HashSet<>();
		return findSuggestions(node, word);
	}
	private Set<String> findSuggestions(TrieNode node, String value) {
		Set<String> results = new HashSet<>();
		Iterator<Character> iterator = node.children.keySet().iterator();
		while(iterator.hasNext()) {
			Character character = iterator.next();
			if (node.children.get(character).complete) {
				results.add(value+character.charValue()+"");
			}
			results.addAll(findSuggestions(node.children.get(character), value+character.charValue()+""));
		}
		return results;
	}
	
	private TrieNode isPrefix(String word) {
		return isPrefix(word, root);
	}
	
	private TrieNode isPrefix(String word, TrieNode node) {
		if (word.length() == 0)
			return null;
		if (node == null)
			return null;
		char character = word.charAt(0);
		
			if (node.children.containsKey(new Character(character))) {
				if (word.length() == 1) {
					return node.children.get(new Character(character));
				}
				return isPrefix(word.substring(1), node.children.get(new Character(character)));
			}
			return null;
		
	}
	
	private void add(TrieNode node, String word) {
		if (word.length() == 0)
			return;
		char character = word.charAt(0);
		if (node == null) {
			node = new TrieNode(new Character(character));
			if (word.length() > 1) {
				add(node, word.substring(1));
			} else {
				node.complete = true;
			}
		} else {
			if (node.children.containsKey(new Character(character))) {
				if (word.length() > 1) {
					add(node.children.get(new Character(character)),
							word.substring(1));
				} else {
					node.children.get(new Character(character)).complete = true;
				}
			} else {
				TrieNode trieNode = new TrieNode(new Character(character));
				node.children.put(new Character(character), trieNode);
				if (word.length() > 1) {
					add(node.children.get(new Character(character)),
							word.substring(1));
				} else {
					node.children.get(new Character(character)).complete = true;
				}
			}
		}
	}
	
	public int calculateCompleteWords() {
		return calculateCompleteWords(root);
	}
	
	private int calculateCompleteWords(TrieNode node) {
		if (node == null)
			return 0;
		int count = 0;
		if (node.complete == true) {
			count = 1;
		}
		Iterator<Character> iterator = node.children.keySet().iterator();
		while (iterator.hasNext()) {
			Character charater = iterator.next();
			count += calculateCompleteWords(node.children.get(new Character(
					charater)));
		}
		return count;

	}
}

class TrieNode {
	Character character;
	Map<Character, TrieNode> children;
	boolean complete;

	public TrieNode(Character character) {
		this.character = character;
		this.children = new HashMap<>();
	}
}