## Hewlett Packard Interview Question for Software Engineer / Developers

Team: Networking
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you explain the desired behavior? Does the bit map act as a memory pool for bits?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
++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);
}
{
std::pair<int, int> tmp = get_array_pos(pos);
return bit_array[tmp.first] & (1 << tmp.second);
}
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.