Google Interview Question for Software Engineer / Developers


Country: Israel
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

TRIE Java Implementation:

import java.util.*;
import java.util.Map.Entry;

public class AutoCompleteTrie {

    protected final Map<Character, AutoCompleteTrie> children;
    protected String value;
    protected boolean isWord = false;

    public AutoCompleteTrie() {
        this(null);
    }

    private AutoCompleteTrie(String value) {
        this.value = value;
        children = new HashMap<Character, AutoCompleteTrie>();
    }
    
    public void insert(String word) {
        if (word == null) {
            throw new IllegalArgumentException("Can't Add NULL.");
        }
        AutoCompleteTrie node = this;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.add(c);
            }
            node = node.children.get(c);
        }
        node.isWord = true;
    }

    protected void add(char c) {
        String val;
        if (this.value == null) {
            val = Character.toString(c);
        } else {
            val = this.value + c;
        }
        children.put(c, new AutoCompleteTrie(val));
    }

    public String find(String word) {
        AutoCompleteTrie node = this;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return "";
            }
            node = node.children.get(c);
        }
        return node.value;
    }

    public Collection<String> autoComplete(String prefix) {
        AutoCompleteTrie node = this;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return Collections.emptyList();
            }
            node = node.children.get(c);
        }
        return node.allPrefixes();
    }

    protected Collection<String> allPrefixes() {
        List<String> results = new ArrayList<String>();
        if (this.isWord) {
            results.add(this.value);
        }
        for (Entry<Character, AutoCompleteTrie> entry : children.entrySet()) {
            AutoCompleteTrie child = entry.getValue();
            Collection<String> childPrefixes = child.allPrefixes();
            results.addAll(childPrefixes);
        }
        return results;
    }
    
    public static void main(String[] args) {
		AutoCompleteTrie root = new AutoCompleteTrie();
		root.insert("team.com");
		root.insert("tea.in");
		root.insert("teamwork.org");
		root.insert("teams.com");
		root.insert("pot.uk");
		root.insert("potter.in");
		root.insert("post.com");
		
		Collection<String> results = root.autoComplete("te") ;
		for (String string : results) {
			System.out.println(" "+ string);
		}
	}
}

Output:

teams.com
teamwork.org
team.com
tea.in

- R@M3$H.N January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- pavelkushtia February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

One word: Trie.

- anan January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- autoboli January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}

- Pradeep kumar R S January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ken February 21, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More