Blending problem solving with software development

  1. Naive solution
/*Approach — 
1. decimal to binary conversion operation & store each bit in vector
2. reverse vector to get the original binary representation of number back
3. traverse each bit and store inverted bits in another vector
4. binary to decimal conversion operation to get the complement of number
*/
int findComplement(int num) {
if(num == 0) return 1; //edgecase
vector<int> bits; //overhead 1 =: there is no need for extra space

while(num){
bits.push_back(num % 2);
num /= 2;
}

reverse(bits.begin(), bits.end()); //overhead 2 =: O(n) operation
//for(auto i : bits)cout<<i<<” “;
vector<int> complement; //overhead 3 =: there is no need for “more” extra space
for(auto i : bits){
if(i == 0) complement.push_back(1); //overhead 4 =: Another O(n) operation
else complement.push_back(0);
}

//cout<<”\n”;
//for(auto i : complement)cout<<i<<” “;

int sz = complement.size()- 1;
int complement_no = 0;

for(int i=sz; i>=0; i — ){
int expr = (complement[i] * pow(2, (sz- i)));
complement_no += expr;
}

//cout<<complement_no<<”\n”;
return complement_no;
}
int findComplement(int num) {        
if(num==0) return 1; //edgecase
vector<int>v; //overhead

//use of and operation and bitwise shifts makes this code little faster
while(num) {
v.push_back(num&1 ? 0:1);
num>>=1;
}
long long sum=0, cnt=0;
for(const auto i:v) {
sum += i*pow(2,cnt);
cnt++;
}
//cout<<sum<<"\n";
return sum;
}
/*Approach -
Find all set bits and calculate xor of set bits with number to get complement.
Let, number ^ complement ==> (A)We know that ==> number ^ complement = set_bits
number ^ (A) = number ^ set_bits (Xoring with number on both sides)
0 ^ complement = number ^ set_bits (number xored with self equals 0)
Hence, complement = number ^ set_bits.
*/
int findComplement(int num) {
if(!num) return 1; //edgecase
int set_bits = pow(2,0);
for(int i=1; set_bits<num; i++) set_bits += pow(2,i);
return num xor set_bits;
}
  1. Usually its difficult to get intuition of last solution at first glance in the interview process. So the average solution is something that works ~okayish~ if you are facing the same problem in interview. The interviewers aren’t just looking for smart solutions; they are looking for well-written solutions. If you code something really smart but you are unable to explain it to your interviewers, all the smartness behind solution is futile.
  2. Usually you start with brute-force and work towards optimising your solution. When asked about optimisation aspects, “yes”, the interviewers are looking for something better from your solution/approach alike the smart solution. (FAANG’s, MSFT and other product-based firms want this!)
  3. Alongside problem-solving, system design, scalability, test-driven development and clean-code practices is something what recruiters are looking within you. Everything coupled above is makes a computer programmer the “real software engineer”

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store