Employees Whose Manager Left the Company - Video Solutions

Problem Overview: You are given an Employees table containing employee_id, manager_id, and salary. The task is to find employees whose salary is less than 30000, whose manager_id is not NULL, and whose manager no longer exists in the table. In other words, the employee references a manager ID that is missing from the employee list.

Approach 1: Self-Join to Find Missing Managers (O(n) time, O(1) extra space)

This method uses a self join on the Employees table. Join the table with itself where the employee’s manager_id matches another row’s employee_id. If the join fails (the manager record is missing), the joined manager fields become NULL. Filtering rows where the joined manager is NULL, while also enforcing salary < 30000 and manager_id IS NOT NULL, gives the required employees. Databases execute joins efficiently using indexes or hash joins, so the scan is typically linear in practice. This is the most direct relational approach and commonly used when working with SQL joins.

Approach 2: Using NOT EXISTS to Validate Manager Presence (O(n) time, O(1) extra space)

Instead of joining tables, this approach checks the absence of a manager using a correlated subquery. For each employee row, run a NOT EXISTS query that attempts to find a matching manager with the same employee_id. If no such row exists, the employee’s manager has left the company. Combine this condition with salary < 30000 and manager_id IS NOT NULL. Query planners often optimize NOT EXISTS into efficient anti-joins, making this solution comparable to the self-join method in performance. It is widely used in database queries where missing relationships must be detected.

Approach 3: Self Join Simulation with Lookups (O(n) time, O(n) space)

In procedural languages such as Python, Java, or JavaScript, the same idea can be implemented using a lookup structure. First iterate through the employee list and insert all employee_id values into a hash set. Then iterate again and check each employee’s manager_id. If the manager ID is not in the set, and the salary condition holds, the employee qualifies. The hash lookup runs in constant time, so the overall algorithm remains linear. This approach mirrors the relational logic of a self join but uses a hash structure instead of SQL joins.

Recommended for interviews: Interviewers typically expect the self-join or NOT EXISTS solution when the problem is presented in SQL form. Both clearly demonstrate understanding of relational data and missing foreign-key references. Showing the lookup-based approach in a programming language also proves you understand how joins translate to hash-based lookups in algorithms. Knowledge of joins and anti-joins is fundamental for problems involving hierarchical relationships or manager–employee structures, especially in join-based queries.