Amazon Interview Question
SDE1sTeam: Bangalore
Country: India
Interview Type: In-Person
It was not as simple as I thought in first go, but with a little thinking I was able to code it.
void getDuplicate(int arr[],int size)
{
int pos = 0;
int desiredPos = 0;
while(pos < size)
{
if(arr[pos] <= 0)
{
pos++;
}
desiredPos = arr[pos] -1;
if(arr[desiredPos] > 0)
{
arr[pos] = arr[desiredPos];
arr[desiredPos] = -1;
}
else
{
arr[desiredPos]--;
arr[pos] = 0;
pos++;
}
}
}
you can check the complete executing code with explanation at : ms-amazon.blogspot.in/2013/07/you-are-given-array-of-n-integers-which.html
Nice solution varun.
One correction
after checking if(arr[pos]<=0)
apart from incrementing pos a continue statement can be given to continue the loop process from the beggining
i.e
if(arr[pos] <= 0){
pos++;
continue;
}
Am i right?
@vishnu yes you are right, I missed it thanks for pointing out.
@algos It words for your example, just try introducing continue as vishnu suggested.
Output for your example:
Element = 1 Frequency = 0
Element = 2 Frequency = 0
Element = 3 Frequency = 0
Element = 4 Frequency = 0
Element = 5 Frequency = 0
Element = 6 Frequency = 0
Element = 7 Frequency = 1
Element = 8 Frequency = 1
Element = 9 Frequency = 9
Element = 10 Frequency = 0
Element = 11 Frequency = 0
@sibendu If you are using counting sort then yes it will.
Given range of array you can sort it in O(n) time.
And by range I mean no. of elements in range must be equal to the number of elements in array.
for eg. if we have 10 int array and range is (1,100) (any 10) then it is not possible but if range is (20,30) yes in this case it is possible.
@varun:im not talking about time complexity .Counting sort takes o(n) extra space which in that case is not allowed by the interviewer.
Sorry forgot to mention it will take O(1) space.
The simplest sorting algo with O(1) space and O(n) time complexity must have 2 conditions all elements must be in some range and all elements must be unique.
I believe this approach can be extended to arrays not satisfying the second condition, that will require some thinking.
In above I have not sorted instead manage to store the frequency without sorting, You can follow the other approach as well.
@varun:
Hi, Sibendu is asking you *how* you can sort the array in O(n) time with O(1) extra storage space. I am interested too. Please tell us how this is (roughly) possible... Thanks.
Btw nice solution!
@chih.chiu this is a separate question, I have coded it for the case where all elements are unique in array.
Complexity:
Time : O(n)
Space: O(1)
void sort(int arr[],int size)
{
int pos = 0;
while(pos <size)
{
int desiredPos = arr[pos]-1;
if(pos == desiredPos)
{
pos++;
continue;
}
else
{
swap(arr,pos,desiredPos);
}
}
}
But giving a second thought to it, why do we even need to sort it when range is given?
All element are unique, we should simply overwrite the values and continue moving forward in array.
We can solve this in two scans Time complexity: o(n) ans space complexity o(1)
1) In first scan for each of occurrence of an element add the array size to that element.
2) In second scan Divide the element value by n gives frequency of occurrence.
void repetitions(int A[],int n)
{
int i=0;
for(i=0;i<n;i++)
A[A[i] %n] + = n;
for(i=0;i<n;i++) {
frequency = A[i]/n;
element=i;
print("Element= %d , frequency = %d", element, frequency );
}
}
@varun, etc: While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
@hj:
both varun and venkatesh's solution are based on counting sort coupled with the fact that every element <= n-1. Thus if we divide any element by n, it is 0. So they use counting sort in-place and add n to elements. In the second pass, while dividing by n, the original content does not matter and we get the frequency. So we are not using any 'extra' space!
Solution goes like this....
{8,1,9,2,5,1,1,1,1} can be treated as the test data.....
{58,11,9,2,15,1,1,11,11} would be the processed data....
The process goes as follows....
8 - > add 10 to location 8 {8,1,9,2,5,1,1,11,1}
1 -> add 10 to location 1 {18,1,9,2,5,1,1,11,1}
9 -> add 10 to location 9 {18,1,9,2,5,1,1,11,11}
2 -> add 10 to location 2 {18,11,9,2,5,1,1,11,11}
5 -> add 10 to location 5 {18,11,9,2,15,1,1,11,11}
1 -> add 10 to location 1 {28,11,9,2,15,1,1,11,11}
1 -> add 10 to location 1 {38,11,9,2,15,1,1,11,11}
11 -> special process ( if element is > 10) compute the modulo and add 10 to that location...11 % 10 = 1 ...so add 10 to location 1 {48,11,9,2,15,1,1,11,11}
11 -> special process ( if element is > 10) compute the modulo and add 10 to that location...11 % 10 = 1 ...so add 10 to location 1 {58,11,9,2,15,1,1,11,11}
{58,11,9,2,15,1,1,11,11}
58 - yields 58 / 10 times 1 and the original value is 58 % 10
and so on for each value....Array values are not lost....
Note : 10 is size of the array + 1...in code we have used 20 as our array size
//Code by FINDMIND TEAM
//Done by Prabhakaran Dhandapani, NN Priya, Vaishnavi
//Guided by Sridhar Arumugasamy
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define SIZE 20
void computeAndPrint( int arr[],int size ) {
int index = 0;
for( index = 0 ; index < size ; index++ )
if( arr[ index ] < ( size + 1 ) )
arr[ arr[ index ] - 1 ] += ( size + 1 );
else
arr[ arr[ index ] % ( size + 1 ) - 1 ] += ( size + 1 );
for( index = 0 ; index < size ; index++ )
printf("\t\t%2d--->%2d--->%2d\n", arr[ index ] % ( size + 1 ), index + 1, arr[ index ] / ( size + 1 ));
}
void assign(int arr[], int size) {
int index;
randomize();
for( index = 0 ; index < size ; index++ )
arr[ index ] = (rand() % size) + 1;
}
void main() {
int arr[SIZE];
assign(arr,sizeof(arr)/2);
computeAndPrint(arr,sizeof(arr)/2);
}
19---> 1---> 1
1---> 2---> 1
20---> 3---> 1
18---> 4---> 1
17---> 5---> 0
19---> 6---> 0
3---> 7---> 0
2---> 8---> 1
4---> 9---> 0
8--->10---> 0
14--->11---> 0
17--->12---> 0
20--->13---> 0
18--->14---> 3
14--->15---> 0
14--->16---> 1
19--->17---> 2
18--->18---> 4
18--->19---> 3
16--->20---> 2
just store value as (val + count * N)
void arrayCount(int* a, int N)
{
for(int i=0; i<N; ++i)
{
int count = a[i] / N;
int val = a[i] - count * N;
a[val] += N;
}
for(int i=0; i<N; ++i)
{
int count = a[i] / N;
cout << count << " ";
}
cout << endl;
}
While very clever, this is an O(n) space algorithm. You are assuming you have additional free bits to add N in which may not be true. Standard complexity analysis would show this as O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
Alternative approach, encode fields which specify a normal value as positive, those that contain a count as negative, then proceed through the array. If the value we see is smaller than the index, simply decrement the field for the value (since we must already have removed any value there) if it is larger, then swap the value in that field currently with the current value and set the field value to -1, except if the field is already negative, in which case just decrement.
Afterwards, the array is filled with negative values which are the counts, so just pop a minus in front of them and voila.
It's a little hard to follow, so here's the code:
public static void countey(int [] nrs)
{
System.out.print("Pre: ");
for(int j = 0; j < nrs.length; j++)
{
System.out.print(nrs[j] + ", ");
}
System.out.println();
int i = 0;
// for(int i = 0; i < nrs.length; i++)
while(i < nrs.length)
{
System.out.print("At " + i + ": ");
int curNr = nrs[i];
if(curNr < 0)
{
i++;
// continue;
}
else if(curNr <= i)
{
nrs[curNr]--;
nrs[i] = 0;
i++;
}
else if(nrs[curNr] < 0)
{
nrs[curNr]--;
nrs[i] = 0;
i++;
}
else
{
int temp = nrs[nrs[i]];
nrs[nrs[i]] = -1;
nrs[i] = temp;
}
for(int j = 0; j < nrs.length; j++)
{
System.out.print(nrs[j] + ", ");
}
System.out.println();
}
for(i = 0; i < nrs.length; i++)
{
System.out.print(-nrs[i] + ", ");
}
System.out.println();
}
While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.
If you can generate a sequence of primes P(1) to P(n) you can create single number that will represent a digest of the data set (there are formulas out there like f(n)=n^2−n+41 that will do that for you). For example, you could use the prime sequence 3,5,7,11,13,17 to represent the set of numbers 1,2,3,4,5,6 where P(1)=3, P(2)=5, P(3)=7, P(4)=11, P(5)=13, P(6)=17.
Start with your digest as equaling 1 (call it D). Every time you see a 1, multiply it be P(1). Every time you see a 2, multiply it by P(2) etc...
Thus if your sequence is: 1,2,4,5,1,1 the 'digest' is:
D = P(1)*(2)*P(4)*P(5)*P(1)*P(1)
or another wards
D = 3 * 5 * 11 * 13 * 3 * 3
Then once you're done. Go through D and divide it with each P(n) in sequence and so long as you get a remainder 0 result you know there's another P(n) in there. In this example:
-Start dividing by 3, you will see that D divides by 3 exactly three times (hence the number 1 repeats exactly 3 times, print this information)
-Then move onto the next prime 5 and you will see that D divides by 5 exactly once (so there is exactly one instance of 2 in the list, print this information)
-Them move onto the next prime 7 and you will see that D divides by 7 zero times (so there are no 3's present in the list, print this information)
Continue doing this until the prime representing P(n) is reached. This entire process will require two passes through the data set, the initial construction of the digest D and the one more to print out the results. This solution will work so long as a number large enough to contain P(1)*(#occurrences of 1) ... * P(n) * P(1)*(#occurrences of n) can be allocated.
Simple solution in java:
public class Counter {
public static void countOccurances(int[] input){
System.out.println(input);
int max = input.length;
int[] posArr = new int[max+1];
for(int i=0; i<max; i++){
int num = input[i];
posArr[num] = posArr[num]+1;
}
for(int i=1; i<=max; i++){
if(posArr[i] < 1){
System.out.println(i+" is missing");
} else {
System.out.println(i+" is appearing "+posArr[i]+" times");
}
}
}
public static void main(String[] args) {
int[] input1 = {1,5,3,7,4,5,6,8};
countOccurances(input1);
int[] input2 = {1,5,3,7,4,5,6,8,9,5,4,10,4};
countOccurances(input2);
}
}
public static void elements(int[] A) {
for (int i = 0; i < A.length; i++) {
while (A[i] != i + 1) {
int temp = A[A[i] - 1];
if (temp == A[i]) {
break;
}
A[A[i] - 1] = A[i];
A[i] = temp;
}
}
System.out.println("Elements that don't exist in array A");
for (int i = 0; i < A.length; i++) {
if (A[i] != i + 1) {
System.out.println(i + 1);
} else {
A[i] = -1;
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
A[A[i] - 1]--;
}
}
System.out.println("Elements that exist in array A and their frequency");
for (int i = 0; i < A.length; i++) {
if (A[i] < 0) {
System.out.println((i + 1) + ": " + (-A[i]));
}
}
}
public static void main(String[] args) {
// TODO code application logic here
int[] A = {9,9,9,9,9,9,9,8,7,9,10};
elements(A);
}
Result:
Elements that don't exist in array A
1
2
3
4
5
6
11
Elements that exist in array A and their frequency
7: 1
8: 1
9: 8
10: 1
I suspect this is impossible under strict definitions of O(1) space. There exist no sorting algorithms with worst-case parameters of O(n) time and O(1) space. Any solution to this problem would allow you to do a linear time, constant space counting sort where the range_of_numbers <= length of array. If you could do that, you should publish a paper.
As noted in comments I've made on other answers (e.g. storing negative numbers or a number larger than len(N) in an element), all solutions thus far provided stretch the definition of O(1) space and in the general sense are O(N).
You have the same issue everyone else does. You are using numbers outside the domain, specifically negative numbers. Your algorithm requires an additional bit per element to store a sign bit.. N bits in total, meaning O(N) space complexity.
My solution changes the input array. I did not use an extra array, so the amount of extra memory is constant.
@xuzheng:
To show that your algorithm (as a general algorithm) is O(n) space, let's use a simple counter-example. Java's a little weird in that you don't have unsigned types, so let's use C.
void elements(unsigned char * A) {
...
//Issue #1
A[i] = -1;
//Issue #2
A[A[i] - 1]--;
Let's say A has 255 elements; the domain for input numbers is 1-255. The issue #X lines both are problematic. You are going to underflow, as a negative is outside the domain. The subtraction creates a large positive number indistinguishable from your original input data -- causing the algorithm to fail.
This isn't so obvious if you use Java, as all integers in Java are signed. In this particular language, you just happen to have that an extra bit of unused space in each element in the input array which you can use for your purposes. But this is not true in general (as in the C example given above).
You cannot rely on such the input array being inefficiently stored. If it is efficiently stored (e.g. as an unsigned type), you must allocate N new bits to store that "count or input" flag.. making it an O(N) space algorithm.
How about that idea. If you encounter element on position i and it is not equal to i. Than you have to place value a[i] to position with index a[i] e.g a[a[i]] = a[i]. But if this position is already captured with right element you go forward. It is preproccessing made by O(n). The next cycle you just scan array, and if value of element with index i isn't equal to i it means that we haven't element with value i. Here is code of my solution.
public static void checkMissedElements(int[] array){
for (int i = 0;i < array.length;i++){
while(array[i] != i && array[array[i]] != array[i]){
int buf = array[i];
array[i] = array[array[i]];
array[buf] = buf;
}
}
for (int i = 0;i < array.length;i++){
if (array[i] != i){
System.out.println("Element " + i + " is missed");
}
}
}
Your solution is the same as my solution. I think it works well, but you forgot to print out the number of occurrences of the elements that do appear in the input array.
This is solution on sorted array. Very basic but it is working fine.
#include<stdio.h>
#include<conio.h>
main()
{
int arr[]={1,1,1,3,4,5,7,8,11,12,17,23,24,24,24,24,24};
int missing_num;
int num=0;
int count;
int flag=0;
int size=sizeof(arr)/sizeof(arr[0]);
for(int i=size-1;i>0;i--)
{
int k=size-1;
int num=arr[k];
//printf("arr[i]=[%d] num=[%d]\n",arr[k-1],num);
count=1;
if(arr[k-1]==num)
{
printf("The number [%d] is repeated.\n", arr[k-1]);
}
else if(arr[k-1]==num-1)
{
}
else if(arr[k-1]<num-1)
{
missing_num=(num-1)-arr[k-1];
//printf("missing numbers [%d]\n",missing_num);
for(int j=num-1;j>(num-1)-(missing_num);j--)
{
printf("The missing number is [%d]\n",j);
}
}
size=size-1;
}
}
This is solution on sorted array. Very basic but it is working fine.
#include<stdio.h>
#include<conio.h>
main()
{
int arr[]={1,1,1,3,4,5,7,8,11,12,17,23,24,24,24,24,24};
int missing_num;
int num=0;
int count;
int flag=0;
int size=sizeof(arr)/sizeof(arr[0]);
for(int i=size-1;i>0;i--)
{
int k=size-1;
int num=arr[k];
//printf("arr[i]=[%d] num=[%d]\n",arr[k-1],num);
count=1;
if(arr[k-1]==num)
{
printf("The number [%d] is repeated.\n", arr[k-1]);
}
else if(arr[k-1]==num-1)
{
}
else if(arr[k-1]<num-1)
{
missing_num=(num-1)-arr[k-1];
//printf("missing numbers [%d]\n",missing_num);
for(int j=num-1;j>(num-1)-(missing_num);j--)
{
printf("The missing number is [%d]\n",j);
}
}
size=size-1;
}
}
My solution in c++ : we use the input array as a container for the counter. Elements i encoutered in the array is associated with a counter at position i-1.
#include <iostream>
#include <vector>
using namespace std;
void printMissing(vector<int> L) {
int j, tmp;
for (int i = 0; i < L.size(); ++i) {
j = L[i];
while (j > 0) {
tmp = L[j - 1];
L[j - 1] = (tmp > 0) ? 0 : (tmp - 1);
j = (tmp != j) ? tmp : -1;
}
}
for (int i = 0; i < L.size(); ++i) {
cout << (i + 1) << ": ";
cout << ((L[i] > 0) ? 0 : (- L[i] + 1)) << endl;
}
}
int main(int argc, char **argv) {
int ar[] = {1, 5, 3, 3, 2};
vector<int> L(ar, ar + sizeof(ar) / sizeof(int));
printMissing(L);
return 0;
}
/*
Outputs :
1: 1
2: 1
3: 2
4: 0
5: 2
*/
First, we need the array to store the count since space is limited at O(1). So we need A[i] to store the count for number i. But how can we distinguish the number itself and the count? We can use negative numbers to store the count. The O(1) space is a pointer to the array for the current number. The solution is raw, with O(1) space and O(n) time, without any sorting.
E.g.
[4, 3, 2, 3, 5] => [3,3,2,-1,5] => [2,3,-1,-1,5] => [3, -1, -1, -1,5] => [0, -1, -2 ,-1, 5] => [0,-1, -2, -1, -1]
a = [2,3,4,3,5]
n = len(a)
pointer = 0
while pointer < n:
if a[pointer] <= 0:
pointer = pointer + 1
else:
if a[a[pointer]-1]>0:
if a[pointer]-1 == pointer:
a[pointer] = -1
pointer = pointer + 1
else:
t = a[a[pointer]-1]
a[a[pointer]-1] = -1
a[pointer] = t
else:
a[a[pointer]-1] = a[a[pointer]-1] -1
a[pointer] = 0
pointer = pointer + 1
for i, num in enumerate(a):
if num==0:
print i + 1
for i, num in enumerate(a):
if num<0:
print i + 1, abs(num)
my solution:
{{
void prep(int arr, int n)
{
for(int i=0; i<n; ++i) {
int v = arr[i];
if (!v || v > n) continue;
arr[i] = 0;
while(v && v<=n) {
if (arr[v-1] > n || arr[v-1] == 0) {
arr[v-1] += v;
break;
} else {
int v1 = arr[v-1];
arr[v-1] = n+v;
v = v1;
}
}
}
}
void print_dup(int arr[], int n)
{
for(int i=0; i<n; ++i) {
if(arr[i]==0 || (arr[i]-n)/(i+1) == 1) continue;
printf("pos[%d] dup times: %d\n", i+1, (arr[i]-n)/(i+1));
}
}
void print_missing(int arr[], int n)
{
for (int i=0; i<n; ++i) {
if (!arr[i])
printf("%d missing\n", i+1);
}
}
}}
int prep(int arr[], int n)
{
for (int i=0; i<n; ++i) {
int v = arr[i];
if (!v || v > n) continue;
arr[i] = 0;
while(v && v < n+1) {
if (arr[v-1] > n || arr[v-1] == 0) {
arr[v-1] += v;
break;
} else {
int v1 = arr[v-1];
arr[v-1] = n+v;
v = v1;
}
}
}
}
void print_dup(int arr[], int n)
{
for(int i=0; i<n; ++i) {
if(arr[i]==0 || (arr[i]-n)/(i+1) == 1) continue;
printf("pos[%d] dup times: %d\n", i+1, (arr[i]-n)/(i+1));
}
}
print missing is simple, check arr[i] == 0.
{{
public static void findMissingNumbers(int array[])
{
for(int i=0;i<array.length;++i)
{
if(array[i]!=(i+1) && array[array[i]-1]!=array[i])
{
int temp = array[array[i]-1];
array[array[i]-1]=array[i];
array[i]=temp;
--i;
}
}
for(int i=0;i<array.length;++i)
{
if(array[i]!= i+1 )
{
System.out.println("the number is not present " + (i+1) );
if(i==0)
array[i] = ( i + 2);
else
{
array[array[i]-1] = array[array[i]-1] + array[i];
}
}
}
for(int i=0;i<array.length;++i)
{
if(array[i]/(i+1)>=2)
{
System.out.println("The number" + (i+1) + " repeated for " + array[i]/(i+1) );
}
}
}
}}
public static void main(String[] args) {
int arr[] = { 6, 4, 1, 4, 3, 2, 5, 2, 1 };
freq(9, arr);
}
public static void freq(int n, int[] array) {
int[] count = new int[n+1];
for (int i = 0; i < array.length; i++) {
count[array[i]]++;
}
int j=1;;
for (int i = 1; i < count.length; i++) {
System.out.println("number" + i + "frequency" + count[i]);
j++;
}
}
package code_exercise;
public class CodeExercise5 {
public static void main(String[] args) {
// swap(a1, b1);
int a[] = {10, 2, 2, 5, 3,
4, 9, 10, 9, 10, 5};
solve(a);
}
public static void swap(Integer a, Integer b) {
a ^= b;
b ^= a;
a ^= b;
}
private static void solve(int [] a) {
int tval = 0;
// determine max val
for (int i = 0; i < a.length; ) {
if (a[i] > 0) {
tval = a[a[i] - 1];
if (tval > 0) {
if (a[i] - 1 == i) {
a[a[i] - 1] = -1;
} else {
a[a[i] - 1] = -1;
a[i] = tval;
}
} else if (tval <= 0) {
a[a[i] - 1] += -1;
a[i] = 0;
i++;
}
} else {
i++;
}
}
for (int i = 0; i < a.length; i++) {
System.out.println("NUM:" + (i+1) + ", OCC:" + Math.abs(a[i]));
}
}
}
The O(1) space requirement implies that we must re-use the given array for storing counts.
Since the range of element values is limited to the length of the array, we can simply store the count of each element at the array index of (element value -1). As we progress through the array, we can distinguish between element counts and element values by keeping the counts negative and the values as they are (between 1 and n).
function account(arr) {
for (var i=0; i< arr.length; i++) {
if (arr[i] <= 0) continue;
else while (arr[i] > 0) {
if (arr[i] -1 == i)
arr[i] = -1;
else if (arr[arr[i] -1] <= 0) {
arr[arr[i] -1] -= 1;
arr[i] = 0
}
else {
temp = arr[arr[i] -1];
arr[arr[i] -1] = -1;
arr[i] = temp;
}
}
}
// TODO: print counts
}
using System;
public class Test
{
public static void Main()
{
int[] arr = { 5, 1, 3, 5, 1 };
CountNumbers(arr);
for(int i = 0; i < arr.Length; i++)
{
var count = -1 * arr[i];
Console.WriteLine("Element {0} appears {1} times", i+1, count);
}
}
private static void CountNumbers(int[] arr)
{
for(int i = 0; i < arr.Length; i++)
{
var elem = arr[i];
if (elem > 0)
{
var value = elem;
arr[i] = 0;
InsertElem(arr, value);
}
}
}
private static void InsertElem(int[] arr, int elem)
{
var aux = arr[elem-1];
if (aux > 0)
{
arr[elem-1] = -1;
InsertElem(arr, aux);
}
else
{
arr[elem-1] += -1;
}
}
}
The worst case would be when you have to call InsertElem for every number, this will take an extra n steps.
So it will take n to print + n to run through all elements + n in the worst case when we have to recurs through all elements, so it is O(3*n) which is O(n). Since it's inline, it's O(1) space.
def print_frequency(array):
n = len(array)
for i in range(1, n+1):
k = array[i-1] % (n+1)
array[k-1] += (n+1)
for i in range(1, n+1):
print(i, array[i-1] // (n+1))
a = [3, 1, 3, 2, 6, 7, 3, 8, 10, 10]
print_frequency(a)
The best solution has already been provided by Venkatesh. The above is a python implementation of the same. Key thing to note is that we know the range of the numbers i.e 1-n and the size of the array i.e. n. So we can use the array as some kinda makeshift hash table.
We iterate through the array and we add (n+1) to the array[item mod n+1]. Basically every time we encounter the number k we add (n+1) to the kth item of the array.
We take the mod to get the original value of k as k would have been modified as result of the above additions.
In the second iteration all we have to do is to divide each item of the array by (n+1) to get the frequency of the index
Clever, but I don't think the problem is fully defined. The size of the array is not specified as size N. If you were guaranteed values 1-n and an array specified as size n, then your solution would work. Still pretty clever.
It says that given an array of n integers.
Below is the output generated for array arr[] = {6,4,1,4,3,2,5,2,1};
Element = 1 Frequency = 2
Element = 2 Frequency = 2
Element = 3 Frequency = 1
Element = 4 Frequency = 2
Element = 5 Frequency = 1
Element = 6 Frequency = 1
Element = 7 Frequency = 0
Element = 8 Frequency = 0
Element = 9 Frequency = 0
#include<iostream>
using namespace std;
int main()
{
int a[]={3,3,2,1,1};
cout<<"repeated:"<<endl;
for(int i=0;i<5;i++)
{
if((a[abs(a[i])-1]) > 0)
{
a[abs(a[i])-1]=- a[abs(a[i])-1];
}
else
{
cout<<a[i]<<endl;
}
}
cout<<"missing:"<<endl;
for(int i=0;i<5;i++)
{
if(a[i]>0)
cout<<i+1<<endl;
}
getchar();
return 0;
}
let's consider -
4,3,5,1,2,9,4,2,7,10
n = 10
start iterating the array like count sort with a slight modification that we add n^i to i-th array entry for each occurrence of i in th array- since n is 10 we will add 10^i
so 4,3,5,1,2,9,4,2,7,10 will end up like -
4+10^1, 3+10^2+10^2, 5+10^3, 1+10^4+10^4, 2+10^5, 9+0, 4+10^7, 2+0, 7+10^9, 10+10^10
Now iterate the array from beginning dividing each entry by n^i, result will be the corresponding counts for integer i (0 will be for absent integers) -
for index 1 - 4+10^1 mod 10 ^1 = 1
for index 2 - 3+10^2+10^2 mod 10^2 = 2
and so on
resultant array is -
1,2,1,2,1,0,1,0,1,1
1 is present once, 2 is present twice ...6 and 8 are missing
void process(unsigned long long *arr, int n) {
unsigned long long cur, x, y;
int i;
for (i = 1; i <= n; i++) {
cur = *(arr + i -1);
y = cur % (unsigned long long)pow(n,i);
x = pow(n,y);
*(arr + y - 1) += x;
}
for (i = 1; i <= n; i++) {
cur = *(arr + i - 1);
*(arr + i - 1) = cur/pow(n,i);
}
for (i = 1; i <=n ; i++) {
printf("%d repeated %llu times\n", i, *(arr+i-1));
}
}
I used the following algo in my code which the interviewer accepted at once ....
1.Start traversing the array . Let there be n elements and array be a[].
2.if a[a[i]-1] > 0 and a[i] >0 , then make a[a[i]-1] negative . This will help to keep track of absent nodes .
3.else if a[i]>0 and a[a[i]-1] <0 , subtract n from a[a[i]-1] . This will help to keep the count of multiple visited nodes.
4. else if a[i]<0 and a[i] >= -n , subtract n from a[-a[i]-1].
5. else if a[i] < -n , find subtract n from a[ (-a[i])%n-1 ] .
6. Now traverse the list and if any a[idx] is positive , that means number idx+1 isn't present in the array .
7. If a[idx] is between -n to -1 , that means idx+1 has occured only one time .
8. else if a[idx] is less than -n , that means idx+1 has occured ( int ) ( -a[idx]/n ) + 1 times .
P.S. I wasn't selected for the next round after telling this answer within 5 minutes .
I had to clear 1 written 3 tech and 1 HR in total but I was ousted after the 2nd round of Interviews in which this question was asked .
Use hash map.
it takes o(n) time and o(1) space.
Correct me if i made mistake
public static frequency(int arr[])
{
map <Integer> fmap = new Hashmap<Integer>;
for (int a : arr)
{
int freq= fmap.get(a);
if (freq!=null)
{
freq++;
m.put(freq);
}
else // this is the first time we are encountering the number
{
freq=1;
m.put(freq);
}
}
}
cheers Krishna
A very simple approach :
printAllAbsentNums(int[] a)
{
for(int i=0;i<a.length;i++)
{
temp=a[i];
a[i]=a[temp];
a[temp]=temp;
temp=a[i];
}
for(int i=0;i<a.length;i++)
{
if(a[i]!=i)
System.out.print(i);
}
}
The solution you're suggesting is O(n) space due to aux array and the question states that there is O(1) solution.
First Let's see what all approaches we can take and then we check if it fits our requirement.
- varun July 15, 20131. Brute Force: Select an element from 1 to N and check it frequency of occurrence. But this will be O(n2) and not O(n) .
2. XOR : but this technique won't work as question mentions an element can be repeated multiple times. so if element repeats 2 times or 4 times each time result of xor will be 0 so we cannot get the frequency of occurrences.
3. HashMap : We can create a HashMap in O(n) key will be elements and value will be their frequency of occurrence. But since we have to do it in O(1) space we cannot take this approach.
So we cannot opt for any of the above 3 approach. We have to check for some 4th approach.
Since we have range of numbers given to us we have to think in those lines.
Array Index is from 0 to N-1 and range is from 1 to N.
Can't we use the array as hash itself?
where array "Index-1" represents the key (element) and value stored at index will represent the "frequency of occurrence".
But how will we take care that an element present at any index is not overwritten as this can cause problem?
We can sort the array in that case value present at index i is I+1 itself.
What is the complexity of sorting the array?
O(nlogn) if we opt for heap/merge/quick sort.
But since the range of element is given to us we can sort it in O(n).