Solve common array/graph interview problems
Company: Art Advisors
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given several independent coding tasks. Implement each function according to the specification below.
## 1) Rotate a square matrix in-place
**Input:** An integer matrix `M` of size `n x n`.
**Task:** Rotate the matrix **90 degrees clockwise** **in-place** (modify `M` directly).
**Constraints:**
- `1 <= n <= 500`
- Aim for `O(n^2)` time and `O(1)` extra space.
**Example:**
- Input:
```
[[1,2,3],
[4,5,6],
[7,8,9]]
```
- Output:
```
[[7,4,1],
[8,5,2],
[9,6,3]]
```
---
## 2) Shortest word transformation steps
**Input:**
- `begin`: a lowercase word
- `end`: a lowercase word
- `words`: a list of lowercase words (dictionary)
**Task:** Return the length of the shortest sequence of transformations from `begin` to `end`, where:
- Each step changes **exactly one character**.
- Every intermediate word must exist in `words`.
- If no sequence exists, return `0`.
**Constraints:**
- All words have the same length `L`.
- `1 <= |words| <= 50_000`, `1 <= L <= 10`.
**Example:**
- `begin = "hit"`, `end = "cog"`, `words = ["hot","dot","dog","lot","log","cog"]`
- Output: `5` (e.g., `hit -> hot -> dot -> dog -> cog`)
---
## 3) Compute the H-index
A researcher’s H-index is defined as the maximum integer `h` such that the researcher has **at least `h` papers** with **at least `h` citations each**.
**Input:** An array `citations` where `citations[i]` is the number of citations for paper `i`.
**Task:** Return the researcher’s H-index.
**Constraints:**
- `0 <= n <= 200_000`
- `0 <= citations[i] <= 1_000_000_000`
- Prefer `O(n)` or `O(n log n)` time.
**Example:**
- Input: `[3,0,6,1,5]`
- Output: `3` (three papers have at least 3 citations)
Quick Answer: This multi-part question evaluates proficiency in array and matrix manipulation, graph traversal and shortest-path reasoning for word transformations, and algorithmic counting/selection for computing metrics like the H-index.
Rotate Square Matrix Clockwise
Rotate an n by n matrix 90 degrees clockwise in place and return it.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,2,3],[4,5,6],[7,8,9]],)
Expected Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Explanation: Rotate 3x3 matrix clockwise.
Input: ([[1]],)
Expected Output: [[1]]
Explanation: Single cell unchanged.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Shortest Word Transformation Steps
Return the number of words in the shortest one-letter transformation sequence, or 0 if unreachable.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('hit','cog',['hot','dot','dog','lot','log','cog'])
Expected Output: 5
Explanation: Shortest ladder length is 5.
Input: ('hit','cog',['hot','dot','dog'])
Expected Output: 0
Explanation: Missing end word gives 0.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Compute H-Index
Return the maximum h such that at least h papers have at least h citations.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([3,0,6,1,5],)
Expected Output: 3
Explanation: Standard H-index example.
Input: ([],)
Expected Output: 0
Explanation: No papers gives H-index 0.
Input: ([10,8,5,4,3],)
Expected Output: 4
Explanation: All top citations support h=4.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.