This is a write-up of the DE Shaw Online Assessment for the SDE Intern 2026 role. The assessment consisted of 3 DSA problems with separate timers.
FORMAT
- 3 programming questions
- Separate timers for each question:
- Q1: 15 minutes
- Q2: 35 minutes
- Q3: 40 minutes
Questions had to be attempted in order. No ability to return to a previous question. Any unused time from one question could not be carried forward.
Problem 1: Good Trace(15 min)
A string is called a good trace if it can be generated using the following rules:- - The empty string is a good trace. - If t is a good trace and c is any lowercase English letter, then adding c to both the beginning and the end of t also produces a good trace. - Example: — "" → "aa" — "bb" → "cbbc" - The concatenation of two good traces is also a good trace. You are given m strings (m ≤ 10, total length up to 10^5). For each string, determine whether it is a good trace.
Approach :
A simple stack-based solution is sufficient.
The idea is to simulate the recursive construction of valid traces. By processing the string appropriately and removing matching enclosing characters, the validity of the string can be determined efficiently.
Problem 2: Number of Subsequences (35 mins)
Given:
A binary string s (n ≤ 2 × 10^5) An integer k
Find the number of subsequences whose binary representation equals k. (preceding zeroes also)
Leading zeros are allowed.
Example: s = "010" k = 2 Binary representation of 2 is "10".
Valid subsequences: "10" , "010"
Hence the answer is 2.
Approach :
This is a dynamic programming problem.
Use a 2D DP over the string and the matched prefix/state of the binary representation of k.
The main observation is that since leading zeros are permitted, every occurrence of the required representation can additionally be prefixed by any number of skipped zeros. Therefore, after computing the DP transitions, the final answer is obtained by summing over all valid DP states corresponding to the completed representation while accounting for preceding zeros.
Problem 3: Helper Banks (40 mins)
You are given a weighted tree with:
n ≤ 1000 nodes n − 1 weighted edges An integer k
For every unordered pair of distinct nodes (a, b), consider the unique path between them.
A node h is called a helper node for the path if:
h lies strictly between a and b (h ≠ a and h ≠ b) The total weight of the path from a to b is divisible by k
For every node, compute how many different paths consider it a helper node.
Return a vector where the i-th element represents the number of paths for which node i is a helper.
Approach :
Since n ≤ 1000, a DFS-based solution is sufficient.
For every source node, perform DFS to traverse the tree while maintaining:
the accumulated path weight, the parent to reconstruct the path if required.
For every valid destination, check whether the total path weight is divisible by k. If so, increment the answer for every intermediate node on that path.
Summary :
Q1 tested stack-based string validation, Q2 required dynamic programming to count binary subsequences (including leading zeros), and Q3 involved DFS on a weighted tree to count intermediate helper nodes on paths whose total weight is divisible by k.
Your Q3 solution is $$$O(n^3)$$$ as you've described it but it can be improved to $$$O(n^2)$$$ by doing a subtree sum over binary values. I think this can be improved to $$$O(n\log n)$$$ using centroid trees: for each centroid subtree with centroid $$$c$$$, track a hash table $$$\text{ht}$$$ mapping weight-sum-to-centroid mod $$$k$$$ to vectors of nodes+counters in DFS order. For each child subtree of $$$c$$$, do a DFS where we increment the end counter of $$$\text{ht}\left[ k-w_{x,c}\right]$$$, then do a second DFS appending $$$x$$$ to $$$\text{ht}\left[ w_{x,c}\right]$$$. After all that, do a suffix sum over each vector, store the resulting values, and do a subtree sum over that.