Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 10 vote

Build a trie. In every node of the trie have a counter. Whenever you are adding a word, increment counters of all nodes you meet on the way down. Counter represents, how many words have this node in its prefix. Counter == 1 means unique prefix.

Then browse the trie and when you meet a node with counter equal to 1 for the first time on the last way down, you have found a unique prefix for that particular word that goes through this node (note that there is exactly 1 word going through that node).

The code could look something like this:

#include <string>
#include <sstream>
#include <map>
#include <iostream>

using namespace std;

// Trie structure
struct Node {
	bool stop = false;
	int counter = 0;
	map<char, Node *> children;
};

// Building a prefix trie
Node * buildTrie(const vector<string> & dictionary) {
	Node * root = new Node;

	for(string word : dictionary) {
		Node * n = root;

		for(char c : word) {
			Node * child;
			auto it = n->children.find(c);
			if(it != n->children.end()) {
				child = it->second;
			} else {
				child = new Node;
				n->children.insert(pair<char, Node *>(c, child));
			}

			++child->counter;
			n = child;
		}

		n->stop = true;
	}

	return root;
}


void _createMap(map<string, string> & result, const Node * n, string prefix) {
	if(n->counter == 1) {
		stringstream word;
		word << prefix;

		while(n->children.size() > 0) {
			// there is only one child here, sice counter == 1
			auto it = n->children.begin();
			n = it->second;
			word << it->first;
		}

		// assert(result.find(prefix) == result.end()); // validity check
		result.insert(pair<string, string>(prefix, word.str()));
		return;
	}

	// "bar", "bartender" situation - unclear instructions from OP
	if(n->stop) { 
		return;
	}

	for(auto it : n->children) {
		_createMap(result, it.second, prefix + it.first);
	}
}


map<string, string> createMap(const Node * root) {
	map<string, string> result;

	for(auto it : root->children) {
		_createMap(result, it.second, string(1, it.first));
	}

	return result;
}


// entry point for the algorithm
map<string, string> createPrefixMap(const vector<string> & dictionary) {
	return createMap(buildTrie(dictionary));
}


void main() {
	auto result = createPrefixMap({"dog", "bear", "duck"});
	for(auto it : result) {
		cout << it.first << "\t" << it.second << endl;
	}
}

- Premun October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

didn't work for this input ?

{"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"}

- Dr.H October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, I didn't test it properly. But the problem is by the commentary, that says:
"bar", "bartender" situation - unclear instructions from OP

There shouldn't be return.

- Premun October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There should be following:
result.insert(pair<string, string>(prefix, prefix));

But I believe that the overall idea is correct no matter the small details.

- Premun October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This was my first idea too, elegant and simple. It does take, however extra O(n*m) space, where n is the number of words and m is the average word length. And the time complexity is O(n*m) to build the trie, plus O(n*m) to produce the result.
All in all, O(n*m) time with O(n*m) space.
There is another solution possible, sorting the array first in O((n*m)logn) and then comparing each word with the next (also keeping what the last common prefix was), this step will require an extra O(n*m) time. This solution overall complexity is O(1) space and O(n*m log n) time.

- Mike October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And this is it:

static String[] uniqueprefix(String[] words){
		String[] prefix = new String[words.length];
		Arrays.sort(words);
		String prevPrefix = "";
		String nextPrefix = "";
		for(int i = 0; i < words.length; i++){
			String current = words[i];
			if(i < words.length-1){
				String next = words[i+1];
				prevPrefix = nextPrefix;
				int idx = 0;
				while(idx < current.length() && current.charAt(idx) == next.charAt(idx)) idx++;
				nextPrefix = idx == 0 ? "" : current.substring(0, idx);
					String elected;
					if(prevPrefix.length() > nextPrefix.length())
						elected = prevPrefix;
					else
						elected = nextPrefix;
					
					if(elected.length() == current.length()){
						prefix[i] = "";
						nextPrefix = nextPrefix.substring(0, nextPrefix.length()-1);
					}
					else
						prefix[i] = elected + current.charAt(elected.length());
			}
			else{
				prefix[i] = nextPrefix + current.charAt(nextPrefix.length());
			}
		}
		return prefix;
	}

- Mike October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

build a trie of all the words. later on go over all the input words you got, and for each word save the node after last "split node" you had in the trie for that word. this "split node" +1 is the prefix you need to find the word later

- ins October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But I think this will be very complicated. Intuition will be go through every word, and add the shortest prefix. The running time might be terrible though

- Sammi October 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

class Solution
{
public:
	vector<string> shortprefix(vector<string> input)
	{
		sort(input.begin(),input.end());
		int l=input.size();
		vector<string> ans(l," ");
		for (int i=0;i<l;++i)
		{
			int left=0,right=0;
			if (i>0)
			{
			int l1=min(input[i].length(),input[i-1].length());
			while (left<l1 && input[i][left]==input[i-1][left]) left++;
			}
			if (i<l-1)
			{
			int l2=min(input[i].length(),input[i+1].length());
			while (right<l2 && input[i][right]==input[i+1][right]) right++;
			}
			int x=max(left,right);
			ans[i]=input[i].substr(0,x+1);
			if (x==input[i].length()) ans[i]="";
		}
		return ans;
	}		
};

- czhao86 October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about a hash map? The unique prefix is the key.

- Kevin918 October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my prefix tree implementation.
time complexity and space complexity are O(n) where n is sum of characters in all words.
Note that behaviour of createPrefix for word that wasn't in initial array of strings is undefined.
And also statement of problem is somewhat ambiguous. I assume that in examples prefix for "dog" should be "dog" itself, and the same for "dot" and "bear". If it should be empty string then it's possible to create wrapper that will compare result of findPrefix and word itself.

import java.util.LinkedList;
import java.util.ListIterator;

class PrefixTree {
	private final char value;
	private int count;
	private LinkedList <PrefixTree> descendants = new LinkedList <PrefixTree> ();

	public PrefixTree (String[] strs) {
		this.value = '\0';
		count = 0;
		
		for (String str : strs)
			this.addWord (str);
	}
	
	private PrefixTree (char value) {
		this.value = value;
		count = 1;
	}
	
	private void updateDescendants (char[] str, int i) {
		if (i < 0 || i >= str.length)
			return;
		PrefixTree ptd = addDescendant (str[i]);
		ptd.updateDescendants (str, i +1);
	}
	
	private PrefixTree addDescendant (char descendantch) {
		PrefixTree descendant = new PrefixTree (descendantch);
		ListIterator <PrefixTree> it = this.descendants.listIterator();
		while (it.hasNext()) {
			PrefixTree ptd = it.next();
			if (ptd.value < descendant.value)
				continue;
			if (ptd.value > descendant.value) {
				it.set (descendant);
				it.add (ptd);
				return descendant;
			}
			if (ptd.value == descendant.value) {
				ptd.count++;
				return ptd;
			}
		}
		this.descendants.add (descendant);
		return descendant;
	}

	private void createPrefix (StringBuilder sb, char[] str, int i) {
		if (i < 0 || i >= str.length)
			return;
		ListIterator <PrefixTree> it = this.descendants.listIterator();
		while (it.hasNext()) {
			PrefixTree ptd = it.next();
			if (ptd.value < str[i])
				continue;
			if (ptd.value > str[i])
				throw new RuntimeException ("Word is not in the PrefixTree");
			if (ptd.value == str[i]) {
				sb.append (ptd.value);
				if (ptd.count == 1) return;
				ptd.createPrefix (sb, str, i +1);
				return;
			}
		}
		throw new RuntimeException ("Word is not in the PrefixTree");
	}
	
	private void addWord (String str) {
		this.updateDescendants (str.toCharArray(), 0);
	}
	
	public String findPrefix (String str) {
		StringBuilder sb = new StringBuilder();
		this.createPrefix (sb, str.toCharArray(), 0);
		return sb.toString();
	}
	
	public static void main (String[] args) {
		PrefixTree pt = new PrefixTree(args);
			
		for (String str : args)
			System.out.println (pt.findPrefix (str));
	}
}

- anonymous October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use trie with count

#include <iostream>
#include <string>

using namespace std;

struct node
{
	char key;
	node *child[26];
	int count=0;
};

class trie
{
public:
node *root;
trie()
{
	root=new node;
}
void insert(string st)
{
	node *cur=root;
	for (int i=0;i<st.length();++i)
	{
		if (!cur->child[st[i]-'a'])
			{
				node *tmp=new node;				
				cur->child[st[i]-'a']=tmp;
			}
		(cur->child[st[i]-'a']->count)++;
		cur=cur->child[st[i]-'a'];
	}
}
bool search(string st)
{
	node *cur=root;
	for (int i=0;i<st.length();++i)
	{
		if (!cur->child[st[i]-'a']) return false;
		else cur=cur->child[st[i]-'a'];
	}
	return true;
}
void print(string prefix, node* &root)
{
	int i=0;
	while (i<26)
	{
		if (root->child[i] && root->child[i]->count==1)
		{
			prefix.push_back(i+'a');
			cout<<prefix<<endl;
			prefix.pop_back();
		}
		else if (root->child[i] && root->child[i]->count!=1)
		{
			prefix.push_back(i+'a');
			print(prefix,root->child[i]);
			prefix.pop_back();
		}
		i++;
	}
}
};

int main()
{
	trie test;
	test.insert("zebra");
	test.insert("dog");
	test.insert("duck");
	test.insert("dot");
	test.insert("bearc");
	test.insert("bear");
	test.print("",test.root);
	cout<<endl;
	cout<<test.root->child[3]->child[14]->child[6]->count<<endl;
	return 0;

}

- czhao86 October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach to this would be
input: ["zebra", "dog", "duck",”dot”]
1. Assume we are dealing with simple characters, maintain a character counter and increment the counter on occurrence of that letter in all the words
example - Using the Hashmaps, we can have z:1,e:1,b:1,r:1,a:1,d:3...
2. Compare the current word and create the prefix in a by appending the letters until you find the letter with 1 occurrence.
With that we the output would be z,dog,du,dot

- RInValley October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It desn't seems right.
For example if input is [dog, god] you'll have wrong prefixes

- anonymous October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also won't work for ["zebra", "bear", "duck", "bearcat"]. Doesn't take into account the positions of characters, simply count won't solve it for you.

- Anonymous October 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

With that logic, in case of dog & god.. wouldnt the prefix be "d" and "g" right
&
["zebra", "bear", "duck", "bearcat"] would be z,bear,d,bearc

- RInValley October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is very easy :
this is O(n) solution
a- scan all the words add the first letter to a map , this will tell you the letters you need to process
b- scan the list for each letter collect the words for that letter
c- for the collected words start add them to a temp map
c-1: if the collected words is more than 1 start by adding using the first 2 letters
c-2: if you couldn't add all the words using first 2 letters retry using 3 letters and so on
d- After all you words added to temp map Add them to the main map
e: continue till you finish your letter map

here it is :

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

void shortestPrefixMap(){
    string wordList[] ={"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"};
    map<char,int> lettersMap ;
    int len = sizeof(wordList)/sizeof(wordList[0]);
    for(int i=0;i<len;i++){
        char firstWordLetter =  wordList[i].at(0);
        if(lettersMap.count(firstWordLetter)>0){
            lettersMap[firstWordLetter]+=1;
        }
        else{
            lettersMap[firstWordLetter]=1;
        }
    }
    map<string,string> wordsMap;
    map<string,string> MainMap;
    vector<string> words;
    for(auto it : lettersMap){
        
        words.clear();
        wordsMap.clear();
        
        for(auto word : wordList){
            if(word.at(0)!=it.first) continue;
            words.push_back(word);
        }
        // for the collected words start the prefix
        if(words.size()==1){
            // add it to the main
            MainMap[words[0]]=words[0].at(0);
        }
        else {
            // prefix
            int substrignEnd=1;
            int count=0;
            while(count<it.second){
                string key = words[count].substr(0,substrignEnd);
                while(wordsMap.count(key)>0){
                    substrignEnd+=1;
                    key = words[count].substr(0,substrignEnd);
                }
                wordsMap[key]=words[count];
                substrignEnd=1;
                count++;
            }
            // everything done add them to the main map
            for(auto it : wordsMap){
                MainMap[it.second]=it.first;
            }
        }
        
    }
    
    for(auto it : MainMap ){
        cout<<it.first<<"=>"<<it.second<<endl;
    }
    
}



int main(int argc, const char * argv[]) {
    
    shortestPrefixMap();
    return 0;
}

- Dr.H October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dr. H the solution looks very complicated what are you trying to do here..
What's wrong with a trie

- Ssl October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are building a trie and the trie node had a container or map for each node !
the trie solution use N containers for N words , it is so complex for the problem you are trying to solve. and will not scale .

read my solution again it is very simple using only a map.

- Dr.H October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
struct Carrier
{
string s;
bool Valid;
Carrier(string a="",bool b=true){s=a;Valid=b;}
};

void printlf(map<string,string> a)
{
map<string,string>::iterator it;cout<<"\n hashMap\n";
for(it=a.begin();it!=a.end();++it)cout<<"\n\t"<<it->first<<"-->"<<it->second ;
}

void print(map<string,Carrier> a)
{
map<string,Carrier>::iterator it;cout<<"\n hashMap\n";
for(it=a.begin();it!=a.end();++it)cout<<"\n\t"<<it->first<<"-->"<<it->second.s <<"\t\t\t Valid:"<<it->second.Valid;
}
void operat(map<string,Carrier> & a,string c,string ts)
{
string n1,n2;
map<string,Carrier>::iterator it;
it=a.find(c);unsigned int ii;
{
Carrier k=it->second;

for(ii=0;ii<ts.size() && ii<k.s.size() && ts[ii]==k.s[ii];n1+=ts[ii],n2+=ts[ii],ii++);
if(ii>=ts.size()){Carrier we;
n2+=k.s[ii];
a[n1]=we;
a[n2]=k.s;}
else if(ii>=k.s.size()){Carrier we;n1+=ts[ii];a[n1]=ts;a[n2]=we;}
else {n1+=ts[ii];n2+=k.s[ii];a[n1]=ts;a[n2]=k.s; }
it=a.find(c);
it->second.Valid=false;
}

}
void problem(string a,string b)
{

}
int main()
{
string a[]={"zebra", "dog", "duck", "dove","bear","bearcat"};
map<string,Carrier> mymap;
map<string,string> lf;
map<string,Carrier>::iterator it;


for(int ii=0;ii<6;ii++)
{ string c;
c+=(a[ii][0]);
if(mymap.find(c)==mymap.end())
{Carrier k(a[ii]);mymap[c]=k;
}
else
{operat(mymap,c,a[ii]);
}
}
print(mymap);


for(it=mymap.begin();it!=mymap.end();++it)if(it->second.Valid)lf[it->second.s]=it->first;

printlf(lf);
}

- jovi October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi my solution for that problem. I was looking for something concise in the code. So you don't have time during 45 min interview implement large portion of the code. You need to be concise.

class ShortPrefixer {
    public static void main(String args[]) {
        String[] input = {"zebra", "dog", "duck", "dot"};
        generateShortcuts(input);

        String[] input2 = {"zebra", "dog", "duck", "dove"};
        generateShortcuts(input2);

        String[] input3 = {"bearcat", "bear"};
        generateShortcuts(input3);
    }

    // returns len of the shared path between two words in input array. Compared words are taken from pos x and y.
    static int getSharedLen(String[] input, int x, int y){
        if ( y < 0 )  return 0;
        if ( y>= input.length ) return 0;

        String w1 = input[x];
        String w2 = input[y];

        int pos = 0;
        while(pos<w1.length() && pos < w2.length() && w1.charAt(pos) == w2.charAt(pos))  pos++;
        return pos;
    }

    static void generateShortcuts(String[] input){
        Arrays.sort(input);

        for(int x=0;x<input.length;x++){
            int prefixLen = (int) Math.max(getSharedLen(input, x,x+1), getSharedLen(input, x,x-1)) +1;
            if (prefixLen<=input[x].length()) {
                System.out.println(input[x] + ":: " +input[x].substring(0, prefixLen));
            }else{
                System.out.println(input[x] + "::"); //no possible unique prefix
            }
        }
    }
}

- Anonymous October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n): hand-made hashmap for quick analysis of each starting letter-

void GetPrefixes(std::list<std::string>& strList, std::list<std::string>& prefixList)
{
    std::list<std::string> wordList[26];

    for(std::list<std::string>::iterator i = strList.begin(); i != strList.end(); i++)
    {
        char c = i->at(0);
        wordList[c - 'a'].push_back(*i);
    }

    for(std::list<std::string>::iterator i = strList.begin(); i != strList.end(); i++)
    {
        char c = i->at(0);
        std::list<std::string>& words = wordList[c - 'a'];

        std::string str;
        str.append(1, c);
        if(words.size() <= 1)
        {
            // this is the only word of this letter! we're done
            prefixList.push_back(str);
        }
        else
        {
            unsigned int letter = 1;
            str.append(1, i->at(letter));

            // append a letter at a time that can be compared against the mini-list
            while(letter < i->size())
            {
                bool foundIt = false;
                for(std::list<std::string>::iterator j = words.begin(); j != words.end(); j++)
                {
                    // make sure we don't compare against ourselves!
                    if(j->find(str) == 0 && (*j != *i))
                    {
                        foundIt = true;
                        break;
                    }
                }

                // if we found a match, keep getting more specific, otherwise: we're done
                if(foundIt)
                {
                    letter++;
                    if(letter >= i->size())
                    {
                        prefixList.push_back(str);
                        break;
                    }
                    else
                    {
                        str.append(1, i->at(letter));
                    }
                }
                else
                {
                    prefixList.push_back(str);
                    break;
                }
            }
        }
    }
}

- Anonymous November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply use a prefix tree to implement and here is an C++ code
[code]

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
    int count;
    map<char,node*>child;
    node():count(0){;}
};
void insert(node*p,string s){
    p->count++;
    if(s.empty())return;
    if(p->child.count(s[0])==0)
        p->child[s[0]]=new node();
    insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
    node*p=root;
    for(int i=0;i<s.size();i++){
        p=p->child[s[i]];
        if(p->count==1)
            return s.substr(0,i+1);
    }
    return s;
}
int main(){
    vector<string>v;
    v.push_back("bearcat");
    v.push_back("bear");

    node*root=new node();
    for(int i=0;i<v.size();i++)
        insert(root,v[i]);
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<":"<<query(root,v[i])<<endl;
    return 0;
}

[/code]

- fmars November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply use a prefix tree to implement and here is an C++ code
[code]

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
struct node{
    int count;
    map<char,node*>child;
    node():count(0){;}
};
void insert(node*p,string s){
    p->count++;
    if(s.empty())return;
    if(p->child.count(s[0])==0)
        p->child[s[0]]=new node();
    insert(p->child[s[0]],s.substr(1,s.size()-1));
}
string query(node*root,string s){
    node*p=root;
    for(int i=0;i<s.size();i++){
        p=p->child[s[i]];
        if(p->count==1)
            return s.substr(0,i+1);
    }
    return s;
}
int main(){
    vector<string>v;
    v.push_back("bearcat");
    v.push_back("bear");

    node*root=new node();
    for(int i=0;i<v.size();i++)
        insert(root,v[i]);
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<":"<<query(root,v[i])<<endl;
    return 0;
}

[/code]

- fmars November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using tree.

#include <vector>
#include <string>
#include <map>
#include <memory>
#include <iostream>

using namespace std;

class GraphNode {
public:
	map<char, shared_ptr<GraphNode>> children;
	string value;
	bool isLeaf;
	GraphNode() {isLeaf = false;}
};

void addWord(shared_ptr<GraphNode> g, string word) 
{
	auto child = g->children[word[0]];
	if(child == nullptr) {
		child = g->children[word[0]] = make_shared<GraphNode>();
		child->value = word.substr(1);
		if(child->value.size() == 0) {
			child->isLeaf = true;
		}
	} else {
		if (child->value.size() > 0) {
			addWord(child, child->value);
			child->value = string();
		}
		addWord(child, word.substr(1));
	}
}
void printGraph(shared_ptr<GraphNode> g, vector<char> sofar)
{
	if(g->isLeaf || g->children.size() == 0) {
		string abbrev;
		for(auto n : sofar) {
			abbrev.push_back(n);
		}
		cout << abbrev << ": " << abbrev << g->value << endl;
	}
	for( auto it = g->children.begin(); it != g->children.end(); ++it ) {
      auto ch = it->first;
      auto child = it->second;
	  auto v = sofar;
	  v.push_back(ch);
	  printGraph(child, v);
    }
}

int main()
{
	auto root = make_shared<GraphNode>();
	addWord(root,"dog");
	addWord(root,"duck");
	addWord(root, "zebra");
	addWord(root, "dot");
	addWord(root, "dogma");
	printGraph(root, vector<char>());
	return 0;
}

- Mhret November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//simple o(nlogn) solution and o(n) space
	private static Map<String,String>  getPrefixes(String [] str) {
		Map<String,String> word2PrefixMap = new HashMap<String, String>();
		int [] lcps = new int[str.length];
		Arrays.sort(str);
		for(int i =0;i<str.length-1;i++) {
			int lcp = lcp(str[i],str[i+1]);
			lcps[i] = Math.max(lcps[i], lcp);
			lcps[i+1] = Math.max(lcps[i+1], lcp);
		}
		for (int i = 0; i < lcps.length; i++) {
			String prefix;
			if(lcps[i] == str[i].length()) {
				prefix = "";
			}
			else {
				prefix = str[i].substring(0,lcps[i]+1);
			}
			word2PrefixMap.put(str[i], prefix);
		}
		
		return word2PrefixMap;
		
	}
	private static int lcp(String str1, String str2) {
		int  j = -1;
		for( int i= 0;i<Math.min(str1.length(),str2.length());i++) {
			if(str1.charAt(i)!=str2.charAt(i)) break;
			j = i;
		}
		return j+1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String [] words = new String[] {"zebra", "dog", "duck","dot"};
//		String [] words = new String[] {"bearcat", "bear"};
		System.out.println(getPrefixes(words));
	}

- naren November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the structure of my PatriciaTree, it has following parameters:
char c, indicate the char the node has.
HashMap<Character, PatriciaTree> children, indicate the children the node has.
String leftString, this a bit difficult to explain. So let me raise an example. If root only has a word "dog". So the structure would be like:
.root.......
..\.........
...d(og)....
But not:
.root.......
..\.........
...d........
....\.......
.....o......
......\.....
.......g....
So, in this case, I use the leftString to store the string after 'd', which is 'og'. And I call the node d(og) string leaf. Because it is a leaf, and it needs to indicate what string it still has.

I define 4 types of nodes in patricia tree:
STATE_ROOT, the root the patricia tree.
STATE_STRINGLEAF, it is a leaf, and it has left string in it. Like the example I showed above.
STATE_LEAF, it is a leaf, and it doesn't has left string.
For example, the 'g' and 't' nodes are both LEAF node, but not string leaf node.
.root.........
..\...........
...d..........
....\.........
.....o........
..../.\.......
...g...t......
STATE_MIDDLE, in the above case, the 'd' and 'o' are middle nodes.

In the following code. I demonstrate how to build a patricia tree, and the method to find if a word exists in a patricia tree.

import java.util.HashMap;

public class PatriciaTree {
	public static final int STATE_ROOT = 0;
	public static final int STATE_LEAF = 1;
	public static final int STATE_STRINGLEAF = 2;
	public static final int STATE_MIDDLE = 3;
	
	char c;
	HashMap<Character, PatriciaTree> children;
	int state;	//0 is root, 1 is leaf, 2 is leaf with string, 3 is middle
	String leftString;	//if the node is leaf with string, it has a rest word
	PatriciaTree parent;
	
	//store word into this PatriciaTree, word starts from pos 
	public boolean addNode(String word, int pos, PatriciaTree parent){
		if(word==null||pos>=word.length()){
			return false;
		}
		PatriciaTree child;
		if(state==STATE_ROOT||state==STATE_MIDDLE){
			//if it is root, then find if it children have tree with character pos[0]
			child = children.get(word.charAt(pos));
			if(child==null){	//it doesn't has word.charAt[pos], then create tree under it.
				child = new PatriciaTree(word, pos, this);
				children.put(word.charAt(pos), child);
				return true;
			}
			return child.addNode(word, pos+1, this);	//it has char, then create tree under its child.
		}
		if(state==STATE_LEAF){
			//now it is leaf, and there are still chars, then just change it to a STRINGLEAF
			this.state = STATE_STRINGLEAF;
			this.leftString = word.substring(pos, word.length()-1);
			return true;
		}
		if(state==STATE_STRINGLEAF){
			if(word.charAt(pos)!=leftString.charAt(0)){
				//1st char of leftString doesn't match word[pos], so create the tree under it.
				//And create leftString as its subtree.
				child = new PatriciaTree(word, pos, this);
				children.put(word.charAt(pos), child);
				child = new PatriciaTree(leftString, 0, this);
				children.put(leftString.charAt(0), child);
				this.state = STATE_MIDDLE;
				return true;
			}
			//1st char of leftString match word[pos], so break the stringleaf into middle,
			//and create its child with char of the 1st leftString
			this.state = STATE_MIDDLE;
			child = new PatriciaTree(leftString, 0, this);
			children.put(leftString.charAt(0), child);
			this.leftString = "";
			child.addNode(word, pos+1, child);
			return true;
		}
		
		return false;
	}
	
	public boolean findString(String word, int pos){
		if(pos>=word.length()){
			if(this.state==STATE_MIDDLE){
				return false;	//is in the middle, is not counted as found.
			}
			if(this.state==STATE_LEAF){
				return true;	//return true if this is leaf
			}
			return false;
		}
		PatriciaTree child;
		if(this.state==STATE_ROOT||this.state==STATE_MIDDLE){
			child = this.children.get(word.charAt(pos));
			return child==null?false:child.findString(word, pos+1);
		}
		if(this.state==STATE_LEAF){
			return false;	//the word is larger than the leaf string
		}
		if(this.state==STATE_STRINGLEAF){
			String strInWord = word.substring(pos, word.length());
			if(leftString.equals(strInWord)){
				return true;
			}
		}
		return false;
	}
	
	public PatriciaTree(){
		this.children = new HashMap<Character, PatriciaTree>();
	}
	
	public PatriciaTree(String word, int pos, PatriciaTree parent){
		this.c = word.charAt(pos);
		this.parent = parent;
		this.state = STATE_LEAF;
		this.children = new HashMap<Character, PatriciaTree>();
		if(pos<word.length()-1){
			this.state = STATE_STRINGLEAF;
			this.leftString = word.substring(pos+1, word.length());
		}
	}

	public static void main(String[] args) {
		PatriciaTree root = new PatriciaTree();
		root.state = STATE_ROOT;
		String[] words = {"zebra", "zero", "dog", "dot", "ducks", "duh", "ducky"};
		for(int i=0;i<words.length;i++){
			root.addNode(words[i], 0, root);
		}
		System.out.println(root.findString("dogg", 0));
	}
	
}

- allen.lipeng47 December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One more approach using string array

#include<iostream>
#include<map>
using namespace std;

map<string,string> m;

int main()
{
    string str[]={"zebra", "zero", "dog", "dot", "ducks", "duh", "ducky"};//{"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"};
    int n=sizeof(str)/sizeof(str[0]);
    sort(str,str + n);
    for(int i=0;i<n;i++)
        cout<<str[i]<<"  ";
    for(int i=0;i<n;i++)
        m[str[i]]="";
    int j=0;
    for(int i=0;i<n;i++)
    {
        j=0;
        for(j=0;j<str[i].length();j++)
        {
            if(i<n-1 && j<str[i+1].length() && str[i][j]==str[i+1][j])
            {
                if(j>=m[str[i]].length())
                    m[str[i]]+=str[i][j];
                m[str[i+1]]+=str[i+1][j];
            }
            else{
                j=m[str[i]].length();
                break;
            }

        }
        m[str[i]]+=str[i][j];
    }
    for(int i=0;i<n;i++)
    {
        cout<<"\n"<<str[i]<<" --- "<<m[str[i]];
    }
    return 0;
}

- Charu Mehndiratta January 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Implementation Using Trie idea.

/**
* input: ["zebra", "dog", "duck", "dot", "key", "keyVAlue"]
* output: {zebra: z, dog: dog, duck: du, dot: dot, key: "", keyValue: keyV}
**/
public class ShortestPrefixRepresent {
    private TrieNode root = new TrieNode();
    public ShortestPrefixRepresent(String[] array) {
        for (String item : array) {
            putIntoTrie(item);
        }
    }
    public String getShortestPrefix(String target) {
        StringBuffer res = new StringBuffer("");
        TrieNode p = root;
        for (int i = 0; i < target.length(); i++) {
            res.append(target.charAt(i));
            if (p.subNodes[target.charAt(i)] == null) {
                return "";
            } else {
                if (p.subNodes[target.charAt(i)].count == 1) {
                    return res.toString();
                }
            }
            p = p.subNodes[target.charAt(i)];
        }
        return "";
    }
    private void putIntoTrie(String item) {
        TrieNode p = root;
        for (int i = 0; i < item.length(); i++){
            if (p.subNodes[item.charAt(i)] == null) {
                p.subNodes[item.charAt(i)] = new TrieNode();
            } else {
                p.subNodes[item.charAt(i)].count += 1;
            }
            p = p.subNodes[item.charAt(i)];
        }
    }
    public static void main(String[] args) {
        String[] array = {"zebra", "dog", "duck", "dot", "key", "keyVAlue"};
        ShortestPrefixRepresent code = new ShortestPrefixRepresent(array);
        for (String item : array) {
            System.out.println(item + ": " + code.getShortestPrefix(item));
        }
    }
}
class TrieNode{
    int count = 1;
    TrieNode[] subNodes = new TrieNode[256];
}

- zhangboryan March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two efficient methods:

a. Using radix sort (From front to back) : Time complexity is O(l) where l is sum of length of all strings.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<String> words = new ArrayList<String>();
		for (int i = 0; i < n; ++i) {
			words.add(br.readLine());
		}
		
		ArrayList<String> result = new ArrayList<String>();
		dfs(words, result, 0);
		
		for (int i = 0; i < result.size(); ++i) {
			out.println(result.get(i));
		}
		
		out.flush();
		out.close();
		
		System.exit(0);
	}
	
	private static void dfs(ArrayList<String> words, ArrayList<String> result, int index) {
		if (words == null || words.size() == 0)
			return;
		else if (words.size() == 1) {
			result.add(words.get(0).substring(0, index));
			return;
		}
		else {
			HashMap<Character, ArrayList<String>> buckets = new HashMap<Character, ArrayList<String>>();
			for (int i = 0; i < words.size(); ++i) {
				String word = words.get(i);
				if (word.length() == index)
					throw new RuntimeException("No unique prefixes");
				char ch = word.charAt(index);
				ArrayList<String> list = null;
				if (!buckets.containsKey(ch)) {
					list = new ArrayList<String>();
					buckets.put(ch, list);
				}
				else {
					list = buckets.get(ch);
				}
				list.add(word);
			}
			Set<Character> keys = buckets.keySet();
			for (Character key:keys) {
				dfs(buckets.get(key), result, index+1);
			}
		}
	}
}

b. Using Trie : Maximum time complexity O(l) where l is sum of length of all strings.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);

		int n = Integer.parseInt(br.readLine());
		ArrayList<String> words = new ArrayList<String>();
		for (int i = 0; i < n; ++i) {
			words.add(br.readLine());
		}

		ArrayList<String> result = uniquePrefixes(words);
		if (result != null) {
			for (int i = 0; i < n; ++i) {
				out.println(result.get(i));
			}
		}

		out.flush();
		out.close();

		System.exit(0);
	}
	
	private static ArrayList<String> uniquePrefixes(ArrayList<String> words) {
		int n = words.size();
		TrieNode root = new TrieNode();
		insert(root, words);
		ArrayList<String> result = populateUniquePrefixes(root, words);
		return result;
	}

	private static void insert(TrieNode root, ArrayList<String> words) {
		if (root == null) {
			return;
		}
		else {
			for (int i = 0; i < words.size(); ++i) {
				TrieNode current = root;
				String word = words.get(i);
				for (int j = 0; j < word.length(); ++j) {
					char ch = word.charAt(j);
					if (current.children.containsKey(ch)) {
						TrieNode next = current.children.get(ch);
						next.count = next.count+1;
						current = next;
					}
					else {
						TrieNode newNode = new TrieNode(ch, 1);
						current.children.put(ch, newNode);
						current = newNode;
					}
				}
			}
		}
	}

	private static ArrayList<String> populateUniquePrefixes(TrieNode root, ArrayList<String> words) {
		ArrayList<String> result = new ArrayList<String>();
		int n = words.size();
		for (int i = 0; i < n; ++i) {
			String word = words.get(i);
			TrieNode current = root;
			StringBuffer sb = new StringBuffer();
			int j = 0;
			for (; j < word.length(); ++j) {
				char ch = word.charAt(j);
				int count = current.children.get(ch).count;
				if (count == 1) {
					sb.append(ch);
					result.add(sb.toString());
					break;
				}
				else {
					sb.append(ch);
					current = current.children.get(ch);
				}
			}
			if (j == word.length()) {
				throw new RuntimeException("No unique prefixes");
			}
		}
		
		return result;
	}
	
	private static class TrieNode {
		public char val;
		public int count = 0;
		public HashMap<Character, TrieNode> children = null;

		public TrieNode() {
			children = new HashMap<Character, TrieNode>();
		}

		public TrieNode(char val, int count) {
			children = new HashMap<Character, TrieNode>();
			this.val = val;
			this.count = count;
		}
	}
}

- srikantaggarwal September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Smallest and easiest solution. Enjoy..

public ArrayList<String> shortestUniquepath(ArrayList<String> a){
		
		ArrayList<String> result = new ArrayList<>();
		
		HashMap<String, Integer> hm = new HashMap<>();
		for(int i = 0;i<a.size();i++){
			String currStr = a.get(i);
			StringBuilder sb =  new StringBuilder();
			for(int j = 0;j<currStr.length();j++){
				sb.append(currStr.charAt(j));
				if(hm.containsKey(sb.toString())){
					hm.put(sb.toString(), hm.get(sb.toString()) + 1);
				}else{
					hm.put(sb.toString(), 1);
				}
			}
		}
		
		for(int i = 0;i<a.size();i++){
			String currStr = a.get(i);
			StringBuilder sb =  new StringBuilder();
			for(int j = 0;j<currStr.length();j++){
				sb.append(currStr.charAt(j));
				if(hm.get(sb.toString()) == 1){
					result.add(sb.toString());
					break;
				}
			}
		}
		
		return result;
	}

- bhavesh170690 November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Trie:
    def __init__(self):
        self.root = {'words_count': 0}

    def add(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur:
                cur[letter] = {'words_count': 1}
            else:
                cur[letter]['words_count'] += 1
            cur = cur[letter]
        cur['END'] = True
        self.root['words_count'] += 1

    def find(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur:
                return 0
            cur = cur[letter]
        return cur['words_count']

- sumitgaur.iiita January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Trie:
    def __init__(self):
        self.root = {'words_count': 0}

    def add(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur:
                cur[letter] = {'words_count': 1}
            else:
                cur[letter]['words_count'] += 1
            cur = cur[letter]
        cur['END'] = True
        self.root['words_count'] += 1

    def find(self, word):
        cur = self.root
        for letter in word:
            if letter not in cur:
                return 0
            cur = cur[letter]
        return cur['words_count']

- sumitgaur.iiita January 15, 2017 | 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