This is a write-up of the DE Shaw Online Assessment for the SDE Intern 2025 role. The test consisted of 3 DSA problems with the following structure:

Format

3 programming questions

Separate timers for each question:

Q1: 20 minutes Q2: 30 minutes Q3: 30 minutes

• Questions had to be attempted in order.
• No ability to return to a previous question.
• Time left on a previous question could not be transferred to the next.

Problem 1: Divisible Substrings (20 mins)

Given a string s of lowercase English letters (length ≤ 1000), map each character c to a value using:

val(c) = (c - 'a' + 1) / 3 + 1

For example:

'a', 'b' → 1 'c', 'd', 'e' → 2 ... 'x', 'y', 'z' → 9

Count the number of substrings such that the sum of character values in the substring is divisible by the length of that substring.

A brute-force O(n²) approach, utilizing a nested loop, is effective.

Problem 2: Airport Scanner Simulation (30 mins)

Given two arrays:

time[i]: time when the i-th person wants to access the scanner (sorted) direction[i]: 0 if arrival, 1 if departure

Only one person can use the scanner at a time. At any given time, the priority rules are:

• If the scanner was used in the previous second, the same direction gets preference.
• If unused in the previous second, departure (1) gets preference.

Determine, for each person (in input order), the exact time they pass through the scanner.

This is a simulation problem. Maintain two queues (one for arrivals, one for departures), both with (index, time) pairs. Process second-by-second, applying the direction rules carefully. Track the scanner's usage state at each second.

Problem 3: Nearest Sensor in Row or Column (30 mins)

Given n sensors (n ≤ 10⁵), each with:

A unique string identifier

An (x, y) coordinate with 0 ≤ x, y ≤ 10⁸

You are given q queries, each being a string ID of a sensor. For each query, report the nearest sensor in the same row (same y) or the same column (same x). If there are multiple such sensors at the same distance, choose the one with the lexicographically smallest ID. If there are no such sensors, return "NONE".

The approach was as follows:

• Group all sensors by their x-coordinate and y-coordinate.
• For each group (i.e., each row or column), sort the sensors by their other coordinate.
• Store these sorted vectors of (coordinate, ID) pairs.
• For each sensor, check its position in its row and column group, and examine only the immediate neighbors (i.e., previous and next in the sorted list).
• Compare the distances and pick the closest sensor. In case of a tie, choose the one with the smaller ID.

Summary Q1: Straightforward brute-force or prefix sum-based substring counting. Q2: Simulation-heavy with direction-based rules and careful time tracking. Q3: Coordinate grouping with adjacent comparisons in sorted row/column lists.

The problems increased in complexity, testing implementation ability, data structure usage, and simulation accuracy under time constraints.