Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
In more detail: create an array (of ints) where each item contains the bits in the character that is indexing it (e.g. numBits['A'] = 2; etc)
Then it is just an indexing/adding per each character in the array.
HI JSDUDE. Can you please post your solution ?
I believe a optimised way than what you suggested might be a SWAR Algo. Check out these posts
http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20%28Ones%20Count%29
Also as KP mentioned if we can use some extra memory lookupTable caching count for 8 bit words can be precomputed
Hi,
Please evaluate my solution. I am preparing for the interview. Please anyone review it.
void bits() {
char string[] = "numberofbits";
int n = 0; // The variable that indicated the number of bits set
int i,j; // loop variables
char c; //temporary variable to read each character in string as there is manipulation
j=7; // 8-1 which is the number of bits used to represent a character, here used as count
for(i=0; i < strlen(string); i++) {
c=string[i];
while(j>=0) {
if((int)c && 1) n++;
c=c>>1;
j++;
}
}
}
Calling strlen(string) for each and every iteration is not very effective!
Call it once and use the value.
I think if you create multiple threads then each of the character can be evaluated in parallel without having to wait for the next character as we know the boundaries are fixed. Thus the update to n because there is no other way to reduce number of read operations. Thus the parallelism can give us better performance.
Another optimal solution I see it is that if we can read more bytes at time we can reduce the number of read operations which is based on per character basis.
This is a case of using bitwise dark magic
public int bitsSet(char[] arr) {
int currentRep;
int count = 0;
for (int i = 0; i < arr.length; i += 4) {
currentRep = hammingWeight[i] << 24 | hammingWeight[i + 1] << 16 | hammingWeight[i + 2] << 8 | hammingWeight[i + 3];
count += hammingWeight(currentRep);
}
}
public int hammingWeight(int i) {
//bit magic here- there is a way to do this in O(1)
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Method 1:
better than O(n). O(b) where b = number of set bits.
int countBits(char c) {
int x = (int) c;
int bitCount = 0;
while(x > 0) {
x = x & (x - 1);
bitCount++;
}
return bitCount;
}
Method 2:
O(1)
If character is 8-bit then use following. It can be extended for 32 bits.
int countBitsInChar(char c) {
int x = (int) c;
x = (x & 0x55) + (x >> 1) & 0x55;
x = (x & 0x33) + (x >> 2) & 0x33;
x = (x & 0x0F) + (x >> 4) & 0x0F;
return x;
}
This can be optimized even further but then it becomes less readable. From the book Hacker's Delight :-)
Hey,
what is the complexity of the solution. Because you are doing x & (x-1) it needs to do a bitwise AND on n bits so you are performing that operation k times so the total complexity is O(k*n) where k = No of set bits
Isn't that worst than plain one time scan of bits and counting number of 1's
One of the best approaches to solving the above algorithm is to use the bit manipulation technique and count the bit 1 in the binary representation
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findcount(int n){
int count = 0;
while(n){
if(n & 1 == 1)
count++;
n = n>>1;
}
return count;
}
int main()
{
int t, n;
cin>>t;
while(t--){
cin>>n;
cout<<findcount(n)<<endl;
}
return 0;
}
Maybe he was expecting that you precalculate the number of bits set in all 256 chars?
- kp May 18, 2015