Skip to main content
Back to Library
cracking the tech interview system design and algorithms in java 25

Part XIII — Essential Techniques

3 min read Chapter 73 of 75
Summary

Overview of bitwise operations and randomized algorithms —...

Overview of bitwise operations and randomized algorithms — techniques that unlock elegant solutions to problems that seem complex with standard approaches.

Part XIII — Essential Techniques

Some interview problems resist conventional approaches. Standard data structures and loop-based logic produce bloated solutions — but a few bitwise operators or a randomized strategy cut through the complexity in a handful of lines. This part equips you with two techniques that interviewers love precisely because they test thinking beyond the obvious.

Why Bit Manipulation Matters

At the hardware level, every operation your CPU performs is a bitwise operation. Integers, characters, floating-point numbers — all of them live as sequences of 0s and 1s. When you manipulate bits directly, you’re working at the lowest abstraction layer, and that unlocks performance and elegance that higher-level operations can’t match.

Interviewers use bit manipulation problems to gauge three things:

  • Low-level understanding: Do you know how numbers are represented in memory?
  • Pattern recognition: Can you spot when a problem has a bitwise shortcut?
  • Efficiency instinct: Can you replace an O(n) loop with an O(1) bit trick?

The XOR operator alone solves a family of problems (finding single numbers, detecting duplicates, computing parity) with zero extra space and linear time. Bitmasks transform subset enumeration from recursive backtracking into a compact integer loop. These aren’t niche tricks — they’re fundamental tools that separate strong candidates from average ones.

Why Randomized Algorithms Matter

Deterministic algorithms follow fixed rules. Randomized algorithms introduce controlled randomness — and gain surprising power from it. A shuffled array gives every permutation equal probability. A random pivot in quicksort avoids worst-case behavior. A random hash function distributes keys uniformly.

The key insight: randomness provides guarantees that deterministic approaches struggle to achieve. A perfectly uniform shuffle requires careful algorithm design — most intuitive approaches produce biased results. Reservoir sampling solves the seemingly impossible task of sampling uniformly from a data stream of unknown length.

These techniques appear in interviews because they test probabilistic reasoning, a skill set distinct from the graph traversals and dynamic programming that dominate most preparation.

What This Part Covers

Bit Manipulation — all six bitwise operators in Java, essential tricks (check/set/clear/toggle bits, power-of-two detection, counting set bits), classic XOR problems, bitmask-based subset enumeration, and two’s complement representation. You’ll build a toolkit of patterns that compress multi-line logic into single expressions.

Fisher-Yates Shuffle — the correct algorithm for generating uniform random permutations, proof of why it works, the common mistake that produces biased shuffles, partial shuffling for random sampling, and reservoir sampling for streaming data. You’ll understand both the theory and the implementation pitfalls.

These two topics round out your interview arsenal with techniques that operate at different levels of abstraction — one at the bit level, one at the probability level — both essential for demonstrating depth.