Katkat
Back

Validate hiring request under role constraints

HubSpotSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage state mapping and validate cardinality constraints using hash maps, requiring efficient lookups to ensure hiring requests remain within predefined role limits.

Problem Statement

You are building a hiring management system. Each 'Role' has a defined 'MaxHeadcount' (the maximum number of people that can be assigned to it). You are given a list of role definitions and a sequence of hiring requests.

A request is a tuple: (employee_id, role_id). A request is considered valid if:

  1. The role_id exists.
  2. The number of employees currently assigned to that role_id is less than its MaxHeadcount.
  3. An employee_id is not already assigned to a different role (an employee can only have one role, and re-hiring into a new role requires explicitly 'moving' them, which is not supported in this version).

Write a function validate_requests(roles, requests) where roles is a dictionary mapping role_id to max_headcount and requests is a list of (employee_id, role_id) tuples. The function should return a list of booleans indicating if each request in the sequence was successful.

Constraints

  • roles size: up to 10^4
  • requests size: up to 10^5
  • employee_id and role_id are strings.

Example

roles = {"Engineer": 2, "Manager": 1}
requests = [
    ("Alice", "Engineer"),  # True
    ("Bob", "Engineer"),    # True
    ("Charlie", "Engineer"),# False (Limit reached)
    ("Alice", "Manager")    # False (Already assigned)
]
# Returns: [True, True, False, False]

Hints

Hint 1

Use a hash map to keep track of how many employees are currently assigned to each role.

Hint 2

Maintain a separate set or dictionary to keep track of which employees have already been assigned to a role to prevent double-hiring.

Hint 3

Process the requests linearly and update your tracking structures only if the request meets all constraints.

Follow-up questions

  • How would you modify your solution to support 'moving' an employee from one role to another?
  • If the number of requests is massive (e.g., billions), how would you handle this state if it no longer fits in the memory of a single machine?
  • How would you handle concurrency if multiple hiring managers are submitting requests for the same role simultaneously?