Title: PhonePe | SDE-1 | OA Experience | August 2026

Status: Completed (Solved 1 fully, 2 partially)
Outcome: Not shortlisted for interview
Format: 4 Questions

Detailed Overview & Problem Formulations

Below are detailed descriptions of the problem logic abstracted from the original test .

Q1. Sequential Task Assignment with Context Switching Cost

• Problem Logic: You have a sequence of K total task slots. For each slot i, you can choose to work on a task from Startup A or Startup B, each yielding a specific payout.
• Constraints:
  1. You can complete at most M tasks in total.
  2. Switching from A to B (or B to A) between consecutive completed tasks requires 1 full idle day (a "context-switching" penalty S).
  3. The total days consumed calculated as (Tasks completed M) + (Switches S) cannot exceed N days (M + S <= N).
• Goal: Determine the choice sequence that maximizes total payout without exceeding the day limit N.

Q2. Substring Count Excluding Specific Subsequences

• Problem Logic: Given a master string S (representing a sequence) and a smaller target pattern string T, you need to evaluate all contiguous substrings of S.
• Conditions: A contiguous substring is invalid if string T appears inside it as a subsequence (meaning the characters of T appear in that substring in exact relative order, though not necessarily adjacent).
• Goal: Count the total number of non-empty continuous substrings of S that do not contain T as a subsequence. Substrings starting or ending at different indices are counted separately even if their text is identical.

Q3. Constrained Jump Sequences to a Target Point

• Problem Logic: There are N discrete locations along a straight line, numbered 1 to N. You start at location A and need to make a sequence of exactly K consecutive jumps. A fixed spotlight is stationed at location B.
• Movement Rules:
  1. You cannot land on the same location twice in a row (X != Y).
  2. For every jump from current position X to next position Y, the distance of the new jump must be strictly less than your current distance to B. Formally: |X - Y| < |X - B|.
• Goal: Compute the total number of valid sequences of K jumps modulo 10^9 + 7.

Q4. Advanced Graph / Combinatorics

• Did not attempt/read in detail due to time constraints.

Key Takeaways

• Reading Complexity: The original problems featured extensive story elements and real-world background narratives. Stripping away the narrative to find the core DP state transitions quickly is key to finishing within time.
• Core Topics: Dynamic Programming (State Compression & Constrained Transitions), String Subsequence Properties, and Combinatorial Path Counting.

Note: The actual problem statements used fictional scenarios. The explanations above reframe the underlying algorithmic requirements to align with posting guidelines.