Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

Isn't this cheating ? Posting questions from a contest running now. :-/

- Reddy June 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems like people cheat without realizing that it won't get them a job. They'll still have to clear the in-person where cheating is harder.

- eugene.yarovoi June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- monu July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What do you mean by word frequency here??
i dont understand..

- Anonymous July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- monu July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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");
    }
}

- monu July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting approach. I see you used a frequency counter. I hadn't thought of that. I was storing the index of the most recent occurrence of each element instead.

- eugene.yarovoi July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

THis question was just posted a few days ago...look through the most recent 20 or 30 ques

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

use sliding window

- jiangok2006 June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u provide some reference which can help in this problem..

- newhere June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same question posted not 5 days ago: www . careercup . com / question?id=14062676

- eugene.yarovoi June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

cool, man!!

- neyshule June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- Rahul July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is not a solution,,
there can be many occurrences of the words
and you are checking just the first.

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

// 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);
	}

- pamit July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Giving Wrong Answer...

- Anonymous July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you provide me your testing inputs ?

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

This can be done using Dynamic Programming. Please refer the below link for the detailed explanation:-

hxxp://stackoverflow.com/questions/16368153/method-to-find-the-shortest-substring-containing-the-given-wordsoptimization-re

- hulk March 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

r u ok

- Anonymous June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

happened due to network problem.....idk

- newhere June 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Sanyam Jain July 07, 2012 | Flag Reply


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