Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
hey recently same ques was asked in amazon india coding contest at interviewstreet.com
because the contest is over now i will give my approach.
Algorithm:
1.Take 2 pointers head and tail both pointing to start of the sentence
now move head ponter untill u get a keyword which is present in our required keyword list and mark it as head
2.now move tail pointer untill all of ur keywords presented in that sentence for at least once now mark it as tail
this is a first valid sub segment of the given sentence with given keywords
3.now check word frequency at head if it is greater than our requirement now move head untill it reaches a valid keyword with exactly it's frequency equals to 1
4.now we cannot move head further which results breaking the all keyword condition
5.so now move tail pointer untill frequency of keyword at head is greater than 1
6.now again move head untill keyword frequency becomes 1 whenever this condition met calculate it's length
finally stores the min length with start and end positions
means no of appearences of word in the sentence
for example consider : this is a mathematical challenge.And it will test your mathematical abilities
now word frequencies are this-1 is-1 a-1 mathematical-2 challenge-1 and-1 it-1 will-1 test-1 your-1 abilities-1 have u got it
here is my implementation in java
import java.util.*;
import java.io.*;
public class Solution
{
public static void main(String[] args)
{
Map<String, Integer> needstofind = new TreeMap<String, Integer>();
Map<String, Integer> hasfound = new TreeMap<String, Integer>();
String final_result="";
String result="";
int begin=0;
int end=0;
String words[];
String text_words[];
String final_words[];
String str_final;
int begin_tmp=0;
int end_tmp=0;
int flag=0;
int z=0;
int len;
int txt_len;
int i;
int count=0;
int needstofind_size;
int min=0;
int final_length=0;
Scanner in = new Scanner(System.in);
String string = in.nextLine();
string = string.replaceAll("[^a-zA-Z| |]", " ");
string = string.replaceAll(" ", " ");
str_final=string;
string=string.toLowerCase();
z = in.nextInt();
words = new String[z+1];
in.nextLine();
for(i=0; i<z; i++)
{
words[i] = in.nextLine();
needstofind.put(words[i],1);
}
text_words = string.split(" ");
final_words=str_final.split(" ");
len=hasfound.size();
txt_len=text_words.length;
i=0;
needstofind_size=needstofind.size();
begin=0;
count=0;
for(end=0; end<txt_len; end++)
{
if(needstofind.containsKey(text_words[end])==false)continue;
hasfound.put(text_words[end],hasfound.get(text_words[end])==null?1:hasfound.get(text_words[end])+1);
if(hasfound.get(text_words[end])<=needstofind.get(text_words[end]) )count++;
if(count==needstofind_size)
{
flag++;
while(needstofind.get(text_words[begin])==null || hasfound.get(text_words[begin])>1)
{
if(needstofind.containsKey(text_words[begin]))
{
if(hasfound.get(text_words[begin])>1)
hasfound.put(text_words[begin],hasfound.get(text_words[begin])-1);
}
begin++;
}
if(flag>1 && end-begin+1>min)continue;
result="";
min=end-begin+1;
for(int j=begin; j<=end; j++)
result=result+final_words[j]+" ";
if(flag==1)
{
final_result=result;
final_length=min;
}
else if(min<final_length && flag>1)
{
final_result=result;
final_length=min;
}
}
}
if(flag>0)System.out.println(""+final_result);
else System.out.println("NO SUBSEGMENT FOUND");
}
}
we can do one thing.....
we shall replace all the spaces in the string with null
then,
1`:-use strcmp function to find the first matching string.....
2:-mark that index as i...
3:-and then go on taversing all the strings till all the words to be searched is found..
4:-then the point where all the words to be matched are found is marked as j..
5:-the lenght i to j gives us the smallest part of the sentence...
// Find the smallest sentence containing a set of words.
public static String smallestSentence(String input, String output, String... words) {
if (input == null || input.isEmpty() || words == null || words.length == 0)
return output;
int startIndex = -1;
int endIndex = -1;
for (String word : words) {
int indexOf = input.indexOf(word);
if (indexOf == -1)
return output;
startIndex = (startIndex < indexOf && startIndex != -1) ? startIndex : indexOf;
endIndex = endIndex > indexOf + word.length() ? endIndex : indexOf + word.length();
}
output = (output.length() < (endIndex - startIndex) && output.length() != 0) ? output : input.substring(startIndex, endIndex);
return smallestSentence(input.substring(endIndex), output, words);
}
There is one more possible solution...
suppose we have the source string (A) of 1000 words and the sub-string to be searched (B) with 50 words..
give each word in B an ID from 1 to 50 and replace the words in A with their respective id's came from B. Now replace the remaining words in A by -50000.
Now search for a max sum sub array with condition that numbers 1-50 exist in it. and to make it perfect, search for the boundary values for duplicates within the resultant array, this will ensure that the words which are already in the array do not occur at boundaries which can happen to maximize the sum while searching with mathematical algorithm.
Isn't this cheating ? Posting questions from a contest running now. :-/
- Reddy June 29, 2012