Syllabus of the Course:

Subject: Advanced Data Structures Subject Code:22CS036

Topic(s) Lectures Weightage
Arrays and Advanced Array Algorithms -1: Frequency Arrays; Prefix Arrays; Two pointers
and problems related to above mentioned topics:
• Checking if two strings are anagrams.
• Finding the mode of an array in constant time after pre-processing.
• Finding the sum of elements within a given range. 6 6%
• Problems related to continuous subarrays, like finding maximum or minimum sums.
• Finding all pairs that sum up to a given value.
• Moving two pointers in opposite directions to find palindromes, meet in the middle,
etc.

Arrays and Advanced Array Algorithms -2: Advance Problems on Sorting:

• Sorting an array to find the kth smallest or largest element.
• Given an array with values representing colors (often {0, 1, 2} for three colors), sort
4 6%
them in place.
• In a sorted array, find two numbers that add up to a specific target. This problem can
be solved using two pointers after sorting.

Advanced String Algorithms: Implementation Problems on Strings, Two pointers in Strings

will be discussed and problems based on that.
• Check if a given string is a palindrome by ignoring non-alphanumeric characters and
case.
• Given two strings, find the smallest substring in the first string that contains all
characters of the second string. 6%
• Determine if a string can be constructed by repeating a substring.
• Finding exact matches of short strings within larger texts.
• Compress a string by replacing sequences of repeating characters with the character
followed by the count (e.g., "aaabb" becomes "a3b2").
• Basic Calculator: Parse and evaluate a simple arithmetic expression. 8
Sliding Window: Advance Problems on Sliding Window
• Find the longest substring where all characters are unique using The sliding window
approach
• Counting elements that satisfy a condition within a window (e.g., number of distinct 6%
characters in a substring).
• Given an array of integers and an integer K, find the maximum sum of a subarray of
length K. 6
Recursion: Basics of Recursion, basic problems on recursion to have better understanding of
the call stack, Types of Recursion. Problems:
• Given a sorted array, find the position of a target element using recursion.
• Generate all permutations of a string.
• Towers of Hanoi
Recursion Backtracking: Implementation based Problems on recursion will be discussed in a
thorough manner with call stacks, Introduction to Backtracking and problems on backtracking
15%
to get the flow of it:
• Given a set of distinct integers, generate all possible subsets (the power set).
• Place n queens on an n x n chessboard so that no two queens threaten each other.
• Given a grid where some cells are passable and others are blocked, find all paths for a
rat to move from the top-left to the bottom-right cell.
• Given an array of integers and a target, find all unique combinations where the sum
equals the target. 12
Advance problems on backtracking: Recursion on Matrix: Discussion on how recursion and
backtracking are used in general to solve problems on matrix/grid.
• Given a 2D grid of letters and a word, determine if the word can be constructed from
adjacent cells (horizontally or vertically).
• In a grid with obstacles, find the number of unique paths from the top-left to the
bottom-right corner.
• Solve a 9x9 Sudoku board by filling empty cells so each row, column, and 3x3 grid
contains unique digits from 1 to 9.
Linked List: Interview Based Problems on LL.
• Detect if a linked list has a cycle and remove it if one exists.
• Given two sorted linked lists, merge them into a single sorted list. 6%
• Determine if a linked list is a palindrome.
• Remove the N-th node from the end of a list in one pass. 4
Stacks: Interview Problems Based on Stacks.
• Given a string containing (, ), {, }, [, and ], determine if the string contains valid
parentheses.
• Design a stack that supports push, pop, top, and retrieving the minimum element in
constant time. 6%
• Given an array representing the heights of bars in a histogram, find the area of the
largest rectangle that can be formed.
• Given a circular array of integers, find the next greater element for each element. If no
such element exists, return -1. 8
Binary Trees and BST: Standard Problems on Binary Trees and Binary Search Trees;
Interview Problems Based on Trees.
• Given the root of a binary tree, return the inorder traversal of its nodes' values.
• Return the level order traversal of a binary tree's nodes.
• Find the maximum depth of a binary tree.
10%
• Given a binary search tree (BST) and two nodes, find their lowest common ancestor
(LCA).
• Return all root-to-leaf paths in a binary tree.
• Given preorder and inorder traversal of a tree, construct the binary tree.
• Find the k-th smallest element in a BST. 8
Hash maps : Advance Hashing Techniques, Interview Problems based Hashing etc.;
• Given a string and an integer K, find the length of the longest substring with at most K
distinct characters.
• Given two strings, s and t, find the smallest substring in s that contains all characters
6%
in t.
• Given a string, find the length of the longest substring without repeating characters.
• Given an array of integers and a target integer k, find the total number of subarrays
whose sum equals k. 8
Priority Queue and Greedy Algorithms: Advance Problems on Heaps. Implementation and
Advance Problems on Greedy.
• Find the kth largest element in an unsorted array.
• Given k sorted linked lists, merge them into one sorted list.
• Given a non-empty array of integers, return the k most frequent elements.
• Given a set of activities with start and finish times, select the maximum number of
activities that don't overlap.
• Given a set of characters and their frequencies, build the optimal prefix-free binary
tree for data compression (Huffman Coding) 10%
Bit-masking: Interview Based Problems on Bit Manipulations.
• Given an array of integers, every element appears twice except for one. Find that
single one.
• Given an integer n, count how many 1 bits it has (Brian Kernighan's Algorithm).
• Given an integer, reverse its bits.
• Given an integer n, find how many times the number 1 appears in the binary
representation of all numbers from 1 to n.
• Given a set of distinct integers, return all possible subsets (the power set). 15
DP - 1: DP company oriented questions and problems:
• Given two strings, find the longest substring they share. This can be solved with
dynamic programming or efficient rolling hashes.
• Find the longest palindromic substring in a given string. This can be solved by
expanding around centers or using dynamic programming.
• Identify the longest substring that appears at least twice. Often solved with suffix
arrays or suffix trees.
• Using dynamic programming to find the edit distance between two strings.
DP – 2: DP Patterns and Multi-dimensional DP
• Match patterns with wildcards in strings.
• Given a set of items, each with a weight and a value, determine the maximum value
you can carry in a knapsack of limited capacity, where you can take fractions of items.
• Given two strings, find the length of the longest subsequence that appears in both
18%
strings.
• Given an array of integers, find the length of the longest strictly increasing
subsequence.
• Given a set of coin denominations, find the minimum number of coins required to
make a given amount.
• Given two strings, find the minimum number of operations (insertions, deletions, and
substitutions) required to convert one string to another.
DP – 3: DP on Trees.
• Find the diameter of a binary tree. The diameter of a tree is the length of the longest
path between any two nodes in the tree.
• Find the maximum sum of values along any path from any node to any other node in a
binary tree. The path can start and end at any node and doesn't necessarily pass
through the root. 24
Graphs and Tries: Problems based on the graphs and Advance problems on Graphs.
• Given an undirected or directed graph, represent it using an Using dynamic
programming to find the edit distance between two strings.
• Given a graph, use BFS to find the shortest path from a starting node to all other
nodes.
• Given a graph, use DFS to traverse all nodes.
• Given a directed graph, detect if it contains a cycle.
• Given a graph with non-negative weights, find the shortest path from a source node 5%
to all other nodes using Dijkstra’s algorithm.
• Given a graph with weights (which could be negative), find the shortest path from
the source node to all other nodes using the Bellman-Ford algorithm.
• Given a directed acyclic graph (DAG), perform a Topological Sort.
• Given a connected, undirected graph with weighted edges, find the Minimum
Spanning Tree (MST) using Kruskal’s Algorithm.
• Basic problems, Range Queries and Interview Problems on Tries. 10