Google Interview Question Principal Software Engineers
Country: United States
def lastIndex(words, keywords):
last = 0
for keyword in keywords:
try:
i = words.index(keyword)
words = words[i + 1:]
last += i
except ValueError:
raise
return last + 1
def minSubstring(words, keywords):
first = keywords[0]
startIndex = endIndex = 0
for i, word in enumerate(words):
if first != word:
continue
try:
start = i
end = lastIndex(words[start + 1:], keywords[1:])
if end - start > startIndex - endIndex:
startIndex = start
endIndex = start + end
except ValueError:
continue
if startIndex != 0:
return words[startIndex:endIndex + 1]
else:
return ''
public class ShortestStringContainingKeywords {
public static void main(String[] args){
String[][] testcases = {
{"sky", "cloud", "google", "search", "sky", "work", "blue"},
{"sky", "blue"},
{"sky", "cloud", "google", "search", "sky", "work", "blue", "sky"},
{"sky", "blue"}};
for(int i = 0; i < testcases.length/2; i++){
String doc[] = testcases[2*i];
String keywords[] = testcases[2*i+1];
String res = search(doc, keywords);
System.out.println(Arrays.toString(doc) + "\t" + res);
}
}
/**
* keep track of list of occurrences of word,
* -- if all words covered have a feasible solution
* -- if word occurring second time, move forward iterators
* until there is a word that is covered only once
*/
private static String search(String[] doc, String[] keywords) {
Map<String, Integer> keywordId = new HashMap<String, Integer>();
int numKeywords = 0;
for(String kw : keywords){
keywordId.put(kw, numKeywords);
numKeywords++;
}
short n = (short) doc.length;
short optWindowStart = 0, currWindowStart = 0;
short optWindowLength = (short) (n + 1);
int[] numMatches = new int[numKeywords];
for(int i = 0; i < numKeywords; i++){
numMatches[i] = 0;
}
int numKeywordMatches = 0;
List<Integer> tokenIdToMatchingKw = new ArrayList<Integer>();
for(short i = 0; i < n; i++){
if(keywordId.containsKey(doc[i])){
int kwIndex = keywordId.get(doc[i]);
tokenIdToMatchingKw.add(kwIndex);
if(numMatches[kwIndex] == 0){
numKeywordMatches++;
}
numMatches[kwIndex]++;
if(numKeywordMatches == numKeywords){
short j = currWindowStart;
while(j < i){
int kwj = tokenIdToMatchingKw.get(j);
if(kwj != -1){
if(numMatches[kwj] > 1){
numMatches[kwj]--;
j++;
} else {
// local maximum
currWindowStart = j;
short currWindowLength = (short) (i - j + 1);
if(currWindowLength < optWindowLength){
optWindowLength = currWindowLength;
optWindowStart = currWindowStart;
}
break;
}
}
j++;
}
}
} else {
tokenIdToMatchingKw.add(-1);
}
}
if(optWindowLength > n)
return null;
String res = "";
for (short j = optWindowStart; j < optWindowStart + optWindowLength; j++) {
if(j > 0){
res += " " + doc[j];
} else {
res += doc[j];
}
}
return res;
}
}
public class ShortestString {
public static void main(String args[]){
String input = "sky cloud google search sky work blue";
String keywords = "sky blue";
String[] keywordsList = keywords.split(" ");
List<Integer> firstWordIndices = new ArrayList<>();
List<Integer> lastWordIndices = new ArrayList<>();
int cInd = -1;
int lastIndex = input.lastIndexOf(keywordsList[0]);
while(cInd < input.length() && cInd != lastIndex){
cInd = input.indexOf(keywordsList[0], cInd+1);
firstWordIndices.add(cInd);
}
cInd = -1;
lastIndex = input.lastIndexOf(keywordsList[1]);
while(cInd < input.length() && cInd != lastIndex){
cInd = input.indexOf(keywordsList[1], cInd+1);
lastWordIndices.add(cInd);
}
Map<Integer, Integer> lastFirstMap = new HashMap<>();
for(Integer index: lastWordIndices){
for(Integer findex: firstWordIndices){
if(findex<index){
if(lastFirstMap.get(index) != null){
if(findex > lastFirstMap.get(index)){
lastFirstMap.put(index, findex);
}
}
else{
lastFirstMap.put(index, findex);
}
}
}
}
Entry<Integer, Integer> currentSmallestEntry = null;
int currentDiff = 0;
for(Entry<Integer, Integer> entry: lastFirstMap.entrySet()){
if(currentSmallestEntry == null){
currentSmallestEntry = entry;
currentDiff = currentSmallestEntry.getKey() - currentSmallestEntry.getValue();
continue;
}
if((entry.getKey() - entry.getValue()) < currentDiff){
currentSmallestEntry = entry;
}
}
System.out.println("currentSmallestEntry: "+input.substring(currentSmallestEntry.getValue(), currentSmallestEntry.getKey()+keywordsList[1].length()));
}
}
public class ShortestString {
/*Give a string [] words,
Find the shortest string [] containing the keyword inside.
example:
words: sky cloud google search sky work blue
keywords: sky blue
return: sky work blue*/
public static void main(String args[]){
String input = "sky cloud google search sky work blue";
String keywords = "sky blue";
String[] keywordsList = keywords.split(" ");
List<Integer> firstWordIndices = new ArrayList<>();
List<Integer> lastWordIndices = new ArrayList<>();
int cInd = -1;
int lastIndex = input.lastIndexOf(keywordsList[0]);
while(cInd < input.length() && cInd != lastIndex){
cInd = input.indexOf(keywordsList[0], cInd+1);
firstWordIndices.add(cInd);
}
cInd = -1;
lastIndex = input.lastIndexOf(keywordsList[1]);
while(cInd < input.length() && cInd != lastIndex){
cInd = input.indexOf(keywordsList[1], cInd+1);
lastWordIndices.add(cInd);
}
Map<Integer, Integer> lastFirstMap = new HashMap<>();
for(Integer index: lastWordIndices){
for(Integer findex: firstWordIndices){
if(findex<index){
if(lastFirstMap.get(index) != null){
if(findex > lastFirstMap.get(index)){
lastFirstMap.put(index, findex);
}
}
else{
lastFirstMap.put(index, findex);
}
}
}
}
Entry<Integer, Integer> currentSmallestEntry = null;
int currentDiff = 0;
for(Entry<Integer, Integer> entry: lastFirstMap.entrySet()){
if(currentSmallestEntry == null){
currentSmallestEntry = entry;
currentDiff = currentSmallestEntry.getKey() - currentSmallestEntry.getValue();
continue;
}
if((entry.getKey() - entry.getValue()) < currentDiff){
currentSmallestEntry = entry;
}
}
System.out.println("currentSmallestEntry: "+input.substring(currentSmallestEntry.getValue(), currentSmallestEntry.getKey()+keywordsList[1].length()));
}
}
Here is my answer in python.
Running time: O(N Log N)
import sys
def find_closest_bigger_number(array, target, next_closest):
if(len(array) == 1):
return array[0] if (array[0] > target) and (next_closest - target) > (array[0] - target) else next_closest
half = len(array)/2
if array[half] > target:
next_closest = array[half] if (next_closest - target) > (array[half] - target) else next_closest
return find_closest_bigger_number(array[:half], target, next_closest)
else:
return find_closest_bigger_number(array[half+1:], target, next_closest)
def find_shortest_sentence(keywords, words):
keywordHash ={}
answer =[]
shortest = sys.maxint
keyword_occurrence_map = []
for pos, keyword in enumerate(keywords):
keywordHash[keyword] = pos
keyword_occurrence_map.append([])
#go through the words and count the occurrence, O(N)
for p, word in enumerate(words):
matched_key_word_pos = keywordHash.get(word, -1)
if matched_key_word_pos == -1:
continue
keyword_occurrence_map[matched_key_word_pos].append(p)
for first_pos in keyword_occurrence_map[0]:
prev_pos = first_pos
last_pos = sys.maxint
for next_word_occurrence_map in keyword_occurrence_map[1:] :
next_word_pos = find_closest_bigger_number(next_word_occurrence_map, prev_pos, sys.maxint)
if (next_word_pos == sys.maxint):
last_pos = sys.maxint
break
last_pos = next_word_pos
if last_pos == sys.maxint:
continue
if (last_pos - first_pos < shortest):
shortest = last_pos - first_pos
answer= [first_pos, last_pos]
return answer
string test()
{
char src[] = "sky cloud google blue search sky work blue";
const char* keys[] = { "sky", "blue" };
map<string, int> strMap;
string tmp;
char* context;
int cnt = 0;
int max = 0;
char*p = strtok_s(src, " ", &context);
do {
if (strcmp(p, keys[0]) == 0)
{
tmp += p;
tmp += " ";
p = strtok_s(NULL, " ", &context);
while (p != NULL)
{
if (strcmp(p, keys[0]) != 0)
{
++cnt;
tmp += p;
tmp += " ";
p = strtok_s(NULL, " ", &context);
}
if (strcmp(p, keys[1]) == 0)
{
tmp += p;
strMap.insert(std::make_pair(tmp, cnt));
cnt = 0;
tmp = "";
break;
}
}
}
p = strtok_s(NULL, " ", &context);
} while (p != NULL);
string final;
auto m = strMap.begin();
max = 0;
for (auto m = strMap.begin(); m != strMap.end(); ++m)
{
if (max == 0)
{
max = m->second;
final = m->first;
}
else if (max > m->second)
{
max = m->second;
final = m->first;
}
}
return final;
}
//C++ code
string test()
{
char src[] = "sky cloud google blue search sky work blue";
const char* keys[] = { "sky", "blue" };
map<string, int> strMap;
string tmp;
char* context;
int cnt = 0;
int max = 0;
char*p = strtok_s(src, " ", &context);
do {
if (strcmp(p, keys[0]) == 0)
{
tmp += p;
tmp += " ";
p = strtok_s(NULL, " ", &context);
while (p != NULL)
{
if (strcmp(p, keys[0]) != 0)
{
++cnt;
tmp += p;
tmp += " ";
p = strtok_s(NULL, " ", &context);
}
if (strcmp(p, keys[1]) == 0)
{
tmp += p;
strMap.insert(std::make_pair(tmp, cnt));
cnt = 0;
tmp = "";
break;
}
}
}
p = strtok_s(NULL, " ", &context);
} while (p != NULL);
string final;
auto m = strMap.begin();
max = 0;
for (auto m = strMap.begin(); m != strMap.end(); ++m)
{
if (max == 0)
{
max = m->second;
final = m->first;
}
else if (max > m->second)
{
max = m->second;
final = m->first;
}
}
return final;
}
- jgriesser January 26, 2018public class Solution { public static String[] shortestSubArray(String[] words, String[] keywords) { // Sliding window of words and their indices Map<String, Integer> wordAtIdx = new LinkedHashMap<>(); Set<String> keywordSet = new HashSet<>(Arrays.asList(keywords)); int solutionSize = Integer.MAX_VALUE; // can alo be words.length + 1 int solutionStartIdx = -1; for (int i = 0; i < words.length; i++) { if (keywordSet.contains(words[i])) { // Remove (if necessary) and re-add word to end of sliding window wordAtIdx.remove(words[i]); wordAtIdx.put(words[i], i); // Check for new solution if our window matches the keyword size if (wordAtIdx.size() == keywordSet.size()) { int windowStartIdx = wordAtIdx.values().iterator().next(); int candidateSize = i - windowStartIdx + 1; if (candidateSize < solutionSize) { solutionSize = candidateSize; solutionStartIdx = windowStartIdx; } // Remove the leftmost element from the window wordAtIdx.remove(words[windowStartIdx]); } } } return solutionStartIdx == -1 ? null : Arrays.copyOfRange(words, solutionStartIdx, solutionStartIdx + solutionSize); } }