Coding Interview Tips

Ask Questions

First things first, ask questions before jumping into coding.

Clarify assumptions and constraints.
Propose naive solution.

Solve the Problem

Use Built-in Functions

__builtin_popcount
__builtin_parity
__builtin_clz
__builtin_ctz

Overflow

See the reverse integer problem for some basic overflow avoidance logic. And the sqrt(x) problem for more advanced overflow when you need to take into account the division and the denominator can be zero so that has to be treated separately.

Underflow

a.size() - b.size() can underflow because they’re both size_t, so you must do (int)(a.size() - b.size()).

Free Up Nodes

It’s often forgotted, but when you remove a node from a linked list, you must free up its memory. Use delete.

Two's Complement

To calculate two's complement of a negative number in C++, do (uint)num — it's as simple as that.

Convert Letter to Uppercase

The result of 'a' & '_' == 'A' and even if the letter is already uppercase 'A' & '_' == 'A'. So, it's safe to bitwise and underscore to convert a letter to its uppercase representation.

Add Unit Tests

Use the std::assert function as replacement for a unit test framework; std::assert will call std::abort in case it fails.

Note that there’s also std::static_assert which is a compile-time assertion function.

assert(1 + 2 == 3);

Improve Runtime Performance

For the curious mind, please see the full list of options that control optimization on the GNU GCC website.

#pragma GCC optimize("Ofast,unroll-loops,max-inline-insns-recursive")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

The following optimization levels are available:

`-O1`	`-O2`	`-O3`	`-Ofast`
`-fauto-inc-dec` `-fcompare-elim` `-fcprop-registers` `-fdce` `-fdefer-pop` `-fdelayed-branch` `-fdse` `-fguess-branch-probability` `-fif-conversion2` `-fif-conversion` `-fipa-pure-const` `-fipa-profile` `-fipa-reference` `-fmerge-constants` `-fomit-frame-pointer` `-fsplit-wide-types` `-ftree-bit-ccp` `-ftree-builtin-call-dce` `-ftree-ccp` `-ftree-ch` `-ftree-copyrename` `-ftree-dce` `-ftree-dominator-opts` `-ftree-dse` `-ftree-forwprop` `-ftree-fre` `-ftree-phiprop` `-ftree-slsr` `-ftree-sra` `-ftree-pta` `-ftree-ter` `-funit-at-a-time`	All in `-O1`, and: `-falign-functions` `-falign-jumps` `-falign-labels` `-falign-loops` `-fcaller-saves` `-fcrossjumping` `-fcse-follow-jumps` `-fcse-skip-blocks` `-fdelete-null-pointer-checks` `-fdevirtualize` `-fexpensive-optimizations` `-fgcse` `-fgcse-lm` `-fhoist-adjacent-loads` `-findirect-inlining` `-finline-small-functions` `-fipa-sra` `-foptimize-sibling-calls` `-fpartial-inlining` `-fpeephole2` `-fregmove` `-freorder-blocks` `-freorder-functions` `-frerun-cse-after-loop` `-fsched-interblock` `-fsched-spec` `-fschedule-insns` `-fschedule-insns2` `-fstrict-aliasing` `-fstrict-overflow` `-fthread-jumps` `-ftree-switch-conversion` `-ftree-tail-merge` `-ftree-pre` `-ftree-vrp`	All in `-O2`, and: `-fgcse-after-reload` `-finline-functions` `-fipa-cp-clone` `-fpredictive-commoning` `-ftree-partial-pre` `-ftree-vectorize` `-funswitch-loops` `-fvect-cost-model`	All in `-O3`, and: `-ffast-math` `-fno-protect-parens` `-fstack-arrays`

std::ios::sync_with_stdio sets whether the standard C++ streams are synchronized to the standard C streams after each input/output operation. If the synchronization is turned off, the C++ standard streams are allowed to buffer their I/O independently, which may be considerably faster in some cases. By default, all eight standard C++ streams are synchronized with their respective C streams. Thus, we turn off the sync for performance gains because we don't care about printing to the standard output during interviews.
std::cin.tie(nullptr) and std::cout.tie(nullptr) unties std::cin from std::cout so that streams aren't flushed between input/output operations.

Measuring Performance Improvements

#include <ctime>
#include <iostream>

using namespace std;

int main()
{
  clock_t t0 = clock();
  long result;

  for (int i = 0; i < 1e6; ++i) {
    for (int j = 0; j < 1e3; ++j) {
      result = i * j;
    }
  }

  clock_t t1 = clock();

  cout << result << endl;
  cout << "Time: " << fixed << (double)(t1 - t0) / CLOCKS_PER_SEC << " seconds" << endl;
}

And here are the results:

g++ -O0 -Wall performance.cc -o performance.out && ./performance.out
998999001
Time: 0.487458 seconds

g++ -O1 -Wall performance.cc -o performance.out && ./performance.out
998999001
Time: 0.230510 seconds

g++ -O2 -Wall performance.cc -o performance.out && ./performance.out
998999001
Time: 0.000001 seconds

g++ -O3 -Wall performance.cc -o performance.out && ./performance.out
998999001
Time: 0.000001 seconds

g++ -Ofast -Wall performance.cc -o performance.out && ./performance.out
998999001
Time: 0.000001 seconds

Draw Diagrams

If required, and only if required, draw diagrams.