Home - bdbenu/Notes GitHub Wiki

Data structure Notes

Intermediate DSA: Time Complexity

Topic 1: Agenda for Today!

Topic 2: Basics of Logarithm

Topic 3: Quiz 1 Explanation - Solution Explanation

Topic 4: Quiz 3 Explanation

Topic 5: Quiz 4 Explanation

Topic 6: Quiz 5 Explanation

Topic 7: Quiz 6 Explanation

Topic 8: Quiz 7 Explanation

Topic 9: Quiz 8 Explanation

Topic 10: Quiz 11 Explanation

Topic 11: Comparing Iterations of two algorithms using Graphs

Topic 12: Asymptotic Analysis of Algorithms

Topic 13: Examples to calculate the Big O from the number of Iterations

Topic 14: Why do we neglect Lower Order Terms

Topic 15: Why do we neglect Constant Coefficients

Topic 16: Issues with Big(O)

Topic 17: Time Limit Exceeded Error

Topic 18: Online Editors and Why TLE occurs?

Topic 19: General Structure to solve a question

Topic 20: Importance of Constraints

Topic 21: Next Class Content

Topic 22: Doubt Resolution

Array

Topic 1: Problem 1 Find the max sum out of all possible subarray of the array

Topic 2: Problem 2 Optimized Solution Contribution Technique

Topic 3: Quiz 1 Explanation

Topic 4: Quiz 2 Explanation

Topic 5: Find sum of all Subarrays sums continued

Topic 6: Total number of subarrays of length K

Topic 7: Problem 3 Given an array, print start and end indices of subarrays of length K.

Topic 8: Problem 4 Given an array, print maximum subarray sum with length K

Topic 9: Problem 4 Bruteforce Approach

Topic 10: Problem 4 Optimized Approach using Prefix Sum Array

Topic 11: Problem 4 Optimized Approach using Sliding Window

Topic 12: Observations for solving problems on Subarrays.

Topic 13: Motivation for attending 2D Matrices

Topic 14: Doubt Resolution

Array 1 One Dimensional.

Topic 1: Mock Interview Awareness

Topic 2: Problem 1 Find Maximum Subarray Sum

Topic 3: Quiz 1 Explanation

Topic 4: Quiz 2 Explanation

Topic 5: Find Maximum Subarray Sum Brute Force

Topic 6: Find Maximum Subarray Sum using Carry Forward

Topic 7: Find Maximum Subarray Sum using Kadanes Algorithm

Topic 8: Find Maximum Subarray Sum Kadanes Pseudocode

Topic 9: Problem 2 Perform multiple Queries from i to last index

Topic 10: Quiz Explanation

Topic 11: Perform multiple Queries from i to last index Solution Approaches

Topic 12: Problem 3 Perform multiple Queries from index i to j

Topic 13: Quiz Explanation

Topic 14: Perform multiple Queries Observations

Topic 15: Problem 4 Rain Water Trapping

Topic 16: Quiz Explanation

Topic 17: Rain Water Trapping Brute Force Approach

Topic 18: Rain Water Trapping Optimised Approach

Topic 19: Doubt Resolution

Array 2 Two Dimensional.

Arranging the data as a grid manner.

// Declar a 2d Array int A[N][M]

[N]- Number of Row [M]- Number of [] column // N = mat.length; M = mat[0].length

How we represent int arr[N][M]; arr[3][4]

Topic 1: Problem 1 Find in rowwise and colwise sorted matrix

Topic 2: Find in rowwise and colwise sorted matrix Optimised Approach

Topic 3: Find in rowwise and colwise sorted matrix Optimised Approach Continued

Topic 4: Find in rowwise and colwise sorted matrix Pseudocode

Topic 5: Problem 2 Row with maximum number of 1s

Topic 6: Row with maximum number of 1s Optimized Approach

Topic 7: Row with maximum number of 1s Pseudocode

Topic 8: Problem 3 Print Boundary Elements

Topic 9: Print Boundary Elements Approach

Topic 10: Problem 4 Spiral Matrix

Topic 11: Spiral Matrix Pseudocode

Topic 12: What is a submatrices and how can we uniquely identify it

Topic 13: Problem 5 Sum of all Submatrices Sum

Topic 14: Sum of all Submatrices Sum Approach

Topic 15: Sum of all Submatrices Sum Pseudocode

Topic 16: Doubt Resolution

Array 3 Interview Problems.

Topic 1: Merge Intervals

Topic 2: Quiz Explanation

Topic 3: Quiz Explanation

Topic 4: Problem 1 Merge sorted Overlapping Intervals

Topic 5: Merge sorted Overlapping Intervals Approach

Topic 6: Problem 2 Sorted Set of Non Overlapping Intervals

Topic 7: Quiz Explanation

Topic 8: Sorted Set of Non Overlapping Intervals Pseudocode

Topic 9: Problem 3 Find First Missing Natural Number

Topic 10: Find First Missing Natural Number Solution Approach

Topic 11: Find First Missing Natural Number Optimised Approach

Topic 12: Find First Missing Natural Number For Negative Numbers

Topic 13: Contest Information

Topic 14: Doubt Resolution

Bit Manipulations Basics.

Topic 1: Decimal Number System

Topic 2: Binary Number System

Topic 3: Binary to Decimal Conversion

Topic 4: Quiz Explanation

Topic 5: Decimal to Binary Conversion

Topic 6: Quiz Explanation

Topic 7: Addition of Decimal Numbers

Topic 8: Addition of Binary Numbers

Topic 9: Quiz Explanation

Topic 10: Bitwise Operators

Topic 11: Bitwise Operations Example

Topic 12: Quiz Explanation

Topic 13: Binary Representation of Negative numbers

Topic 14: Range of Data types

Topic 15: Importance of Constraints

Topic 16: Contest Information

Topic 17: Motivation for attending String Basics

Topic 18: Summarise

Topic 19: Unlock Assignment

Topic 20: Doubt Resolution

Intermediate DSA: Strings.

Following are the topics we shall be covering in the upcoming class.

Topic 1: Revision Quiz 1 Explanation

Topic 2: String

Topic 3: Question 1 Switch upper to lower and vice verse

Topic 4: Question 1 approach - subtract or add 32

Topic 5: Question 1 Changing same string is not possible in Java or

Topic 6: Question 1 Using character array instead

Topic 7: Quiz 2 Explanation

Topic 8: Substring

Topic 9: Quiz 3 Explanation

Topic 10: Question 2 Check Palindrome

Topic 11: Question 2 Approach

Topic 12: Question 3 Problem Statement

Topic 13: Question 3 Brute Force Approach

Topic 14: Question 3 Optimized Approach

Topic 15: Immutability of Strings

Topic 16: String Builder in Java

Topic 17: Motivation for attending Interview Problems

Topic 18: Contest Information

Topic 19: Doubt Resolution

Bit Manipulations Basics

Topic 1: Decimal Number System

Topic 2: Binary Number System

Topic 3: Binary to Decimal Conversion

Topic 4: Quiz Explanation

Topic 5: Decimal to Binary Conversion

Topic 6: Quiz Explanation

Topic 7: Addition of Decimal Numbers

Topic 8: Addition of Binary Numbers

Topic 9: Quiz Explanation

Topic 10: Bitwise Operators

Topic 11: Bitwise Operations Example

Topic 12: Quiz Explanation

Topic 13: Binary Representation of Negative numbers

Topic 14: Range of Data types

Topic 15: Importance of Constraints

Topic 16: Contest Information

Topic 17: Motivation for attending String Basics

Topic 18: Summarise

Topic 19: Unlock Assignment

Topic 20: Doubt Resolution

Intermediate DSA: Arrays: 2D Matrices

Topic 1: 2D Matrices

Topic 2: Question 1 Given a matrix print row-wise sum

Topic 3: Row-wise sum Approach

Topic 4: Quiz 3 Explanation

Topic 5: Question 2 Given a matrix print col-wise sum

Topic 6: Col-wise sum Approach

Topic 7: Question 3 Given a square matrix print diagonals

Topic 8: Print diagonals Approach

Topic 9: Quiz 4 Explanation

Topic 10: Given square matrix, print Anti-diagonal

Topic 11: Question 4 Print diagonals in a rec matrix (right to left)

Topic 12: Quiz 5 Explanation

Topic 13: Print diagonals in a rec matrix approach

Topic 14: Question 5 Transpose of a square matrix

Topic 15: Transpose Approach

Topic 16: Quiz 8 Explanation

Topic 17: Question 6 Rotate a matrix to 90 degree clockwise

Topic 18: Rotate a matrix approach

Topic 19: Doubt Resolution

Intermediate DSA: Sorting Basics

Topic 1: Revision Quiz 2 Explanation

Topic 2: Revision quiz 3 Explanation

Topic 3: Introduction to Sorting

Topic 4: Quiz 1 Explanation

Topic 5: Why sorting is required?

Topic 6: Sorting library in different languages

Topic 7: Problem 1 Minimize the cost to empty array

Topic 8: Quiz 2 Explanation

Topic 9: Quiz 3 Explanation

Topic 10: Problem 1 Solution Approach

Topic 11: Problem 2 Find count of Noble Integers

Topic 12: Quiz 4 Explanation

Topic 13: Problem 2 Bruteforce Solution

Topic 14: Problem 1 Optimised Solution

Topic 15: Problem 3 Find count of nobel integers (Not Distinct)

Topic 16: Quiz 5 Explanation

Topic 17: Quiz 6 Explanation

Topic 18: Quiz 7 Explanation

Topic 19: Problem 3 Solution

Topic 20: Sorting Algorithm - Selection Sort

Topic 21: Sorting Algorithm - Insertion Sort

Topic 22: Motivation for attending Bit Manipulation

Topic 23: Summarise

Topic 24: Unlock Assignment

Topic 25: Doubt Resolution

Intermediate DSA: Memory Management

Topic 1: Introduction to stack

Topic 2: Introduction to call stack

Topic 3: What is a reference variable ?

Topic 4: Types of memory

Topic 5: Example 1

Topic 6: Example 2

Topic 7: Example 3

Topic 8: Example 4

Topic 9: Example 5

Topic 10: Example 6

Topic 11: Example 7

Topic 12: Quiz 1 Explanation

Topic 13: Quiz 2 Explanation

Topic 14: Quiz 3 Explanation

Topic 15: Quiz 4 Explanation

Topic 16: Quiz 5 Explanation

Topic 17: Quiz 6 Explanation

Topic 18: Quiz 7 Explanation

Topic 19: Quiz 8 Explanation

Topic 20: Motivation for attending Sorting Basics

Topic 21: Summarise

Topic 22: Unlock Assignment

Topic 23: Doubt Resolution

Intermediate DSA: Arrays: Sliding Window & Contribution Technique

Topic 1: Problem 1 Find sum of all Subarrays sums

Topic 2: Subarrays Sums - Prefix Sum

Topic 3: Subarrays Sums - Carry Forward

Topic 4: Subarrays Sums - Contribution Technique

Topic 5: Quiz 1 Explanation

Topic 6: Quiz 2 Explanation

Topic 7: Subarrays Sums continued

Topic 8: Count subarrays of length K

Topic 9: Problem 3 Max subarray sum with length K

Topic 10: Max subarray sum with length K Bruteforce Approach

Topic 11: Max subarray sum with length K - Sliding Window

Topic 12: Motivation for attending 2D Matrices

Topic 13: Summarise

Topic 14: Unlock Assignment

Topic 15: Doubt Resolution

Intermediate DSA: Arrays - Prefix Sum.

Following are the topics we shall be covering in the upcoming class.

Topic 1: Revision Quiz 3 Explanation

Topic 2: Revision Quiz 4 Explanation

Topic 3: Revision Quiz 5 Explanation

Topic 4: Stock Portfolio Performance Tracking

Topic 5: Given N elements and Q queries. For each query, calculate sum of all elements from L to R

Topic 6: Quiz 1 Solution

Topic 7: Quiz 2 Solution

Topic 8: Quiz 3 Solution

Topic 9: Quiz 4 Solution

Topic 10: Quiz 5 Solution

Topic 11: Observation for Optimised Solution

Topic 12: How to create Prefix Sum Array ?

Topic 13: Brute Force Code to create Prefix Sum Array and observation for Optimisation

Topic 14: How to answer the Queries ?

Topic 15: Problem 1 Sum of even indexed elements

Topic 16: Problem 1 Observation for Optimisation

Topic 17: Quiz 7 Explanation

Topic 18: Problem 1 Pseudocode

Topic 19: Problem 1 Extension Sum of all odd indexed elements

Topic 20: Problem 2 Special Index

Topic 21: Quiz 8 Explanation

Topic 22: Quiz 9 Explanation

Topic 23: Quiz 10 Explanation

Topic 24: Problem 2 Observation for Optimised Approach

Topic 25: Next Class Content

Topic 26: Doubt Resolution

Intermediate DSA: Arrays: 2D Matrices.

Following are the topics we shall be covering in the upcoming class.

Topic 1: 2D Matrices

Topic 2: Question 1 Given a matrix print row-wise sum

Topic 3: Row-wise sum Approach

Topic 4: Quiz 3 Explanation

Topic 5: Question 2 Given a matrix print col-wise sum

Topic 6: Col-wise sum Approach

Topic 7: Question 3 Given a square matrix print diagonals

Topic 8: Print diagonals Approach

Topic 9: Quiz 4 Explanation

Topic 10: Given square matrix, print Anti-diagonal

Topic 11: Question 4 Print diagonals in a rec matrix (right to left)

Topic 12: Quiz 5 Explanation

Topic 13: Print diagonals in a rec matrix approach

Topic 14: Question 5 Transpose of a square matrix

Topic 15: Transpose Approach

Topic 16: Quiz 8 Explanation

Topic 17: Question 6 Rotate a matrix to 90 degree clockwise

Topic 18: Rotate a matrix approach

Topic 19: Doubt Resolution

Intermediate DSA: Arrays: Carry Forward & Subarrays.

Following are the topics we shall be covering in the upcoming class.

Topic 1: Contest Information

Topic 2: Problem 1 Count of Pairs ag

Topic 3: Quiz 1 Explanation

Topic 4: Quiz 2 Explanation

Topic 5: Problem 1 Brute Force Solution

Topic 6: Problem 1 Optimised solution

Topic 7: Introduction to Subarrays

Topic 8: Quiz 3 Explanation

Topic 9: Representation of a Subarray

Topic 10: Quiz 4 Explanation

Topic 11: Quiz 5 Explanation

Topic 12: Formula to count total no. of subarrays

Topic 13: Print the subarray of the array that starts from the start index and ends at the end index