Hewlett Packard Interview Question
Software Engineer / DevelopersTeam: Networking
Country: United States
Interview Type: In-Person
#include <vector>
class BitMap
{
const int N;
vector<int> bit_array;
vector<char> bit_count; // Number of used bits in each 256bits region
public:
BitMap(int num_bytes = 2048) : N(num_bytes * 8), bit_array(num_bytes / sizeof(int), 0)
{
bit_count(N / 256, 0);
}
void clear_bit(int pos)
{
assert(pos >= 0 && pos < N);
assert(bit_count[pos >> 8]);
--bit_count[pos >> 8];
std::pair<int, int> tmp = get_array_pos(pos);
bit_array[tmp.first] &= ~(1 << tmp.second);
}
int get_bit()
{
int chunk = 0;
while (chunk < (N >> 8) && bit_count[chunk] == 255)
++chunk;
assert (chunk < (N >> 8));
++bit_count[chunk];
int res = chunk << 8;
while (read_bit(res) == 1)
++res;
std::pair<int, int> tmp = get_array_pos(res);
bit_array[tmp.first] |= 1 << tmp.second;
return res;
}
private:
int log2(int val) const
{
return 8 * sizeof(int) - cntlz(val) - 1;
}
std::pair<int, int> get_array_pos(int bitpos)
{
int offset = 3 + log2(sizeof(int));
int arr_pos = bitpos >> offset;
int arr_offset = bitpos & (( 1 << offset) - 1);
return make_pair(arr_pos, arr_offset);
}
int read_bit(int pos)
{
std::pair<int, int> tmp = get_array_pos(pos);
return bit_array[tmp.first] & (1 << tmp.second);
}
};
Store bits in array of long ints, 16K / 64 = 256 elements are required.
On Intel CPUs we can use popcnt instruction for fast counting of number of "ones" in each dword.
To speed up get_bit() we could create 128 bytes array were each byte counts the number of bits that are set on each 128 bits interval. I believe we could further develop similar idea and create some counting interval tree, but this seems overkill for just 16K bits.
Could you explain the desired behavior? Does the bit map act as a memory pool for bits?
- JonathanBarOr November 01, 2015