Lecture-Questions

Lecture-2 ✔️
Sieve Method

Prime numbers in a range

Sum of prime numbers in a range

Count of prime numbers in a range

Smallest prime factor of a number

Count of elements in an array divisible p or q or both

Euclidean Division

Extended Euclidean Division

Modular Multiplicative Inverse

Segmented Sieve

Lecture-3 ✔️
Modular Exponentiation

Maximum sum of continuous subarray

All pairs in an array whose sum is k (using two pointer technique)

All pairs in an array whose difference is k

All triplets in an array whose sum is k

Lecture-Questions 1
 All unique pairs in an array whose sum is k

Cut-Stick problem (Print the number of steps till all sticks

disappear)

Sky fall problem

Lecture-4 ✔️
Maximum sum of subarray of size k (Sliding window)

Largest subarray without repeating characters

First negative number in each window of size k

Largest and smallest subarray of sum k

Minimum match substring, 2 strings given, conditions: order

doesnt matter, atleast 2 characters

pick the toy problem, conditions: 1. rack should be continuous 2.

atmost 2 types of toys in any quantity Find max no of toys you
can pick. ( Largest substring of unique elements)

Lecture-5
SumPower Problem ✔️
Prefix Sum Problem- Consider a problem where you are given an array of size
n and for each query you need to compute the sum of elements in a subarray b/w
indices l and r. You also need to find sum of odd numbers b/w l and r. For each
query you’re asked to find max freq of any number in sub-array. (Keep 2d array
for frequency, 1d for prefix sums)

✔️
Lecture-Questions 2
 Lecture-6 ✔️
Find next (right) greatest element

Largest rectangle in histogram

StockSpan

Lecture-7
Celebrity Problem ✔️
Trapping Rainwater Problem ✔️
atleast two different alternates ✔️
Kth smallest element of an array without sorting. Implement

Prefix Sum Addicts

Lecture-8
STL

Lecture-9 ✔️
✔️
Find single element in sorted array where all except one element
exist twice. O(logn)

Search element in sorted rotated array- ✔️

Find the index from where it is rotated

Find a key

Find minimum element

Koko eating bananas ✔️

Lecture-Questions 3
 Find the nth root of an integer ✔️
✔️
Find the first and last occurence of each element in a sorted array

Lecture - 10 ✔️
Kth missing positive integer in sorted array ☑️
Aggressive Cows ✔️
Allocate Minimum Pages(Book Allocation Problem) ✅
Given an array arr[] and an integer k, where arr[i] denotes the number of pages of
a book and k denotes total number of students. All the books need to be allocated
to k students in contiguous manner, with each student getting at least one book.

The task is to minimize the maximum number of pages allocated to a student. If it

is not possible to allocate books to all students, return -1.

Painter Partition ✅
Least Capacity to ship packages within d days ✔️
Median of 2 sorted arrays of different sizes ✅
Search in 2D array (matrix -rows and columns are sorted) ✔️
LECTURE - 11 ✅
MaxVote

a+b stack

Sort a k sorted array

k closest points to the origin

Lecture-Questions 4
 LECTURE - 12 ✅
Find max element using min Priority queue O(nlogn)

Merge two max priority queues A[m+n] B[n] in O(m+n.log(m+n))

Convert BST to max heap in O(n)

Find kth smallest element in max priority queue in O(klogk)

Given a big file of billions of elements find max 10 numbers from

the file (hint-divide into a few parts)
make file

Last stone weight problem

Lecture - 13

✔️
Find the kth smallest element in an unsorted array using median
of medians algorithm

Find median of stream of integers

Tournament Sorting ✔️
✔️
Lab- kth smallest element in rows, column sorted
matrix

Lecture - 14
Separate indices of linked list (odd,even) ✅
Separate data values of linked list (odd, even) ✅
Middle of linked list ✅
Lecture-Questions 5
 Detect cycle, 1st node of cycle and remove cycle ✔️
Remove nth node from the end ✔️
Remove every kth node ✅
Right rotation by k places ✔️

Palindrome ✔️

Lecture 15
Flatten a doubly linked list- using down pointers ✔️
Clone a linked list with random pointers ✔️
Lecture 16- Recursions
✅
Find the super digit for a given array

Possible sub sequences for a string☑️

Print keypad combinations - use a mapping technique ✔️

Fit squares of base m, in a right, isosceles triangle of base b ✔️
✅
Print n-bit binary numbers having more 1s than 0s for every prefix

✅
Rat in a maze It can only move up or down, left or right, Return all
possible paths

Kingdom of ice and fire Codechef ✔️

Lecture-Questions 6
 Inorder, Preorder, Postorder

Max of binary tree

Sum of all nodes of binary tree

Copy of binary tree

Find mirror image of binary tree

Count leaf and non-leaf nodes

Find whether a binary tree is left skewed or right skewed

Lecture- 17 Backtracking ✔️
Palindrome Partition- Return all possibilities ✔️
Two button Problem- Hint: try reversing the problem ☑️
Fair distribution of cookies, k is no of students Calculate the min

☑️
unfairness (Unfairness- Max total cookies obtained by single
children in distribution
N-Queen Problem ☑️
Sum of subsets ✔️
Graph Coloring ☑️
Hamiltonion graphs ✔️
Lecture 18
min n- digit no with digits in increasing order ✔️
(4,6,7,7): 46,47,67,77,467,477,677,4677

knights tour - 8 possibilites do using warnsdroff algorithm ✔️

warnsdroff algorithm- chose min of valid moves

Word search ✔️
Lecture-Questions 7
 Matchstick to square (1,1,2,2,2), (3,3,3,3,4)

Lecture 19
logical shift

arithmetic shift

set ✔️
toggle✔️
clear✔️

modify

toggle first and last bit ✔️

toggle all bits except kth bit ✔️
how to check if a given no is power of two ✔️
duplicate in array ✔️
compute a raised to the power n ✅
count no of 1s in binary notation ✔️

motivation behind bitsets ✔️

Lecture 20 ✔️
all numbers are repeated except 2(x,y). Find x, y ☑️

Lecture-Questions 8
 ✅
An array has n+2 elements in the range 1 to n and exactly two
numbers x and y are repeated. find x and y

XOR without XOR ✔️

Swap without third element ✔️
All numbers repeating thrice except one, find the number ☑️
Reverse binary of a number (16 bit number) ☑️
You have an integer and you can flip exactly one bit from zero and

✔️
one, find the length of longest sequence of 1s, you can create in
its binary representation

✔️
Given a positive n number, print next smallest no than n having
same no of 1s

LECTURE 21 Greedy
Dijsktra✔️
Prims ✔️

Kruskal ✔️

Find minimum no of coins ✔️

Find minimum no of platforms for trains ✔️
Hoffman Coding ☑️
N meetings in one room (Job scheduling) ✔️
SJF in CPU Scheduling ✔️
Lecture-Questions 9
 Sweep line algorithm

Lecture 22
Disjoint sets: Find set, union
linked list (union by size) ✔️
tree

Path compression ✔️
Union by rank and size ✔️
Strongly connected components ✔️
dfs ✔️
bfs - confirm if method correct ✔️
Q1: Detect cycle in undirected graph ✔️
Q2: City and Flood ✔️
Kahns for cycle detection ✔️
Kosaraju ✔️
Tarjan Algorithm for BRIDGE ✔️
Tarjan for articulation point
Tarjan for scc

Q3: Covid Spread ✔️

Questions from group

Lecture 23

Lecture-Questions 10
 Road Decoration ✔️
Lecture 24
m-ary tree ☑️
convert a tree to a left child right sibling binary tree, first child of a node is stored
in left pointer, all other siblings become right children of their intermediate siblings

✔️
Diameter of a tree- longest path between two nodes

Nextsibling for binary tree

Zig zag traversal

Inorder, Postorder, Postorder tree

LCA Least common ancestor

Find minimum and maximum depth

Sum of nodes equal to k

Book

Lecture-Questions 11