Microsoft Interview Question Software Engineer in Tests
one quick que. In (m*n+7)/8byte where does +7 comes from?besides shouldn't (x*m+y)/8 byte should be (x*m+y*n)/8? sry i think i'm wrong. so please correct me. thx
"and locate the bit to be at: (x*m+y)/8 byte, and (x*m+y)%8 bit, "
Don't you mean "(x*y)/8 byte and (x*y)%8 bit" ?
@handsomeguy
The +7 is just to make sure u allocate enough space.( actually +6 is enough)
suppose we need to allocate 6x7 array.. we require 42 bits
and m*n/8 will give 42/8 = 5 so only that +6.
instead of (x*m+y) it should be ((x-1)*n+y) to get the bit number . Just as we do in getting access to the element of a 2d array .
//Mainly bitwise operations
namespace MinBool
{
class Program
{
static byte[] InitBoolArray(int size)
{
int ratio = sizeof(byte) * 8;
byte[] array = new byte[(int)Math.Ceiling((float)size / ratio)];
return array;
}
static bool Get(byte[] array, int index)
{
int ratio = sizeof(byte) * 8;
int rindex = (int)Math.Floor((float)index / ratio);
byte ans = array[rindex];
int offset = index % ratio;
ans <<= offset;
ans >>= sizeof(byte) * 8 - 1;
if (ans == 1)
return true;
else
return false;
}
static void Set(byte[] array, bool value, int index)
{
int ratio = sizeof(byte) * 8;
int rindex = (int)Math.Floor((float)index / ratio);
byte ans = array[rindex];
int offset = index % ratio;
byte mask = 1;
mask <<= sizeof(byte) * 8 - 1;
mask >>= offset;
if (!value)
{
mask = (byte) ~mask;
ans = (byte) (ans & mask);
}
else
{
ans = (byte) (ans | mask);
}
array[rindex] = ans;
}
static void Main(string[] args)
{
byte[] array = InitBoolArray(11);
Set(array, true, 10);
bool b1 = Get(array, 9);
bool b2 = Get(array, 10);
System.Console.Out.WriteLine("{0}, {1}. {2} bits occupied.", b1, b2, array.Count() * 8);
System.Console.In.Peek();
}
}
}
I think this answer should be very simple:
int n;
int m;
char* arry ;
initialize(){
int total = n*m/8 + (int)(n*m%8) ;
arry = new char[total] ;
for(int i=0; i<total; i++)
arry[i]= 0x00 ;
}
func(int i, int j, bool val){
char tmp = val ;
int offset = (i*m+j)%8 ;
int rownum = (i*m+j)/8 ;
arry[rownum] |= tmp<<offset ;
}
Any feedback ?
total computation seems incorrect i.e.
m*n/8 + m*n%c gives suboptimum total. Eg, if m = 10, n = 5, then we have total = 50/8 + 50%8 = 8 bytes which can store 64 bits. But what was needed was only 50, which can be done using 7 bytes.
Further for m=10,n=5, if i = 3, j = 4, then we get
offset = 34%8 = 2, rownum = 34/8 = 4. This accesses array[4] which is bit#24 - bit#31. Offset of 2 in that gives bit#26. But what we actually need is bit#4 of row#3 i.e. bit#28. I may be a bit off here, but there seems to be something wrong.
There also needs to be a check for out of bounds, so that the extra/dummy bits are not accessed.
Overall, seems like you have converted the 2-D problem into a 1-D problem, which I think is the key idea - that is good! My first instinct was to use a 2-D array - but in that case there will be those extra/dummy bits in every row.
#include <iostream>
#include <math.h>
int main() {
int m=5;
int n=6;
int numBits=m*n;
int numBytes = ceil(numBits / 8.0);
std::cout << numBytes << "\n";
char arr[numBytes];
int r = 4;
int c = 5;
int val = (r - 1) * n + 5;
std::cout << val << "\n";
// val = 16;
int which = val / 8 + 1;
int offset = val - ((val / 8) * 8);
if (offset == 0) {
offset = 8;
which = which - 1;
}
std::cout << which << "\n";
std::cout << offset << "\n";
}
to minimize memory consumption, the idea here is to allocate an array of bytes, and treat each bit of byte as a boolean.
- colin November 08, 2008so if the bool 2d array is m*n, then you need (m*n+7)/8 byte.
now if you need to access the element (x, y) in your 2d bool array, convert the index to x*m+y,
and locate the bit to be at: (x*m+y)/8 byte, and (x*m+y)%8 bit,
you set the bit using & or |