INFOSYS DSE — COMPLETE TOPIC LIST (ONLY WHAT YOU NEED)

Difficulty: Easy → Medium

Coding round usually has 2 Medium questions or 1 Easy + 1 Medium.

🟢 1. Programming Basics (MUST KNOW)

 Input/Output

 Loops, Conditions

 Functions

 Recursion basics

 Time complexity (Big-O notation)

🟢 2. Core DSA (MAIN PART for DSE)

Arrays

 Traversal, prefix sums

 Kadane’s algorithm

 Two pointers

 Sliding window (basic-medium)

Strings

 String manipulation

 Frequency counting

 Anagram checks

 Substrings & subsequences (basic)

HashMap / Dictionary

 Counting frequency

 Storing indices

 HashMap of lists

 Duplicate detection

 Pair sum using hashmap

Sorting

 Built-in sort

 Custom comparator (basic)

  Sorting + two pointers combo

🟦 3. Medium DSA (Most important for DSE test)

Binary Search

 Standard binary search

 First/Last occurrence

 Binary search on answer (basic)

Recursion

 Print subsequences

 Backtracking basics

Stacks & Queues

 Valid parentheses

 Monotonic stack basics

 Next greater element

Basic Graphs

 BFS

 DFS

 Adjacency list build

No need for DP on trees (only SP needs that)

Trees

 Level order traversal

 DFS on tree (simple)

 Parent-child traversal

🟧 4. Math + Number Theory (Light Version)

Nothing too complex.

Learn only:

 GCD (Euclidean algorithm)

 LCM

 Modulo arithmetic

 Prime checking for small values

  Factorization (only for numbers ≤ 10⁵)

🟣 5. Basic Dynamic Programming (DP)

Only foundational DP — very small set:

Study these:

 Fibonacci (DP)

 0/1 Knapsack (basic understanding)

 Subset sum DP

 LIS (Longest Increasing Subsequence) — very important

 DP on 1D and 2D arrays

 Memoization basics

DSE will NOT ask:

✘ Tree DP
✘ XOR DP
✘ Complex DP transitions
✘ Bitmask DP

Those are SP-only.

🔵 6. Bit Manipulation (Basic)

 XOR basics

 AND, OR

 Bit shifts

 Properties of XOR for pair problems

NO need for:
✘ Advanced bit DP
✘ Binary trie
✘ XOR subset DP
(These belong to SP.)

🔥 7. Practice Question Categories (VERY IMPORTANT)

DSE typically asks:

✔ Array + hashmap question

✔ String + hashing question

✔ Sliding window / two-pointer question

✔ Simple tree BFS/DFS question

✔ DP medium question (LIS or subset sum level)

No complicated SP-level logic.

🎯 COMPLETE FINAL CHECKLIST (LEARN ONLY THESE FOR DSE)

✔ Arrays

✔ Strings

✔ Hashmaps

✔ Sorting

✔ Two pointers

✔ Sliding window

✔ Stack/Queue

✔ BFS/DFS basics

✔ Simple Tree traversal

✔ Recursion

✔ Basic DP (LIS, knapsack, subset sum)

✔ Basic bitwise (XOR, AND, OR)

✔ GCD, LCM

That’s it. COMPLETE.

🔥 INFOSYS SP — COMPLETE TOPIC LIST (ONLY WHAT YOU NEED)

Difficulty: Medium → HARD → VERY HARD

🟢 1. Core Medium DSA (Foundation for Hard SP Problems)

These MUST be strong:

Arrays (Advanced usage)

 Prefix sum, suffix sum

 Difference array technique

 Counting using hashmap

 Coordinate compression (important!)

Strings

 Rolling hash basics

 Substring hashing (optional)

 Pattern matching intuition (for complex tree patterns)

HashMap / HashSets

 Map of maps

 Hashing pairs, vectors

 Custom Hash functions

 Frequency maps

 Prime factor → mask mapping

Sorting (Advanced use cases)

 Sorting with custom key

 Sorting nodes/queries

 Multi-parameter sort

🔵 2. HARD Number Theory (REQUIRED FOR SP)

Used in Tree Beauty Problem + GCD question.

✔ Prime Factorization (Fast)

 Trial division up to sqrt

 Precomputation for factorization

 Factorization for numbers up to 1e9

✔ Square-free Form / Parity Vector (VERY important)

 Parity of prime exponents

 Reduce number → square-free kernel

 Perfect square pair logic using parity map

(core idea for Q1: Tree Beauty)
✔ GCD Deep Concepts

 GCD of full array

 GCD under updates

 GCD properties for subsequences

 When gcd(a, b, c) = p possible

✔ Modular Arithmetic

 Modulo 1e9+7 everywhere

 Modular addition

 Modular multiplication

🟣 3. Graphs + Trees (MAIN SP CONTENT)

SP loves tree-based heavy logic.

Your PDF has 3 tree problems.

Basic Tree Concepts

 Adjacency list

 DFS

 BFS

 Depth, parent, children

Subtree Algorithms

 Subtree aggregation

 Frequency merging

 Using returned maps from children

 Euler tour (optional but useful)

Tree DP (Important)

 DP on rooted trees

 Merging children maps

 DP returning multiple values (struct)

Tree Matching Concepts

In hardest problem:

 Maximum matching

 Independent edge flips (no two share a node)

🔥 4. Dynamic Programming (HARD LEVEL)

SP requires deep DP understanding:

✔ DP + XOR

Used in problem 3 (Longest Non-Decreasing XOR Subsequence)

 XOR state DP

 DP with (index, last_value, xor_value)

 DP compression

 State pruning

✔ DP on Conditions

 Non-decreasing subsequence DP

 DP with constraints

 DP with multi-state transitions

✔ Tree DP (Advanced)

 DP on root-to-leaf paths

 DP where children combine results

 DP + pattern matching

 DP + flips with cost minimization

(problem 4 in PDF)

🔴 5. Bit Manipulation (Advanced Usage)

Not basic level.

Need:

 XOR properties

 XOR with DP

 Bitmask representation

 Storing factor parity in bitsets

 Using XOR to merge states

 Using AND/OR/XOR for transitions

⚫ 6. Hard Algorithms and Techniques

These separate SP from DSE.

Frequency Merging on Trees (Very Important)

Used in Tree Beauty Problem:

 Each node returns a hashmap

 Combine children's maps

 While combining: count good pairs

 Maintain reduced form of factors

Segment Tree / Fenwick Tree Basics (Light)

Only for:

 Range gcd concept

 Updates + tracking gcd

Not full segment tree implementation.

Pattern Matching on Trees (Hardest Topic)

For the Complex Query:

 Root-to-leaf path extraction

 Matching query string q

 Choosing edge flips

 dp[node][pattern_index][flip_used]

Min-Cost Optimization

 Maximize natural paths

 Minimize cost among those

 DP to compute best cost

🚀 7. Problem Patterns You MUST MASTER for SP

SP test revolves around these:

✔ Perfect square pair counting (number theory + trees)

✔ GCD maintenance under updates

✔ Subtree DP merging

✔ XOR DP + non-decreasing subsequences

✔ Pattern matching on trees

✔ Edge flip matching (tree matching)

✔ Multi-state DP with cost optimization

⭐ FINAL — SUPER CLEAN CHECKLIST FOR SP (MEMORIZE THIS)

DSA

 Trees (advanced)

 Graphs

 HashMaps (nested maps)

 Sorting (custom rules)

Math

 Prime factorization

 Square-free forms

 GCD advanced

 Modular math

DP

 XOR DP

 DP with constraints

 Tree DP

 DFS + DP merging

Bitwise

 XOR transitions

 Bitmask DP

Advanced Concepts

 Frequency merging

 Tree pattern matching

 Tree matching (independent edges)

 Min-cost DP

INFOSYS SP + DSE — COMMON SYLLABUS

Difficulty: Easy → Medium

🟢 1. Programming Fundamentals
✔ Input/Output
✔ Loops
✔ Conditionals
✔ Functions
✔ Recursion basics
✔ Time & Space Complexity (Big-O)

🟢 2. Arrays (Very Important)

✔ Traversal
✔ Prefix sum
✔ Two pointers
✔ Sliding window (easy–medium)
✔ Maximum subarray (Kadane)
✔ Sorting + searching in arrays
✔ Partitioning, merging

🟢 3. Strings

✔ Basic string manipulation

✔ Frequency counting
✔ Palindrome checks
✔ Anagram detection
✔ Substrings vs subsequences
✔ Basic pattern matching

🔵 4. Hashing / HashMaps

✔ Count frequency
✔ Map of key → list
✔ Check duplicates
✔ HashMap for pair sums
✔ HashMap + prefix logic
✔ Using sets to track visited

🔵 5. Searching + Sorting

✔ Binary search
✔ First/last occurrence
✔ Sorting arrays of pairs
✔ Two pointers on sorted arrays

🔵 6. Stacks & Queues

✔ Valid parentheses
✔ Next greater element
✔ Monotonic stack (basic)
✔ Queue operations
✔ BFS using queue

🟣 7. Graphs (Basics Only)

✔ Adjacency list
✔ BFS
✔ DFS
✔ Visiting all components
✔ Simple tree traversal (DFS/BFS)

(SP goes way deeper, but these basics are common.)

🟣 8. Trees (Basics Only)

✔ Tree representation from parent array

✔ DFS traversal
✔ Preorder / Postorder basics
✔ Level order traversal (BFS)
✔ Subtree size (simple counting)

(DSE stops here, SP goes into tree DP, but the basics overlap.)

🟠 9. Mathematics / Number Theory (Basic Level)

✔ GCD (Euclidean)
✔ LCM
✔ Prime checking
✔ Factorization (basic)
✔ Modular arithmetic basics

(SP requires advanced NT, but these are common.)

🟠 10. Bit Manipulation (Basic)

✔ XOR basics
✔ AND, OR
✔ Bit properties
✔ Swapping using XOR
✔ Count set bits

🔴 11. Dynamic Programming (Foundation Level)

✔ 1D DP: Fibonacci / climbing stairs
✔ 2D DP basics
✔ Subset sum DP
✔ Knapsack basics
✔ LIS (Longest Increasing Subsequence)

(SP goes into DP+XOR, bitmask DP, tree DP. But these are common basics.)

🔥 12. Classic Medium-Level Problems (Common to Both)

Both SP and DSE get questions from these categories:

✔ Arrays + HashMap

(e.g., subarray sum = k, longest unique substring)

✔ Strings + Hashing

(e.g., anagrams, character windows)

✔ BFS/DFS

(e.g., connected components, tree traversals)

✔ DP Medium

(e.g., LIS, subset sum)

✔ Greedy Techniques

(e.g., activity selection, interval scheduling)

⭐ FINAL — COMMON TOPIC MASTER LIST for SP + DSE

Memorize this checklist:

1. Arrays

2. Strings

3. Hashing

4. Two pointers + sliding window

5. Sorting + searching

6. Stacks + queues

7. BFS + DFS

8. Basic tree traversal

9. Basic number theory (GCD, primes)

10. Basic bitwise ops

11. Basic DP (LIS, knapsack, subset sum)

These topics appear in both roles.

Variables, loops, functions

Arrays & Strings

Recursion
Time complexity (BIG-O)
Input/output formatting

DS

Arrays & Prefix logic

Hash Map / Dictionary ← heavily used in Tree Beauty & GCD problems

Stacks & Queues

2D arrays & sliding window

Trees & Graphs

1. adjacency list

2. DFS, BFS

3. subtree queries

4. storing parent/child

Binary Search

Heaps / Priority Queues (optional but useful)

🔥 High-priority algorithms:

 Prefix sum

 GCD / LCM

 Fast prime factorization

 Bitwise operations (XOR, AND, OR)

 DP basics
  Sorting (all techniques + custom comparators)

🔥 For their PDF questions specifically:

 Perfect square detection using prime factorization parity

 Hash map frequency counting

 DFS subtree traversal

 Maintaining GCD during updates

 XOR logic with DP (for the subsequence problem)

DSA Practice Level-wise

You should practise in this order:

⭐ Easy

 Two sum

 Maximum subarray (Kadane)

 GCD problems

 Frequency maps

 Simple tree DFS

⭐ Medium

 Subtree queries

 XOR queries

 Recursion + memoization

 Bitmasking basics

 Graph traversal

 Sliding window medium-level questions

⭐ Hard

 DP with bitwise

 Segment tree / Fenwick tree (only basic understanding)

 Tree flattening (Euler tour)

Q1: Tree Beauty Problem

 DFS to get subtree nodes

 Prime factorization

 Using hash map to count perfect-square compatible factor signatures

 Summation over all nodes

✔ Q2: Good Subsequence with GCD

 Keep track of how many elements divisible by p

 Maintain global GCD

 Handle updates dynamically

✔ Q3: Longest Non-Decreasing Subsequence with XOR

 DP + XOR

 Binary constraints (N ≤ 1000, M ≤ 500)

✔ Q4: Hard Tree Pattern Matching (advanced DP on trees)

These are not beginner questions – they test logic + DS mastery, not aptitude.