Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

There is no O(N) and constant space solution for this.
The best with constant space can be O(nlogn)

- loveCoding July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This can be done in O(n) time and constant space.

See my comment below!!

- words&lyrics July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@words&lyrics : your solution is incorrect .
take this test case : {100 , 1 , 1 , 3 , 5 , 3 , 3 } , Max =100 , Min = 1 , a[a[0]-min] = a[100-1] = a [99] - ArrayIndexOutOfBound

- Zee July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@niteeshm I think you commented on wrong post

- loveCoding July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@maverick: By extra space, I guess you used a hash table?

- ramblersm July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are correct.

- maverick July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort, parse for a number with even

- gs July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Solution without using extra space:

Check the same no. encountered till the array ends and also keep the count when we find the same no. (for each pass) .
Count is even= return the number.
Time Complexity : O(n*n) No extra space is used.

- ramblersm July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can sort the list and do it without using extra space in O(nlogn) time

- student July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorting is the best way without using extra space.

- Kishan August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well I could think of 3 solutions by which we can solve this...

1) Using two loops to traverse the array and count the number of times each digit is 
encountered...... Time Complexity O(n^2)   Space Complexity O(1)

2) Using hash table                       
Time ComplexityO(n)    Space ComplexityO(n)


3)Sorting the list and then checking the number at position i with i+1 and i+2 
Time Complexity   O(nlogn)   Space Complexity O(1)

i want to know if its possible to solve it in Time complexity O(N) and space complexity O(1)

- student July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@student what kind of sorting you are assuming? I read that in-place sorting (constant space complexity) is not that practical for a complexity of nlogn.

- Daru August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what would your implementation look like with hashtable?

- metal January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we assign bit value 1 to all element as default value and when number repeats then toggle bit value to 0.Repeating same procedure we get the elements with even appearance with bit value 1.

- Dacron July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose long takes 4 bytes of memory!
so the size of array has to be 2^32 Its too much memory!

- Psycho August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did they mention anything abt the range of n?? or random number??

For example :
if he mention the range of no lyk 1...n, we can use XOR and find

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

1. Take XOR of all elements and store in a variable 'temp'
2. Now with two pointer in the list... with first one(say 'first') points to head and other(say 'second') moves through the list, when two pointer have same values , delete both the nodes.(by this time first = first->next and second = first -> next). Repeat this step until moving pointer reach the end.
3. now the list contain only element that are repeated odd number of times
4. now xor this list and then xor with temp.
5. you will get the element which is repeated even number of times

- cobra July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no need to use extra space here just one integer variable is enough

- vigneshb06 July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n2)

- jiangok2006 July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution doesn't work. but good attempt .

- krishna July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey guys, can anyone of you kindly help me out with the sorting algo which u are using for O(1) space complexity and O(nlgn) time complexity?

- fire and ice July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using quick sort will be fine??? because as far as i know recursive algorithms are also considered as using extra space in the form of stack...

- fire and ice July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

use heap sort then!

- Psycho August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

written following code which is using dictionary in o(n) time and space (n) times

public static void RepeatedEvenTimes(int[] inputArray)
        {
            Dictionary<int, int> numbers = new Dictionary<int, int>();
            int length = inputArray.Length;
            int num = -1;
            for (int i = 0; i < length; i++)
            {
                if (numbers.Keys.Contains(inputArray[i]))
                {
                    numbers[inputArray[i]] = numbers[inputArray[i]] + 1;
                }
                else
                {

                    numbers.Add(inputArray[i], 1);
                }
            }

            Console.Write("input Array ");
            Console.WriteLine(string.Join(",", inputArray));

            foreach (var item in numbers)
            {
                if (item.Value % 2 == 0)
                {
                    num = item.Key;
                    Console.WriteLine("{0} Repeated {1} times ", item.Key, item.Value);
                    break;
                }

            }

            if (num == -1)
            {
                Console.WriteLine("No number Repeated even number of times");
            }

            Console.WriteLine("-----------------------------------------------");
        }

- ajaypathak July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Sort the list in O(nlogn)
2. var xor1=start->info;
for(ptr1=start->next,ptr2=start;ptr1!=null;ptr1=ptr1->next,ptr2=ptr2->next)
{
if(ptr2->info==ptr1->info)
continue;
else
xor1^=ptr1->info;
}
3. var xor2= XOR of all the nodes in the list
4. xor1 ^ xor2 = result

- Leo July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//after sorting..
# include <conio.h>
# include <stdio.h>

main()
{
      int arr[] = {1,1,1,2,2,2,2,3,3,3,4,4,4};
      
      int i,j,k,m;
      
      for (i=0;i<13;)
      {
          m = i;
          k = 0;
          for(j=i;j<13;j++)
          {
                           if (arr[i]!=arr[j])
                           {
                                              break;
                           }
                           
                           else
                           {
                               k++;
                               m++;              
                           }
          }
          if(k%2 == 0)
          {
                 printf("Found = %d", arr[i]);
                 break;
          }
          i = m;
      }
      
      getch();
      return(0);
}

- Mintu July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int a[] = {1,1,1,2,2,2,2,3,3,3,4,4,4};
int count = 0,tmp=0;
for(int i=0; i < 13; i++)
{
tmp = a[i];
if(tmp == a[i+1])
{
count++;
}
else
{
if(tmp == a[i-1])
count++;

if(count%2 ==0)
cout<<a[i]<<"appears even no of times"<<endl;
count =0;
}
}
}

time complexity o(nlogn) with space complexity o(1)

- Ashish j August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream.h>
#include<conio.h>
  void main(){
      int a[100],n,i,j,count;
      clrscr();
      cout<<"\nEnter the size of the array :";
      cin>>n;
      cout<<"\nEnter the Positive integers one by one :";
      for(i=0;i<=n-1;i++)
             cin>>a[i];
      //Finding the integer repeated Even times
      for(i=0;i<=n-1;i++){
          count=1;
          for(j=i+1;j<=n-1;j++){
                  if(!(a[i]^a[j]))
                        count++;
          }
     if(count%2==0){
          cout<<"\nThe Element repeated even times is :"<<a[i];
          break;
     }
   }
 
//If no such repetition
 if(i==n)
  cout<<"\nNo element is repeated even times";
 getch();
}

- Pam_Six September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a bit vector and flip the resp. bit while scanning the list.

- ashwanilabs July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What part of "no extra space" didn't you understand?

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

you can always use a constant space. if know the range of numbers here a bit vector can be used.

- ashwanilabs July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Stop making additional assumptions which make the problem trivial.

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

1. Hey guys use two for loop and compute the count for each item and check whether count%2==0 if the condition gets satisfied then print the result

Time Complexity: O(N2) Space Complexity: O(1)

2. Sort the list and use two pointers to check the count and check the same condition as i have mentioned above and if that gets satissfied print the result
Time Complexity: O(N) Space Complexity : O(1)

- vigneshb06 July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have to take care of the time complexity of sorting the list too..
so the time complexity wont be O(n)

- cobra July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no problem sorting time complexity will be O(nlogn) as in case of merge sort summing up O(nlogn)+O(n) we get O(n) only nested for loops have time complexity as O(N2)

- Vignesh July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

-> Sort ascending or descending.
int i = 0;

for(; i<length; i=i+3){
     if(a[i] == a[i+1] && a[i] == a[i+2])continue;
     else break
}
a[i] will be that even repeated number.

- AJ July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

lets say the array contains only {2,2,2,2,2}....How does your logic works?

- Sai July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

xor all the numbers....only the one occuring once will remain finally..

- ank July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

will work if the odd n even interchanged in the question

- anonymous July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Then we can do xnor.
The final number that we obtain after doing xnor is, number repeated even times.

- anon July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

xnor of all the numbers will be same as xor of all the numbers.

- Leo July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would the 'a[[a[i]- min]]' be possibly out of boundary?

- emma.wang July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@words&lyrics : your solution is incorrect .
take this test case : {100 , 1 , 1 , 3 , 5 , 3 , 3 } , Max =100 , Min = 1 , a[a[0]-min] = a[100-1] = a [99] - ArrayIndexOutOfBound

- Zee July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You are a PIG.

- loveCoding July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ words&lyrics
if you inherently meant allocate the extra space then you are no longer in O(1) space. just because you use the same array does not mean your solution is O(1) space. Your solution could potentially use a lot of extra space in it's current format, using a hashtable it would be O(n). but not a bad idea as long as you don't call it O(1), interviewers love seeing this kind out of the box soln.

- agniva July 19, 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