Katkat
Back

Solve anagram grouping and in-place allocator

NVIDIASoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests string hashing/sorting techniques for grouping anagrams and the ability to manage fixed-size memory blocks in-place without auxiliary data structures.

Part 1: Anagram Grouping

Given a list of strings, group all anagrams together and return them as a list of lists. Two strings are anagrams if they contain the same characters with the same frequencies.

def group_anagrams(strs: list[str]) -> list[list[str]]:
    # Example: input ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
    # Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Part 2: In-place Block Allocator

You are managing a contiguous array of n memory slots, represented by an integer array where 0 indicates a free slot and 1 indicates an occupied slot. Implement a function that defragments the memory by shifting all occupied slots to the beginning of the array while maintaining their relative order. You must perform this operation in-place using O(1) extra space.

def defragment(memory: list[int]) -> None:
    # Example: input [0, 1, 0, 1, 1, 0]
    # Output: memory becomes [1, 1, 1, 0, 0, 0]

Constraints

  • Part 1: Strings contain lowercase English letters; total length of all strings <= 10^5.
  • Part 2: The array length n can be up to 10^6.

Hints

Hint 1

For Part 1, consider using a sorted version of each string or a character frequency tuple as a key in a hash map.

Hint 2

For Part 2, use a 'write pointer' to keep track of the next available position for an occupied slot as you iterate through the array.

Hint 3

For Part 2, ensure you only move slots that are actually occupied and skip the zeros until you find the next '1'.

Follow-up questions

  • How would Part 1 change if you were asked to group anagrams without using a hash map (e.g., memory constraints)?
  • What is the time complexity of your defragmentation algorithm, and can it be done in one pass?
  • How would you modify the defragmentation to handle an array of structs rather than just integers?