Online Assesment Questions (with solutions and submittable codeforces links)

Sigma Rule #82: Questions looking hard are hard and vice-versa, period.

Uber

These quesions are taken from this GFG article and leetcode discussions.

 

Q1. There is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can’t be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.

 

Constraints: 

1<=t<=1o^9

0<=k<=n

1<=n<=10^5

e[i]<=s[i+1],   0<=i <n-1

s[i] < e[i] for 0<=i<=n-1

Codeforces Question link: 

 Editorial:

 

Hint 1: Think of Greedy Approach Here.

Hint 2:  How many shifts you have to do merge two free times? It's just one shift! And we won't benefit by shifting non-contiguous intervals

Let's consider this case:

[[2,4],[7,10],[11,13],[13,14],[14,15]], k=2

and t=16

 

The free spots available between two consecutive presentations are: [0,2] ,[4,7],[10,11],[14,14],[15,16]

The length of these free spots are: [2,3,1,0,1]

(Note that I have taken 14,14 also)

 Now we have to shift k presentations, now we know that shifting any presentation can merge the two spots available on its left and right. So we just take k+1 consecutive free spots and sum them up and maximize the result for the whole free spot array.

Code: 

Q2) You are given a n x  m grid consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. Your task is to calculate the total number of ways of reaching the target.

Solution: Very trivial Question(https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/)

Q3) You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition.

 

Hint 1: Think of Dijkstra's Algorithm!

Hint 2: We can only use one curved edge. This leads to a binary condition at any stage of process of finding shortest path.

Solution:

This is very similar to this question. So the basic idea here is to perform Dijkstra's Algorithm. In Normal Dijkstra Algorithm, we create a heap which stores the distance from the source node and the node number. But here, we have to include another parameter, isCurved, that will be a boolean variable with its true state describing that we took any curved edge to go to this node and false state that we still can traverse through a curve edge. Similarly we have to create two distance arrays with one denoting distance of src node to ith node without using any curved edge and other, using a curved edge. 

Codeforces Link:

Solution Code Link:

Q4)You are given two arrays of integers a and b, and two integers lower and upper.
Your task is to find the number of pairs (i, j) such that lower ≤ a[i] * a[i] + b[j] * b[j] ≤ upper.
Example:
For a = [3, -1, 9], b = [100, 5, -2], lower = 7, and upper = 99, the output should be boundedSquareSum(a, b, lower, upper) = 4.
There are only four pairs that satisfy the requirement:
If i = 0 and j = 1, then a[0] = 3, b[1] = 5, and 7 ≤ 3 * 3 + 5 * 5 = 9 + 25 = 36 ≤ 99.
If i = 0 and j = 2, then a[0] = 3, b[2] = -2, and 7 ≤ 3 * 3 + (-2) * (-2) = 9 + 4 = 13 ≤ 99.
If i = 1 and j = 1, then a[1] = -1, b[1] = 5, and 7 ≤ (-1) * (-1) + 5 * 5 = 1 + 25 = 26 ≤ 99.
If i = 2 and j = 2, then a[2] = 9, b[2] = -2, and 7 ≤ 9 * 9 + (-2) * (-2) = 81 + 4 = 85 ≤ 99.

 

Solution: Square the arrays and binary search for the answer on b. 

Codeforces Question: 

Solution link:

Q5)Given an array A of N elements, you can perform the following operation any number of times(possibly 0). You can replace any integer of the array with an integer. Your task is to print the minimum operations required to make the elements continuous. 

 

Constraints: 1 <= N <= 1e6, 1 <= A[i] <= 1e9 

 

Example:

Input: 4 7 11 6 9  

Output: 2 

 

Explaination: We can replace 11 with 5 and 9 with 8, resulting in the array [4, 7, 8, 6, 5] which contains all the elements from 4 to 8.

Solution: 

 

Q6) Convert a 2 base number to 6 base number. 

Codeforces Link:

Hint 1: Just think what you do while converting decimal to binary.

Hint 2: You can change 2 base to decimal and decimal to 6 base.

Solution:

Solution Code: 

Q7) Find the number of magical sub sequences in an array. A magical sub sequence is the sequence which contains any two consecutive numbers with absolute difference less than or equal to 0. For example, in [2,3,6], you can have 2 subsequences: [2,3],[2,3,6].

Constraints: n<=1000

 

Q8) Bob is painting a wall. The wall contains N sections and he has already painted some sections of the wall randomly. The wall consists of a string of length N containing lower-case alphabets 'a' to 'z' denoting the color of the section.

In 1 operation, Bob can paint a single section of the wall to any new color. He is now tired and does not want to do more than k operations. So, he decides to create a continuous segment of the wall which is completely the same color (a range [i, j] where all wall[k] are equal, i <= k <= j)

What is the maximum length of such a segment he can create.

Constraints
1 <= N <= 5 * 10^5
wall[i] = 'a' to 'z'

0 <= k <= 5 * 10^5

CodeNation

These questions are from various sources including LeetCode articles, GFG, and YouTube videos. 

Q1) You are given a string s of n characters. You have to delete at most k characters from it to make it lexicographic biggest string. 

For example: s=abzdef and k=2, you can delete first, second and fourth character to make string zef. 

 

Codeforces Question Link:

 

Hint 1: Think of how you should erase characters and erasing which characters would be beneficial? Making the first character biggest is always preferable.There can be cases where we cannot make first character biggest, but we want our first character as big as possible.

Hint 2: There are only 26 alphabets. So we can store indices of each character and for each index see the biggest character we can get at this position using k deletes.

Solution: You should be clear using hint 2, it's literally all of the solution. Just store the indices and see biggest character we can get. You can use map of char and vector or a queue array. 

Solution Code:

Q2) We are given two arrays, A and B of size n and m. We have to insert some numbers to A such that B becomes a sub sequence of A. We have to minimize the number of insertions. 

Constraints: 

n,m<=10^5

1<=A[i],B[i]<=10^9

Elements in second array are distinct.

Codeforces Link:

Hint 1: Think of LCS.

Hint 2: LCS giving TLE? Try LIS.( Read constraints carefully)

Solution: The intuition which comes to mind is simple: Just take in the longest common subsequence of both the arrays, our answer would be the length of second array- length of LCS. But computing LCS make the time complexity O(n*m) which is bound to give you TLE. 

But the elements of second element are distinct. So, these elements act as an ID. What we can do is we can change the elements to their indices, and the corresponding elements element in array A as well. Now, why should it work? Just think of it, we don't really care about the numbers itself, we just care about their order in both the arrays.

Solution Code:

Q3) You have given an array A of size N. You are also given q queries of the form " L R S T" where you have to find number of sub-arrays of size S between indices L and R whose Bitwise & comes up to be greater than or equal to T.

Constraints:

N<=10^5

q<=500

0<=L,R<N

1<=S<=R-L+1

Hint 1: These are Queries and read the constraints carefully.

Hint 2: Binary AND operation is Idempotent. (A&A=A)

Hint 3: Sparse Tables.

Solution: There can be a number of ways to do this problem. One way is to create a segment tree and find the queries in n*log(n) time by querying every subarray of size S in range L to R. And as Binary AND relation is idempotent, we can also use Sparse tables. With sparse tables, we would require N*log(n) preprocessing time and O(N) query time. So total time complexity would be O(nlog(n)+n*q) instead of O(nlog(n)+n*log(n)*q) in case of segment trees.

Q4) You are given a tree having A nodes numbered from 0 to A-1 rooted at Node 0. Each Node has a distinct value ranging between 0 and A-1, ith node having value C[i].(No two nodes have the same value)

For each node in the tree, you have to find the smallest non-negative integer value which is not present in subtree of that node. 

Constraints

1<=A<=10^5

0<=C[i]<=A-1

All values of C are distinct and unique.

 

Codeforces Link: 

Hint 1: Think of mex and its properties. Think of those nodes which would have mex as 0.

Hint 2: Nodes which don't have mex as 0, how do we find their mex in efficient way? We ought to have some way in which we can see if there exists a value x in a subtree in O(1).

Solution:

 

Solution Code:

Q5) Given an array A of size n, find for each a[i], the number of pairs, i and j where A[i]%A[j]==0 or A[j]%A[i]==0. Basically, find all the factors and multiples of ith element in the array.

Constraints:

1<=n<2*10^5

1<=A[i]<=10^5

 

Codeforces Link: 

Solution:

 

Solution Code:

 

Q6) Given an array A of size n and queries q, you have two types of queries:

1 i x: change A[i] to x

2 l r: The magical sum of array between l and r. Return this value mod 1000000007.

The magical sum of the array A between l and r is given by A_l-A_l+1+A_l+2-A_l+3+...(-1)^(r-l)A_r .

Contraints:

1<=n<=10^5

1<=q<=10^5 

 

Codeforces Link: 

Hint 1:

Hint 2:

Solution:

 

Solution Code: