Google Interview Question


Country: United States




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

def is_reset( cur_char, sub_index, sub_string ){
  sub_index > 0 && 
  ( cur_char @  sub_sequence_string[0:sub_index-1]  ) && // is in 
  ( cur_char !@  sub_sequence_string[sub_index-1:-1]  ) // not in 
}

def find_all_subsequences_indices( host_string, sub_sequence_string ){
  host_size = size(host_string)
  sub_size = size(sub_sequence_string)
  hi = 0 // host index 
  si = 0 // sub seq index 
  collector = list()
  tmp_list = list()
  while ( hi < host_size ){
    // this is for that ... god knows what. 
    // it is not a typical subsequence problem .. so reset when ... 
    if ( is_reset( host_string[hi] , si, sub_sequence_string ) ){
      si = 0 
      tmp_list.clear() 
    }
    if ( host_string[hi] == sub_sequence_string[si] ){
        tmp_list += hi 
        si += 1
        if ( si == sub_size ){
          collector.add( tmp_list )
          si = 0 
          tmp_list = list()
        }
    }
    hi += 1
  }
  collector // return 
}
/*
Given for example S = BCXXBXXCXDXBCD, then the result should be [[4,7,9],[11,12,13] 
find BCBC in String S = BCXXBXCXBCBC 
the result should be [[0,1,4,6],[8,9,10,11]]
*/

println( jstr( find_all_subsequences_indices( "BCXXBXXCXDXBCD" , "BCD" ) ) )
println( jstr( find_all_subsequences_indices( "BCXXBXCXBCBC" , "BCBC" ) ) )

- undefined June 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<int[]> findLocation(String subString, String str) {
        if (subString == null || str == null) return null;
        List<int[]> result = new ArrayList<>();
        int[] location = new int[subString.length()];
        Map<Character, Integer> countChar = new HashMap<>();
        Map<Character, Integer> foundChar = new HashMap<>();
        int i = 0;
        int j = 0;

        while (j < str.length()) {

            countChar.put(str.charAt(j), countChar.containsKey(str.charAt(j)) ? countChar.get(str.charAt(j)) + 1 : 1);

            if (str.charAt(j) == subString.charAt(i)){
                foundChar.put(str.charAt(j), foundChar.containsKey(str.charAt(j)) ? foundChar.get(str.charAt(j)) + 1 : 1);
                location[i] = j;
                i++;
            }

            if(foundChar.containsKey(str.charAt(j)) && countChar.get(str.charAt(j)) > foundChar.get(str.charAt(j))) {
                countChar.clear();
                foundChar.clear();
                location = new int[subString.length()];
                if(str.charAt(j) == subString.charAt(0)) {
                    location[0] = j;
                    i = 1;
                }
            }

            if (i == subString.length()){
                result.add(location);
                location = new int[subString.length()];
                i = 0;
            }
            j++;
        }

        return result;
    }

- Danny June 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello

- Hello World June 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This could be solved with regex, O(nm) or using modified KMP, i.e preprocess string first and then run KMP 2O(n).

- nooooob June 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This wont work. KMP is only for substring not subsequence.

- code reviewer June 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

modified KMP, i.e preprocess string first and then run KMP 2O(n)?
Do you mean by removing the X and then use the KMP to do string matching?

- bottleneck56 June 04, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, it could be done in two ways.

1) Create an array of valid indices, i.e if you ever encounter X at index (k) it should point you to the valid character (B, C , D etc) i < k. And this could be factored in the KMP algorithm while matching the pattern with the string.

2) Remove Xs, and while doing it create an array that will give you indices of B, C, and D in the original input. In this case, run KMP and for valid outputs, you can get the indices information from the array while printing the results.

Let me know if you need an example.

- nooooob June 08, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes please, example would be good here. Thanks in advance.

- code reviewer June 08, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def patSearch(txt,pat):
	txtpos=0
	patpos=0
	txtlen=len(txt)
	patlen=len(pat)
	result=[[]]
	while txtpos!=txtlen:
		if(txt[txtpos]==pat[patpos]):
			result[-1].append(txtpos)
			patpos+=1
			if(patpos==patlen):
				result.append([])
				patpos=0
		elif(txt[txtpos]!='X'):
			result[-1]=[]
			patpos=0
			if(txt[txtpos]==pat[patpos]):
				result[-1].append(txtpos)
				patpos+=1
		txtpos+=1
	return result
print(patSearch("BCXXBXCXBCBC" , "BCBC"))
print(patSearch("BCXXBXXCXDXBCD" , "BCD" ))

- Anonymous June 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def patSearch(txt,pat):
	txtpos=0
	patpos=0
	txtlen=len(txt)
	patlen=len(pat)
	result=[[]]
	while txtpos!=txtlen:
		if(txt[txtpos]==pat[patpos]):
			result[-1].append(txtpos)
			patpos+=1
			if(patpos==patlen):
				result.append([])
				patpos=0
		elif(txt[txtpos]!='X'):
			result[-1]=[]
			patpos=0
			if(txt[txtpos]==pat[patpos]):
				result[-1].append(txtpos)
				patpos+=1
		txtpos+=1
	return result
print(patSearch("BCXXBXCXBCBC" , "BCBC"))
print(patSearch("BCXXBXXCXDXBCD" , "BCD" ))

- Anonymous June 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def patSearch(txt,pat):
	txtpos=0
	patpos=0
	txtlen=len(txt)
	patlen=len(pat)
	result=[[]]
	while txtpos!=txtlen:
		if(txt[txtpos]==pat[patpos]):
			result[-1].append(txtpos)
			patpos+=1
			if(patpos==patlen):
				result.append([])
				patpos=0
		elif(txt[txtpos]!='X'):
			result[-1]=[]
			patpos=0
			if(txt[txtpos]==pat[patpos]):
				result[-1].append(txtpos)
				patpos+=1
		txtpos+=1
	return result
print(patSearch("BCXXBXCXBCBC" , "BCBC"))
print(patSearch("BCXXBXXCXDXBCD" , "BCD" ))

- Anonymous June 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Slightly modified to make it simpler

def patSearch(txt,pat):
txt_count=0
pat_count=0
txtlen=len(txt)
patlen=len(pat)
result=[[]]
while txt_count!=txtlen:
if txt[txt_count] == pat[pat_count]:
# print(pat_count)
result[-1].append(txt_count)
pat_count+=1
list_elem_count = sum([len(list_elem) for list_elem in result])
if list_elem_count == 8: # remove the last empty list
return result
elif pat_count == patlen:
result.append([])
pat_count=0
txt_count+=1
return result
print(patSearch("BCXXBXCXBCBC" , "BCBC"))

- peter April 11, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Slightly modified to make it simpler

def patSearch(txt,pat):
    txt_count=0
    pat_count=0
    txtlen=len(txt)
    patlen=len(pat)
    result=[[]]
    while txt_count!=txtlen:
        if txt[txt_count] == pat[pat_count]:
            # print(pat_count)
            result[-1].append(txt_count)
            pat_count+=1
            list_elem_count = sum([len(list_elem) for list_elem in result])
            if list_elem_count == 8:  # remove last empty list
                return result
            elif pat_count == patlen:
                result.append([])
                pat_count=0
        txt_count+=1
    return result
print(patSearch("BCXXBXCXBCBC" , "BCBC"))

- peter April 11, 2020 | Flag Reply
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