Amazon Interview Question Software Engineer / Developers
Team: Instant Video
Country: United States
Interview Type: Phone Interview
One thing missing from delete. Update A[B[C-1]] to A[x] (use the old values before the swap).
@ben.wxc: "One thing missing from delete. Update A[B[C-1]] to A[x]". No, he's right. That is, in fact, necessary.
@ben:
The anonymous who wrote the answer, is same as the anonymous who wrote the comment.
I know this because I wrote it :-)
Since editing is not allowed, you miss something and it becomes a comment.
Why can't we use just one array say A of size 1000.
initialize with -1 and do all operations like insert, delete or search on it. Why do we need other arrays? Am I missing something in this question?
We can use one array A of size 1000 along with a counter C.
With the help of the counter we can generate random numbers as explained above. I don't understand why we use two arrays.One array only stores index, is it necessary.
Insertion: A[x]=x;
Similarly other operations
How will yo find randon number only using counter and the Array A?
You can't find random number, we have to use two arrays or Hash map.
The problem is that if you only use one array and you use it as a bitset, since the numbers are not necessarily inserted in order, you will have gaps. Because of that, you won't be able to implement an O(1) algo to choose a random number.
Why do you have to keep a seperate array for generating the random number? If they are unique numbers from 1-1000 then each number has a probability of 1/1000 to be randomly selected. So when you are inserting the number use a random number generator with the probability (1/total numbers inserted till now) to determine if you need to store the currently generated number or not. I think an extra array is an overkill for this problem..
Why do you have to keep a seperate array for generating the random number? If they are unique numbers from 1-1000 then each number has a probability of 1/1000 to be randomly selected. So when you are inserting the number use a random number generator with the probability (1/total numbers inserted till now) to determine if you need to store the currently generated number or not. I think an extra array is an overkill for this problem..
Why do you have to keep a seperate array for generating the random number? If they are unique numbers from 1-1000 then each number has a probability of 1/1000 to be randomly selected. So when you are inserting the number use a random number generator with the probability (1/total numbers inserted till now) to determine if you need to store the currently generated number or not. I think an extra array is an overkill for this problem..
Why do you have to keep a seperate array for generating the random number? If they are unique numbers from 1-1000 then each number has a probability of 1/1000 to be randomly selected. So when you are inserting the number use a random number generator with the probability (1/total numbers inserted till now) to determine if you need to store the currently generated number or not. I think an extra array is an overkill for this problem..
Why do you have to keep a seperate array for generating the random number? If they are unique numbers from 1-1000 then each number has a probability of 1/1000 to be randomly selected. So when you are inserting the number use a random number generator with the probability (1/total numbers inserted till now) to determine if you need to store the currently generated number or not. I think an extra array is an overkill for this problem..
Use a variation on the Briggs-Torczon sparse set data structure. Google it if you're unfamiliar with it. Then everything takes constant time, including (rather interestingly) initialization.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
unsigned int forward[1000];
int backward[1000];
int n;
int contains(int x)
{
assert(0 <= x && x < 1000);
unsigned int i = forward[x];
return i < n && backward[i] == x;
}
void insert(int x)
{
assert(0 <= x && x < 1000);
if (!contains(x)) {
unsigned int i = n++;
forward[x] = i;
backward[i] = x;
}
}
void delete(int x)
{
assert(0 <= x && x < 1000);
unsigned int i = forward[x];
if (i < n && backward[i] == x) {
int y = backward[n-1];
forward[y] = i;
backward[i] = y;
n--;
}
}
int choose()
{
assert(n > 0);
return backward[rand() % n];
}
int main()
{
insert(0);
insert(500);
insert(3);
assert(contains(0));
assert(contains(500));
assert(contains(3));
assert(!contains(4));
assert(!contains(123));
for (int i = 0; i < 10; i++)
printf("%d ", choose());
printf("\n");
delete(3);
insert(999);
for (int i = 0; i < 10; i++)
printf("%d ", choose());
printf("\n");
delete(500);
delete(0);
for (int i = 0; i < 10; i++)
printf("%d ", choose());
printf("\n");
return 0;
}
I like your solution. Also, you could re-use the contains() method in the delete() method.
I don't understand how delete works if the exsisting data is 3,4,5 and I have to delete 4
Create a hash table of size 1000. Map each input element to the key value of the hash table. i.e use direct hashing.
All operations can be done in 0(1) time.
That's right - random number can be generated like so - hashtable.get((int)(Math.random()*hashtable.size()));
we do not need to have an array of 1000 integers. We can do this with an array of just 32 integers. Each ON bit in arr[i] will represent a number between i*32 to (i+1)*32 - 1.
To insert a number x, get the block number (x/32) and then the bit pos in that block (x%32) and set that bit 1.
To delete a number x, get the block number (x/32) and then the bit pos in that block (x%32) and set that bit 0.
To search for a number x, get the block number (x/32) and then the bit pos in that block (x%32) and see if that bit is 1.
an int is 4 bytes or 32 bits. So, each bit can represent a number between 1 to 31. Since the range of the numbers is from 1 to 1000, we will need an array of 32 ints (as 32 * 32 = 1024)
Initially I will initialize all the ints in the array to 0.
then as and when a number comes for insertion, use the above logic to set the corresponding bit.
an int is 4 bytes or 32 bits. So, each bit can represent a number between 1 to 31. Since the range of the numbers is from 1 to 1000, we will need an array of 32 ints (as 32 * 32 = 1024)
Initially I will initialize all the ints in the array to 0.
then as and when a number comes for insertion, use the above logic to set the corresponding bit.
we do not need to have an array of 1000 integers. We can do this with an array of just 32 integers. Each ON bit in arr[i] will represent a number between i*32 to (i+1)*32 - 1.
To insert a number x, get the block number (x/32) and then the bit pos in that block (x%32) and set that bit 1.
To delete a number x, get the block number (x/32) and then the bit pos in that block (x%32) and set that bit 0.
To search for a number x, get the block number (x/32) and then the bit pos in that block (x%32) and see if that bit is 1.
My solution is similar to the one above that uses multiple arrays. Basically I use an array to store all the current elements. I also have a HashMap that stores the position of each element. The only tricky part is when removing an element, we need to swap it with the last element in the array so that the array has no gap in it. The HashMap supports the insert/delete/search operations in O(1) while the array supports the random operation in O(1).
class EfficientOperations {
static int count = 0;
static HashMap<Integer, Integer> positions = new HashMap<Integer, Integer>();
static int[] elements = new int[1000];
static void insert(int n) {
if(contains(n))
return;
positions.put(n, count);
elements[count++] = n;
}
static void delete(int n) {
if(!contains(n))
return;
int pos = positions.get(n);
elements[pos] = elements[count-1];
count--;
positions.remove(n);
positions.put(elements[pos], pos);
}
static boolean contains(int n) {
return positions.containsKey(n);
}
static Integer random() {
if(count == 0)
return null;
int pos = (int)Math.random()*count;
return elements[pos];
}
}
Use boolean array of size 1000. Then all the operations are straight forward.
Initialize the elements in the array to zero
Insertions(Element i): a[i]=1;
Delelet(Element i): a[i]=0;
Search(Element i): a[i] == 1;
getany random nubmber; if(a[i]==1) return i;
It works for first 3 but not for "Get any random number".
"Get any random number" means that the index can be can be a random number between 1 and 1000 so you could potentially get a deleted/empty (a[i]==0) node.
-1. They tough part is getting the random generation to work.
I don't want to register etc just for the sake of downvoting.
Hi Tanvi Reddy,
Can you be a bit more elaborate on this? What are you trying to achieve by using a boolean array ?
Top 3 operations could be done using the mentioned algo,
For random no. generation we could store the numbers in an array and used pseudo random number generator to give random numbers.
n = number of elements in set
Array[1-n]
f(0) = arbitrary chosen value
f(x)= a*f(x-1) +b;
return Array[(f(x)%n)+1]
We can use hashing with chaining(linked-list).
For this we have to choose an array of size M = 1113 (larger than the number of keys).
We choose a large array so that average number of keys per linked-list remains almost ~1. Let’s say no. is 997, so 997 % 1113 = 997.
997 will be my array index, Key = 997, Value = 997.
Going by this way out search hit, search miss, insert, delete, and finding any random number will be executed in constant-time.
We have to choose the load-factor very wisely such that list sizes are small and number of comparisons if needed be (no. of keys in the arrays / size of the array)
This approach can't work in general. If the number of elements in the set is prime, for example, it is impossible to divide the elements evenly between buckets, so that each bucket has the same size. That manifests in a non-uniform probability distribution, where elements in larger buckets are less likely to be picked.
BTW, just to show that the issue isn't unique to primes, consider what happens when n is the square of a prime, p^2. Then the only even division of the set (which we need for uniform random generation) has p buckets with p elements each. But then lookup takes O(p) = O(sqrt(n)) time! You're going to have issues like that whenever n doesn't have small prime factors (small relative to n).
Binary search trees are not constant time.
Constant time is O(1), it takes the same time regardless of N, the number of elements.
Use two arrays A and B. Also maintain a count C of how many distinct elements have been inserted.
- Anonymous February 10, 2012Initially A and B are initialized with -1, and C is set to 0.
Each element of array A contains index into element of Array B.
On an insert of element x, if A[x] is -1, then we set B[C] to x, set A[x] to C and increment C.
On a search we check if A[x] is -1 or not.
On a delete we swap B[A[x]] and B[C-1], decrement C, and set A[x] to -1.
On a random number required, we generate a random number r from 0 to C-1, and return B[r].
All operations are O(1) (assuming random number generator is O(1)).