PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates implementation skills in memory management and in-memory data modeling, covering first-fit allocation semantics, free/merge behavior, CRUD operations for user records, and hierarchical traversal of reporting relationships.

  • medium
  • Microsoft
  • Coding & Algorithms
  • Software Engineer

Implement Memory Allocation and In-Memory Records

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following two implementation problems. ### Problem A: First-Fit Memory Allocator You are given a contiguous block of memory containing `n` units, indexed from `0` to `n - 1`. Implement an in-memory allocator that supports: - `allocate(size)`: Allocate a contiguous block of `size` free units using a first-fit strategy. Return the starting index of the allocated block, or `-1` if no block is large enough. - `free(start)`: Free the allocated block whose starting index is `start`. Return whether the operation succeeded. Requirements: - Allocated blocks must not overlap. - Freeing an invalid or already-freed block should fail safely. - Adjacent free blocks should be merged so future allocations can reuse larger ranges. - Write meaningful test cases, including allocation failure, freeing invalid addresses, and reusing freed memory. ### Problem B: In-Memory Record Store Implement an in-memory data service for user records. Each user record has at least: - `id` - `name` - `email` Support the following operations: - Create a user record. - Retrieve a user by row id. - Update a user by row id. - Delete a user by row id. You may expose these operations through functions or HTTP-style handlers, for example: ```python create_response = client.post( "/user/", json={"name": "Alice", "email": "alice@example.com"} ) user_id = create_response.json()["id"] response = client.get(f"/user/{user_id}") assert response.status_code == 200 assert response.json()["name"] == "Alice" ``` Follow-up: Suppose the records represent employees in a company hierarchy. Each employee may have a list of direct reports or a manager field. Implement a function that, given one employee id, returns all direct and indirect reports under that employee. Write your own tests for the basic CRUD operations and the hierarchy traversal follow-up.

Quick Answer: This question evaluates implementation skills in memory management and in-memory data modeling, covering first-fit allocation semantics, free/merge behavior, CRUD operations for user records, and hierarchical traversal of reporting relationships.

Part 1: First-Fit Memory Allocator Simulation

You are given a contiguous memory of size n, with unit indices from 0 to n - 1. Implement a first-fit allocator that processes a sequence of operations. Each operation is one of: - [1, size]: allocate a contiguous free block of length size using the first-fit rule. Return the starting index of the allocated block, or -1 if no suitable block exists. - [2, start]: free the block that was originally allocated starting at start. Return 1 if the free succeeds, or 0 if start is invalid or already freed. Rules: - Allocated blocks must never overlap. - Freeing must only succeed for currently allocated block starts. - When a block is freed, adjacent free blocks must be merged. - Process all operations in order and return one result per operation.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(operations) <= 10^5
  • For allocation operations, value >= 1
  • For free operations, value is an integer start index
  • All operations must be processed online in the given order

Examples

Input: (10, [[1, 3], [1, 4], [2, 0], [1, 2], [1, 3], [2, 3], [1, 5]])

Expected Output: [0, 3, 1, 0, 7, 1, 2]

Explanation: After freeing the block at 0, allocation reuses that space. Later freeing the block at 3 merges adjacent free space, allowing a size-5 allocation at index 2.

Input: (5, [[1, 5], [1, 1], [2, 4], [2, 0], [2, 0]])

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

Explanation: The whole memory is allocated first. A second allocation fails. Freeing start 4 fails because no block starts there. Freeing start 0 succeeds once, then fails the second time.

Input: (1, [[1, 1], [2, 0], [1, 1]])

Expected Output: [0, 1, 0]

Explanation: Single-unit memory can be allocated, freed, and reused.

Input: (8, [])

Expected Output: []

Explanation: Edge case with no operations.

Hints

  1. Keep a sorted list of free intervals and scan it from left to right to implement first-fit.
  2. Store allocated blocks by their starting index so that free(start) can verify validity and know the block size.

Part 2: In-Memory Record Store CRUD

Implement a simple in-memory user record store that supports create, retrieve, update, and delete operations. Each user record contains: - id (assigned automatically starting from 1) - name - email You are given a sequence of operations. Process them in order. Operation formats: - ['CREATE', name, email] - ['GET', id] - ['UPDATE', id, name, email] - ['DELETE', id] Return one string result per operation using the following rules: - CREATE: return the new id as a string - GET: return 'id|name|email' if found, otherwise 'NOT_FOUND' - UPDATE: return 'UPDATED' if the record exists, otherwise 'NOT_FOUND' - DELETE: return 'DELETED' if the record exists, otherwise 'NOT_FOUND' Deleted ids are not reused.

Constraints

  • 0 <= len(operations) <= 10^5
  • 1 <= length of each name and email <= 200
  • Names and emails do not contain the '|' character
  • Ids generated by CREATE start at 1 and increase by 1
  • Average-case O(1) map operations are expected

Examples

Input: ([['CREATE', 'Alice', 'alice@example.com'], ['GET', '1'], ['UPDATE', '1', 'Alice Smith', 'alice.smith@example.com'], ['GET', '1'], ['DELETE', '1'], ['GET', '1']],)

Expected Output: ['1', '1|Alice|alice@example.com', 'UPDATED', '1|Alice Smith|alice.smith@example.com', 'DELETED', 'NOT_FOUND']

Explanation: Basic create, read, update, delete flow on a single record.

Input: ([['CREATE', 'A', 'a@x.com'], ['CREATE', 'B', 'b@x.com'], ['GET', '2'], ['UPDATE', '3', 'C', 'c@x.com'], ['DELETE', '2'], ['GET', '2']],)

Expected Output: ['1', '2', '2|B|b@x.com', 'NOT_FOUND', 'DELETED', 'NOT_FOUND']

Explanation: Shows multiple records, lookup by id, and failure when updating a non-existent record.

Input: ([],)

Expected Output: []

Explanation: Edge case with no operations.

Input: ([['CREATE', 'Solo', 's@x.com'], ['DELETE', '1'], ['DELETE', '1'], ['GET', '1']],)

Expected Output: ['1', 'DELETED', 'NOT_FOUND', 'NOT_FOUND']

Explanation: Deleting the same record twice should only succeed once.

Hints

  1. A hash map from id to record gives fast GET, UPDATE, and DELETE.
  2. Keep a separate next_id counter. Do not use the current number of records, because deleted ids must not be reused.

Part 3: Employee Hierarchy Traversal

You are given a company hierarchy as a list of employees. Each employee is represented by [employee_id, manager_id], where manager_id is the direct manager of that employee. A value of -1 means the employee has no manager. Given one employee_id, return all direct and indirect reports under that employee. Return the result as a list of employee ids sorted in ascending order. If the given employee_id does not exist, return an empty list.

Constraints

  • 0 <= len(employees) <= 10^5
  • Employee ids are distinct integers
  • manager_id is either -1 or the id of another employee
  • The hierarchy contains no cycles
  • If employee_id is absent from employees, return []

Examples

Input: ([[1, -1], [2, 1], [3, 1], [4, 2], [5, 2], [6, 3]], 1)

Expected Output: [2, 3, 4, 5, 6]

Explanation: Employee 1 manages 2 and 3 directly, and 4, 5, 6 indirectly.

Input: ([[1, -1], [2, 1], [3, 1], [4, 2], [5, 2], [6, 3]], 2)

Expected Output: [4, 5]

Explanation: Employee 2 has two direct reports and no deeper descendants.

Input: ([[1, -1], [2, 1]], 2)

Expected Output: []

Explanation: Edge case where the employee exists but has no reports.

Input: ([[1, -1], [2, 1]], 7)

Expected Output: []

Explanation: Edge case where the requested employee id does not exist.

Input: ([[10, -1]], 10)

Expected Output: []

Explanation: Single-employee company.

Hints

  1. Build an adjacency list from manager to direct reports, then run DFS or BFS starting from the given employee.
  2. Collect every reachable subordinate, and sort once at the end if the required output order is ascending.
Last updated: May 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Return Top K Open Businesses - Microsoft (hard)
  • Implement K-Means and Detect Divisible Subarrays - Microsoft (medium)
  • Sort Three Categories In Place - Microsoft (medium)
  • Retain Top K Elements - Microsoft (medium)
  • Implement SFT Sample Packing - Microsoft (medium)