Approach to DSA Questions in Coding Round

1. Read constraints before coding

Constraint Meaning

N <= 10^3 O(N^2) may pass

N <= 10^5 Need O(N log N) or O(N)

Need math, greedy, binary search, or recursion with

N <= 10^9
memorization (DP)

Grid N*M <= 10^6

BFS/DFS is usually expected
approx.

DFS preprocessing, subtree idea, LCA, or DSU-on-tree style

Tree + queries
thinking

Dynamic components DSU is usually the first thought

2. Check out the brute-force solution in mind. Will it fail? If yes, what data
structure avoids repeating work?
3. Convert the story in the problem statement into a standard DSA pattern
(specifically for medium and hard level questions).

Sample Sheet 1 — Part 1

Problem What the story is Standard DSA Direction of solution
story/title really saying pattern
You can repeatedly
choose food items.
Each repeated Greedy + priority “I need to pick the best M
purchase gives queue / binary decreasing rewards
Food Stamps e iciently. Cannot
decreasing value. search on
Maximize total taste contribution simulate if M is huge.”
points under meal
limit.
Maximum “Choose a subarray, then
Swap at most k useful
subarray sum + improve it by replacing
MSS with pairs to maximize
optimization / DP small values inside with
Swaps maximum subarray
/ sorting inside- large values outside.”
sum.
outside values
 Approach to DSA Questions in Coding Round
Problem What the story is Standard DSA Direction of solution
story/title really saying pattern
“This is not just minimum
Assign keys to locks on cost. I must satisfy a
the right, each parity condition.” The
Matching-like paper explicitly lists
assignment has cost.
selection + candidate key-lock edges
Lock & Parity Final chosen set must
greedy/parity by cost and marks them
satisfy even-cost
constraint odd/even, showing why
assignments ≥ odd-
cost assignments. the cheapest odd edges
may be invalid.

“Convert undirected
Choose a simple path edges into valid
in graph. Layers along transitions based on layer
Layer-Split order, then maximize path
path must be non- Graph DP /
Path
decreasing. Moving to a constrained path score.” The sample
Maximization explains path value as
higher layer gives optimization
with Penalties node value sum minus
penalty. Maximize
value minus penalty. squared layer-jump
penalties.

Sample Sheet 2 — Part 2

Problem What the story is Standard DSA Direction of solution

story/title really saying pattern
“Each update is linear in
index. I need to update
For each query [l, r, ranges without visiting
Arithmetic Di erence array
x, y], assign values x, every element.” The
Progression / range update
x+y, x+2y... to that question gives repeated
Range with arithmetic
range. Finally find range assignment queries
Assignment progression
total array sum. and asks the final sum
modulo 10^9+7.

For every index, Dynamic “At every step I have

X, Y, Z choose one of three programming / choices and limited
Operations operations. Some resource resources. This is a DP
operations reduce allocation DP state problem.” The
 Approach to DSA Questions in Coding Round
Problem What the story is Standard DSA Direction of solution
story/title really saying pattern
resources X, Y, Z; statement gives three
maximize final sum. possible operations for
each i, including
subtracting B[i] or
decreasing pairs among X,
Y, Z.

“Subtree means DFS

For each query node interval. Ancestor-
s, choose maximum descendant condition
nodes from its means selected nodes
subtree such that Tree DFS + must lie on one root-to-leaf
Beautiful Set path.” The hard problem
selected nodes form subtree queries
in Tree defines beautiful sets using
an ancestor- + color tracking
descendant chain di erent colors and
and have distinct ancestor relationship, then
colors. asks subtree query
answers.

Some tips:
“Range query? Use prefix/di erence/segment tree.”
“Repeated choice with limited variables? Use DP.”
“Tree + subtree query? Use DFS preprocessing.”

Sample Sheet 3 — Part 3

What the story is Standard DSA Solution approach

Problem story/title
really saying pattern
“There are 10^5
Two query types: queries, so direct range
Segment tree / lazy update will fail.” The
Range Replace + update a range
propagation / paper presents Type 1
Range Sum using a formula
formula-based range-replacement and
Queries and answer range
range update Type 2 range-sum
sum.
queries.
 Approach to DSA Questions in Coding Round
What the story is Standard DSA Solution approach
Problem story/title
really saying pattern
“At most k distinct
Find maximum means sliding window.
subarray sum Negative values mean
Sliding window + answer can be zero.”
Maximum Sum where number of
hashmap + max The problem defines a
Good Subarray distinct elements
sum handling good subarray by
is at most k. Empty
subarray allowed. distinct count and asks
maximum sum.

Choose initial oil

quantity so that
buy/sell Greedy simulation “This is like keeping a
Oil Tank operations cause / prefix balance / running level between 0
Disturbance minimum boundary and capacity C.”
disturbance when condition
tank becomes
empty/full.
Reduce number
using allowed “Large N means I
Greedy / recursion
operations: cannot build DP up to N
Reduce Soldiers to with memoization /
subtract 1, reduce if N is huge. Think
1 shortest path on
by half, reduce by recursively.”
number states
two-thirds. Find
minimum moves.
Cells marked A
spread to adjacent “This is rotten oranges /
E cells every Multi-source BFS infection spread
Grid Invasion problem.” Start BFS
second; blocked on grid
cells cannot be from all A cells.
crossed.
Divide array into “Consecutive floors
contiguous teams. MEX + partition DP means subarrays. First
Expert Number
Each team value is / greedy missing skill means
Partition
MEX. Maximize segmentation MEX.”
total MEX.
Covered Ranges in Add edges DSU + maintaining “Dynamic connectivity
Connected dynamically; for component means DSU. Covered
Component query, find number intervals/ranges ranges means count
 Approach to DSA Questions in Coding Round
What the story is Standard DSA Solution approach
Problem story/title
really saying pattern
of continuous breaks between sorted
ranges in the node labels.” The
connected statement defines Type
component of a 1 edge addition and
node. Type 2 component-
range query.

Partition array into “Maximum subset XOR

subarrays of means linear basis.
length at least K. Partitioning means DP.”
Array Partition with Beauty of subarray DP partition + XOR The problem defines
XOR Beauty is maximum basis subarray beauty as
subset XOR. maximum bitwise XOR
Maximize total of a subset.
beauty.
Construct a
directed graph “Permutation usually
from a Permutation graph means cycles. First
Permutation
permutation and / cycles / graph identify cycle structure
Directed Graph
parameter m; traversal before coding.”
answer graph-
based quantity.

Some tips:
“Array + range query” → segment tree/di erence array
“Subarray with distinct limit” → sliding window
“Grid spreading” → BFS
“Dynamic connected components” → DSU
“Tree/subtree” → DFS
“XOR maximum” → bit manipulation/XOR basis
Story to DSA tips
Story words in question Usually means

“subarray”, “at most k distinct” Sliding window

Segment tree / lazy propagation / di erence

“range update”, “range sum query” array
 Approach to DSA Questions in Coding Round

Story words in question Usually means

“spread every second to adjacent BFS / multi-source BFS

cells”
“connected component after adding DSU
edges”
“tree rooted at node 1”, “subtree DFS traversal / Euler tour
queries”

“partition into consecutive groups” DP on array / greedy segmentation

“maximum subarray sum” Kadane / DP

“minimum moves to reduce number” Greedy / recursion / BFS over states

“maximum subset XOR” XOR basis

“permutation graph” Cycle decomposition

“choose one operation at every step” Dynamic programming

“capacity, empty, full, disturbance” Simulation + prefix balance

Plan to prepare

Step 1.

Topic Must revise

Arrays prefix sum, di erence array, Kadane

Sliding window at most k distinct elements

HashMap frequency counting

BFS/DFS grid BFS, tree DFS

Greedy sorting, priority queue

Modulo 1e9+7, negative modulo handling

 Approach to DSA Questions in Coding Round
Step-2

Topic Why important

DP Many medium problems are decision-based

DSU Dynamic graph/component questions appear

Segment tree basics Range update/range query appears repeatedly

Bit manipulation XOR-based questions appear

Tree DFS Hard problems often use subtree/ancestor logic