Google Interview Question for Software Engineer / Developers


Country: India




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

here is my solution which (I believe) works correctly and also prints the sequence

package info.hevi.interviews.google.questions;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: uerturk
 * Date: 08/10/13
 * Time: 17:04
 * To change this template use File | Settings | File Templates.
 */
public class HasChain {

    Map<Character, List<String>> startsWith = new HashMap<Character, List<String>>();
    Map<Character, List<String>> endsWith = new HashMap<Character, List<String>>();

    private Character getFirstChar(String str) {
        return str.charAt(0);
    }

    private Character getLastChar(String str) {
        return str.charAt(str.length() - 1);
    }

    boolean hasChain(List<String> stringList) {
        for (String str : stringList) {
            Character start = getFirstChar(str);
            Character end = getLastChar(str);
            List<String> startsWithList;
            List<String> endsWithList;

            if (startsWith.containsKey(start)) {
                startsWithList = startsWith.get(start);
            } else {
                startsWithList = new ArrayList<String>();
                startsWith.put(start, startsWithList);
            }

            if (endsWith.containsKey(end)) {
                endsWithList = endsWith.get(end);
            } else {
                endsWithList = new ArrayList<String>();
                endsWith.put(end, endsWithList);
            }
            startsWithList.add(str);
            endsWithList.add(str);
        }

        Stack<String> stringStack = new Stack<String>();
        for (String str : stringList) {
            if (hasChain(stringList.size(), str, stringStack)) {
                System.out.println(stringStack);

                return true;
            }
        }

        return false;
    }

    private boolean hasChain(int size, String startString, Stack<String> stringStack) {
        if (size == stringStack.size()) return true;
        Character last = getLastChar(startString);
        if (startsWith.containsKey(last)) {
            List<String> stringList = startsWith.get(last);
            for (int i = 0; i < stringList.size(); i++) {
                String candidate = stringList.remove(i--);
                stringStack.push(candidate);
                if (hasChain(size, candidate, stringStack)) {
                    return true;
                }
                stringStack.pop();
                stringList.add(++i, candidate);
            }
        }

        return false;
    }

    public static void main(String[] args) {
        List<String> stringList = new ArrayList<String>();
        stringList.add("bd");
        stringList.add("fk");
        stringList.add("ab");
        stringList.add("kl");
        stringList.add("cf");
        stringList.add("ff");
        stringList.add("fa");
        stringList.add("ak");
        stringList.add("ka");
        stringList.add("lf");
        stringList.add("bc");

        System.out.println(new HasChain().hasChain(stringList));

        stringList.remove("ka");

        System.out.println(new HasChain().hasChain(stringList));

    }
}

- ??? October 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

public static boolean chaintermed(String[] strings){
NodePP[] arr=new NodePP[26];
int count=0;
for(int i=0;i<strings.length;i++){
int pre=strings[i].charAt(0)-'a';
int pro=strings[i].charAt(strings[i].length()-1)-'a';
if(arr[pre]==null){
NodePP nPre=new NodePP();
arr[pre]=nPre;
}
if(arr[pro]==null){
NodePP nPro=new NodePP();
arr[pro]=nPro;
}
arr[pre].pre++;
arr[pro].pro++;
}
for(int j=0;j<strings.length;j++){
int pre=arr[strings[j].charAt(0)-'a'].pro;
int pro=arr[strings[j].charAt(strings[j].length()-1)-'a'].pre;
if(((pre==0)&&(pro==0))){return false;}
if((pre!=pro)){
count++;
}
}
return count==2?true:false;
}

- yy October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

use ruler path. Return true when there are exact two odd number of vertices.

- Sarahyangub October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm won't work for input like {"aaa","aaaa","aaaaa"} or {"ab","ba","ac","ca"}.

- GK February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

In the perfect case the posed problem would be resolved with a graph and searching for Hamiltonian path, which is NP-complete, so I avoided graph and did a brute-force solution: build all combinations of strings recursively and return false if it fails to build the combination at any level, here's working code:

bool validChain(std::vector<std::string*> &newChain) {
    if(newChain.size() <= 1) return true;
    for(int i = 1; i < newChain.size(); ++i) {
        std::string *prevString = newChain[i-1];
        if((*newChain[i])[0] != (*prevString)[prevString->size() - 1]) {
            return false;
        }
    }
    return true;
}

bool isChainable(std::vector<std::string*>::iterator start,
                 std::vector<std::string*>::iterator end,
                 std::vector<std::vector<std::string*>> &chains) {
    if(std::distance(start, end) == 1) {
        std::vector<std::string*> singleChain({*start});
        chains.push_back(singleChain);
        return true;
    }

    std::string *head = *start;
    std::vector<std::vector<std::string*>> tmpChains;
    if(isChainable(++start, end, tmpChains)) {
        for(std::vector<std::string*> chain : tmpChains) {
            for(int i = 0; i <= tmpChains.size(); ++i) {
                std::vector<std::string*> newChain(chain.size() + 1);
                newChain[i] = head;
                std::copy(chain.begin(), chain.begin() + i, newChain.begin());
                std::copy(chain.begin() + i, chain.end(), newChain.begin() + i + 1);
                if(validChain(newChain)) chains.push_back(newChain);
            }
        }
    }
    return chains.size() > 0;
}

bool isChainable(std::vector<std::string*> arr) {
    std::vector<std::vector<std::string*>> chains;
    return isChainable(arr.begin(), arr.end(), chains);
}

int main()
{
    std::string str1("abc"), str2("feg"), str3("cef");
    std::cout << isChainable(std::vector<std::string*>({&str1, &str2, &str3}));

    return 0;
}

- Iuri Covalisin November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It should be eurler path issue rather than Hamiltonian path issue.

- evi February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 16 vote

1) Consider all ending and initial character as vertices of graph.
2)string as edge.
3) Form a directed graph
4) find "Euler path"
i) if path found concatenation all string in path.
ii) else no chain possible

eg:
1) a...d
2) q...b
3) n...f
4) a...q
5) f...a
6) d....n

Nodes will be: a b d n f q

Edged will be: 1) a->d 2) q->b 3) n->f 4)a->q 5)f->a 6)d->n

One possible path will be:
a->d->n->f->a->q->b

so chain will be:
a...d...n...f...a...q...b

- Abhi October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

who is giving -1 to all ans??
if you hv any better sol give it..

- Abhi October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

+1. Euler tour is right idea.

And Yeah. If you pick a random visitor of this site, you will likely get a f***g idiot.

- Anonymous October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 votes

You want the Hamiltonian path, not the Eulerian path. Every transition (path) need not be visited, only every vertex, in other words, every word.

- memo October 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Euler path will not work , if there are duplicate pair's.

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

With duplicate pairs , we add another edge.

example: cab chb.. should produce a graph with 2 edges from c->b .. in such a graph there is no euler path

- Anonymous November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@memo
you are right - this is Hamiltonian path problem, not Eulerian, because last allows same vertex to be visited twice, which is not acceptable solution.
This is NP-Complete problem and seems all combinations have to be verified in worst case.

I wonder if this problem can be converted to another, not NP-Complete so we'll have better complexity.

- Iuri Covalisin November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

7 positive votes for an incorrect solution? At least people should have the ability to judge the correctness of given solution.

- jatin085 April 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi please let me know if the following is failing for any test case:

#include <stdio.h>
#include <stdlib.h>

struct list{
int v;
int indegree;
struct list *next;
};

struct Graph{
int V;
struct list **Adj;
};

struct Graph *createG(int n){
int i=0,j=0;
struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph));

G->V=n;

G->Adj=(struct list**)malloc(sizeof(struct list*)*n*2);

for(j=0;j<n;j++){
G->Adj[i]=(struct list*)malloc(sizeof(struct list));

G->Adj[i]->v=i;
G->Adj[i]->indegree=0;



G->Adj[i+1]=(struct list*)malloc(sizeof(struct list));
G->Adj[i+1]->v=i+1;

G->Adj[i+1]->indegree=0;



struct list *temp=(struct list*)malloc(sizeof(struct list));
temp->v=i+1;
temp->next=NULL;
G->Adj[i]->next=temp;

struct list *temp2=(struct list*)malloc(sizeof(struct list));
temp2->v=i;
temp2->next=NULL;
G->Adj[i+1]->next=temp2;



i+=2;
}



return G;

}

void createEdge(struct Graph *G,struct list *u,struct list *v){
int p,q;

p=u->v;
q=v->v;

struct list *temp=(struct list*)malloc(sizeof(struct list));
temp->v=q;
temp->next=G->Adj[p]->next;
G->Adj[p]->next=temp;
G->Adj[p]->indegree+=1;

struct list *temp2=(struct list*)malloc(sizeof(struct list));
temp2->v=p;
temp2->next=G->Adj[q]->next;
G->Adj[q]->next=temp2;
G->Adj[q]->indegree+=1;

return;



}

struct list_t{
char key;
struct list *val;
struct list_t *next;
};


struct hash_table{
int size;
struct list_t **table;
};

struct hash_table *createH(int size){
int i;
struct hash_table *t=(struct hash_table*)malloc(sizeof(struct hash_table));

t->size=size;

t->table=(struct list_t**)malloc(sizeof(struct list_t)*size);

for(i=0;i<size;i++)
t->table[i]=NULL;

return t;
}


int hash(struct hash_table *t,char key){
unsigned int hashval=0;

hashval=((int)key)<<5 -(int)key;

return hashval%t->size;

}


struct node{
struct list *v;
struct node *next;

};

void Insert(struct node **head,struct list *v){
struct node *temp=(struct node*)malloc(sizeof(struct node));

temp->v=v;

temp->next=*head;
*head=temp;

}


struct list *lookupH(struct hash_table *t,char key){

int hashval=hash(t,key);

struct list_t *list_val=NULL;

struct node *head=NULL;

for(list_val=t->table[hashval];list_val;list_val=list_val->next){
if(list_val->key==key)
Insert(&head,list_val->val);
}

return head;
}

void InsertH(struct hash_table *t,char key,struct list *val){


int hashval=hash(t,key);

struct list_t *list_val=(struct list_t*)malloc(sizeof(struct list_t));

list_val->key=key;
list_val->val=val;

list_val->next=t->table[hashval];

t->table[hashval]=list_val;


}


int main()
{

int i,j=0,n;
printf("Enter # of strings\n");

scanf("%d",&n);

char **A=(char**)malloc(sizeof(char*)*n);

for(i=0;i<n;i++){
printf("Enter string # %d\n",i+1);
A[i]=(char*)malloc(sizeof(char)*20);
scanf("%s",A[i]);
}

struct Graph *G=createG(n);


struct hash_table *t1=createH(n);
struct hash_table *t2=createH(n);

j=0;



for(i=0;i<n;i++){
int len=strlen(A[i]);

InsertH(t1,*(A[i]),G->Adj[j]);

struct node *head=lookupH(t2,*(A[i]));

while(head){
createEdge(G,G->Adj[j],head->v);
head=head->next;
}


InsertH(t2,*(A[i]+len-1),G->Adj[j+1]);


head=lookupH(t1,*(A[i]+len-1));


while(head){
createEdge(G,G->Adj[j+1],head->v);
head=head->next;
}



j+=2;

}

j=0;
int count1=0,count2=0;


for(i=0;i<n;i++){
if(G->Adj[j]->indegree==0)
count1++;
if(G->Adj[j+1]->indegree==0)
count2++;
j+=2;
}



if(count1>1 || count2>1)
printf("NO");
else
printf("YES");

return 0;
}

- Anonymous October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.

- Amr Gamal October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this alone is not enough, assume a set (a,b), (b,d), (c,b), (b,c). to find the chain (and print it), you have to find the correct order as well. if ab->bd is chosen we stuck at that point, we have to follow as ab->bc->cb->bd.

- ??? October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You are checking for necessary condition. A sufficient condition and solution thereafter is an NP complete problem.

- jatin085 April 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider the resultant string to be S1...E1 S2... E2 ................ Sn... En
where Si is the starting character of String i and Ei is the ending character of String i. Here, E1 must be equal to S2 and E2 must be equal to S3 and En-1 must be equal to Sn. But S1 and En donot have any relation with any other character. So consider that the Set of starting characters S = {S1, S2, ...., Sn} and the set of ending characters E = {E1, E2, ..... , En}. We need these sets to differ only by at most one element. This element will be the start of the first String and the end of the last string). But for every other value in Set S, other than the value that differs, there must be a corrsponding value in set E. A way to implement this is to have an array of integers with a cell for each character. First, for every character in set S, we increment its position in the array by one. Then for every character in Set E we decrement its place in the array by one. Afterwards if the array is all zeros (every charcater in the set S had a matching character in set E) or if the array consists of zeros except for one cell having value one and one cell having value negative one (in that case only one character differs between set S and set E) then all strings can be adhered together and there's a solution.

- Amr Gamal October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can I use bucket sort? Create 1 array each with 26 entries. All strings will first character a in the 0th entry, b in 1st entry and so on. It takes O(n) to create such an array.
Now we traverse the array once, pop the just word we encounter in the array, read its last character, pop the first string with that character in corresponding entry of the array. Keep doing it until there are no more string in the array. This procedure also takes O(n) times.
Total run time is O(n).

- Random guy October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can also use a hash table:

for(i=0;i<NumStrings;i++)
  table[s[i].at(0)]=i; // this can be modified to contain a chain of i values to address overlapping starting characters between different strings
for(i=0;i<NumStrings;i++)
{
  if(table[s[i].at(s[i].size()-1)]!=-1 && i!=table[s[i].at(s[i].size()-1)])
     Code to Append String at index i and String at index table[s[i].at(s[i].size()-1)]
}

- Anonymous October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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


int main() {

string in[] ={"adsd", "qasdasdb", "ndasdf", "aasddq", "fasda", "deasdn", "oooa"};
int n = 7;
int a[26] ={};

for(int i =0; i<n; i++) {
	int s = (in[i][0])-97;
	int e =	(in[i][(in[i].length()-1)])-97;
	a[s]++;
	if(s != e) {		
		a[e]++;
	}
}
int count =0;
for(int i =0; i<26; i++){
	if(a[i]%2 !=0) count++;
}

if(count == 2) cout<<" YES "<<endl; else cout<<"NO "<<endl;

return 0;
}

- pxe October 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in C++ code

bool concatenateString(string strs[], int n)
{
	int tail[26]={0};
	int count = 0;
	for(int i = 0; i < n; i++)
	{
		tail[strs[i][strs[i].size()-1]-'a']++;
		tail[strs[i][0]-'a']--;
	}
	for(int i = 0; i < 26; i++)
	{
		count += abs(tail[i]);
	}
	if(count == 2)
		return true;
	else
		return false;
}

- nkpangcong October 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The basic idea is keep two list,
src and dest.
- when you need to check whether to put current Scr in srcList, check if previous any one of destinations is same as that of curSrc then remove that from destList and don't put current scr into srcList.
- Similarly for current dest.

At the end you should have only one source.

public static boolean isChained(String [] words) {
	    
	    ArrayList<Character> src = new ArrayList<Character>();
	    ArrayList<Character> dest = new ArrayList<Character>();
	    int i;
	    int n = words.length;
	    boolean putSrc = false;
	    boolean putDest = false;
	    for(i=0; i<n; i++) {
	        String str = words[i];
	        Character s = str.charAt(0);
	        Character e = str.charAt(str.length()-1);
	        if(dest.contains(s)) {
	        	putSrc = false;
	        	dest.remove(s);
	        } else {
	        	putSrc = true;
	        }
	        
	        if(src.contains(e)) {
	        	putDest = false;
	        	src.remove(e);
	        } else {
	        	putDest = true;
	        }
	        
	        if(putSrc)
	        	src.add(s);
	        if(putDest)
	        	dest.add(e);
	    }
	    
	    if(src.size() == 1) {
	        return true;
	    } else {
	        return false;
	    }
	}

- Anand October 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we create an array of 26 length? Initialize all elements to null. Then iterate through each string, setting the array as follows:
first look at string[0]. Compare to string[len(string)-1]. They can be equal or not equal.
1. If equal: set array[f(string[0])]=MAXINT but only if array[f(string[0])]==NULL, otherwise skip this string.
f(X)=numeric place of X in the alphabet e.g.A=1,B=2, etc.
2. If not equal:
a. If array[f(string[0])==NULL or MAXINT, set it to 1.
b. Otherwise, increment it.
c. Perform same test on array[f(string[len(string)-1])] but decrement instead of increment.
When we are done we iterate through the 26-element array.
-If we see any element with value >1 or <-1, return false.
-Else if we count more than one element with 1 or -1, also return false.
-Else return true.
This should be O(N) complexity, no?

- Rob December 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To solve this problem, you need to know SCC(strongly connected components) at first.
Just build the directed graph as many guys said before, then combinate every circles(SCC) into a node one by one, then check whether the final graph is a single link.
Time: O(N) Space: O(N)

- Prowindy December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My God. I cannot believe so many people mention Hamilton circle. What are you thinking? Here is a case: Three words, sag,gs,sk. They can be chained as sagsk. If we build a graph, node s is visited more than once. Thus it's Eulerian path in a directed graph. There is another similar question on geeksforgeeks " given-array-strings-find-strings-can-chained-form-circle/ “

- buptyc December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// works only when the first and last chars are not duplicated in words
// i.e. abcd, aefg are not working on this code since there are two a's

import java.util.*;

public class ChainOfStringsUsingMaps {

public static boolean chainableString( List<String> words ) {
Map<Character, Character> map = new HashMap<Character, Character>();

for( String word : words ) {
char[] S = word.toCharArray();
char f = S[0];
char l = S[S.length-1];

map.put( f, l );
}

Set<Character> visited = new HashSet<Character>();
List<Character> list = new LinkedList<Character>();

int count = 1;

for( Map.Entry<Character, Character> entry : map.entrySet() ) {
Character first = entry.getKey(); // key = first char
Character last = entry.getValue(); // val = last char

if( map.containsKey(last) && !visited.contains(last) ) {
list.add(last);
visited.add(last);
count = count*2;
}
}

if( list.size()*2 == map.size()*2 - 2) return true;
else return false;
}

public static void main(String[] args) {
List<String> stringList1 = new ArrayList<String>();
stringList1.add("sdfg");
stringList1.add("dfgs");
stringList1.add("ghjhk");

System.out.println( chainableString( stringList1));

List<String> stringList2 = new ArrayList<String>();
String dict[] ={"sdfg", "ydfgfx", "dfgs", "nertty", "ghjhn"};
for(String word : dict )
stringList2.add(word);

System.out.println( chainableString( stringList2));

}

}

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

// works only when the first and last chars are not duplicated in words
// i.e. abcd, aefg are not working on this code since there are two a's 

import java.util.*;

public class ChainOfStringsUsingMaps {
	
	public static boolean chainableString( List<String> words ) {
		Map<Character, Character> map = new HashMap<Character, Character>();
		
		for( String word : words ) {
			char[] S = word.toCharArray();
			char f = S[0];
			char l = S[S.length-1];

			map.put( f, l );
		}

		Set<Character> visited = new HashSet<Character>();
		List<Character> list = new LinkedList<Character>();

		int count = 1;

		for( Map.Entry<Character, Character> entry : map.entrySet() ) {
			Character first = entry.getKey();			// key = first char
			Character last = entry.getValue();		// val = last char

			if( map.containsKey(last) && !visited.contains(last) ) {
				list.add(last);
				visited.add(last);
				count = count*2;
			}
		}

		if( list.size()*2 == map.size()*2 - 2) return true;
		else return false;
	}

    public static void main(String[] args) {
       List<String> stringList1 = new ArrayList<String>();
        stringList1.add("sdfg");
        stringList1.add("dfgs");
        stringList1.add("ghjhk");

        System.out.println( chainableString( stringList1));

       	List<String> stringList2 = new ArrayList<String>();
        String dict[] ={"sdfg", "ydfgfx", "dfgs", "nertty", "ghjhn"};
        for(String word : dict )
        	stringList2.add(word);

        System.out.println( chainableString( stringList2));

    }

}

- tester September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 7 vote

THis problem can be solved by using topological sorting. We need to build a directed graph, where each node corresponds to either 1st or last char of string.

Assume 1st char of a string is directed to last char of same string, And in the beginning graph does not have any nodes.

Traverse from 1st string.
1. Take 1st string. Build a graph where 1st and last char will represent two nodes, pointing from 1st to last char.
2. Take 2nd string. If 1st char of this string exists in a graph, then add last char of this string as a node in the graph. Else, build one more graph, the way we built in step 1. Here we have two disconnected graphs.
3. Take 3rd string. If 1st char of this string exists in graphs, then check if last char exists. If it exists, then connect these two nodes. Else, add last char of this string as a node in the graph, else build one more disconnected graph.

Say, we have,
first string=sdfg
second string=ydfgfx
third string=dfgs
fourth string=nertty
fifth string=ghjhn

from 1st string = [s]-->[g] (1st graph)
from 2nd string = [y]-->[x] (2nd graph)
from 3rd string = [d]-->[s]-->g ( Since, 's' is already in 1st graph, connect 3rd string to 1st string)
from 4th string = [n]-->[y]-->x ( Since, 'y' is already in 2nd graph, connect 4th string to 2nd string)
from 5th string = d-->s-->[g]-->[n]-->y-->x (Since, 1st char 'g' is in 1st graph, and last char 'n' is in 2nd graph, so connect these two graphs)

Now, we can check if there is more than one connected graphs using DFS. A chain can be formed if there is only one graph.
In above scenario, a chain can be formed.

- algo October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

wtf. why -1 ? reply if u have any concern with my answer.

- algo October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what if it has cycles? topological sort assumes you always find an element that has no incoming edges, and little modification of original example breaks the topological sort possibility ("S ← Set of all nodes with no incoming edges" will not do anything):

first string=sdfd
second string=dfgs
third string=dhjhs

- Iuri Covalisin November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Form a Bipartite graph having the starting characters of the strings in one group and ending characters in the other group. Create two hash maps one will contain starting characters and other will contain ending characters. while inserting a starting character or ending character of a string in the hashmap check whether the character is already in the other hashmap. If yes then connect an edge between the corresponding nodes in the Graph. In the graph each source node is connected to its corresponding end node.
Now if the graph contains more than one node with in degree 0 then Its NOT POSSIBLE to form the chain. If the graph contains only one node with in degree 0 and if it has only one component then its possible to form a chain.

- kauarba October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

1. Create directed graph from strings.
dfgs -> sdfg -> ghjhk
This graph could be complex with cycles.
2. Check if directed graph has Euler path/cycle.

2.1. A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
2.2. A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).

- m@}{ October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Euler path is a trail in a graph which visits every edge exactly once. you want to visit each node! not edge!
You probably mean Hamiltonian path

- Bee October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public static boolean canChain(String[] strs) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() < 2 || strs[i].charAt(0) == strs[i].charAt(strs[i]
.length() - 1))
continue;
if (map.containsKey(strs[i].charAt(0))) {
map.remove(strs[i].charAt(0));
} else {
map.put(strs[i].charAt(0), i);
}
if (map.containsKey(strs[i].charAt(strs[i].length() - 1))) {
map.remove(strs[i].charAt(strs[i].length() - 1));
} else {
map.put(strs[i].charAt(strs[i].length() - 1), i);
}
}

if (map.size() == 0 || map.size() == 2)
return true;
return false;
}

- genier October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

In this program i am populating map and array of strings manually.
And considering all N no of strings are unique.


public class Chain
{


public static void main(String a[])
{

Map<String,String> map=new HashMap<String,String>();
map.put("a","abc");
map.put("d","def");
map.put("c","cod");
map.put("g","geb");
map.put("b","bea");

String[] arr=new String[5];
arr[0]="abc";
arr[1]="def";
arr[2]="cod";
arr[3]="geb";
arr[4]="bea";

int i=0;
String temp;
int count=0;
while((arr.length)!=i)
{
StringBuilder sb=new StringBuilder();
temp=arr[i];
sb.append(temp);
count=0;
while(true)
{
if(map.get(temp.substring(temp.length()-1))!=null)
{
temp=map.get(temp.substring(temp.length()-1));
sb.append(temp);
count++;
}
else
{
if(count!=(arr.length-1))
{
break;
}
else
{
System.out.println("Chain Found: "+sb.toString());
break;
}
}
}

if(count==(arr.length-1))
{
break;
}
i++;

if((arr.length)==i)
{
System.out.println("Chain not Found");
}
}

}
}

- Ankit Garg October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public boolean isChain(ArrayList<String> p_list){
        int index;
        index = 0;
        String firstword,secondword;
        
        while(index < (p_list.size()-1)){
            firstword = p_list.get(index);
            secondword = p_list.get(index+1);
            if( (firstword.charAt(firstword.length()-1)) !=
                    secondword.charAt(0)){
                return false;
            }
            index++;
            
        }
        
       
        return true;
    }

the way i understand the question is that you need to only compare the neighboring strings. so i will compare the last character in first string and first character in next string and so on will moving along the list and that will be O(n). if we are only interested in the answer to the question can a chain be formed then returning a boolean seems sufficient.

- tmsagila October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.


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