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.
K-th Smallest Element without Sorting
Return the 1-indexed k-th smallest element. This implementation uses a selection heap rather than sorting the full array.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([3,1,2,2], 2)
Expected Output: 2
Explanation: Duplicates count.
Input: ([7], 1)
Expected Output: 7
Explanation: Single element.
Input: ([-1,5,0], 2)
Expected Output: 0
Explanation: Negative values.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.
Count Stair-Climbing Ways with 1 to 3 Steps
Return the number of distinct step sequences to climb exactly n steps using 1, 2, or 3 steps per move.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (10,)
Expected Output: 274
Explanation: Prompt asks n=10.
Input: (0,)
Expected Output: 1
Explanation: One empty way.
Input: (3,)
Expected Output: 4
Explanation: 1+1+1,1+2,2+1,3.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.