Amazon Interview Question


Country: India
Interview Type: Phone Interview




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

Can you explain how the answer is 8 for n = 3?

- eugene.yarovoi November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

because index 0 is 1, index 1 is 5 since 2 is repeated value that's why not considered index 2 is 11 and index 3 is 8

- junk.programmer November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Algo:

1. During the first scan create a hashmap for all elements storing the count of the key.
2. Now during the next scan consider only those elements whose hash[key] ==1 (Meaning key present only once in the input.) and find the desired element based on the index.

- pratikrd November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

May be you are not familiar with the concept of 'streaming'.
You don't get a second chance.

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

if we don't have second chance we definetly need to store all numbers..because 1 which is at place 0 might appear as last character...correct me if I am wrong
2ndly storing them in hasmap would sort them according to value,how will we preserve their position?

- kaur November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We need to track numbers that are distinct, so need to go with Set. We need to check if the next number already exists in the Set and if it does then we need to remove it, so need to have a quick lookup - Hash. Insertion order is important so need to be Linked. So, use LinkedHashSet - add numbers as they arrive but check if it exists already. If it exists then rather than additing to the Set, remove it from the Set. So, O(n) time and O(n) space.

- aka.gusu November 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Using LinkedHashMap-----

static Map<Integer,Integer> inputs = new LinkedHashMap<Integer,Integer>();

	
	private static void processStream(int a){
		int count = 0;
		if(inputs.containsKey(a)){
			count = inputs.get(a);
		}
		inputs.put(a, ++count);
	}
	
	private static int findNumber(int index){
		int i = 0;
		for(Entry<Integer,Integer> ent : inputs.entrySet()){
			if(ent.getValue() == 1){
				i++;
				if(i==index){
					return ent.getKey();
				}
			}
		}
		return -1;
	}

- jenish.shah November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

need better implementation this in o(n) space and o(n) time.

- junk.programmer November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain a hash map, and index = -1
Start iterating through the stream,
check if number is in the hashmap
if yes go to next number
if no then put number in hash map and index ++
if number is required number then return index.

- Pushkar November 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a linked list and store the value and count in each node.
2. While searching, do not consider nodes which has count > 1

- Sangeet Kumar April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

LinkedHashMap

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

how will u solve using linked Hashmap?

- junk.programmer November 05, 2012 | Flag


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