Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
@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
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.
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 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.
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.
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
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?
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...
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("-----------------------------------------------");
}
//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);
}
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)
#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();
}
you can always use a constant space. if know the range of numbers here a bit vector can be used.
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)
you have to take care of the time complexity of sorting the list too..
so the time complexity wont be O(n)
-> 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.
Then we can do xnor.
The final number that we obtain after doing xnor is, number repeated even times.
@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
@ 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.
There is no O(N) and constant space solution for this.
- loveCoding July 17, 2012The best with constant space can be O(nlogn)