DE Shaw 15 Problems - Python Solutions with Detailed Logic
1. Product of Array Except Self
Problem Statement
Given an integer array nums, return an array answer such that answer[i] is equal to the
product of all elements except nums[i]. You cannot use division and must solve it in O(n)
time.
Concepts in Python
• Lists
• Prefix and suffix computation
• In-place updates
Logic / Intuition (Python)
We compute the prefix products and suffix products in two passes. The first pass stores
prefix products directly into the result array. The second pass uses a suffix accumulator,
multiplying it into result[i] in reverse order. This gives O(n) time and O(1) extra space.
Works naturally with zeros.
Python Code:
def product_except_self(nums):
n = len(nums)
result = [1] * n
for i in range(1, n):
result[i] = result[i - 1] * nums[i - 1]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
Explanation
Two passes – left to right for prefix, right to left for suffix. Uses O(1) space besides output
array.
2. Job Scheduler (Weighted Interval Scheduling)
Problem Statement
Given N jobs each with start, end, and profit, select a set of non-overlapping jobs to
maximize total profit (Weighted Interval Scheduling).
Concepts in Python
• Dynamic Programming
• Sorting
• Binary Search (manual)
Logic / Intuition (Python)
We sort jobs by end time. dp[i] stores the max profit up to job i. For each job, find last non-
conflicting job using binary search. Include or exclude each job and take the max.
Complexity O(n log n).
Python Code:
def max_profit(jobs):
[Link](key=lambda x: x[1])
n = len(jobs)
dp = [0] * n
dp[0] = jobs[0][2]
def last_non_conflict(i):
lo, hi = 0, i - 1
target_start = jobs[i][0]
while lo <= hi:
mid = (lo + hi) // 2
if jobs[mid][1] <= target_start:
if mid == i - 1 or jobs[mid + 1][1] > target_start:
return mid
lo = mid + 1
else:
hi = mid - 1
return -1
for i in range(1, n):
incl = jobs[i][2]
l = last_non_conflict(i)
if l != -1:
incl += dp[l]
dp[i] = max(dp[i - 1], incl)
return dp[-1] if dp else 0
Explanation
Sort jobs by end time. dp[i] stores max profit using jobs[0..i]. Manual binary search finds last
non-overlapping job. Transition chooses between including or excluding current job.
3. Edit Distance (Minimum Operations)
Problem Statement
Given strings word1 and word2, compute minimum number of insertions, deletions, or
replacements to convert word1 to word2.
Concepts in Python
• 2D Dynamic Programming
• String manipulation
Logic / Intuition (Python)
We build a DP table dp[i][j] = min operations to convert word1[:i] to word2[:j]. Base
rows/columns handle insertions/deletions. If characters match, inherit dp[i-1][j-1], else
take 1 + min(replace, insert, delete). Time O(m*n).
Python Code:
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete
dp[i][j - 1] # insert
)
return dp[m][n]
Explanation
DP computes edit distance bottom-up. Each cell considers replace, delete, insert. Uses
nested loops for O(m*n) time.