Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

start loop
find the first valid word put in stack
search for next valid word push to stack.
positive case all char will form valid case.

if after finding kth valid word, no word is getting formed
pop the kth word from stack find next word for which this popped word was subset. then keep moving ahead. Keep trying until correct set of words.

else pop the( k-1)th word and try the same above steps.


e.g "Hernameisjuli"

push "He"
then rest of the chars not making any words

pop "He"
push "Her"
push "name"
push "is"
push "juli" ( Provided juli is in dictionary ;))

- Sandeep February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if there could be a sentence in which more than one valid combination is possible????????/

For instance: Therestonecrushedspirit

1. The rest one crushed spirit
2. There stone crushed spirit

- vik February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@VIK, I doubt we have to find all the sentences which can be framed with available valid words in given input. with my approach you will find "The rest one crushed spirit" as out put.

But yes we can think of extending solution to find all possible valid sentences.

- Anonymous February 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

dynamic programming improves time complexity

- Anonymous February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

void separateWords_rec(string text, int start_pos, string sentence)
    {
        for (int i = 1; i <= text.size() - start_pos; i++) {
            string word = text.substr(start_pos, i);
            if (isValidDictionaryWord(word)) {
                if (i == text.size() - start_pos) { //solution
                    cout<<sentence<<" "<<word<<endl;
                } else {
                    string new_sentence = sentence;
                    new_sentence.append(" ").append(word);
                    separateWords_rec(text, start_pos + i, new_sentence);
                }
            }
        }
    }

and call it with

separateWords_rec(text, 0, "");

- 88adio February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Naive Recursive approach Approach..
Scan the string.. At every point you find a word. check if you can form a sentence from the rest of the charactors. if yes return 1 and the string formed.
else move on to the next charactor.
If you move till the end of the charactor return 0. -- A sentence cannot be formed.

int CheckSentence(char c[], char rest[], int l) {
    char sentence[2 * strlen(c)];
    char rest[2*strlen(c)];
    if(l>=strelen(c))
           return 1;
    for (int i = l; c[i]!=0; i++) {
        sentence[j] = c[i];
        if (isWord(toWord(c,l, i)) && CheckSentence(c, rest,i+1)) {
            strapp(sentence, ' ');
            strapp(sentence, rest);
            strapp(sentence,'\0');
            strcpy(rest,sentence);
            return 1;
        } 
    }
    return 0;
}

- isandesh7 February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Maintain a Trie structure for dictionary of words.
Traverse the tree from root node as you parse and print each character in the string.
When trie tells you that you have successfully traversed a word, print space and start over from root for remaining characters.

- td.abinesh February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think you have the chance to know the dictionary, because it only provides the interface to query whether a word is in the dictionary or not.

- jilong.liao February 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean makesSentence(String remString,String consideredString,List <String> list)
	{
		int n = remString.length();
        int p = consideredString.length();
		if(n<0)
			return false;
	     boolean b1=false;
		 boolean b2= false;
		 if(isValidDictionaryWord(consideredString))
			{
			 if(n==0)
			 b1 =true;
			 else
			  b1= makesSentence(remString, "", list);
			 if(b1)
				list.add(consideredString);
			}
 	    if(n>0)
 		  b2 = makesSentence(remString.substring(1),consideredString+remString.charAt(0),list);
 	  return b1||b2 ;
	}

- deepak February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We have 2 use cases when a word matches
1.Either the next word starts from the next char
2.The word is part of a bigger word hence continue to check

some examples - timesofindia - we should match times of india
timesoftindia - time soft india.

Code below returns boolean of whether all words are part of dictionary

public static boolean validDictionarywords(String s, int startIndex, int endIndex){
		boolean status = false;
		for(int end = startIndex+1,start=startIndex ; end <= endIndex; end++){
			if( isValidDictionaryword(s.substring(start, end))){
				if(end == endIndex){
					return true;
				}
				String newString = s.substring(end, endIndex);
				status = validDictionarywords(newString, 0,newString.length() );
				if(status){
					return true;
				}
			}
		}
		return status;
	}

- Mohan February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have a collection of linkedlists. These are global variables.
Find the first word. in the example it would be "the".
Put into linkedlist with its starting and ending index.
recursively call a new search from the ending index and then complete the original search.
The next word would be none for the recursive call.
delete the linkedlist starting with "the".
Comes back and gets to next word which is "there".
Put into linkedlist with ending index. Do same call.
Next word is is. starting index one more than ending index of one linkedlist. Add is to that linkdelist. Update ending index.

Also complete initial call which searches for one giant word. Any linkedlist which does not complete till end of string. (its ending index is smaller)... gets deleted.
The left linkedlists contain words in order that complete the sentence.
These are the solutions.

Worst case complexity: n squared time. Memory -- n^n, But unlikely.

- TusharKGerg February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;

public class TriesNode {
char data;
boolean end_of_string;
LinkedList<TriesNode> child;

public TriesNode(char c) {
this.data = c;
this.end_of_string = false;
this.child = new LinkedList<TriesNode>();

}

public TriesNode() {
this.end_of_string = false;
this.child = new LinkedList<TriesNode>();

}

public TriesNode subTriesNode(char c) {
if (this.getData() == c)
return this;
if (child != null) {
for (TriesNode node : child)
if (node.getData() == c)
return node;
}
return null;
}

public char getData() {
return data;
}

public void setData(char data) {
this.data = data;
}

public boolean isEnd_of_string() {
return end_of_string;
}

public void setEnd_of_string(boolean end_of_string) {
this.end_of_string = end_of_string;
}

public LinkedList<TriesNode> getChild() {
return child;
}

public void setChild(LinkedList<TriesNode> child) {
this.child = child;
}
}

public class Tries {
TriesNode root;

public Tries() {

}

void insert(String s) {
TriesNode cur = root;
if (s.length() == 0)
return;
if (s.length() == 1) {
if (cur == null) {
this.root = new TriesNode();
root.setData(s.charAt(0));
cur = root;
}
}

for (int i = 0; i < s.length(); i++) {
if (cur == null) {
this.root = new TriesNode();
root.setData(s.charAt(i));
cur = root;

} else {
TriesNode child = cur.subTriesNode(s.charAt(i));
if (child != null) {
cur = child;
}

else {
cur.child.add(new TriesNode(s.charAt(i)));
cur = cur.getChild().getFirst();
}
}

}
if (cur.isEnd_of_string() == false)
cur.setEnd_of_string(true);

}

boolean search(String s) {
TriesNode cur = root;
if (s.length() == 0)
return false;
for (int i = 0; i < s.length() - 1; i++) {
if (cur.getData() == s.charAt(i))
cur = cur.getChild().getFirst();
}
if (cur.isEnd_of_string() == true)
return true;
return false;
}

public static void main(String[] args) {
Tries tries = new Tries();


tries.insert("there");
tries.insert("is");
tries.insert("a");
tries.insert("stone");
tries.insert("on");
tries.insert("the");
tries.insert("road");
tries.search("thereisastoneontheroad");



}
}

- uday February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi friendz..
We can also use the following approach instead of using stack for storing words. Extra space not required.

- Start with the first index, have two variables for eg. (int start=0; int end1=0;, int end2 = 0;)
- Then start with the first char and while moving ahead make the 'start' pointing to the first char and then increase 'end1' as we are moving ahead and see if the substring from (start, end1) is a valid word or not?
Case a: If Its a valid word, then we know (start, end1) index of valid sub string.
Case b: If not a valid word, then move the 'end1' further and look for the sub string valid/not valid.

If suppose, in the Case a, But we are interested in finding the largest valid word. So in that case, we have the first substring points (start, end1). So now start with 'end2 = end1' and increase 'end2' and see if the subString from (start, end2) is valid or not. If it is valid then change 'end1 = end2' and again cont.. Till the point, we found the largest valid word. Otherwise ,we are on the safe side, by getting the last largest word by getting (start, end1).

Repeat this...We will get the valid substring without extra space.

Please add, If I am missing something?

Thanks you...!!

- Manpreet February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the complete java running code is given in dsalgo.com.

- Partha Pratim Sirker February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you Partha from Roorkee ??

- Abhi February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala:

def isValidWord(w: String) = List("There", "is", "a" "stone", "on", "the" ,"road").contains(w)

def construct(s: String, sent: String, w: String): String = s.toList match {
  case Nil => sent
  case c :: rest if (isValidWord(w+c)) => construct(rest.mkString, sent+ " "+ w+c, "")
  case c :: rest => construct(rest.mkString, sent, w+c)
}

- rbsomeg February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public string findSent(String sentNoDelim)
{
if (sentNoDelim == null || sentNoDelim == "")
{
return "";
}
for (int i = 0; i<sentNoDelim.length;i++)
{
string tempWrd = sentNoDelim.subString(o,i);
if (isValidWord(tempWord))
{
return tempWrd + " " +
findSent(sentNoDelim.subString(i+1), sentNoDelim.length()));
}
}
}

- shrikool February 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You should try to find the longest word as possible. e.g. try "thereisastoneontheroad", then "thereisastoneontheroa", until you find "there". Not efficient but will be accurate I believe

- north212 February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works :
using recursion.
The method is similar to what Sandeep has explained, so I wont bother.
This just does not use a stack.

private static final String ERROR_STRING="whatever the hell";
	private static String getSpacedSenterce(String str) {
		if ( isValidDictionaryword(str)){
			return str;
		}
		for ( int i=0 ; i<str.length() ; i++ ){
			if ( isValidDictionaryword(str.subSequence(0, i).toString())){
				String result = getSpacedSenterce(str.substring(i));
				if ( ! result.equals(ERROR_STRING)){
					return str.substring(0,i)+" "+result;
				}
			}
		}
		return ERROR_STRING;
	}

- gautam142857 March 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Very strange question. What's the big deal. There has to be atleast one word and the sentence should start from it. Start a linear traversal from beginning and keep on adding characters, for every character added see if the word formed so far is a well formed word. If NO add more characters. If Yes, print this valid word and repeat the process for the remaining sentence.

- Abhi February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

agree this task seems to be very easy...

- S.Abakumoff February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for the sentence thereisastoneontheroad when you reach the 3rd character ('e') you have a good word ('the') and the rest ('reisastoneontheroad') is not a well formed word.. in this case you should keep trying.

- rodrigoreis22 February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

i dont understand

- tomer February 02, 2013 | 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