Your task is to implement a simplified employee management system. This problem consists of 4 levels that progressively add complexity:
Each level is unlocked when the current level is correctly solved.
Implement basic employee management functionality including adding new employees and tracking when they enter and leave the office.
class Employee:
def __init__(self, name: str, position: str, hourly_salary: float):
self.name = name
self.position = position
self.hourly_salary = hourly_salary
self.clock_records = [] # List of (clock_in, clock_out) tuples
self.current_clock_in = None
class EmployeeManagementSystem:
def __init__(self):
self.employees = {} # name -> Employee
def add_employee(self, name: str, position: str, hourly_salary: float) -> None:
self.employees[name] = Employee(name, position, hourly_salary)
def clock_in(self, name: str, timestamp: int) -> None:
employee = self.employees[name]
employee.current_clock_in = timestamp
def clock_out(self, name: str, timestamp: int) -> None:
employee = self.employees[name]
if employee.current_clock_in is not None:
employee.clock_records.append((employee.current_clock_in, timestamp))
employee.current_clock_in = None
Support querying employee office time statistics and ranking employees by time spent in the office.
Building on Level 1, add these methods to EmployeeManagementSystem:
import heapq
class EmployeeManagementSystem:
# ... Level 1 methods ...
def get_total_office_time(self, name: str) -> int:
employee = self.employees[name]
total_time = 0
for clock_in, clock_out in employee.clock_records:
total_time += clock_out - clock_in
return total_time
def top_k_employees_by_office_time(self, k: int) -> list[str]:
# Calculate total time for each employee
times = []
for name in self.employees:
total_time = self.get_total_office_time(name)
times.append((-total_time, name)) # Negative for max-heap behavior
heapq.heapify(times)
result = []
for _ in range(min(k, len(times))):
_, name = heapq.heappop(times)
result.append(name)
return result
Implement promotion functionality with deferred activation and support querying total compensation for any time period.
Key insight: Store the hourly rate with each clock record to handle salary changes between sessions.
class Employee:
def __init__(self, name: str, position: str, hourly_salary: float):
self.name = name
self.position = position
self.hourly_salary = hourly_salary
self.clock_records = [] # (clock_in, clock_out, hourly_salary_at_time)
self.current_clock_in = None
self.pending_promotion = None # (new_position, new_salary)
class EmployeeManagementSystem:
def __init__(self):
self.employees = {}
def add_employee(self, name: str, position: str, hourly_salary: float) -> None:
self.employees[name] = Employee(name, position, hourly_salary)
def clock_in(self, name: str, timestamp: int) -> None:
employee = self.employees[name]
# Apply pending promotion on clock in
if employee.pending_promotion:
new_position, new_salary = employee.pending_promotion
employee.position = new_position
employee.hourly_salary = new_salary
employee.pending_promotion = None
employee.current_clock_in = timestamp
def clock_out(self, name: str, timestamp: int) -> :
employee = .employees[name]
employee.current_clock_in :
employee.clock_records.append(
(employee.current_clock_in, timestamp, employee.hourly_salary)
)
employee.current_clock_in =
() -> :
employee = .employees[name]
employee.pending_promotion = (new_position, new_salary)
() -> :
employee = .employees[name]
total_salary =
clock_in, clock_out, hourly_rate employee.clock_records:
overlap_start = (clock_in, start)
overlap_end = (clock_out, end)
overlap_start < overlap_end:
hours_worked = overlap_end - overlap_start
total_salary += hours_worked * hourly_rate
total_salary
Support designating certain time periods as double salary periods, where employees earn twice their normal hourly rate.
Key insight: Use interval segmentation - split work periods at double salary boundaries and calculate each segment separately.
class EmployeeManagementSystem:
def __init__(self):
self.employees = {}
self.double_salary_periods = [] # List of (start, end) tuples
# ... Level 1-3 methods ...
def define_double_salary_period(self, start: int, end: int) -> None:
self.double_salary_periods.append((start, end))
def query_salary_for_period(self, name: str, start: int, end: int) -> float:
employee = self.employees[name]
total_salary = 0.0
for clock_in, clock_out, hourly_rate in employee.clock_records:
# Find overlap between work session and query period
work_start = max(clock_in, start)
work_end = min(clock_out, end)
if work_start >= work_end:
continue
# Calculate salary considering double salary periods
total_salary += self._calculate_salary_with_double(
work_start, work_end, hourly_rate
)
return total_salary
def _calculate_salary_with_double(self, start: int, end: int, hourly_rate: float) -> float:
"""Calculate salary for a work period, accounting for double salary periods."""
# Collect all relevant boundaries within [start, end]
points = {start, end}
ds_start, ds_end .double_salary_periods:
ds_start > start ds_start < end:
points.add(ds_start)
ds_end > start ds_end < end:
points.add(ds_end)
sorted_points = (points)
total =
i ((sorted_points) - ):
seg_start, seg_end = sorted_points[i], sorted_points[i + ]
mid = (seg_start + seg_end) //
is_double = (ds <= mid < de ds, de .double_salary_periods)
multiplier = is_double
total += (seg_end - seg_start) * hourly_rate * multiplier
total
Here is the full implementation with all levels combined:
import heapq
from typing import List, Tuple, Optional
class Employee:
def __init__(self, name: str, position: str, hourly_salary: float):
self.name = name
self.position = position
self.hourly_salary = hourly_salary
self.clock_records: List[Tuple[int, int, float]] = [] # (in, out, rate)
self.current_clock_in: Optional[int] = None
self.pending_promotion: Optional[Tuple[str, float]] = None
class EmployeeManagementSystem:
def __init__(self):
self.employees: dict[str, Employee] = {}
self.double_salary_periods: List[Tuple[int, int]] = []
# Level 1
def add_employee(self, name: str, position: str, hourly_salary: float) -> None:
self.employees[name] = Employee(name, position, hourly_salary)
() -> :
emp = .employees[name]
emp.pending_promotion:
emp.position, emp.hourly_salary = emp.pending_promotion
emp.pending_promotion =
emp.current_clock_in = timestamp
() -> :
emp = .employees[name]
emp.current_clock_in :
emp.clock_records.append((emp.current_clock_in, timestamp, emp.hourly_salary))
emp.current_clock_in =
() -> :
(out - in_ in_, out, _ .employees[name].clock_records)
() -> []:
times = [(-.get_total_office_time(n), n) n .employees]
heapq.heapify(times)
[heapq.heappop(times)[] _ ((k, (times)))]
() -> :
.employees[name].pending_promotion = (new_position, new_salary)
() -> :
total =
in_, out, rate .employees[name].clock_records:
ws, we = (in_, start), (out, end)
ws < we:
total += ._calc_with_double(ws, we, rate)
total
() -> :
.double_salary_periods.append((start, end))
() -> :
points = {start, end}
ds, de .double_salary_periods:
ds > start ds < end:
points.add(ds)
de > start de < end:
points.add(de)
sorted_points = (points)
total =
i ((sorted_points) - ):
seg_start, seg_end = sorted_points[i], sorted_points[i + ]
mid = (seg_start + seg_end) //
is_double = (ds <= mid < de ds, de .double_salary_periods)
multiplier = is_double
total += (seg_end - seg_start) * rate * multiplier
total
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| add_employee | O(1) | O(1) |
| clock_in | O(1) | O(1) |
| clock_out | O(1) | O(1) |
| get_total_office_time | O(R) | O(1) |
| top_k_employees_by_office_time | O(E log E) | O(E) |
| announce_promotion | O(1) | O(1) |
| query_salary_for_period | O(R * D) | O(D) |
| define_double_salary_period | O(1) | O(1) |
Where: