Blending problem solving with software development

Spoiler alert: This post is not just about getting solution to some problem statement. Its more about understanding how competitive programmers and the “future” software developers should write their solutions. It is also not about the never ending debate of competitive programming(CP) vs software development.

Software development is more than just about getting green ticks/clearing test cases on hackerrank/leetcode/codechef. Its more about how well you write you appraoch problems, considering edge-cases, thinking about scaling the same solutions to larger codebase and most important documenting/commenting your approach for those problems.

Here, I present a ~few~ solutions to the Day4 May LeetCode Challenge. You can view problem statement here. I have included a potential code review section which can be helpful in understanding how technical recruiters might evaluate your code during interviews.

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;
}

Potential code review -
1. Space complexity isn’t that great.
2. Not a single pass solution.
3. Lots of logging involved here maybe the programmer isn’t confident on the use of STL libraries.
4. Integer overflow condition isn’t handled well.

2. Average solution

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;
}

Potential code review -
1. Well written and easy to understand.
2. Handles overflow condition.
3. Good use of bit manipulation operations and const keyword.

3. Smart high-school math solution

/*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;
}

Potential code review -
1. Well documented, short and less verbose code.
2. Difficult to understand at first glance without comments / approach.

Final thoughts -

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”

Software development != (CP)

Don’t blindly aim for green ticks / clearing test-cases; focus on getting better at software development 😄

Thanks for reading. Happy coding!

You can find me on LinkedIn , Github and Twitter