Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 77 ยท CS Fundamentals Interview Questions

Bit Manipulation, Greedy and Backtracking Question Patterns

Learn the bit tricks, greedy proofs and backtracking templates behind common coding interview questions, with Python programs that verify each answer.

Three families of coding questions look unrelated but share one trait: each has a small trick that turns a hard-looking problem into a short loop. Bit manipulation questions ("find the number that appears once", "is it a power of two?") are solved with a handful of identities on binary numbers. Greedy questions ("schedule the most meetings", "make change with the fewest coins") are solved by a locally best choice, but only when you can justify it. Backtracking questions ("place N queens", "list all permutations") are solved by a choose, explore, undo template with pruning.

The earlier lessons cover array and string patterns, dynamic programming, recursion and the first backtracking templates (subsets and combination sums), and trees and graphs. This lesson adds the missing pattern families. All programs run in the Python runner, and you can read more in the DSA tutorial.

Three pattern families

Bit tricks XOR, masks and x & (x - 1).
Greedy Sort, then take the best next option.
Backtracking Choose, explore, undo, prune.

Name the pattern first, then write the loop.

1 / 2

Bit manipulation: the identities to know

Python integers are unbounded and use two's complement semantics for negatives, so mask with & 0xFFFFFFFF when a question assumes 32-bit values. The identities that cover most questions:

Expression Meaning
x & 1 lowest bit: 1 if odd
x & (x - 1) clears the lowest set bit
x & -x isolates the lowest set bit
x ^ x = 0, x ^ 0 = x XOR cancels equal values; order does not matter
1 << k a mask with only bit k set
x | (1 << k), x & ~(1 << k), x ^ (1 << k) set, clear, toggle bit k
(x >> k) & 1 test bit k

Counting set bits (Brian Kernighan): each x &= x - 1 removes one 1, so the loop runs once per set bit, not once per bit position. Power of two: a positive number is a power of two exactly when it has a single set bit, that is x > 0 and x & (x - 1) == 0. Single number: if every value appears twice except one, XOR everything; the pairs cancel and the unique value remains, in O(n) time and O(1) space. Missing number in 0..n: XOR all indices and all values. Bits to flip to turn A into B: popcount(A ^ B). Swap without a temp: a ^= b; b ^= a; a ^= b (a known trick, but mention that clarity beats cleverness). Subsets as masks: for a set of n items, every integer from 0 to 2โฟ โˆ’ 1 is one subset.

Python Bit tricks, verified

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the last line carefully: right shift of a negative number in Python is an arithmetic shift (it keeps the sign), and an integer has no fixed width unless you mask it. In C, Java or C++, mention integer width and signed overflow before you answer.

Greedy: choose locally, prove globally

A greedy algorithm makes the best-looking choice at each step and never reconsiders. It is correct only when the problem has the greedy-choice property (a locally best choice is part of some optimal solution) and optimal substructure. The standard way to justify it is an exchange argument: take any optimal solution that does not use your greedy choice and show you can swap the choice in without making it worse.

The recurring greedy question types:

  • Interval scheduling (activity selection): to fit the most non-overlapping meetings, sort by finish time and take each meeting that starts after the last chosen one ends. Sorting by start time or by duration is wrong.
  • Minimum number of platforms or rooms: sort start and end times separately and sweep (or use a heap of end times).
  • Fractional knapsack: sort items by value per unit weight and take as much as fits. (The 0/1 version needs DP, because you cannot take fractions.)
  • Jump game: track the farthest reachable index while scanning left to right.
  • Huffman coding, Dijkstra, Prim and Kruskal are classic greedy algorithms on graphs and data.

The danger is a greedy that looks right but is not. The standard counterexample is coin change: with coins {1, 5, 10, 25} the greedy "largest coin first" is optimal, but with coins {1, 3, 4} and target 6, greedy picks 4 + 1 + 1 (three coins) while 3 + 3 uses two. When greedy fails, use dynamic programming.

Python Activity selection, and when greedy fails

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The finish-time greedy fits 4 meetings here and the start-time greedy only 3. The coin test confirms the claim: greedy matches the optimum for the US-style coins and is wrong for {1, 3, 4}. In an interview, state which property makes greedy safe, or say "I would verify with a counterexample or switch to DP".

Backtracking: N-Queens and permutations with duplicates

The template is the same as in the previous lesson: choose, explore, un-choose, with pruning to cut off branches that can never succeed. Two classics show pruning clearly.

N-Queens: place N queens on an Nร—N board so that none attack each other. Place one queen per row, and track the columns and both diagonals already attacked. A square in row r and column c lies on the diagonal r - c and the anti-diagonal r + c, so three sets give O(1) conflict checks and prune most of the search tree. The number of solutions for N = 4, 5, 6, 7, 8 is 2, 10, 4, 40 and 92.

Permutations with duplicates: for [1, 1, 2] you want the 3 distinct arrangements, not 6. Sort the input, and skip a value if it equals the previous value and the previous one is not currently in use. That skip is the pruning step interviewers look for.

Python N-Queens and distinct permutations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solution counts match the known values, which is the check to run when you write N-Queens yourself. Complexity answers: N-Queens with pruning is far below N! in practice but still exponential; permutations are O(n ยท n!) in the worst case.

How do you pick the pattern?

Clue in the question Pattern
"appears once", "pairs", "without extra space" XOR
"power of two", "number of 1 bits", flags, subsets of at most about 20 items bit masks
"maximum number of non-overlapping", "minimum number of", sorted order matters greedy (then prove it)
"all possible", "generate every", "place without conflict" backtracking
"minimum cost", but greedy has a counterexample dynamic programming

Backtracking classics: Sudoku, rat in a maze, combination sum, word break

N-Queens and permutations with duplicates above use the same template as every other backtracking question: choose an option, recurse, then undo the choice. What changes from problem to problem is the state you keep and the pruning you add. Interviewers ask these four constantly, and they like to hear the complexity as an upper bound.

Combination sum: reuse, order and pruning

Problem: given distinct positive integers candidates and a target, return every combination that sums to the target. A number may be used any number of times.

Keep a start index so you never go "backwards". That prevents [2, 3] and [3, 2] from both appearing. Sort first so you can stop a loop as soon as one number overshoots (pruning). To allow reuse you recurse with the same index; to forbid it you would pass i + 1.

Python Combination sum with pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The running time is bounded by the number of nodes in the recursion tree: roughly O(n^(target/min)) in the worst case, which is why you should say "exponential, pruned by sorting".

Rat in a maze: paths on a grid

Problem: a rat starts at the top-left cell of a grid and must reach the bottom-right cell, moving only through open cells (1). Print every path, never visiting a cell twice in the same path.

The state is the grid plus a visited marker. Mark a cell when you enter it and unmark it when you leave. That second step is the backtracking part, because the same cell may be used by a different path later.

Python All paths through a maze

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Worst case is O(4^(nยฒ)) for an open grid, but pruning on walls and visited cells makes real inputs much smaller. If the question only asks whether a path exists, or the shortest one, switch to BFS: it is O(nยฒ) and does not need backtracking.

Sudoku solver

Problem: fill a 9x9 grid so every row, column and 3x3 box contains the digits 1 to 9 exactly once. 0 marks an empty cell.

Find an empty cell, try each digit 1 to 9 that is legal (not already in its row, column or box), recurse, and undo by setting the cell back to 0 if the recursion fails. The function returns True as soon as the board is complete, which stops the search. The complexity is O(9^m) for m empty cells in theory, but constraint checks make it fast in practice. To go faster, keep sets for each row, column and box, or always pick the empty cell with the fewest candidates (the minimum remaining values heuristic).

Python Solve a Sudoku by backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Word break: where backtracking meets DP

Problem: can a string s be split into words from a dictionary? The backtracking answer tries every prefix that is a word and recurses on the rest. It repeats the same suffix many times (aaaa...b with the words a, aa, aaa is exponential), so add a memo keyed by the start index. The overlapping subproblems are the signal that this is dynamic programming in disguise: O(nยฒ) prefix checks with memoization.

Python Word break with memoization, and listing the sentences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Template and what to say about complexity

  1. Define the state (what the path so far means) and the base case (a complete answer).
  2. Loop over the choices that are legal now. Checking legality early is pruning.
  3. Choose, recurse, undo. Copy the path when you save a result.
  4. State the bound: the size of the recursion tree, usually O(b^d) for branching factor b and depth d, and say what pruning does to it. If subproblems repeat, say "memoize".

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does x & (x - 1) do?

    Subtracting 1 flips the lowest set bit and the zeros below it; ANDing with x then clears that lowest set bit. It underlies popcount and the power-of-two test.
  2. 2. Every number in an array appears twice except one. Which technique finds it in O(n) time and O(1) space?

    XOR of equal values is 0 and XOR is order independent, so the pairs cancel and only the unique number remains.
  3. 3. To fit the maximum number of non-overlapping meetings, in which order should a greedy algorithm consider them?

    Choosing the meeting that finishes earliest leaves the most room for the rest. An exchange argument proves it optimal.
  4. 4. With coins {1, 3, 4} and target 6, what does largest-coin-first give, compared with the optimal answer?

    Greedy takes 4 + 1 + 1 = 3 coins; 3 + 3 uses only 2. This is why coin change needs dynamic programming in general.
  5. 5. In N-Queens, why track a row-minus-column set and a row-plus-column set?

    Two squares attack along a diagonal exactly when they share row - col or row + col.

Summary

  • Bit tricks: x & (x - 1) clears the lowest set bit, x & -x isolates it, XOR cancels pairs; masks represent subsets.
  • Greedy needs the greedy-choice property, proven by an exchange argument; interval scheduling sorts by finish time, and coin change is a classic counterexample.
  • Backtracking is choose, explore, un-choose with pruning: sets for conflicts in N-Queens, a duplicate skip for permutations.
  • Choose the pattern from the wording of the question, and verify greedy with a counterexample before trusting it.
  • Backtracking is choose, recurse, undo; combination sum, rat in a maze, Sudoku and word break differ only in state and pruning.
  • If a backtracking search repeats subproblems (word break), memoize it and it becomes dynamic programming.

Next: OOP, SOLID and Design Patterns Questions.