Google Directi Interview Question for Software Engineer / Developers






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

The below solution works. I answered this in my Google Interview :

void findSubstring(char s1[], char s2[])
{
// s2 is Ssmall
// s1 is Sbig

int hash[26] = {0};
int hash1[26] = {0};
for(int i = 0; i < len(s2); i++)
hash[s2[i] - 'a'] += 1;

int left = 0;
int minL = 0;
int minR = len(s1) - 1;

for(int i = 0; i < len(s1); i++)
{
if(flag == 0)
left = i;

if(hash[s1[i] - 'a'] != 0)
{

hash1[s1[i] - 'a'] += 1;
if(hash1[s1[i] - 'a'] > hash[s1[i] - 'a'])
{
while(hash1[s1[i] - 'a'] > hash[s1[i] - 'a'])
{
hash1[s1[left] - 'a']--;
left++;
}
}

int u;
for(u = 0; u < 26; u++) // checking if hash1 has same entries as hash.
{
if(hash[u] != hash1[u])
break;
}

if(u == 26) // If hash1 has same entries as hash then we have one more substring containing all entries of Ssmall
{
if(minR - minL > i - left)
{
minL = left;
minR = i;
}
}
flag = 1;
}
else if(flag == 1)
{
reset(hash1); // make all hash1 entries to zeros.
flag = 0;
}
}

for(int i = minL; i <= maxL; i++)
cout << s[i] <<;
cout << endl;

return;
}

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

it works, thanks for your code. But next time, you can explain more your code. Then it makes our life easy.

- remlostime November 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If someone understood the above code can someone explain in simple english, I don't know why people just add the code, because what you have in mind you can code it but reverse engineering of it is pretty much complex process.

- JamesBond November 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

nice logic...looks correct....its better if there is some solid code....

- dream January 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Logic is wrong. Even in your example, 9 - 13 has same gap with 2 -6 but they do not have a chance to be consider at all. This imply we cannot just narrow down starting the one element's the smallest gap.

- Sam October 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can build a suffix tree in O(n) time and then just look for the smallest string containing the characters, on the appropriate branch. Not sure what the time would be, O(n) + something...

- Anonymous January 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach:
very similar to minimum window covering the word subset in the text.
u can find answer in this website.

- T January 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is it the same as the minimum window covering problem?

- creationw August 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

String big = ...
String small = ...

int[] sfa; 
List allPoss = new ArrayList();

char c;
int j = 0;

while(j < big.length())
{
	sfa = new int[small.length()];

	for(int i=0; i<small.length(); i++)
	{
		c = small.charAt(i);

		while(j<big.length())
		{
			if(big.charAt(j) == c)
			{
				sfa[i] = j;
				i++;
				j++;
				break;
			}
			else
			{
				j++;
			}
		}
	}
	j = sfa[0] + 1;

	allPoss.add(sfa);	
}

if(allPoss.size() == 0) print ("not found");

int shortest = 0;
int[] currShortest = allPoss[shortest];
int d1 = currShortest[currShortest.length - 1] - currShortest[0];

for(int k=1; k<allPoss.length; k++)
{
	int[] atNow = allPass.get(k);
	int d2 = atNow[atNow.length - 1] - atNow[0];
	if(d2 < d1)
	{
		shortest = k;
		currShotest = atNow;
		d1 = currShortest[currShortest.length - 1] - currShortest[0];
	}
}

print("Shortest is start from " + currShortest[0] + " to " + currShortest[currShortest.length - 1]);

- Anonymous January 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String big = ...
String small = ...

int[] sfa; 
List allPoss = new ArrayList();

char c;
int j = 0;

while(j < big.length())
{
	sfa = new int[small.length()];

	for(int i=0; i<small.length(); i++)
	{
		c = small.charAt(i);

		while(j<big.length())
		{
			if(big.charAt(j) == c)
			{
				sfa[i] = j;
				i++;
				j++;
				break;
			}
			else
			{
				j++;
			}
		}
	}
	j = sfa[0] + 1;

	allPoss.add(sfa);	
}

if(allPoss.size() == 0) print ("not found");

int shortest = 0;
int[] currShortest = allPoss[shortest];
int d1 = currShortest[currShortest.length - 1] - currShortest[0];

for(int k=1; k<allPoss.length; k++)
{
	int[] atNow = allPass.get(k);
	int d2 = atNow[atNow.length - 1] - atNow[0];
	if(d2 < d1)
	{
		shortest = k;
		currShotest = atNow;
		d1 = currShortest[currShortest.length - 1] - currShortest[0];
	}
}

print("Shortest is start from " + currShortest[0] + " to " + currShortest[currShortest.length - 1]);

- Voila January 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Minimum spanning tree. Each letter can be considered a node and there will be an edge for adjacent character. May be suffix tree would be a better approach than this.

- Anonymous January 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from the definition it appears like that small string could be "oe" and the result could be still "ello" (it contains all the characters in "o").

- Anonymous January 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about LCS(longest common subsequence)..once its complete backtrack to get the minimum window..complexity is however bad O(m*n)

- Anonymous February 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in 0(M+N) time with constant memory.
Create a hash of characters in small string (flat array of 26 bools),scan through the long string keeping track of smallest sequence which encompasses all characters in the hash.

- kkalyana February 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How dumb!!
The algo is wrong and the space complexity mentioned is wrong even for that wrong algo.

- Mahesh April 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mahesh, you really suck

- a March 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello friends... I am giving a small logic and it is limited to some extent. here is the code:

String Sbig= given input sentence;
char *Ssmall;
int flag=0;
int pos1,pos2=0;
int i=0;

// read the substring into Ssmall array

char ch="";
while((ch=Sbig.charAt(i))!='\0')
{
if(ch==Ssmall[0])
{
pos1=i;
flag=2;
}

if(ch==' ')
flag=1;

if(flag==2 && ch==Ssmall[1])
{
pos2=i;
// print subString with pos1,pos2 as boundaries
}
i++;
}

Here if a word has 'first character' and 'second character' in the same word without any space it is considered and printed.
If space is encountered, the flag is set which signals that we need to search for one more substring as the previous one(if present) has been rejected because of space in between them.

Hope u understood

- Sunil April 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

few observations -
small string - would be atmost 4 to 5 chars - all chars of this should be within a word in large string (see above 'e yo' is not found. )
basic idea is calculate spread between chars found in big string and maintain them. also make a hash for all possible combinations of chars from small string. each time a char is found we need to only check for last set of chars (length == length of small string)

Create a node with char and counter - counter has number of spaces away from last found char of small string.

Go on traversing large string each char at a time, if matching char is found note how far it is from previous matching char and check if last combination is in hash - if found maintain total length and found pointer. go on till end of big string - if small length combination is found, store new value and pointer....

overall TC O(n) but will require high space is small string becomes bigger.

- pm April 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a dynamic programming question. Apply Knuth Morris Pratt algorithm. Search it in wikipedia.

- Messi April 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although KMP isn't 1000 line, how you could apply it to this problem. It does not make sense at all.

- Sam October 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is set of characters not string. read problem carefully

- pankaj March 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

genious buddy . how can you be so illogical?. Think before posting a solution or suggestion.

- prathimzn July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Okay ,if you aim for Google , dont paste 1000 lines of code here.. if you are really brilliant just put ideas in words , like the way human communicates .

- World's Next Super Power April 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool hasZero(int* arr, int len){
	for (int x = 0; x<len; x++) 
		if (arr[x] == 0) 
			return true;
	return false;
}
void smallsubset(string sb, string ss){
	int *occurances = new int[ss.length()];
	for (int x = 0; x<ss.length(); x++) {
		occurances[x] = 0;
	}
	int i ,j, ibest, jbest, min;
	ibest = jbest = -1;
	i=0; j=0;
	min = sb.length();
	while (j<sb.length()) {
		do {
			j++;
			int k = ss.find(sb.substr(j, 1));
			if (k >= 0) 
				occurances[k]++;
		}while (hasZero(occurances, ss.length()));
		if((j-i)< min){
			min = j- i;
			ibest = i;
			jbest = j;
		}
		while (true) {
			int k = retin(sb.substr(i, 1),ss);
			i++;
			if (k >= 0) {
				occurances[k]--;
				if (hasZero(occurances, ss.length())) 
					break;
			}
		}
		if((j-i)< min){
			min = j- i;
			ibest = i-1;
		}
	}
	cout << sb.substr(ibest, jbest-ibest+1)<<endl;
}

- aliyakamercan July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

frm example:Sbig = "hello what are you doing"
Ssmall= "eo"
answer is "ello"

max=count=0;
while(Sbig[i]!=null)
{

while(Sbig[i]!=' ')
{
	if(Ssmall[i]!=Sbig[i])
		i++;
	else
	{
		 count++;
		 	while(Ssmall[i]!=' ')
			{
			count++; // similarily we can track the starting n ending positions of the subset along wid the elements
			if(Ssmall[len]==Sbig[i])
				{
				max=count;
				break while loop;
				}
			i++;
			}

	}
}
max=count=0;

}.

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int test(char[], char[],int);
int main()
{
  char str[]="hello world";
  char sub[]="elo";
  int i,s,e,len,k,j;
  int small=strlen(str);
  for(i=0;i<strlen(str);i++)
  {
   // for(j=0;j<strlen(sub);j++)
    //{
        if (str[i]==sub[0])
        { 
          e = test(str,sub,i);
          //}
          if ((e-i) < small)
          {
             small=e-i;
             k=i;len=e;

for (j=k; j<=len;j++)
{
printf("%c",str[j]);
}
getchar();
getchar();
return 0;
}
int test(char a[],char b[],int s)
{ int count =1;
int i=1;
int k=s;
while((count <= (strlen(b)- 1)) && (k+1)<strlen(a))
{
if (a[k+1]==b[i])
{
++count;++i;}
++k;
}
return (k);
}

- Nascent_coder November 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is set of character not string stupid and your algo sucks

- pankaj March 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please stop pasting your fucking codes here.
It makes this thread unreadable.

- Alex.B.Yin March 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

str1 : This is a test string
str2 : tist

step1 : Find first sub string from str1 that contains all characters of sring2.
"this is a t"
step2 :

Whenever a character is added, check if the added character matches the left most character of substring.
If matches, then add the new character to the right side of substring and remove the leftmost character and all other extra characters after left most character. After removing the extra characters, get the length of this substring and compare with min_len and update min_len accordingly.
remove all the characters which exceeds the number of number of that character in the substring.

first round:
“is a test”

second round :
“is a test str”

third round:
“t stri”

- Praveen Raj July 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

str1: "Hello this class is effectively closed"
str2: "etc".

So lets have 3 stacks which will keep storing the indexed of e, t and c.

e --> 2, 20, 23, 28, 36
t --> 7, 25
c --> 12, 24, 32.

Keeping in mind that index(e)<index(t)<index(c).

Take the first no. out of c-stack. 32.
Take the first no. out of t-stack. 25. 25<32 so it stays
Take the first no. out of e-stack. 36. 25<36 so discard ... so on .. the next valid no. is 23. So 23-25-32 is the first no. "ectively c"

Similarly for next possible no. leave out 32 from c-stack and go with next element. The only other possible e-t-c-stack combos are 2-7-24 and 2-7-12.

Needless to say first combo was the smallest.

I am using one stack per character to illustrate the soln but more like LinkedHashMap<Char, List> can be used.

- Kamal Tripathi August 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this a straightforward Dynamic Programming problem O(lenA)(lenB)?

- Anonymous February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this a straightforward Dynamic Programming problem O(lenA)(lenB)?

- Anonymous February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include<cstring>
using namespace std;
int length,start;
int cmp(char *big,char *small,int st,int len)
{
	if(*small=='\0')
	{
		if(len-st<length)
		{
				length=len-st;
				start=st;	
		}
		return length;
	}	
	else if(*big=='\0' || *big==' ')
		return 1000000007;
	else if(*big==*small) 
	{	
		if( st==-1)
			return min(cmp(big+1,small+1,len,len+1),cmp(big+1,small,st,len+1));
		else  
			return cmp(big+1,small+1,st,len+1);
	}
	return cmp(big+1,small,st,len+1);		
		
}
int main() {
	char *big="hello what are you doing";
	char *small="eo";
	start=-1;
	length=strlen(big);
	cout<<"length "<<cmp(big,small,-1,0)<<endl;
	cout<<"start from "<<start<<endl;
	for(int i=start;i-start<length;i++)
		putchar(big[i]);
	return 0;
}

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

I am assuming small does not have duplicates.

1. Find first char of the sSmall in sBig, scan until last char of sSmall is found in sBig. If another sSmall was found, change start to this index. Save start and end index, min = end-start. Keep on scanning on the right and when sSmall is found check if the window (end-start) is smaller than previous set, if yes replace previous min window values.

- Joy June 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

logic is something like below :

1. scan the entire string and store the occurances of 'a', 'b', & 'c' in different arrays , lets say A , B , C are the arrays

2. find out the least diff ( 2 ) elements b/w arrays A & B , B & C

3. lets suppose the arrays are somehitng like below :

A - 6 10
B - 2 5 13
C - 3 8 9


then from A&B we get 5,6

from B & C we get 2 & 3

so we have to decide b/w 236 and 356

the diff b/w 6 and 3 is lesser than 6 and 2 , so we have to consider the substring starting from the index 3

- Anonymous January 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose after step 1, we have
A- 6 10
B- 2 5 13
C- 3 7 9
Step 2: A&B we get 5,6; B&C we get 2&3
Step 3: 356
But, the smallest substring is 567

- Anonymous January 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree. Instead of finding the B & C We can do a cross product of sets and put them into 2x2 array. For example, consider the following s = "a##b#c#a#b##c"
sStr = "abc"
index of a = [0, 7]
b = [3, 9]
c = [5, 12]
After cross product we have
0,3,5,
0,3,12,
0,9,5,
0,9,12,
7,3,5,
7,3,12,
7,9,5,
7,9,12,
Now finding the shortest path will be for each records, it is the total of the substraction of each number. for example take 0,3,5. It will be |0-3|+|0-5|+|3-5|=7. The smallest number is the smallest subset.

I am sure that by constructing the tree will be much efficient.
But this is the program

class TestSubmallsetString
{
static LinkedHashMap map = new LinkedHashMap();

static int[][] vvv;

public static int calc()
{
int total = 0;
int min = 99999;
int index = -1;
for (int i=0;i<vvv.length;i++)
{
for (int j=0;j<vvv[i].length;j++)
{
for (int k=j+1;k<vvv[i].length;k++)
{
total += Math.abs(vvv[i][j] - vvv[i][k]);
}
}
if (total<min)
{
index = i;
min = total;
}
total = 0;
}
return index;
}
public static void fillCrossProductArray(String s, String sStr)
{
int colIndex = 0;
int rowPointer = 0;
int tLength = vvv.length;
int counter = 0;
int tmp = 0;
for (int xx = 0; xx < sStr.length(); ++xx) // start with "a" level
{
Object[] l = ((HashSet) map.get(sStr.charAt(xx))).toArray();
for (int i1 = 0; i1 < l.length; i1++) // loop array
{
tmp =tLength / l.length;
for (int kk=rowPointer; kk < vvv.length; kk += tLength) // loop rows
{
while(counter<tmp)
{
vvv[kk+counter][colIndex] = (Integer)l[i1];
counter ++;
}
counter = 0;
}
rowPointer += tLength / l.length ;
}
tLength = tLength / l.length ;
rowPointer = 0;
colIndex ++ ;
}
}
public static void init(String s,String sStr)
{
for (int i = 0; i < sStr.length(); i++)
{
map.put(sStr.charAt(i), new LinkedHashSet());
}
for (int i = 0; i < sStr.length(); i++)
{
for (int j = 0; j < s.length(); j++)
{
if (s.charAt(j) == sStr.charAt(i))
{
((LinkedHashSet) map.get(sStr.charAt(i))).add(j);
}
}

}
Iterator it = map.keySet().iterator();
int numOfRow = 1;
HashSet hs = null;
for (int i = 0; i < map.size(); i++)
{
hs = ((LinkedHashSet) map.get(it.next()));
System.out.println(hs);
numOfRow *= hs.size();
}
vvv = new int[numOfRow][sStr.length()];
}
public static void test(String s, String sStr)
{

init(s,sStr);
fillCrossProductArray(s,sStr);
int idx=calc();

System.out.println(s);
System.out.println(sStr);
for (int i = 0; i < vvv.length; i++)
{
for (int j=0;j<vvv[i].length; j++)
{
System.out.print(vvv[i][j]+",");
}
System.out.println();
}
System.out.println("Shortest path");
for (int j=0;j<vvv[idx].length; j++)
{
System.out.print(vvv[idx][j]+",");
}
// System.out.println(s.substring((Integer)newArr.get(0),1+(Integer)newArr.get(newArr.size()-1)));
}
}

- zhizhi2007 March 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
This is the formatted code class TestSubmallsetString {{{ static LinkedHashMap map = new LinkedHashMap(); static int[][] vvv; public static int calc() {{{ int total = 0; int min = 99999; int index = -1; for (int i=0;i<vvv.length;i++) {{{ for (int j=0;j<vvv[i].length;j++) {{{ for (int k=j+1;k<vvv[i].length;k++) {{{ total += Math.abs(vvv[i][j] - vvv[i][k]); }}} }}} if (total<min) {{{ index = i; min = total; }}} total = 0; }}} return index; }}} public static void fillCrossProductArray(String s, String sStr) {{{ int colIndex = 0; int rowPointer = 0; int tLength = vvv.length; int counter = 0; int tmp = 0; for (int xx = 0; xx < sStr.length(); ++xx) // start with "a" level {{{ Object[] l = ((HashSet) map.get(sStr.charAt(xx))).toArray(); for (int i1 = 0; i1 < l.length; i1++) // loop array {{{ tmp =tLength / l.length; for (int kk=rowPointer; kk < vvv.length; kk += tLength) // loop rows {{{ while(counter<tmp) {{{ vvv[kk+counter][colIndex] = (Integer)l[i1]; counter ++; }}} counter = 0; }}} rowPointer += tLength / l.length ; }}} tLength = tLength / l.length ; rowPointer = 0; colIndex ++ ; }}} }}} public static void init(String s,String sStr) {{{ for (int i = 0; i < sStr.length(); i++) {{{ map.put(sStr.charAt(i), new LinkedHashSet()); }}} for (int i = 0; i < sStr.length(); i++) {{{ for (int j = 0; j < s.length(); j++) {{{ if (s.charAt(j) == sStr.charAt(i)) {{{ ((LinkedHashSet) map.get(sStr.charAt(i))).add(j); }}} }}} }}} Iterator it = map.keySet().iterator(); int numOfRow = 1; HashSet hs = null; for (int i = 0; i < map.size(); i++) {{{ hs = ((LinkedHashSet) map.get(it.next())); System.out.println(hs); numOfRow *= hs.size(); }}} vvv = new int[numOfRow][sStr.length()]; }}} public static void test(String s, String sStr) {{{ init(s,sStr); fillCrossProductArray(s,sStr); int idx=calc(); System.out.println(s); System.out.println(sStr); for (int i = 0; i < vvv.length; i++) {{{ for (int j=0;j<vvv[i].length; j++) {{{ System.out.print(vvv[i][j]+","); }}} System.out.println(); }}} System.out.println("Shortest path"); for (int j=0;j<vvv[idx].length; j++) {{{ System.out.print(vvv[idx][j]+","); }}} // System.out.println(s.substring((Integer)newArr.get(0),1+(Integer)newArr.get(newArr.size()-1))); }}} }}} - zhizhi2007 March 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
class TestSubmallsetString {{{{ static LinkedHashMap map = new LinkedHashMap(); static int[][] vvv; public static int calc() {{{{ int total = 0; int min = 99999; int index = -1; for (int i=0;i<vvv.length;i++) {{{{ for (int j=0;j<vvv[i].length;j++) {{{{ for (int k=j+1;k<vvv[i].length;k++) {{{{ total += Math.abs(vvv[i][j] - vvv[i][k]); }}}} }}}} if (total<min) {{{{ index = i; min = total; }}}} total = 0; }}}} return index; }}}} public static void fillCrossProductArray(String s, String sStr) {{{{ int colIndex = 0; int rowPointer = 0; int tLength = vvv.length; int counter = 0; int tmp = 0; for (int xx = 0; xx < sStr.length(); ++xx) // start with "a" level {{{{ Object[] l = ((HashSet) map.get(sStr.charAt(xx))).toArray(); for (int i1 = 0; i1 < l.length; i1++) // loop array {{{{ tmp =tLength / l.length; for (int kk=rowPointer; kk < vvv.length; kk += tLength) // loop rows {{{{ while(counter<tmp) {{{{ vvv[kk+counter][colIndex] = (Integer)l[i1]; counter ++; }}}} counter = 0; }}}} rowPointer += tLength / l.length ; }}}} tLength = tLength / l.length ; rowPointer = 0; colIndex ++ ; }}}} }}}} public static void init(String s,String sStr) {{{{ for (int i = 0; i < sStr.length(); i++) {{{{ map.put(sStr.charAt(i), new LinkedHashSet()); }}}} for (int i = 0; i < sStr.length(); i++) {{{{ for (int j = 0; j < s.length(); j++) {{{{ if (s.charAt(j) == sStr.charAt(i)) {{{{ ((LinkedHashSet) map.get(sStr.charAt(i))).add(j); }}}} }}}} }}}} Iterator it = map.keySet().iterator(); int numOfRow = 1; HashSet hs = null; for (int i = 0; i < map.size(); i++) {{{{ hs = ((LinkedHashSet) map.get(it.next())); System.out.println(hs); numOfRow *= hs.size(); }}}} vvv = new int[numOfRow][sStr.length()]; }}}} public static void test(String s, String sStr) {{{{ init(s,sStr); fillCrossProductArray(s,sStr); int idx=calc(); System.out.println(s); System.out.println(sStr); for (int i = 0; i < vvv.length; i++) {{{{ for (int j=0;j<vvv[i].length; j++) {{{{ System.out.print(vvv[i][j]+","); }}}} System.out.println(); }}}} System.out.println("Shortest path"); for (int j=0;j<vvv[idx].length; j++) {{{{ System.out.print(vvv[idx][j]+","); }}}} // System.out.println(s.substring((Integer)newArr.get(0),1+(Integer)newArr.get(newArr.size()-1))); }}}} }}}} - zhizhi2007 March 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just say what you want to do in words, dumbfuck. We know how to code.

- Mahesh April 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zhizhi2007
ban such hectic morons frm this wonderful website!!

- aravind646 November 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

how about regular expression?

- Anonymous January 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And how will you use it? Care to explain?

Just throwing random terms at the interviewer won't get you the job.

- Anonymous January 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am agree too.

- Anonymous January 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

me agree three.

- Anonymous January 23, 2010 | Flag


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