Google Interview Question
Country: United States
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;
}
This could be solved with regex, O(nm) or using modified KMP, i.e preprocess string first and then run KMP 2O(n).
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?
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.
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" ))
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" ))
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" ))
# 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"))
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"))
- undefined June 01, 2019