SDE - 1

You have been given string 'S' of length 'N' that may contain duplicate alphabets. Your task is to return the count of distinct subsequences of it.

For example:

For the given string “deed” :
The possible subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“d”}, {“dd”}, {“ed”}, {“ded”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}.

As, {“d”}, {“e”}, {“de”}, {“ed”} and {“ded”} are repeated. 

The distinct subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“dd”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}

Thus, the output will be 11. 

Note:

As the answer can be large, return your answer modulo 10^9  + 7.  

In an internet cafe, there are 'N' computers numbered from 1 to ‘N’. These computers are connected by 'M' wires. Each wire connects two different computers. Information can be transmitted between two computers if there exists a path between the two computers by travelling through some ( possibly Zero ) intermediate computers. The cafe owner wants to remove some of the existing wires and then use those wires to connect some other pair of computers in such a manner that after the rearrangement, it is possible to transmit information between all the pairs of computers.

You are given the description of each of the 'M' wires, i.e., the two computers that the wire connects. Your task is to find the minimum number of wires that the cafe owner needs to remove and rearrange to satisfy the above conditions.

If there is no possible way to remove and rearrange wires to satisfy the above conditions, then return -1.

You are working as a cab driver. Your car moves in a straight line and moves toward the forward direction only. Initially, you have ‘C’ empty seats for the passengers.

Now, you are given ‘N’ number of trips that you have to make. In each trip, you are given three integers ‘Num’, ‘pickPoint’, and ‘dropPoint’ denoting that there are ‘Num’ numbers of passengers standing at 'pickpoint’ and you have to drop them at 'droppoint’.

Your task is to find if it is possible to pick up and drop off all the passengers of all the given trips or not.

Note :

You have a special type of car containing any number of seats.

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

In this interview, I explained to him my most recent project which I did standalone in my previous internship.
Some of his questions were.
Why do you prefer MongoDB over SQL?
If I had to do this with SQL, what will be the schemas and the changes?
How do you handle concurrency?
How optimal is this? Is there any scope for improvements?
What can be done for improvements?
Explain the flow of this project.

What are mutex locks, deadlocks and their prevention? These questions were asked concerning my project.
Along with this question, he asked me some language-specific ( c++ ) questions. He asked about the internal implementation of unordered maps and maps in c++. He was expecting a one of the self-balancing tree explanation.