How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at NVIDIA.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at NVIDIA during technical interviews.

Implement matrix transpose and KV store

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The phone screen for a Linux-oriented software engineering role included multiple coding tasks: 1. **Transpose an `n x n` matrix** Given a square matrix of size `n x n`, transform it so that rows become columns. In other words, return the matrix transpose, where `result[i][j] = matrix[j][i]`. 2. **Design an object-oriented key-value store with `set`, `get`, and `setAll`** Implement a key-value store supporting the following operations: - `set(key, value)`: assign `value` to `key` - `get(key)`: return the current value for `key`, or indicate that the key does not exist - `setAll(value)`: update all existing keys so that they now return `value` The design should be object-oriented. Discuss the expected time complexity of each operation, and implement the API efficiently. A separate prompt mentioned reviewing a short C snippet and identifying bugs or issues, but the code itself was not provided, so that part is omitted here.

Quick Answer: This question evaluates array manipulation and algorithmic reasoning via an n x n matrix transpose and object-oriented design, data structure competency, and time-complexity reasoning for a key-value store API.

Part 1: Transpose an n x n Matrix

Given a square matrix of size n x n, return its transpose. In a transposed matrix, rows become columns, so the value at result[i][j] must be equal to matrix[j][i]. Return a new matrix rather than modifying the input.

Constraints

0 <= n <= 200
-10^9 <= matrix[i][j] <= 10^9
The input matrix is guaranteed to be square

Examples

Input: []

Expected Output: []

Explanation: An empty matrix stays empty after transposition.

Input: [[42]]

Expected Output: [[42]]

Explanation: A 1 x 1 matrix is unchanged.

Input: [[1, 2], [3, 4]]

Expected Output: [[1, 3], [2, 4]]

Explanation: The first column becomes the first row, and the second column becomes the second row.

Input: [[0, -1, 2], [7, 5, 9], [3, 8, 6]]

Expected Output: [[0, 7, 3], [-1, 5, 8], [2, 9, 6]]

Explanation: Each column of the original becomes a row in the result.

Hints

Figure out where matrix[i][j] should appear in the output.
Create an empty n x n result matrix, then fill result[j][i] = matrix[i][j].

Part 2: Key-Value Store with set, get, and setAll

You must process operations on a key-value store that supports set(key, value), get(key), and setAll(value). The setAll operation changes the value returned by every key that already exists at that moment. To make the task suitable for a coding function, you are given a list of operations and must return the results of all get operations in order. Your implementation should be object-oriented internally and should aim for average O(1) time per operation.

Constraints

0 <= len(queries) <= 200000
Keys are strings of length 1 to 50
-10^9 <= value <= 10^9
An efficient solution should avoid touching every existing key during setAll

Examples

Input: []

Expected Output: []

Explanation: No operations means no get results.

Input: [("set", "x", 10), ("get", "x")]

Expected Output: [10]

Explanation: After setting x to 10, getting x returns 10.

Input: [("set", "a", 1), ("set", "b", 2), ("setAll", 7), ("get", "a"), ("get", "b")]

Expected Output: [7, 7]

Explanation: Both existing keys are updated logically by setAll.

Input: [("get", "missing"), ("setAll", 5), ("get", "missing")]

Expected Output: [None, None]

Explanation: A missing key stays missing, even if setAll is called when no such key exists.

Input: [("set", "a", 1), ("set", "b", 2), ("setAll", 5), ("set", "b", 8), ("get", "a"), ("get", "b")]

Expected Output: [5, 8]

Explanation: Key a keeps the setAll value, while b is overwritten by a later set.

Hints

A naive setAll that updates every stored key is too slow when there are many keys.
Store a timestamp for each key's latest set, and compare it with the timestamp of the most recent setAll.

Quick Overview

This question evaluates array manipulation and algorithmic reasoning via an n x n matrix transpose and object-oriented design, data structure competency, and time-complexity reasoning for a key-value store API.