DSA interview question

Pascal's Triangle

Easy · Algorithms · Topics: array, dynamic programming

The problem

A maths-learning app draws Pascal's triangle, where each row starts and ends with 1 and every inner number is the sum of the two numbers diagonally above it. The app needs three things: the first numRows rows for the drawing, a single entry (row r, column c) for a quiz question, and one full row on demand. All three rest on the fact that the entries are binomial coefficients, C(r − 1, c − 1), and that neighbouring coefficients in a row differ by a simple ratio.

Example: numRows = 5 → [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

Function signature

vector<vector<long long>> generate(int numRows);  // the first numRows rows
long long entry(int r, int c);                    // 1-indexed row r, column c: C(r-1, c-1)
vector<long long> row(int r);                     // the r-th row (1-indexed) in O(r)

Test cases

Input	Output	Explanation
`generate(5)`	`[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]`	Each inner entry is the sum of the two above
`generate(1)`	`[[1]]`
`generate(2)`	`[[1],[1,1]]`
`entry(5, 3)`	6	C(4, 2)
`row(6)`	`[1, 5, 10, 10, 5, 1]`	Row 6 is C(5, 0..5)
`entry(31, 16)`	155117520	C(30, 15) computed without factorials

(Confirm: rows and columns are 1-indexed; numRows ≥ 1; values fit in a long long for the sizes used.)

How interviewers phrase it

"Generate the first numRows of Pascal's triangle" (LeetCode 118).
"Return the r-th row using O(r) extra space" (LeetCode 119).
"Find the element at row r, column c" (a binomial coefficient).

Clarifying questions to ask

Are rows and columns 0-indexed or 1-indexed?
Which variant: whole triangle, one row, or one entry?
How large can the row number be? (Overflow.)

Follow-ups to expect

"How do you build a row from the previous one?"
"How do you get a single entry without building the triangle?"
"How do you generate one row in O(r)?"
"Why multiply before dividing?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview