Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
I assume '?' means "any one character".
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class TrieNode {
public:
TrieNode()
{
terminal_ = false;
}
~TrieNode()
{
for (auto &child : children_) {
delete child.second;
}
}
TrieNode *AddChild(char ch)
{
TrieNode *child = children_[ch];
if (!child) {
child = new TrieNode();
children_[ch] = child;
}
return child;
}
TrieNode const *Child(char ch) const
{
auto it = children_.find(ch);
return it != children_.end() ? it->second : NULL;
}
unordered_map<char, TrieNode *> const &Children() const
{
return children_;
}
void Terminal(bool terminal)
{
terminal_ = terminal;
}
bool Terminal() const
{
return terminal_;
}
private:
unordered_map<char, TrieNode *> children_;
bool terminal_;
};
class Trie {
public:
void Add(string const &s)
{
TrieNode *n = &root_;
for (auto const &c : s) {
n = n->AddChild(c);
}
n->Terminal(true);
}
TrieNode *Root()
{
return &root_;
}
private:
TrieNode root_;
};
void Search(TrieNode const *n, string const &pattern, vector<string> &out, string word = "", int idx = 0)
{
if (idx < 0 ||
idx > pattern.size() ||
!n)
{
return;
}
if (idx == pattern.size()) {
if (n->Terminal()) {
out.push_back(word);
}
return;
}
if (pattern[idx] == '?') {
for (auto &el : n->Children()) {
char ch = el.first;
TrieNode const *child_node = el.second;
Search(child_node, pattern, out, word + ch, idx + 1);
}
} else {
Search(n->Child(pattern[idx]), pattern, out, word + pattern[idx], idx + 1);
}
}
int main(int argc, char const **argv)
{
vector<string> const dict = {"cat", "rat", "mat", "apple", "boy", "bat"};
Trie trie;
for (string const &word : dict) {
trie.Add(word);
}
vector<string> out;
Search(trie.Root(), "?at", out);
for (auto &s : out) {
cout << s << "\n";
}
return 0;
}
- Makarand August 30, 2017