DSA

Part 4 — Primitive Types

The Hidden Power of Bits, Mathematics, and Representation. Staff-level coding interviews aren't about memorizing bit tricks.

Deepak Mishra21 min read

Staff-level coding interviews aren’t about memorizing bit tricks. They’re about learning to see hidden structure.

In Parts 1–3, we built the foundation for Staff and Principal-level coding interviews:

  • Part 1: How to prepare
  • Part 2: How to solve and communicate
  • Part 3: How interviewers evaluate you

Now we enter the actual algorithmic toolbox. And the first topic is deceptively simple:

Primitive Types

At first glance, this sounds like the easiest part of data structures and algorithms. Integers. Bits. Arithmetic. But primitive-type problems are among the best ways to test whether an engineer can reason about representation, invariants, mathematical properties, and computational efficiency. The deeper lesson is not about bits. It is about this:

Can you discover the structure hidden inside a problem and use it to eliminate unnecessary work?

1. What Part 4 Is Really Teaching

Part 4 is the first major DSA section of the series. It starts with bit manipulation and progressively moves through:

  • Bit counting
  • Parity
  • Bit swapping
  • Bit reversal
  • Mathematical transformations
  • Arithmetic without arithmetic operators
  • Division
  • Exponentiation
  • Digit manipulation
  • Random number generation
  • Rectangle intersection

But these aren’t isolated problems. They follow a common reasoning pattern: Primitive / Integer ↓ Representation ↓ ┌──────┼──────┐ ↓ ↓ ↓ Bits Digits Arithmetic ↓ ↓ ↓ Mask Modulo Shift ↓ ↓ ↓ Mathematical Property ↓ Efficient Algorithm

The recurring progression is: Brute Force ↓ Understand Representation ↓ Find Mathematical / Bit Property ↓ Exploit Invariant ↓ Eliminate Repeated Work ↓ Optimal Solution

That is exactly the reasoning style expected from a strong Staff engineer.

2. Why Primitive Types Matter at Staff Level

Consider a simple interview question:

“Count the number of 1 bits in an integer.”

A beginner may immediately think: Check every bit ↓ Count the 1s

A stronger engineer asks:

“Do I really need to inspect every bit?”

That question leads to one of the most useful bit-manipulation identities: x & (x - 1)

This operation removes the lowest set bit. Therefore, instead of iterating over every bit, we can iterate only over the bits that are actually set. If an integer has:

  • n total bits
  • k set bits

we can move from: O(n)

to: O(k)

The important lesson isn’t memorizing the expression. It’s learning to ask:

“What structural property allows me to eliminate unnecessary work?”

That question appears repeatedly throughout Staff-level algorithmic interviews.

3. Python Has an Important Twist

There is a subtle but very important distinction when solving primitive-type problems in Python. Many classic interview problems assume a fixed-width machine integer, such as a: 32-bit integer 64-bit integer

Python integers are different. Python 3 integers have arbitrary precision. That means: x = 2 ** 1000

is perfectly valid. Therefore, when an interviewer says:

“Given a 64-bit unsigned integer…”

don’t blindly apply normal Python integer semantics. Clarify the model:

“Should I treat this as a fixed-width 64-bit unsigned integer?”

That’s a small question, but it demonstrates strong engineering awareness. Especially when working with negative numbers, Python’s behavior differs from the fixed-width two’s-complement model commonly assumed in languages such as C or C++.

4. Bit Manipulation Fundamentals

You should be completely comfortable with these operators: & AND | OR ^ XOR ~ NOT << Left shift >> Right shift

Let’s understand the most important ones.

5. AND — &

AND returns 1 only when both bits are 1. 1011 & 1101 -—– 1001

In Python: x & y

One of the simplest uses is checking the least significant bit: x & 1

For a non-negative integer: 0 → even 1 → odd

For example: 13 = 1101

13 & 1 = 1

Therefore, 13 is odd.

6. OR — |

OR returns 1 if either bit is 1. 1010 | 0101 -—– 1111

A common use is setting a bit. x |= (1 << i)

This sets bit i.

7. XOR — ^

XOR is arguably the most important operator in this Part. Its truth table is: 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0

The key properties are: x ^ 0 = x x ^ x = 0 x ^ y = y ^ x (x ^ y) ^ z = x ^ (y ^ z)

These properties make XOR extremely useful for:

  • Toggling bits
  • Swapping bits
  • Detecting differences
  • Combining independent computations
  • Parallel reduction

8. XOR as a Toggle

Suppose: x = 1010 mask = 0010

Then: 1010 ^ 0010 -—– 1000

The selected bit has been flipped. Therefore: x ^= (1 << i)

toggles bit i. This tiny operation becomes the foundation of several interview problems.

9. Shift Operators

Left shift

x << k

For non-negative integers, this is conceptually: x × 2^k

Example: 5 = 0101

5 << 2 = 10100 = 20

Right shift

x >> k

For non-negative integers: x >> k ≈ floor(x / 2^k)

Example: 20 >> 2 = 5

10. Masks — The Foundation of Bit Manipulation

A mask is simply a value whose bits are arranged to select or modify particular bits. For example: mask = 1 << i

If: i = 4

the mask looks conceptually like: 00010000

Now: x & mask

checks whether bit 4 is set. x | mask

sets bit 4. x ^ mask

toggles bit 4. This gives us a compact mental model: Test → & Set → | Toggle → ^ Clear → & ~

11. The Most Important Bit Trick

If you remember only one expression from this Part, remember: x & (x - 1)

It removes the lowest set bit. Consider: x = 1011000 x - 1 = 1010111

Now: 1011000 & 1010111 -–––– 1010000

The lowest 1 has disappeared. Why? Suppose: x = ABC1000

where the 1 is the lowest set bit. Then: x - 1 = ABC0111

ANDing them gives: ABC1000 & ABC0111 -–––– ABC0000

The lowest set bit is removed. So whenever you see:

“Process only set bits.”

think: x &= x - 1

12. Problem: Compute Parity

Parity asks:

Does the integer contain an odd or even number of 1 bits?

For example: 1111

contains four 1s: Parity = 0

while: 1011

contains three: Parity = 1

A straightforward implementation processes every bit: def parity(x): result = 0

while x:
    result ^= x & 1
    x >>= 1

return result

Complexity: Time: O(n) Space: O(1)

where n is the number of bits.

13. Optimize by Removing Set Bits

Instead of processing every bit: def parity(x): result = 0

while x:
    result ^= 1
    x &= x - 1

return result

Now the number of iterations equals the number of set bits. If there are k set bits: Time: O(k) Space: O(1)

This is a perfect Staff-level optimization pattern: Don’t process everything. Process only what matters.

14. What If Parity Is Computed Billions of Times?

Now the interviewer may ask:

“Can you make it even faster?”

This is where the problem moves from pure algorithmics into engineering. Suppose you’re working with fixed-width 64-bit values. You could divide the integer into smaller chunks: 64 bits ↓ 4 × 16-bit chunks ↓ Precompute parity ↓ Lookup ↓ Combine using XOR

A lookup table can contain: parity[0] parity[1] … parity[65535]

Then parity of the full 64-bit value can be computed by looking up each chunk and XORing the results. This reveals a much broader engineering pattern: Expensive computation + Small finite input domain + Repeated queries ↓ Precompute ↓ Lookup

The same pattern appears in:

  • Memoization
  • Database indexes
  • Caches
  • ML inference caches
  • Compiled expressions
  • Lookup tables

The trade-off is:

CPU time ↔ Memory

15. XOR and Parallel Reduction

XOR has another important property: Associativity + Commutativity

That means: (a ^ b) ^ c

can be regrouped as: a ^ (b ^ c)

This enables a tree-style computation: XOR / \ XOR XOR / \ / \ a b c d

Instead of one long dependency chain, computation can happen in parallel. This same conceptual pattern appears in:

  • MapReduce
  • Parallel reductions
  • GPU kernels
  • Distributed aggregation

This is where a simple bit-manipulation concept connects directly to distributed systems.

16. Problem: Swap Two Bits

Suppose you’re given a 64-bit integer and two bit positions i and j. The key observation is:

If the bits are equal, nothing needs to change.

If they are different, flip both. def swap_bits(x, i, j): bit_i = (x >> i) & 1 bit_j = (x >> j) & 1

if bit\_i != bit\_j:
    mask = (1 << i) | (1 << j)
    x ^= mask

return x

Complexity: Time: O(1) Space: O(1)

The reason XOR works is simple: 0 ^ 1 = 1 1 ^ 1 = 0

So XOR with 1 flips a bit.

17. Problem: Reverse Bits

Given a fixed-width integer: 101100…

reverse the bits: …001101

For a 64-bit value: def reverse_bits(x): result = 0

for \_ in range(64):
    result = (result << 1) | (x & 1)
    x >>= 1

return result

Complexity: O(64) = O(1)

for fixed-width 64-bit integers. For a generalized n-bit integer: O(n)

Again, repeated computation creates an opportunity for caching. Split the integer into chunks, reverse each chunk through a lookup table, and reassemble the result.

18. Problem: Closest Integer With the Same Weight

This is one of the most beautiful problems in the Part. Here, weight means:

The number of 1 bits in the binary representation.

For example: 6 = 0110

has weight: 2

The goal is to find another integer with:

  • The same number of 1 bits
  • Minimum absolute difference from the original integer

The key insight is mathematical. If two bits at positions k1 and k2 are swapped, the numerical difference depends on: 2^k1 - 2^k2

To minimize that difference, the two positions should be as close as possible. Therefore:

Find the rightmost pair of adjacent bits that differ and swap them.

The implementation is: def closest_int_same_bit_count(x): NUM_BITS = 64

for i in range(NUM\_BITS - 1):
    if ((x >> i) & 1) != ((x >> (i + 1)) & 1):
        mask = (1 << i) | (1 << (i + 1))
        return x ^ mask

raise ValueError("All bits are 0 or all bits are 1")

Complexity: Time: O(64) = O(1) Space: O(1)

The deeper lesson is: Don’t enumerate candidates. ↓ Understand the mathematical structure. ↓ Minimize the change directly.

That’s a very Staff-level way of thinking.

19. Multiplication Without *

Now the interview can become more interesting. Suppose you’re asked:

Multiply two non-negative integers without using multiplication or addition.

Instead of thinking about arithmetic syntax, think about binary representation. Binary multiplication is essentially: Shift + Add

For: x × y

process the bits of x. If bit i is 1, add: y × 2^i

which is simply: y << i

But there is another restriction:

Addition is also forbidden.

So we need to construct addition from: XOR + AND + SHIFT

20. Addition Using XOR and Carry

For two numbers: a b

the sum without carry is: a ^ b

The carry is: (a & b) << 1

So: def add(a, b): while b: carry = (a & b) << 1 a = a ^ b b = carry

return a

Now multiplication becomes: def multiply(x, y): result = 0

while x:
    if x & 1:
        result = add(result, y)

    x >>= 1
    y <<= 1

return result

The conceptual decomposition is: Multiplication ↓ Repeated addition ↓ Binary shift + add ↓ Addition ↓ XOR + carry ↓ AND + shift

This is a powerful systems-thinking pattern:

Build a complex operation from simpler primitives.

21. Division Without /

Suppose you’re asked to calculate: x / y

without using division. A naive solution repeatedly subtracts y. For: x = 1,000,000 y = 1

that means: 1,000,000 iterations

Clearly inefficient. Instead, use binary decomposition: y 2y 4y 8y 16y …

Find the largest power-of-two multiple that fits inside x. Then subtract it and continue. This is essentially binary long division. The pattern is: Repeated subtraction ↓ Doubling ↓ Binary decomposition ↓ O(number of bits)

The resulting algorithm runs in: Time: O(n) Space: O(1)

where n is the number of bits.

22. Exponentiation by Squaring

This is one of the most important patterns in algorithmic interviews. Suppose we need: x^y

The naive approach performs y multiplications: O(y)

But consider: x^(2a) = (x^a)^2

and: x^(a+b) = x^a × x^b

Now binary representation becomes useful. For example: 13 = 1101₂ = 8 + 4 + 1

Therefore: x^13 = x^8 × x^4 × x

We can calculate: x² x⁴ x⁸

through repeated squaring. Python: def power(x, y): if y < 0: x = 1.0 / x y = -y

result = 1.0

while y:
    if y & 1:
        result \*= x

    x \*= x
    y >>= 1

return result

Complexity: Time: O(log y) Space: O(1)

The interview pattern to remember is: Large exponent ↓ Binary representation ↓ Repeated squaring ↓ O(log n)

This idea extends far beyond primitive types:

  • Matrix exponentiation
  • Fibonacci
  • Modular exponentiation
  • Cryptography
  • Polynomial transformations

23. Reverse Digits

Now we move from bits to decimal representation. Given: 1234

return: 4321

For: -314

return: -413

The key operations are: digit = x % 10 x //= 10

For example: 1132 % 10 = 2

Then: 1132 // 10 = 113

Build the result using: result = result * 10 + digit

A clean implementation: def reverse(x): sign = -1 if x < 0 else 1 x = abs(x)

result = 0

while x:
    result = result \* 10 + x % 10
    x //= 10

return sign \* result

Complexity: Time: O(n) Space: O(1)

where n is the number of digits.

24. Palindrome Numbers

Now consider: 121 → True 123 → False

Instead of converting the number to a string, we can reason directly about its decimal representation. Compare: Most significant digit ↕ Least significant digit

Then remove both and continue. Important edge cases include: 0 → True 7 → True 11 → True 121 → True 123 → False -121 → False 100 → False

The source treats negative numbers as non-palindromes because their representation begins with -. The deeper pattern is: Number ↓ Representation ↓ Extract components ↓ Compare

This same idea appears everywhere: String → Characters Integer → Digits Bitmask → Bits IP address → Octets Timestamp → Components

A strong engineer doesn’t think only about the abstract value. They think about its representation.

25. Uniform Random Numbers and Modulo Bias

This is one of the most deceptively sophisticated problems in the Part. Suppose you have only a fair random bit: 0 or 1

with equal probability. You need to generate a uniformly distributed random integer in: [a, b]

The obvious approach might be: random_value % range

But this can introduce modulo bias. For example, if you generate three random bits: 000 → 0 001 → 1 010 → 2 011 → 3 100 → 4 101 → 5 110 → 6 111 → 7

you have eight equally likely outcomes. But suppose you need six: 0–5

If you simply use modulo 6, some values receive more representations than others. Therefore, the distribution becomes biased.

26. Rejection Sampling

Instead, generate the required number of bits and: Accept valid range Reject invalid range Retry

For the previous example: 0–5 → Accept 6–7 → Reject

Every accepted value now has the same probability. That’s rejection sampling. The interview response should be:

“I wouldn’t directly use modulo if the source range isn’t divisible by the target range, because that can introduce bias. I’d use rejection sampling.”

That single answer demonstrates:

  • Probability
  • Algorithmic reasoning
  • Awareness of bias
  • Correctness

27. Rectangle Intersection — Decompose the Problem

The final problem in this Part moves into geometry. Given two axis-aligned rectangles: (x, y, width, height)

determine whether they intersect and calculate the intersection rectangle. The mistake is to think about the entire 2D problem at once. Instead: Rectangle Intersection │ ├── X-axis intersection │ └── Y-axis intersection

For X: R1 = [x1, x1 + w1] R2 = [x2, x2 + w2]

They intersect if: x1 <= x2 + w2 AND x2 <= x1 + w1

Do the same independently for Y. If they intersect: left = max(x1, x2) bottom = max(y1, y2)

right = min(x1 + w1, x2 + w2) top = min(y1 + h1, y2 + h2)

Then: width = right - left height = top - bottom

The complexity is: O(1)

But there is another Staff-level question:

“If two rectangles only touch at an edge or corner, does that count as an intersection?”

That is a requirements question. And it connects directly back to Part 2: Clarify requirements ↓ Avoid wrong implementation

28. The 8 Patterns You Should Remember

Don’t memorize 11 different problem solutions. Memorize these patterns.

Pattern 1 — Extract a bit

(x >> i) & 1

Pattern 2 — Create a bit mask

1 << i

Pattern 3 — Toggle a bit

x ^ (1 << i)

Pattern 4 — Remove the lowest set bit

x &= x - 1

Pattern 5 — Binary decomposition

Repeated doubling / shifting

Useful for:

  • Multiplication
  • Division
  • Power

Pattern 6 — Exponentiation by squaring

n → binary ↓ square ↓ multiply when bit = 1

Pattern 7 — Digit extraction

digit = x % 10 x //= 10

Useful for:

  • Reverse digits
  • Palindrome

Pattern 8 — Decompose dimensions

2D problem ↓ X problem + Y problem

These patterns transfer much better to unfamiliar problems than memorizing individual solutions.

29. Complexity Patterns to Internalize

Part 4 teaches several important optimization patterns.

Linear → Set-bit dependent

O(n) ↓ O(k)

where k is the number of set bits.

Repeated computation → Lookup

Expensive computation ↓ Precompute ↓ Lookup

Repeated work → Logarithmic

x^n ↓ Binary representation ↓ Repeated squaring ↓ O(log n)

Repeated subtraction → Binary decomposition

O(value) ↓ O(number of bits)

Candidate enumeration → Mathematical property

Instead of trying every candidate, understand what property guarantees the closest or optimal candidate. This is perhaps the most important optimization lesson of the Part:

Don’t make the computer do work that your reasoning can eliminate.

30. Invariants Are Everywhere

Part 4 is full of invariants. For example:

Parity

result = parity of bits processed so far

Multiplication

result + remaining contribution = final product

Division

original x = quotient × y + remaining x

Power

result × x^(remaining power) = original x^y

Rectangle

Intersection = X intersection AND Y intersection

The Staff-level question is:

“What remains true after every iteration?”

If you can answer that question, you’re not merely coding. You’re reasoning about correctness.

31. Space Optimization

Another recurring theme is:

“Can I avoid allocating another data structure?”

Many of these problems can be solved with constant auxiliary space: Parity → O(1) Swap bits → O(1) Closest bits → O(1) Reverse digits → O(1) Palindrome → O(1) Rectangle → O(1)

This teaches an important Staff-level habit: Don’t automatically reach for: list set dict

First ask:

Can I operate directly on the representation?

Sometimes the representation itself is the data structure.

32. The Python Interview Cheat Sheet

These should become automatic:

Operation Python
Test bit i (x >> i) & 1
Set bit i x | (1 << i)
Clear bit i x &= ~(1 << i)
Toggle bit i x ^= (1 << i)
Remove lowest set bit x &= x - 1
Lowest set bit x & -x
Extract last digit x % 10
Remove last digit x //= 10
Large exponent Exponentiation by squaring
Repeated subtraction Binary decomposition
Uniform random range Rejection sampling
Independent dimensions Solve separately

The important point is not to memorize code. Memorize the trigger. For example: “Remove lowest set bit” ↓ x & (x - 1)

or: “Large exponent” ↓ Binary representation ↓ Repeated squaring

33. How to Talk Through These Problems in an Interview

Suppose the interviewer asks:

“Compute x^y.”

A weak answer:

“I’ll use a loop.”

for _ in range(y): result *= x

That’s technically correct, but it misses the deeper opportunity. A strong Staff-level answer is:

“The straightforward approach performs y multiplications. Since the exponent can be large, I’d exploit its binary representation. Using repeated squaring, I can square the base each iteration and multiply it into the result whenever the corresponding exponent bit is set. That reduces the number of multiplications to O(log y).”

Then write the code. The explanation demonstrates: Problem ↓ Baseline ↓ Constraint ↓ Mathematical property ↓ Optimization ↓ Complexity

That’s what the interviewer wants to see.

34. Don’t Hide Behind Python

Suppose the interviewer asks:

“Count the number of set bits.”

You could write: bin(x).count(“1”)

It works. But it may bypass the algorithmic reasoning being tested. A stronger response is:

“I’ll start with the bit-by-bit approach. Then I can optimize it because x & (x - 1) removes the lowest set bit, so the number of iterations becomes proportional to the number of set bits.”

Then: def count_bits(x): count = 0

while x:
    x &= x - 1
    count += 1

return count

The interviewer isn’t only evaluating whether Python can solve the problem. They’re evaluating whether you understand why it works.

35. The Deepest Lesson From Part 4

Part 4 isn’t really about bits. It’s about hidden structure. Look at the progression: Parity ↓ Don’t inspect unnecessary bits

Closest integer ↓ Don’t enumerate candidates

Multiplication ↓ Don’t repeatedly add

Division ↓ Don’t repeatedly subtract

Power ↓ Don’t repeatedly multiply

Randomness ↓ Don’t introduce modulo bias

Rectangle ↓ Don’t reason about 2D directly

The common principle is:

Find the structure that allows you to eliminate unnecessary work.

That is the mindset you want to carry into every future algorithmic problem.

36. The Staff/Principal Mental Model

Now combine Parts 1–4: PART 1 How to prepare ↓ PART 2 How to solve + communicate ↓ PART 3 How the interviewer evaluates you ↓ PART 4 Primitive algorithmic toolbox ↓ ┌────────────────────────────┐ │ STAFF CODING INTERVIEW │ └────────────────────────────┘ ↓ Understand representation ↓ Find invariant ↓ Eliminate repeated work ↓ Optimize complexity ↓ Explain trade-offs ↓ Write clean Python

This is the transition we’re trying to make throughout this series: LeetCode Solver ↓ Senior Engineer ↓ Staff Engineer

The difference isn’t simply knowing more algorithms. It’s seeing more structure.

Final Takeaway

When you encounter a primitive-type problem in a Staff-level interview, don’t immediately think:

“Which problem have I seen before?”

Instead ask:

1. What is the representation?

Bits? Digits? Geometry?

2. What operation is being repeated?

Checking? Adding? Subtracting? Multiplying? Searching?

3. What structure can eliminate that work?

Bit trick? Mathematical property? Binary decomposition? Caching? Invariant?

4. What is the complexity?

O(1)? O(bits)? O(set bits)? O(log n)? Expected complexity?

5. What assumptions am I making?

Especially in Python:

Am I dealing with arbitrary-precision integers or fixed-width machine integers?

And finally:

Can I explain why the algorithm works—not just write the code?

That’s the real lesson of Part 4. Primitive types are not about low-level tricks. They are your first serious training ground for representation thinking, mathematical reasoning, invariants, complexity optimization, and engineering judgment. And those skills will matter long after the interview is over.

Up Next

In Part 5, we move from primitive values to one of the most important data structures in coding interviews:

Arrays

And we’ll focus not on memorizing array problems, but on recognizing the patterns that repeatedly appear in Staff-level interviews: two pointers, sliding windows, prefix sums, partitioning, invariants, and in-place transformations.