CS & IT 20 24

ENGINEERING
Data structures &
Algorithms

DPP - 01 By- Aditya sir

Afon
11

1 Tomorrow

Card is
2 TCS NOT Admit

Out
 About Aditya Jain sir

1. Appeared for GATE during BTech and secured AIR 60 in GATE in very first attempt - City topper
2. Represented college as the first Google DSC Ambassador.
3. The only student from the batch to secure an internship at Amazon. (9+ CGPA)
4. Had offer from IIT Bombay and IISc Bangalore to join the Masters program
5. Joined IIT Bombay for my 2 year Masters
E
program, specialization in Data Science
6. Published multiple research papers in well known conferences along with the team
7. Received the prestigious excellence in Research award from IIT Bombay for my Masters thesis
8. Completed my Masters with an overall GPA of 9.36/10
9. Joined Dream11 as a Data Scientist
10. Have mentored working professions in field of Data Science and Analytics 101
11. Have been mentoring GATE aspirants to secure a great rank in limited time
12. Have got around 27.5K followers on Linkedin where I share my insights and guide students and
professionals.
Telegram Link for Aditya Jain sir:
TTTe
[Link]
[NAT]
#Q. Maximum Subarray Sum – Kadane’s Algorithm
Problem Statement: Given an array arr[], the task is to find the subarray
that has the maximum sum and return its sum.
Examples
Example 1:
Input: arr[] = {2, 3, -8, 7, -1, 2, 3}
Output: 11
Explanation: The subarray {7, -1, 2, 3} has the largest sum 11.
Example 2:
Input: arr[] = {-2, -4}
Output: -2
Explanation: The subarray {-2} has the largest sum -2.
Example 3:
Input: arr[] = {5, 4, 1, 7, 8}
Output: 25
Explanation: The subarray {5, 4, 1, 7, 8} has the largest sum 25.
[NAT]
#Q. Find Smallest Missing Positive Number
Problem Statement: Given an unsorted array arr[] containing both positive
and negative elements, the task is to find the smallest positive number
missing from the array.
Note: You can modify the original array.
Examples
Example 1:
Input: arr[] = {2, -3, 4, 1, 1, 7}
o
Output: 3
Explanation: The positive numbers in sorted order are {1, 2, 4, 7}. The
smallest missing positive number is 3.
Example 2:
Input: arr[] = {5, 3, 2, 5, 1}
Output: 4
o
Explanation: The positive numbers in sorted order are {1, 2, 3, 5, 5}. The
smallest missing positive number is 4.
Example 3: Ñ
Input: arr[] = {-8, 0, -1, -4, -3}
Output: 1
Explanation: There are no positive numbers in the array, so the smallest
missing positive number is 1.
APRIL aus

sort a

O n
i
for
ans
ali
if
Σ anstt

ans
ebeit ali

break
APPI send unclementaindx
A N an G N

not
int
Smallest pos
His
1
 1
temp o max arr

0
010,0 0,0

13 1131270

Nt
 temp N
0

0,9 10
I

For int elemia

dem 1 and elem n

n
3 For i o
0
temp i
if
Lositi
break
[NAT]
#Q. Third largest element in an array of distinct elements
Problem Statement: Given an array of n distinct integers, the task is to find
the third largest element in the array.
Examples
Example 1:
Input: arr[] = {1, 14, 2, 16, 10, 20}
Output: 14
Explanation:
•Largest element: 20
•Second largest element: 16
•Third largest element: 14
Example 2:
Input: arr[] = {19, -10, 20, 14, 2, 16, 10}
Output: 16
Explanation:
[MCQ]
#Q. Finding sum of digits of a number until sum becomes single digit
Problem Statement: Given an integer n, the task is to repeatedly find the
-
sum of its digits until the result becomes a single-digit number.
Examples
Example 1:
Input: n = 1234
Output: 1
1 2 34

51
Explanation:
1. Step 1: 1 + 2 + 3 + 4 = 10 1
2. Step 2: 1 + 0 = 1
Example 2:
Input: n = 5674 I
Output: 4
Explanation:
1. Step 1: 5 + 6 + 7 + 4 = 22 1 0
2. Step 2: 2 + 2 = 4
 109

1 0 9 10 stop

I
110
as
 13210
14
1324,0 1320410
a
132 10 13 10

3 10 1 10010
1 0
10
16787 72,21
we

logD

[Link]
[MCQ]
#Q. Sort an array in wave form
Problem Statement: Given an unsorted array of integers, sort the array into
a wave array.
An array arr[0..n-1] is in wave form if:
•arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ...
In other words, the elements should alternate between high and low values
in a wave-like pattern.
Examples
Example 1:
Input: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80}
Explanation:
• The elements follow a wave pattern: large - small - large - small - large
- small
• Other valid wave forms could be {20, 10, 6, 2, 100, 3, 80, 5}
Example 2:
Input: arr[] = {20, 10, 8, 6, 4, 2}
Output: arr[] = {20, 8, 10, 4, 6, 2}
Explanation:
•The wave pattern is maintained: large - small - large - small - large - small
•Other valid wave forms could be {10, 20, 6, 8, 2, 4}
[MCQ]
#Q. Longest Common Subsequence (LCS)
Problem Statement: Given two strings, s1 and s2, the task is to find the
length of the Longest Common Subsequence. If there is no common
subsequence, return 0. A subsequence is a string generated from the
original string by deleting 0 or more characters, without changing the
relative order of the remaining characters.
For example, sub sequences of “ABC” are “”, “A”, “B”, “C”, “AB”, “AC”, “BC” and
“ABC”. In general, a string of length n has 2n sub sequences.
Examples
Example 1:
Input: s1 = "ABC", s2 = "ACD"
Output: 2
Explanation: The longest subsequence common to both strings is "AC",
which has a length of 2.
Example 2:
• Input: s1 = "AGGTAB", s2 = "GXTXAYB"
•Output: 4
Explanation: The longest common subsequence is "GTAB", which has a
length of 4.
Example 3:
• Input: s1 = "ABC", s2 = "CBA"
•Output: 1
Explanation: The longest common sub sequences of length 1 are "A", "B",
and "C". Hence, the result is 1.
[NAT]
#Q. Imf
Maximum consecutive one’s (or zeros) in a binary array
Problem Statement: Given an array arr[] consisting of only 0’s and 1’s, the
task is to find the maximum count of consecutive 1’s or 0’s present in the
array.
Examples
Example 1:
Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Output: 4
Explanation: 0 2T
•The longest streak of 1’s is 4, from index 8-11.
Example 2:
Input: arr[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}
Output: 2
Explanation:
•The longest streak of 0’s is 2, from index 0-1.
Example 3: Am
Input: arr[] = {0, 0, 0, 0}
Output: 4
Explanation:
•The longest streak of 0’s is 4, as the entire array consists of 0’s.
int ans 0
count

i o n
for
ali a i i
if
Ftt
the
I max ans court
am

court 1
3
an max am cont
v
Impf
 2
XOR operator
Apr using

if ali a aliti o

Teakett
3
clue max an_stack
am

I
style
[NAT]
#Q. Maximum product of a triplet (subsequence of size 3) in array
Problem Statement:Given an integer array, the task is to find the maximum
product of any three numbers (triplet) in the array. Examples
Example 1:
Input: arr[] = [10, 3, 5, 6, 20]
Output: 1200
Explanation: The triplet with the maximum product is (10, 6, 20): 10 × 6 ×
20 = 1200
Example 2:
Input: arr[] = [-10, -3, -5, -6, -20]
Output: -90
Explanation: The triplet with the maximum product is (-3, -5, -6): (-3) × (-5)
× (-6) = -90
Example 3:
Input: arr[] = [1, -4, 3, -6, 7, 0]
Output: 168
 mmms
In prod

mag­APIIi

Bruteforce.i

possible
triplets
All
Teetprodut
 n
i o
for
for jian
fil
n
i
for
Max Pro
Max Pro max

alj xalk
ali x

01m
max pro teems

the

the

a n

sort
array
 6 20
A 10 3 5

sost
60 5 3
20 101

6 5 3

30 3
91
 A 1 4,3 7 6,0

MR MI
8025 M3

4,011,307

2 61

1 6 4 240 7 3 1 20
1168J
max 3 deny product

Xodef3lements
 909 an
S

010

max mar 3
maxi

mini mind A maxi