Micro-questions over the math and geometry module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The vocabulary

1. What does in-place mean here?

Answer

Transforming data directly inside the input structure with extra space — rearranging books on a shelf without a second shelf.

2. What is transposition?

Answer

Swapping matrix[i][j] with matrix[j][i] across the main diagonal — reflecting a chessboard along its diagonal.

3. What is binary exponentiation?

Answer

Computing in by repeatedly squaring rather than multiplying times.


B. Rotate image

4. What two steps make a 90° clockwise rotation?

Answer

Transpose, then reverse each row.

5. What happens if you do them in the other order?

Answer

You get a 90° counter-clockwise rotation.

6. Why does the transpose loop start at j = i + 1?

Answer

To touch only above the diagonal — going over the whole matrix would swap every pair twice and leave it unchanged.

7. How would you get 90° counter-clockwise deliberately?

Answer

Reverse each row first, then transpose — or transpose then reverse the column order.


C. Set matrix zeroes

8. State the problem.

Answer

If any cell is 0, set its entire row and column to zero.

9. What is the naive approach and its cost?

Answer

Store zero-row and zero-column indices in separate arrays — space.

10. What is the -space trick?

Answer

Use the first row and first column of the matrix itself as the marker arrays, plus two booleans for whether the first row/column themselves contained a zero.

11. Why are the two extra booleans necessary?

Answer

Because the first row and column are being overwritten as markers, so their own original zero status would otherwise be lost.

12. Why must the marker pass run before the writing pass?

Answer

Writing a zero would otherwise be read as a marker by a later cell, cascading zeros across the whole matrix.


D. Spiral matrix

13. What is the strategy?

Answer

Maintain four shrinking boundaries — top, bottom, left, right — peel off one edge per direction in rotation, moving each boundary inward after processing.

14. Give the four directions in order.

Answer

Right along the top row (top += 1), down the right column (right -= 1), left along the bottom row (bottom -= 1), up the left column (left += 1).

15. Why are the third and fourth passes guarded by if?

Answer

When only a single row or column remains, the guards prevent double-visiting it.


E. Fast power

16. What is the naive cost, and what is the insight?

Answer

Naive: multiplications. Insight: when is even — halving the exponent each step gives .

17. What happens when is odd?

Answer

Peel off one factor of and continue with , which is even.

18. How do you handle a negative exponent?

Answer

Take the reciprocal of and make positive before the main loop — explicitly, not implicitly.

19. What is the overflow trap?

Answer

In fixed-width languages, the intermediate x * x can overflow 64-bit integers even when the final answer would fit.


F. Happy number

20. How is cycle detection used here?

Answer

Floyd’s slow/fast pointers over the sequence of digit-square sums — two runners on a circular track, the faster lapping the slower.

21. Why is a cycle guaranteed to exist for any starting number?

Answer

The digit-square sum of any number is bounded, so the sequence must eventually revisit a value — either 1 (happy) or a loop (unhappy).

22. What is the alternative to Floyd’s here, and its cost?

Answer

A hash set of seen values — same -ish time but space instead of .

23. Summarise the module in one sentence.

Answer

Matrix problems become space by reusing the matrix itself as scratch, and number problems become by halving the exponent rather than counting down.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms