Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

I would also start with trie.
Second option is the compressed trie.
Last one is hashing:
If we are talking about the real words it is hard to imagine the dictionary with the elements length more than 10 average. Also we probably don't want to store more than 10-20 suggestions for user (we can update frequency or use other idea to choose the right words) but for each prefix (or prefix hash and length) we can store a set of suggestions. Of course we store only prefixes we have in the dictionary. So in other words we use the prefix with length X as the key and words (only 10 best as values).

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

Trie is good option but the problem with trie is that it wastes a lot of memory. Ternary tree can be used instead of trie.

- shsf January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

really depends on implementation of trie. the classic trie implementation which has a slot for ever possible character in the language at each node would be wasteful of memory. if you design your trie such that each node has a pointer only for characters of strings it stores, it should be fine.

share your thoughts.

- anon123 January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Google prefix search, it is distinct problem in search. Also trie will be ok. But what will you do with typos and request with a few words?

- glebstepanov1992 January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Imp thing here is it is designed for a mobile. I think best you can do apart from TRIE is store all the words in 26 files. Words starting with each unique alphabet in English each file (a-z 26 files). Inside the file you will have words with similar prefix just like in TRIE on different lines. So when user types first three letters of the word you know where exactly to search !

- Anuj Kulkarni February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ternary search tree will be a good solution. It will not use extra space like trie.

The ternary search tree contains three types of arrows. First, there are arrows that correspond to arrows in the corresponding trie. Traversing a down-arrow corresponds to “matching” the character from which the arrow starts. The left- and right- arrow are traversed when the current character does not match the desired character at the current position. We take the left-arrow if the character we are looking for is alphabetically before the character in the current node, and the right-arrow in the opposite case.

.
             A
		    :   \
		    B    B
		    :    :
	    	C    C
	      /	:   :
	     B   D   D
	     :
	     A

The elements are ABCD,ABBA,BCD

- febinrasheed July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Use TreeSet as dictinary to hold all the possible valid strings, and for each word typed by user invoke a webservices, which return all the string with prefix typed by user.

- SAM January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

suffix tree will be good option. Nodes will be allocated only when they are required.

take example of apple, application, aptitude
                 a
                /
              p
             /  \
         pl     titude
        /   \
      e     ication

if user type: ap then output will: aptitude, apple, application
if user type: app then output will be: apple, application

whenever there is new addition of word and that word require to break node at some level, then break it and make two or more nodes.
"Apartment" and "Applied" addition will make tree like this
                             a
     	                    /
                       _    p
                     /    /   \
                 artment pl  titude
                         /   \
                       e     i
                           /  \
                          ed   cation

- SK January 30, 2014 | 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