Booking.com Interview Question
Software DevelopersCountry: Netherlands
Interview Type: Phone Interview
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.
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<>();
}
}
TRIE can used for Auto-Complete.
Here is a simple java implementation:
- R@M3$H.N November 12, 2015