Amazon Interview Question for Software Engineer / Developers






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

isnt it same as finding all permutations of a string ?

- Anonymous November 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes

- swapnilkant11 June 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

No - anagrams are permutations that are also words (eg, found in a dictionary).

- Raja November 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will you do that? I gave a solution where in we get a next permute of a given word and check in dictionary if it is available or not.

- Anonymous November 11, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can always optimize by checking if the given prefix is present in dictionary. If its not present we stop generating permutation for that prefix.

- Anonymous November 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use suffix trees. Another problem on a similar note.
how would you implement word completion on a telephone keypad ?

- knap November 17, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can we use suffix tree for this? Can you please give a algo? Also saying Suffix tree is not enough..building a suffix tree itself is complex and impossible while phone interview

- Anonymous November 20, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

While generating a permutation of the string itself, check for the validity by using a prefix Tree(Trie).

- Ace February 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you populate the trie?

- G May 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about having a hash table with keys as sorted letters combined to make a string, of the valid dictionary words and the value as all the possible words in the dictionary that fit into the group of letters which make up the key.
For eg --> Valid words like 'dog','god' will be values in a hash table entry with key as 'dgo' {sorted order of letters that make up the word}
This is precomputed, assuming we have access to the dictionary.

Now try checking for a word, which would essentially mean sorting all the letters of the word. Then basically it many involve performing a look up for the values for this key and print all the words in the value List.
Any opinions ?

- amit October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A key point is avoid duplicate.

- BUAA March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what if the original string has duplicate characters? how do you generate/print out unique strings without caching previous string in memory?

- Itcecsa June 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One of the methods is to print all possible permutations of the string.

Implementation:

#include<bits/stdc++.h>
using namespace std;
void swap(char *x, char *y){
int temp = *x;
*x = *y;
*y = temp;
}
void printanagrams(char *str, int l, int r){
if(l == r)
cout<<str<<endl;
else{
for(int i = l; i <= r; i++){
swap((str+l), (str+i));
printanagrams(str, l+1, r);
swap((str+l), (str+i));
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
printanagrams(str, 0, n-1);
return 0;
}

- swapnilkant11 June 03, 2019 | 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