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.

Solve anagram grouping and in-place allocator

Quick Overview

This two-part question evaluates algorithmic problem-solving across string grouping and constrained in-place memory allocation, testing string-processing and data-organization skills as well as low-level memory layout reasoning under strict O(1) extra-space limits.

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve **two coding tasks**. ## 1) Group anagrams Given an array of strings `strs`, group the strings that are anagrams of each other. - Two strings are anagrams if they contain the same characters with the same counts (order can differ). - Return the groups in any order. **Input:** `strs: string[]` **Output:** `string[][]` where each inner array is one anagram group. **Constraints (typical):** - `1 <= len(strs) <= 10^5` - Each string length `<= 100` - Characters are lowercase English letters (unless otherwise stated). --- ## 2) Implement `allocate()` / `free()` with no extra space You have a fixed memory pool represented by an array `mem` of **32 slots**: - `mem` has length `N = 32`. - Each `mem[i]` is a **64-bit unsigned value**. - Each allocated slot stores exactly one 64-bit value. Implement the following API: - `init(mem)`: initialize the pool so all slots are free. - `allocate(x) -> handle`: stores value `x` into one free slot and returns a `handle` (an integer index `0..31`). If no space is available, return `-1`. - `free(handle)`: marks the slot at `handle` as free. **Key constraint:** - You may not use additional data structures proportional to `N` (no separate boolean/bitmap arrays, hash sets, etc.). Only **O(1)** extra variables are allowed beyond the given `mem` array. **Clarifications to state/assume in your solution (as an interviewer would):** - Whether `free()` may be called on an invalid or already-freed handle, and what to do in that case. - Whether all 64 bits are available for user data, or whether you are allowed to reserve some bits for metadata. Design for good time complexity (ideally O(1) per operation).

Quick Answer: This two-part question evaluates algorithmic problem-solving across string grouping and constrained in-place memory allocation, testing string-processing and data-organization skills as well as low-level memory layout reasoning under strict O(1) extra-space limits.

Part 1: Group Anagrams

Given a list of lowercase strings, group together strings that are anagrams of each other. Two strings are anagrams if they contain exactly the same letters with the same counts, regardless of order. To make the output deterministic, sort each group lexicographically, then sort the list of groups lexicographically before returning it.

Constraints

0 <= len(strs) <= 100000
0 <= len(strs[i]) <= 100
Each string contains only lowercase English letters

Examples

Input: (['eat', 'tea', 'tan', 'ate', 'nat', 'bat'],)

Expected Output: [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]

Explanation: The words 'eat', 'tea', and 'ate' form one anagram group; 'tan' and 'nat' form another.

Input: ([''],)

Expected Output: [['']]

Explanation: A single empty string is its own anagram group.

Input: ([],)

Expected Output: []

Explanation: Empty input should return no groups.

Input: (['ab', 'ba', 'abc', 'cab', 'bca', 'ab'],)

Expected Output: [['ab', 'ab', 'ba'], ['abc', 'bca', 'cab']]

Explanation: Duplicate words should be preserved in the output.

Hints

Words that are anagrams share the same canonical signature.
Because the alphabet is fixed to 26 lowercase letters, a 26-length frequency tuple is a good hash key.

Part 2: Simulate an In-Place Fixed-Size Allocator

You have a memory pool with exactly 32 slots. Each slot can hold one unsigned 64-bit value. Simulate the allocator API on a fresh pool using only O(1) extra allocator state beyond the memory array itself. Operations are given as tuples: ('init',) resets the pool so all 32 slots are free, ('allocate', x) stores x in a free slot and returns its handle 0..31 or -1 if the pool is full, and ('free', h) frees a previously allocated handle h. Assume every free operation is valid: h is in range, was returned by an earlier allocate, and has not already been freed. A free slot may store allocator metadata inside the slot itself.

Constraints

0 <= len(operations) <= 100000
The pool size is fixed at 32 slots
0 <= x <= 18446744073709551615 for allocate operations
Every free(handle) in the tests is valid and never double-frees a slot

Examples

Input: ([],)

Expected Output: []

Explanation: No operations means no results.

Input: ([('allocate', 10), ('allocate', 20), ('free', 0), ('allocate', 30)],)

Expected Output: [0, 1, -2, 0]

Explanation: After freeing handle 0, the allocator should be able to reuse that slot.

Input: ([('allocate', 5), ('allocate', 6), ('init',), ('allocate', 7)],)

Expected Output: [0, 1, -2, 0]

Explanation: init resets the allocator so the next allocation starts again from slot 0.

Input: ([('allocate', 1), ('allocate', 2), ('allocate', 3), ('free', 1), ('free', 0), ('allocate', 9), ('allocate', 8)],)

Expected Output: [0, 1, 2, -2, -2, 0, 1]

Explanation: Freed slots are reused in LIFO order when using the free-list head as a stack.

Input: ([('allocate', 0), ('allocate', 1), ('allocate', 2), ('allocate', 3), ('allocate', 4), ('allocate', 5), ('allocate', 6), ('allocate', 7), ('allocate', 8), ('allocate', 9), ('allocate', 10), ('allocate', 11), ('allocate', 12), ('allocate', 13), ('allocate', 14), ('allocate', 15), ('allocate', 16), ('allocate', 17), ('allocate', 18), ('allocate', 19), ('allocate', 20), ('allocate', 21), ('allocate', 22), ('allocate', 23), ('allocate', 24), ('allocate', 25), ('allocate', 26), ('allocate', 27), ('allocate', 28), ('allocate', 29), ('allocate', 30), ('allocate', 31), ('allocate', 32)],)

Expected Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, -1]

Explanation: The first 32 allocations succeed, and the 33rd fails because the pool is full.

Hints

When a slot is free, it does not need to store user data. It can store the index of the next free slot instead.
Maintain the free slots as a singly linked list or stack using the memory array itself.

Quick Overview