I recently interviewed with Kivi Capital for the Quant Researcher role. The first round lasted around 60 minutes and consisted of one algorithmic problem followed by several conceptual computer science questions.
Question 1 – Shipment Delivery Optimization
You need to deliver N shipments. For each shipment, you may hire either Vendor X or Vendor Y.
-
Vendor X delivery times:
X = [x₁, x₂, …, xₙ] -
Vendor Y delivery times:
Y = [y₁, y₂, …, yₙ]
Constraints:
-
Vendor X processes shipments sequentially
→ total time = sum of delivery times assigned to X -
Vendor Y processes shipments in parallel
→ total time = maximum delivery time among shipments assigned to Y
Goal: Minimize the total completion time for delivering all shipments.
Let:
- Shipments assigned to X → indices (i₁, i₂, …)
- Shipments assigned to Y → indices (j₁, j₂, …)
Then:
- Time taken by X = sum(x[i₁], x[i₂], …) = t₁
- Time taken by Y = max(y[j₁], y[j₂], …) = t₂
Total completion time:
max(t₁, t₂)
Approach
-
If xᵢ > yᵢ, assigning that shipment to Vendor Y is always beneficial since Y completes it faster.
-
For cases where xᵢ < yᵢ, the choice is non-trivial because:
- Assigning to X increases the sequential sum
- Assigning to Y increases the maximum parallel time
-
For such shipments, create pairs (yᵢ, xᵢ) and sort them by yᵢ.
-
Consider partition points in this sorted list:
- Shipments up to index k are assigned to Vendor Y
- Remaining shipments are assigned to Vendor X
-
Compute:
- Vendor Y time = yₖ
- Vendor X time = suffix sum of x-values after k
-
Track the minimum value of:
max(yₖ, suffix_sum_x)
Time complexity: O(N log N) due to sorting.
Conceptual / CS Questions Asked
After the algorithmic question, the interviewer asked several conceptual questions:
- Difference between Multithreading and Multiprocessing
- What is a Semaphore?
- What is a Mutex Lock?
- Difference between Semaphore and Mutex
- Why do we need Multithreading if we have Async/Await? (use cases)
- Difference between Virtual Memory and Physical Memory
- What is a Page Table?
