Amazon Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

#include <stdio.h>

main()
{
        int a[5] = {10,2,100,50,101},index=0,big;
        big = a[0];

        for(index = 1;index < 5;index++)
        {
                if(a[index] > big)
                {
                        big = a[index];
                }
        }

        printf("biggest element :%d\n",big);
}

output : biggest element :101

- nani.m March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 for not trying to sort. :) The question never asked about sorting

- Kavitha March 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 10 vote

Quicksort will be best. After the first iteration the pivot is in the right position and all values left are smaller than pivot and all values to the right are larger than the pivot. Now do the same iteration again on the right subarray till you set the last element. Avg: O(logN). Worst case (already sorted array): O(n).

- Gagan March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

Hi, after your first iteration, you have already visited all the elements in the array. so should this be O(N)?

- Richard March 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, modifying quicksort is best (lg n)
Not sure you can beat logarithmic unless array is already sorted (then it is O[1] ).

- Anonymous March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

QuickSort is the best for sorting , not for finding max element in array. At the first iteration itself with constant pivot we are traversing all the element to do the partition(small->left,max->right).
Instead with dynamic (NewPivot=>(pivot<currentvalue)) pivot value at the first iteration itself will find the max value. And this too is not O(logn) ,It's O(n).
Correct me if i'm wrong.

- Vijayashankar March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

There is no way that this is less than O(n) since on your first pass with a selection algorithm will touch every element on its first run and logarithmically degrades after that. The easiest solution is to just scan the entire list and keep track of which is the highest for O(n). This can change given the circumstances. If the list is sorted or even partially sorted you can achieve better than O(n) but otherwise that's the best you can do.

- Matt March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 Matt

But what does "logarithmically degrade" mean?

- Le Subbu, King of CC March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

So, there's plenty of explanation on how/why to do a QuickSort, but in my opinion, something MAJOR is left out here, which is to *Ask your interviewer questions before answering!* QuickSort can quickly become the wrong answer with some detail.

1. Is the list sorted? Probably not, but worst case you get "no" and best case, you're applauded for being thorough.

2. Can I sort the list? And if not, do I have the memory to copy then sort the list? A no here means that again QuickSort is out.

3. How big is the list? If you've got an int array list of a constant size 5, QuickSort is sort of using the broad sword when the butter knife will do.

All a bit pedantic here perhaps, but keeping this mindset is vital.

- kakitayuri March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

there is simply NO NEED to sort it.

- meow March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Bubble sort in increasing order
2. Linear scan to end of array, and grab last element (which should be max)

O(n^2) + O(n) .
Easy.

- Le Snob. March 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Idiot.

- Le snob. March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Comedian.

- La oaf. March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes - this solves the problem, check the complexity.

- dumb March 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks good to me. Why idiot? The code is working for me.

- Vincent March 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^ it's extremely inefficient. O(n^2) ... just no.

- Jonathan March 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are all dumb

- La oaf March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 6 vote

Do a quicksort.
After the first iteration the pivot is in the right position and all values left are smaller than pivot and all values to the right are larger than the pivot.
Sort the array left of the pivot and you have the largest element, or just do comparisons.
Best case, if pivot is the largest number.
Worst case, if pivot is the smallest number.
Average case, O(log N)

- Kruz March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Average case is not O(log N) in an unordered array.
Still have to account for comparison operations and swaps using the partitioning strategy.

- Anonymous March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a is an array
max=a[1]
for i 2 to n
if(a[i]>max)
max=a[i]

- Anonymous March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int max,i=0,a[10];
max=a[0];
while(i<10)
{
if(max=a[i])
max=a[i];
}
printf("max=%d",max);
}

- 11oodp14 March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.If the array is sorted the largest element can be found at the end of array
2.If the array is not sorted traverse through the array find the max
3.If there are frequent insert options that can be taking place on the array along with the finding largest element,
- sort the array first
- do the insert options in the sorted order
- find largest element at the end of array

- Satish Kumar March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the input sequence has been sorted,use binary search.If not,i think there should just has a algorithm with O(N)

- Anonymous March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the input sequence has been sorted,use binary search.If not,i think there should just has a algorithm with O(N)

- Anonymous March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have you tried using a hashmap?

- Joshua March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I see people have commented using Bubble Sort. For those people who say Bubble Sort is stupid, How about you do only one iteration of Bubble Sort which will be O(n)[Now please note I am not saying n iterations of Bubble Sort] and the last element will always be the max. Think about it.

- Aditya Narain March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Given an array of arbitrary length
int i = 0;
int max = array[0];
while(array[i] != '\0')
{
if(array[i] > max)
{
max = array[i];
}
i++;
}

- Mac N Cheese March 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Ruby, the simple way assuming the program runs like ./prog 1 2 34 5 6 7 6 5 4 3 2 1

puts ARGV.max

With the actual logic and using inject to save some variable declaration:

puts ARGV.map(&:to_i).each.inject(ARGV[0].to_i) {|highest, val| val > highest ? highest = val : highest}

- Anonymous April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Hi, Please help me to understand why we need of bubble sort. This can be achieved simply traversing array once which is O(n-1).
{{class Maxinarray {

public static void main(String[] args) {

int[] a={1,5,6,8,90,4,3,2,2};
int max=a[0];
for(int i=1;i<a.length;i++)
{
if(a[i]>max) max=a[i];
}
System.out.println("Max is="+max);
}
}
}}}

- Vijayashankar March 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

We don't need bubble sort. Either that guy is an idiot, or a comedian.

- Anonymous March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(N) the -1 is arbitrary

- Radzell March 18, 2014 | 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