PROBLEM SOLVING
SDE Readiness Training
Self-Practice No. VII
Topics Covered : Array, String, Arraylist, Priority Queue, Control Flow
Statements, Bit Manipulation, Treeset, Hashset
Date : 16-05-2025
Solve the following problems
Q Question Detail Level
No.
1 Top K Frequent Elements Medium
Problem Statement : Given an integer array nums and an
integer k, return the k most frequent elements. You may
return the answer in any order
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= [Link] <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the
array].
It is guaranteed that the answer is unique.
2 Dot Product of Two Sparse Vectors Medium
Problem Statement : Given two sparse vectors, compute their
dot product.
Implement class SparseVector:
Little practice is worth more than a ton of
theory
1
PROBLEM SOLVING
SDE Readiness Training
SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the
instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you
should store the sparse vector efficiently and compute the dot
product between two SparseVector.
Example 1:
Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 =
SparseVector(nums2)
[Link](v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Example 2:
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 =
SparseVector(nums2)
[Link](v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Example 3:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6
Constraints:
n == [Link] == [Link]
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 100
3 Contiguous Array Medium
Problem Statement : Given a binary array nums, return the
maximum length of a contiguous subarray with an equal
number of 0 and 1.
Example 1:
Little practice is worth more than a ton of
theory
2
PROBLEM SOLVING
SDE Readiness Training
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with
an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous
subarray with equal number of 0 and 1.
Constraints:
1 <= [Link] <= 105
nums[i] is either 0 or 1.
4 Gray Code Medium
Problem statement : Given a number ‘grayNumber’. Find the
gray code sequence.
Conditions for a gray code sequence :
1. Gray code sequence contains numbers from 0 to
2^'grayNumber'-1 in bit/binary form.
2. Two consecutive gray code sequence numbers only differ by
1 bit.
3. Gray code sequence must start with 0.
Example :
Given 'grayNumber' : 2.
Little practice is worth more than a ton of
theory
3
PROBLEM SOLVING
SDE Readiness Training
As depicted from above image, the gray code sequence is
0,1,3,2.
Note :
1. The output sequence must contain the decimal
representation of numbers instead of the binary form.
2. There can be multiple answers print anyone.
Sample Input 1 :
2
2
3
Sample Output 1 :
Valid
Valid
Explanation For Sample Input 1 :
For first test case,
Given 'grayNumber' : 2
Bits representation of a number from 0 to 2^2-1 = 3 is “ 00,
01, 10, 11’’.
But we have arranged these bits in such a way that two
consecutive bits only differ by 1.
Only one possible way is “00, 01, 11, 10 ”.
Hence return value of every number “ 00 - 0 , 01 - 1, 11 - 3, 10
- 2”.
Sequence : {0, 1, 3, 2}.
For second test case,
Given 'grayNumber' : 3
Bits representation of a number from 0 to 2^3-1 =7 is “000,
001, 010, 011, 100, 101, 110, 111’’.
But we have arranged these bits in such a way that two
consecutive bits only differ by 1.
One of the possible ways is “000, 001, 011, 111, 101, 100, 110,
010”.
Hence return value of every number “000 - 0, 001 - 1, 011 - 3,
111 - 7, 101 - 5, 100 - 4, 110 - 6, 010 - 2 ”.
Sequence : {0, 1, 3, 7, 5, 4, 6, 2}.
One another possible sequence can be : {0, 1, 3, 2, 6, 7, 5, 4}.
Little practice is worth more than a ton of
theory
4
PROBLEM SOLVING
SDE Readiness Training
Sample Input 2 :
2
4
1
Sample Output 2 :
Valid
Valid
Explanation For Sample Input 2 :
For first test case,
Given 'grayNumber' : 4
Sequence : {0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8}.
For second test
case, Given
'grayNumber' : 1
Sequence : {0, 1}.
Constraints :
1 <= T <= 2
0 <= grayNumber <= 15
5 Task Scheduler Medium
Problem statement : You are given an array of CPU tasks,
each represented by letters A to Z, and a cooling time, n. Each
cycle or interval allows the completion of one task. Tasks can be
completed in any order, but there's a constraint: identical tasks
must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete
all tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B
-> idle -> A -> B.
After completing task A, you must wait two cycles before doing
A again. The same applies to task B. In the 3rd interval, neither
Little practice is worth more than a ton of
theory
5
PROBLEM SOLVING
SDE Readiness Training
A nor B can be done, so you idle. By the 4th cycle, you can do
A again as 2 intervals have passed.
Example 2:
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -
> B.
With a cooling interval of 1, you can repeat a task after just
one other task.
Example 3:
Input: tasks = ["A","A","A", "B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle ->
A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be
separated by 3 intervals. This leads to idling twice between
repetitions of these tasks.
Constraints:
1 <= [Link] <= 10^4
tasks[i] is an uppercase English letter.
0 <= n <= 100
6 Find All Anagrams in a String Medium
Problem statement : Given two strings s and p, return an
array of all the start indices of p's anagrams in s. You may
return the answer in any order.
An Anagram is a word or phrase formed by rearranging the
letters of a different word or phrase, typically using all the
original letters exactly once.
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Little practice is worth more than a ton of
theory
6
PROBLEM SOLVING
SDE Readiness Training
Explanation:
The substring with start index = 0 is "cba", which is an
anagram of "abc".
The substring with start index = 6 is "bac", which is an
anagram of "abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an
anagram of "ab".
The substring with start index = 1 is "ba", which is an
anagram of "ab".
The substring with start index = 2 is "ab", which is an
anagram of "ab".
Constraints:
1 <= [Link], [Link] <= 3 * 10^4
s and p consist of lowercase English letters.
7 Strong Password Checker Hard
Problem statement : A password is considered strong if the
below conditions are all met:
It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one
uppercase letter, and at least one digit.
It does not contain three repeating characters in a row
(i.e., "Baaabb0" is weak, but "Baaba0" is strong).
Given a string password, return the minimum number of steps
required to make password strong. if password is already
strong, return 0.
In one step, you can:
Insert one character to password,
Delete one character from password, or
Replace one character of password with another character.
Little practice is worth more than a ton of
theory
7
PROBLEM SOLVING
SDE Readiness Training
Example 1:
Input: password = "a"
Output: 5
Example 2:
Input: password = "aA1"
Output: 3
Example 3:
Input: password = "1337C0d3"
Output: 0
Constraints:
1 <= [Link] <= 50
password consists of letters, digits, dot '.' or exclamation mark '!'.
Little practice is worth more than a ton of
theory
8
PROBLEM SOLVING
SDE Readiness Training
8 Rearrange string Hard
Problem statement : You are given a string “S”. Your task is to
rearrange the characters of a string “S”, such that it does not contain
any two adjacent characters which are the same.
If it is possible to rearrange the string “S”, then print any possible
arrangement. else, print “not possible” without quotes.
For Example:
For a string “qaacde”, This string has two same adjacent characters.
So, one possible way to rearrange the string is “qacade”. Now, this
string does not have two adjacent characters that are the same.
Sample Input 1 :
2
coding
abaab
Sample Output 1 :
Yes
Yes
Explanation :
For the first test case, the given string is “coding”. This string does
not have two adjacent characters that are the same. So if we return
“coding", then we will get an output as “Yes”.
Little practice is worth more than a ton of
theory
9
PROBLEM SOLVING
SDE Readiness Training
For the second test case, the given string is “abaab”. This string has
two adjacent characters that are the same i.e. abaab, So we can
rearrange the string as “ababa”.Hence we return “ababa”, then we
will get an output as "Yes”.
Sample Input 2 :
1
bbbbbb
Sample Output 2 :
Yes
Explanation :
For the first test case, the given string is “bbbbbb”. No matter how
you rearrange characters of string , it will always remain the same as
[Link] we return “not possible” as an answer, then we will get an
output as ‘Yes”.
Constraints :
1 <= T <= 10
0 <= |S| <= 10^5
9 Longest Duplicate Substring Hard
Problem statement : Given a string s, consider all duplicated
substrings: (contiguous) substrings of s that occur 2 or more
times. The occurrences may overlap.
Return any duplicated substring that has the longest possible
length. If s does not have a duplicated substring, the answer is "".
Example 1:
Input: s = "banana"
Output: "ana"
Example 2:
Input: s = "abcd"
Output: ""
Constraints:
Little practice is worth more than a ton of
theory
10
PROBLEM SOLVING
SDE Readiness Training
2 <= [Link] <= 3 * 10^4
s consists of lowercase English letters.
Little practice is worth more than a ton of
theory
11