Google Interview Question Software Engineer / Developers
Country: -
Interview Type: In-Person
My Algorithm:-
1. Create a HashSet<Number>
2. Create a minheap of first hundred values
3.For getNumber() method always looks into this min heap and removes and returns the first number.
3.1 Once heap is empty, reload it with next 100 values and crosscheck with the set(assigned) values
3.2 insert the number into hash set and return.
4. For RequestNumber method, check if given number is in the hash set.
4.1.if it is there, return false
4.2 else
insert the number into hash set and return true;
Since there are 10^10 possible numbers, we can use a bit set to encode whether or not each of the numbers are assigned using 10GB/8~1.25 GB. This ensures that requestNumber(Number number) can run in O(1) time if we are allowed to use this much memory for a single machine. If getNumber() is permitted to run in O(N) time then we can iterate over the bitset to find the next unassigned number.
To make getNumber() run in amortized O(1) time while maintaining the efficiency of the requestNumber(Number number) operation, we can maintain a hash set with a subset of the unassigned numbers and limit its size to <= 10^8 numbers so that it can fit in memory. When the size of the hash set becomes zero or at another convenient time, a linear scan can be performed on the bit set that adds unassigned numbers to the hash set. The linear scan would require O(N) time but would be done rarely, hence the amortized nature of the getNumber() operation. We can count the number of assigned numbers or store a boolean that equals true if unassigned numbers are not available so we only perform this linear scan when there are numbers to add.
Using the hash set would allow insertion and removal of unassigned numbers to be done in O(1) time so that the requestNumber(Number number) operation can keep the hash table consistent without sacrificing time efficiency, and using the bitset would allow getNumber() to keep the available numbers consistent when requestNumber(Number number) is called.
I forgot to clarify how the hash set would remove numbers in O(1) time. Doing this requires something similar to Java's LinkedHashSet which maintains a doubly linked list through its entries.
// Solution with segment trees.
//
// TIME: O(log(N)) for both getNumber() and requestNumber(), since N
// is bound to 10^10 in this case, each lookup is done in
// exactly 34 steps
// MEMORY: grows towards O(N) maximum as numbers are added
// Basic idea: traverse the segment tree from the root to the leaf at each
// getNumber() or requestNumber() invocation, creating child nodes as needed.
// When number is successfully chosen (wasn't chosen before), decrease the
// remain counter of the each node in the chain from the leaf to the parrent
// by 1.
//
// [ lb=0 : ub=7 ]
// [ remain = 8 ]
// / \
// / \
// [ lb=0 : ub=3 ] [ lb=4 : ub=7 ]
// [ remain = 4 ] [ remain = 4 ]
//
#include <iostream>
#include <cassert>
class SegmentTree {
private:
struct Node {
long long lb;
long long ub;
long long remain;
Node *parent;
Node *left;
Node *right;
Node(long long lb_i, long long ub_i, Node *parent_i): lb(lb_i),
ub(ub_i), remain(ub_i-lb_i+1), parent(parent_i), left(nullptr),
right(nullptr) { }
};
Node *root;
int MSB;
public:
SegmentTree(long long lb_i, long long ub_i) {
MSB = 0;
while (ub_i) {
++MSB;
ub_i >>= 1;
}
this->root = new Node(lb_i, (1LL << MSB)-1, nullptr);
}
long long getNumber() {
if (this->root->remain > 0) {
Node *cn = this->root;
while (true) {
cn->remain -= 1;
if (cn->lb == cn->ub) {
return cn->lb;
}
long long mid = cn->lb + (cn->ub - cn->lb)/2LL;
if (!cn->left) {
cn->left = new Node(cn->lb, mid, cn);
cn = cn->left;
}
else if (cn->left->remain > 0) {
cn = cn->left;
}
else if (!cn->right) {
cn->right = new Node(mid+1, cn->ub, cn);
cn = cn->right;
}
else {
assert(cn->right->remain > 0);
cn = cn->right;
}
}
}
return -1;
}
bool requestNumber(long long num) {
if (this->root->remain > 0) {
Node *cn = root;
while (true) {
if (cn->lb == cn->ub) {
if (cn->remain > 0) {
while (cn) {
cn->remain -= 1;
cn = cn->parent;
}
return true;
} else {
break;
}
}
long long mid = cn->lb + (cn->ub - cn->lb)/2LL;
if (num <= mid) {
if (!cn->left) {
cn->left = new Node(cn->lb, mid, cn);
}
cn = cn->left;
} else {
if(!cn->right) {
cn->right = new Node(mid+1, cn->ub, cn);
}
cn = cn->right;
}
}
}
return false;
}
};
int main() {
SegmentTree store(0, (long long) (1e10) - 1);
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "reqNum(0) > " << (store.requestNumber(0)?"true":"false");
std::cout << std::endl;
std::cout << "reqnum(1) > " << (store.requestNumber(1)?"true":"false");
std::cout << std::endl;
std::cout << "reqNum(1) > " << (store.requestNumber(1)?"true":"false");
std::cout << std::endl;
std::cout << "reqNum(3) > " << (store.requestNumber(3)?"true":"false");
std::cout << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
std::cout << "getNum > " << store.getNumber() << std::endl;
}
we can achieve O(logN) time complexity for getNumber() and requestNumber(Number) using BST for storing unassigned numbers and Set for assigned numbers.
getNumber(){
number = BST.remove
Set.add(number)
}
requestNumber(number){
if(!Set.contains(number)){
BST.remove(number)
Set.add(number)
return true;
} else {
return false;
}
}
The numer of digits can be 10 at max and each digit can take 10 values at max. If we have an array of size 10 each representing one digit and the contents of each array is a sorted arry or a bit set with 10 bits each representing one number, then initially all the arrays will be empty. When get number is requested, from the array traverse every digit and see the first empty bit and return that value. For requestnumber check if the corresponding bits in every digit is free and return success. This way memory requirement will be at max 100 digits. Time complexity is O(N) where N is the number of digits.
Use a linked list (queue) of nodes where each node holds a range (two integers: left, right) of unassigned numbers. Initially, this list will contain one node with left = 0 and right = 9999999999. This borrows from the concept of tracking memory allocation in operating systems and uses an amount of memory that generally does not scale up proportionally to the amount of memory to track. It's limitation is the possibility of fragmentation after lots of assigning/unassigning that don't result in coalescing nodes, but this can be avoided by being smart about choosing to assign in a manner that nodes don't get fragmented.
getNumber: get left range of first node in list. If left == right, remove this node from the list. Otherwise, set left = left + 1.
requestNumber: traverse list. Assuming current node is c, while n > c.right c = c.next. Eventually you will hit a node where c.left > n (n has already been assigned) so return false, or n >= c.left and <= c.right (n has not been assigned).
In the latter case, there are 2 scenarios:
a) n is at the edge of the node's range:
If n == left, set c.left++
If n == right, set c.right--
b) n is not in the edge of the range:
1. Create a new node with range [n+1, right]
2. Place new node between current node and it's next node
3. Update current node's range to become [left, n-1]
Alternatively, could also track unassigned ranges using an n-ary tree, which increases lookup of requestNumber() from O(n) to O(lgn). This datastructure somewhat borrows from the concept of how an OS tracks the filesystem with a hierarchy of i-nodes.
Use a linked list (queue) of nodes where each node holds a range (two integers: left, right) of unassigned numbers. Initially, this list will contain one node with left = 0 and right = 9999999999. This borrows from the concept of tracking memory allocation in operating systems and uses an amount of memory that generally does not scale up proportionally to the amount of memory to track. It's limitation is the possibility of fragmentation after lots of assigning/unassigning that don't result in coalescing nodes, but this can be avoided by being smart about choosing to assign in a manner that nodes don't get fragmented.
getNumber: get left range of first node in list. If left == right, remove this node from the list. Otherwise, set left = left + 1.
requestNumber: traverse list. Assuming current node is c, while n > c.right c = c.next. Eventually you will hit a node where c.left > n (n has already been assigned) so return false, or n >= c.left and <= c.right (n has not been assigned).
In the latter case, there are 2 scenarios:
a) n is at the edge of the node's range:
If n == left, set c.left++
If n == right, set c.right--
b) n is not in the edge of the range:
1. Create a new node with range [n+1, right]
2. Place new node between current node and it's next node
3. Update current node's range to become [left, n-1]
Alternatively, could also track unassigned ranges using an n-ary tree, which increases lookup of requestNumber() from O(n) to O(lgn). This datastructure somewhat borrows from the concept of how an OS tracks the filesystem with a hierarchy of i-nodes.
We have two kinds of allocation requests: requests for specific numbers ("custom request"), and requests for arbitrary numbers ("generic request"). We also have a need to be able to verify whether a given number is used or not. We can fulfill all of these operations in O(1) expected amortized time.
Create a hash table that will store all of the numbers allocated through custom requests. Additionally, store a counter, nextGenericNumber, that will start at 0. This counter will represent the next number that will be allocated for a generic request -- all lower numbers will have already been allocated.
When we receive a custom request for a requestedNumber, we check that requestedNumber is absent in the hash table, and also that nextGenericNumber <= requestedNumber. If so, we allocate the number, add it to the hash table, and return true. If not, we return false since the number has already been allocated either for a custom request or a generic request.
When we receive a generic request, we check whether nextGenericNumber is absent from the hash table. If yes, we return nextGenericNumber and increment it (for the next time this operation is done). If not, we keep incrementing nextGenericNumber and checking whether it's in the hash table. This is O(1) expected amortized time because a failed check and the need to try another lookup can occur only once for every number that was inserted in the hash table. We may add a small optimization to reduce the hash table's space usage: remove from the hash table any entries that become covered by nextGenericNumber.
Another approach
---------------
Other approaches are possible. For example, we could store all the allocated numbers (whether allocated through custom or generic requests) in a hash table. We serve custom requests simply by checking against the hash table. When serving generic requests, we pick a random number and see if it's taken, and then repeat until we pick a random number that's not taken. As long as there's always a good amount of unused values, this has good expected performance -- O(1) if there exists a fixed K such that K percent of the values are unused at any given time. One advantage is that because the numbers are being allocated randomly, they may interfere less with custom requests. In our previous approach, many custom requests could have gotten declined if everyone was requesting small numbers that would have already been taken by generic requests. The disadvantage is that now we need to store all the allocated numbers in the hash table, not just the ones allocated through custom requests.
Optimization
---------------
One other possible optimization, as suggested by some others on this thread, is that once the data structure is using more than 1.25 GB of space, we can switch to using a bitset. Since there's 10^10 possible numbers, the bitset will use 1.25 GB. That would be, in most cases, a very large amount of space to consume up-front, but it makes sense to switch to it if the hash table gets bigger than that.
divide entire range into samller heap say each of size 10 million ,therefore we will have 1000 heaps,each heap can be divided into smaller heaps.lower most heap should allocate number serially and store the last number allocated number.whenever another request comes it should allot next number.
SELECTION OF HEAPS:
level one heap can be selected by random fxn, similarly after selecting main heap inner heap can be selected randomly. if a heap becomes full then it will make full flag==true.
note: for more randomness have multiple level heaps.
We can use Hashing mechanism here and to resolve collisions choose Open Addressing.
Input size : known before
Range of Values: Known before
All the phone numbers in range from 0 to 9999999999 will not be used. We can consider only 1 million of numbers can be used initially (if want in future we can increase the table size using grow-able array concept)
Initially we can start with a size of 181 array (181 is a prime number, prime number will distributes numbers as uniformly as possible)
We have to define a hash function which converts the following thing.
1. Convert the key (phone number) into the range of array size.
Choose double hashing technique
I will copy the code as reply to this comment
package com.cnu.ds.hash;
public class DoubleHasingHashtable {
public void put(Long phonenumber) {
int hashValue = phonenumber.hashCode();
int probeSize = hashCode(phonenumber);
int index = hashValue % capacity;
if (loadfactor <= (((float) size) / capacity)) {
rehash(getPrime(capacity * 2));
System.out.println("new capacity : " + getPrime(capacity));
}
while (hashtable[index] != null) {
hashValue = hashValue + probeSize;
index = hashValue % capacity;
System.out.println(probeSize);
}
// finds empty place
hashtable[index] = phonenumber;
size++;
}
private int hashCode(Long key) {
return (int) (89L - key % 89L);
}
public boolean contains(Long key) {
int hashValue = key.hashCode();
int probeSize = hashCode(key);
int index = hashValue % capacity;
while (hashtable[index] != null) {
Long entry = hashtable[index];
if (entry.equals(key)) {
return true;
}
hashValue = hashValue + probeSize;
index = hashValue % capacity;
}
return false;
}
public DoubleHasingHashtable(float loadfactor, int capacity) {
this.capacity = capacity;
hashtable = new Long[capacity];
}
private void rehash(int newCapacity) {
Long newHashtable[] = new Long[newCapacity];
for (int i = 0; i < capacity; i++) {
Long entry = hashtable[i];
if (entry != null) {
int hashValue = entry.hashCode();
int index = hashValue % newCapacity;
while (newHashtable[index] != null) {
hashValue = hashValue + 1;
index = hashValue % newCapacity;
}
newHashtable[index] = entry;
}
}
hashtable = newHashtable;
capacity = newCapacity;
}
private int getPrime(int capacity) {
for (int i = capacity + 2; true; i += 2) {
if (isPrime(i)) {
return i;
}
}
}
private boolean isPrime(int num) {
int factors = 1;
for (int i = 2; i < num; i++) {
if (num % i == 0) {
factors++;
}
if (factors > 1) {
return false;
}
}
return true;
}
static class Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
private Long hashtable[];
private int capacity = 11;
private float loadfactor = 0.75f;
private int size;
public DoubleHasingHashtable() {
this(0.75f, 11);
}
}
One pointer to keep track of one empty number which is not assigned. getNumber will just return the number in the the pointer and make sure that there is another number ready when it is needed. Both will take O(1)
Keep HashSet with int as value. requestNumber - O(1) to check if value contains, and O(1) to add if not there. At each requestNumber call, make sure that there is one empty element present in the HashSet which is not assigned. This will take another O(1) in case the item needs to be added in HashSet and modify the current pointer.
#include <iostream>
#include <set>
using namespace std;
struct FreeRange {
long startRange;
long endRange;
bool operator < (FreeRange const &other) const {
return (endRange < other.startRange);
}
};
set<FreeRange> freeRanges;
long getNumber() {
if (freeRanges.empty()) {
return -1;
}
set<FreeRange>::iterator iter = freeRanges.begin();
long num = iter->startRange;
if (num == iter->endRange) {
// This range has been exhausted
freeRanges.erase(iter);
} else {
FreeRange freeRange = *iter;
freeRange.startRange++;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
}
return num;
}
bool requestNumber(long num) {
if (num < 0 || num > 9999999999) {
return false;
}
FreeRange freeRangeToSearchFor = { num, num };
set<FreeRange>::iterator iter = freeRanges.find(freeRangeToSearchFor);
if (iter == freeRanges.end()) {
return false;
}
if (num == iter->startRange) {
if (num == iter->endRange) {
// This range has been exhausted
freeRanges.erase(iter);
} else {
FreeRange freeRange = *iter;
freeRange.startRange++;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
}
} else if (num == iter->endRange) {
FreeRange freeRange = *iter;
freeRange.endRange--;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
} else {
// Need to split the range
FreeRange newFreeRange = { num + 1, iter->endRange };
FreeRange freeRange = *iter;
freeRange.endRange = num - 1;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
freeRanges.insert(newFreeRange);
}
return true;
}
int main() {
FreeRange freeRange = { 0, 9999999999 };
freeRanges.insert(freeRange);
if (requestNumber(11)) {
cout << "Allocated id '11'" << endl;
} else {
cout << "ERROR when allocating id '11'" << endl;
}
long gotId_0 = getNumber();
cout << "Got id '" << gotId_0 << "'" << endl;
if (requestNumber(11)) {
cout << "ERROR got allocated id '11' a second time" << endl;
} else {
cout << "OK, could not allocate id '11' again" << endl;
}
if (requestNumber(2222)) {
cout << "Allocated id '2222'" << endl;
} else {
cout << "ERROR when allocating id '2222'" << endl;
}
if (requestNumber(2)) {
cout << "Allocated id '2'" << endl;
} else {
cout << "ERROR when allocating id '2'" << endl;
}
long gotId_1 = getNumber();
cout << "Got id '" << gotId_1 << "'" << endl;
long gotId_3 = getNumber();
cout << "Got id '" << gotId_3 << "'" << endl;
if (requestNumber(4)) {
cout << "Allocated id '4'" << endl;
} else {
cout << "ERROR when allocating id '4'" << endl;
}
if (requestNumber(10)) {
cout << "Allocated id '10'" << endl;
} else {
cout << "ERROR when allocating id '10'" << endl;
}
if (requestNumber(8)) {
cout << "Allocated id '8'" << endl;
} else {
cout << "ERROR when allocating id '8'" << endl;
}
for (set<FreeRange>::iterator iter = freeRanges.begin();
iter != freeRanges.end();
++iter)
{
cout << iter->startRange << " --> " << iter->endRange << endl;
}
}
#include <iostream>
#include <set>
using namespace std;
struct FreeRange {
long startRange;
long endRange;
bool operator < (FreeRange const &other) const {
return (endRange < other.startRange);
}
};
set<FreeRange> freeRanges;
long getNumber() {
if (freeRanges.empty()) {
return -1;
}
set<FreeRange>::iterator iter = freeRanges.begin();
long num = iter->startRange;
if (num == iter->endRange) {
// This range has been exhausted
freeRanges.erase(iter);
} else {
FreeRange freeRange = *iter;
freeRange.startRange++;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
}
return num;
}
bool requestNumber(long num) {
if (num < 0 || num > 9999999999) {
return false;
}
FreeRange freeRangeToSearchFor = { num, num };
set<FreeRange>::iterator iter = freeRanges.find(freeRangeToSearchFor);
if (iter == freeRanges.end()) {
return false;
}
if (num == iter->startRange) {
if (num == iter->endRange) {
// This range has been exhausted
freeRanges.erase(iter);
} else {
FreeRange freeRange = *iter;
freeRange.startRange++;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
}
} else if (num == iter->endRange) {
FreeRange freeRange = *iter;
freeRange.endRange--;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
} else {
// Need to split the range
FreeRange newFreeRange = { num + 1, iter->endRange };
FreeRange freeRange = *iter;
freeRange.endRange = num - 1;
freeRanges.erase(iter);
freeRanges.insert(freeRange);
freeRanges.insert(newFreeRange);
}
return true;
}
int main() {
FreeRange freeRange = { 0, 9999999999 };
freeRanges.insert(freeRange);
if (requestNumber(11)) {
cout << "Allocated id '11'" << endl;
} else {
cout << "ERROR when allocating id '11'" << endl;
}
long gotId_0 = getNumber();
cout << "Got id '" << gotId_0 << "'" << endl;
if (requestNumber(11)) {
cout << "ERROR got allocated id '11' a second time" << endl;
} else {
cout << "OK, could not allocate id '11' again" << endl;
}
if (requestNumber(2222)) {
cout << "Allocated id '2222'" << endl;
} else {
cout << "ERROR when allocating id '2222'" << endl;
}
if (requestNumber(2)) {
cout << "Allocated id '2'" << endl;
} else {
cout << "ERROR when allocating id '2'" << endl;
}
long gotId_1 = getNumber();
cout << "Got id '" << gotId_1 << "'" << endl;
long gotId_3 = getNumber();
cout << "Got id '" << gotId_3 << "'" << endl;
if (requestNumber(4)) {
cout << "Allocated id '4'" << endl;
} else {
cout << "ERROR when allocating id '4'" << endl;
}
if (requestNumber(10)) {
cout << "Allocated id '10'" << endl;
} else {
cout << "ERROR when allocating id '10'" << endl;
}
if (requestNumber(8)) {
cout << "Allocated id '8'" << endl;
} else {
cout << "ERROR when allocating id '8'" << endl;
}
for (set<FreeRange>::iterator iter = freeRanges.begin();
iter != freeRanges.end();
++iter)
{
cout << iter->startRange << " --> " << iter->endRange << endl;
}
}
hey, you can use trie tree.
we can implement this with boolean matrix of 10x10.
for example the number 0 will be: the first row true
the number 1 will be: 0 0 0 ... 1
reqnum() = will be O(10) = O(1)
getNum() = we will search the matrix if its all full of true then it full , the first false we fild is a number we can assagin. that is O(100) = O(1)
Why not, increment linearly and save the first available "ID", getNumber will return ID, requestNUmber will compare ID whether smaller or larger.
- Anonymous February 02, 2015