Find kth smallest and count stair-climbing ways
Company: Nio
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two separate algorithm questions.
## A) Find the k-th smallest element in an array (no sorting)
Given an integer array `nums` of length `n` and an integer `k` (1-indexed), return the **k-th smallest** element in the array.
**Requirements**
- You **may not sort** the array (i.e., no `O(n log n)` sorting-based solution).
- Target time complexity: **O(n)** (expected or worst-case should be clarified in discussion).
- Extra space should be **O(1)** or **O(n)** depending on your approach.
**Input**
- `nums`: array of integers (may contain duplicates)
- `k`: integer, `1 <= k <= n`
**Output**
- The value of the k-th smallest element.
## B) Staircase DP counting (1 to 3 steps)
A person is climbing a staircase. Each move they can climb **1, 2, or 3** steps.
1. For a staircase with **10 steps**, how many distinct ways are there to reach exactly the top?
2. Generalize your solution for `n` steps.
**Output**
- The number of distinct ways to reach the top (for `n = 10`, and as a function of general `n`).
**Notes**
- Two ways are different if the sequence of step sizes differs.
Quick Answer: This pair evaluates proficiency with order-statistics and selection algorithms for finding the k-th smallest element and with dynamic programming and combinatorial recurrence reasoning for the staircase counting problem.