Komprise

Role: SDE Technical Interview

College: Not Specified

Interview Date: September 2021

Interview Type: Not Specified

Result: Rejected

Difficulty: Hard

Rounds: 1 (Technical Round-1 mentioned)

Topics Asked: Algorithms (Greedy/Dynamic Programming, Interval Overlap)

Experience:

This candidate encountered a challenging coding question in a technical round for an SDE role at Komprise India.

Technical Round-1:

Coding Question: "Find maximum lampposts that can be removed to save power."

Description: There are several lampposts on the road. The list `lampPositions` contains the position of each lamp and is sorted. The list `lightingRange` contains the range of each lamppost. The range of the i'th lamp with position `lampPositions[i]` is equal to `lightingRange[i]`. Each lamp covers a certain range, and the ranges can overlap. Due to overlapping ranges, power is being wasted. The goal is to remove extra lampposts so that power is saved. Find the maximum lampposts which can be removed.

Example: Given input: `lampPositions = [-9, -6, -5, -2, 1, 3, 4, 12]` and `lightingRange = [5, 3, 9, 1, 1, 4, 2, 3]`. Output: 5.

The candidate considered approaches like overlapping intervals or sliding window but was unable to solve the problem. This was the candidate's first Tier-1 company interview, and they were rejected due to this question.