Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
Here is the C++ Implementation:
#include <iostream>
#include <string>
#include <list>
#include <unordered_map>
using namespace std;
class Node {
public:
bool isLeaf;
std::unordered_map<char, Node*> childMap;
std::string value;
Node() {
isLeaf = false;
value = "";
}
void insertUrl(std::string toInsert, std::string value) {
int len = toInsert.length();
if (len == 0 ) {
this->isLeaf = true;
return;
}
char firstChar = toInsert[0];
if (childMap[firstChar] == NULL) {
Node* child = new Node();
child->value = value + firstChar;
childMap[firstChar] = child;
}
Node* child = childMap[firstChar];
child->insertUrl(toInsert.substr(1, len-1), value + firstChar);
}
void findMatch(std::string toFind, std::list<std::string>& matchedString){
if (this->isLeaf) {
matchedString.push_back(this->value);
}
int len = toFind.length();
// empty string all children are eligible
if (len == 0) {
for (std::unordered_map<char, Node*>::iterator it = childMap.begin();
it != childMap.end(); it++) {
Node* node = it->second;
node->findMatch(toFind, matchedString);
}
return;
}
if (childMap[toFind[0]] != NULL) {
Node* node = childMap[toFind[0]];
node->findMatch(toFind.substr(1, len-1), matchedString);
}
}
};
int main() {
Node* root = new Node();
root->insertUrl("team.com", "");
root->insertUrl("tea.in", "");
root->insertUrl("teamwork.org", "");
root->insertUrl("teams.com", "");
root->insertUrl("pot.uk", "");
root->insertUrl("potter.in", "");
root->insertUrl("post.com", "");
std::list<std::string> myList;
root->findMatch("te", myList);
for (list<std::string>::iterator it = myList.begin(); it != myList.end(); it++) {
cout << *it << endl;
}
return 0;
}
Build a trie from given input string array. At query time, given the input string, (i) follow the trie at the node where incomplete url string stops. Then, (ii) follow the left-most non null node and return the first complete url you find in the trie.
Note: This would work for old ASCII URLs but for new URLs that can contain unicode characters the overhead would be unfeasible. One can consider e.g. R-way trie.
import java.util.regex.*;
import java.util.Vector;
public class AllPossibleURL
{
private static void printAllPossibleURL(Vector<String> urls,String str)
{
for(int i=0;i<urls.size();i++)
{
Pattern pattern=Pattern.compile( "^"+ str +"[a-zA-Z]*" );
Matcher match =pattern.matcher(urls.elementAt( i ));
if(match.find())
{
System.out.println( urls.elementAt( i ) );
}
}
}
public static void main(String [] args)
{
Vector<String> urls = new Vector<String>();
urls.add("team.com");
urls.add("tea.in");
urls.add("teamwork.org");
urls.add("teams.com");
urls.add("pot.uk");
urls.add("potter.in");
urls.add("post.com");
printAllPossibleURL(urls,"pot");
}
}
Simple implementation:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct trie {
struct trie *next[256];
};
void trie_init(struct trie *t)
{
memset(t, 0, sizeof(*t));
}
int trie_add(struct trie *root, char *str)
{
char c;
struct trie **slot, *curr = root;
for (;;) {
c = *str++;
slot = &curr->next[(unsigned char)c];
if (!*slot) {
*slot = malloc(sizeof(**slot));
if (!*slot)
return -1;
trie_init(*slot);
}
curr = *slot;
if (!c)
break;
}
return 0;
}
struct trie *trie_find(struct trie *curr, char *str)
{
char c;
for (;;) {
c = *str++;
if (!c)
break;
curr = curr->next[(unsigned char)c];
if (!curr)
return NULL;
}
return curr;
}
void trie_possible2(struct trie *cur, char *out, int o)
{
int i;
if (cur->next[0])
printf("%.*s\n", o, out);
for (i = 1; i < 256; i++) {
if (!cur->next[i])
continue;
out[o] = (char)i;
trie_possible2(cur->next[i], out, o+1);
}
}
void trie_possible(struct trie *root, char *str)
{
int o = 0;
char c, out[1024];
struct trie *cur = trie_find(root, str);
if (!cur)
return;
while ((c = *str++))
out[o++] = c;
trie_possible2(cur, out, o);
}
int main(void)
{
struct trie root;
char *str[] = {
"team.com", "tea.in", "teamwork.org", "teams.com",
"pot.uk", "potter.in", "post.com",
};
int i, scnt = (int)sizeof(str)/sizeof(*str);
trie_init(&root);
for (i = 0; i < scnt; i++)
if (trie_add(&root, str[i]))
return -1;
printf("=t:\n");
trie_possible(&root, "t");
printf("=ze:\n");
trie_possible(&root, "ze");
printf("=pot:\n");
trie_possible(&root, "pot");
printf("=po:\n");
trie_possible(&root, "po");
return 0;
}
TRIE Java Implementation:
Output:
- R@M3$H.N January 27, 2015