SDE - 1

Approach : 

1) Take two variables ‘cnt0’ and ‘cnt1’ to store the count of 0s and 1s respectively. Also, take a variable ‘cnt’ which stores the count of the number of substrings.

2) Now for each i from 0 to N - 1,
2.1) If str[i] is equal to ‘0’ , We increment ‘cnt0’ by 1.
2.2) If str[i] is equal to ‘1’ , We increment ‘cnt1’ by 1.

3) If ‘cnt0’ and ‘cnt1’ are equal, increment ‘cnt’ by 1.

4) If ‘cnt0’ is equal to ‘cnt1’ we return ‘cnt’.

5) Else, we return -1

TC : O(N), where N = length of the string
SC : O(1)

Approach (Using BFS) : 

1) Create an empty queue and enqueue source cell and mark it as visited

2) Declare a ‘STEPS’ variable, to keep track of the length of the path so far

3) Loop in level order till the queue is not empty
3.1) Fetch the front cell from the queue
3.2) If the fetched cell is the destination cell, return ‘STEPS’
3.3) Else for each of the 4 adjacent cells of the current cell, we enqueue each valid cell into the queue and mark them visited.
3.4) Increment ‘STEPS’ by 1 when all the cells in the current level are processed.

4) If all nodes in the queue are processed and the destination cell is not reached, we return -1.

TC : O(N * M), where N and M are the number of rows and columns in the Binary Matrix respectively.
SC : O(N * M)

Approach 1 (Brute Force) :
In this approach, we make use of an idea based on selection sort.

1) Traverse over the given numsnums array choosing the elements nums[i]. For every such element chosen, we try to
determine its correct position in the sorted array. For this, we compare nums[i] with every nums[j], such that i < j < n.

2) If any nums[j] is lesser than nums[i], it means both nums[i] and nums[j] aren't at their correct position for the sorted
array. Thus, we need to swap the two elements to bring them at their correct positions.

3) Instead of swapping, just note the position of nums[i] (given by i) and nums[j] (given by j). These two elements now
mark the boundary of the unsorted subarray(atleast for the time being).

4) Out of all the nums[i] chosen, we determine the leftmost nums[i] which isn't at its correct position. This marks the
left boundary of the smallest unsorted subarray(l).

5) Similarly, Out of all the nums[j] considered for all nums[i] we determine the rightmost nums[j] which isn't at its
correct position. This marks the right boundary of the smallest unsorted subarray(r).

6) Therefore, the length of the smallest unsorted subarray = r−l+1.


TC : O(N^2)
SC : O(1)


Approach 2 (Using Sorting) :

1) We can sort a copy of the given array nums, say given by nums_sorted.

2) Then, if we compare the elements of nums and nums_sorted, we can determine the leftmost and rightmost
elements which mismatch.

3) The subarray lying between them is, then, the required shorted unsorted subarray.


TC : O(N*log(N))
SC : O(N)

Approach 1 (Naive Solution ) :

One by one calculate sum of all sub-arrays possible and check divisible by K.

TC : O(N^2)
SC : O(1)


Approach 2 (Efficient Solution) :

Observe : Let sum(i,j)=subarray sum from arr[i] to arr[j] (both inclusive) (arr[i]+arr[i+1]...+arr[j])
Now for sum(i,j) to be divisible by k , th following condition must hold :
sum(0,j)%k=sum(0,i-1)%k

Keeping the above points in mind , let's design an efficient algo for this problem :

Algorithm :

1) Make an auxiliary array of size k as Mod[k] . This array holds the count of each remainder we are getting after
dividing cumulative sum till any index in arr[].

2) Now start calculating cumulative sum and simultaneously take it’s mod with K, whichever remainder we get
increment count by 1 for remainder as index in Mod[] auxiliary array.

3) Sub-array by each pair of positions with same value of ( cumSum % k) constitute a continuous range whose sum is
divisible by K.

4) Now traverse Mod[] auxiliary array, for any Mod[i] > 1 we can choose any two pair of indices for sub-array by
(Mod[i]*(Mod[i] – 1))/2 number of ways .

5) Do the same for all remainders < k and sum up the result that will be the number all possible sub-arrays divisible
by K.


TC : O(N) where N=size of the array
SC : O(k)

Answer :

Destructor : A destructor in C++ is a member function of a class used to free the space occupied by or delete an
object of the class that goes out of scope. A destructor has the same name as the name of the constructor function in
a class, but the destructor uses a tilde (~) sign before its function name.


Virtual Destructor : A virtual destructor is used to free up the memory space allocated by the derived class object or
instance while deleting instances of the derived class using a base class pointer object. A base or parent class
destructor use the virtual keyword that ensures both base class and the derived class destructor will be called at run
time, but it called the derived class first and then base class to release the space occupied by both destructors.

Answer :

Constructors :
1) A Constructor is a block of code that initializes a newly created object.
2) A Constructor can be used to initialize an object.
3) A Constructor is invoked implicitly by the system
4) A Constructor is invoked when a object is created using the keyword new.
5) A Constructor doesn’t have a return type.
6) A Constructor’s name must be same as the name of the class.
7) A Constructor cannot be inherited by subclasses.


Method :
1) A Method is a collection of statements which returns a value upon its execution.
2) A Method consists of Java/C++ code to be executed.
3) A Method is invoked by the programmer.
4) A Method is invoked through method calls.
5) A Method must have a return type.
6) A Method’s name can be anything.
7) A Method can be inherited by subclasses.

Approach : 

1) We will maintain two tail pointers to the end of each linked list. 
2) When we will traverse in the original linked list, we alternatingly append the current node to the end of each list.
3) For that, we will point the next of the tail node to the current node and move the tail pointer forward. 

TC : O(N), where N = number of nodes in the linked list.
SC : O(1)

Approach : 

1) Calculate the length of both the lists, say len1 and len2

2) Get the absolute difference of the lengths, diff = |len1 – len2|

3) Now traverse the long list from the first node till ‘diff’ nodes so that from there onwards both the lists have equal number of nodes

4) Then traverse both the lists in parallel and check whether a common node is reached (Note that getting a common node is done by comparing the address of the nodes, not the data)
4.1) If yes, return that node’s data
4.2) If no, return -1

TC : O(N) , where N = maximum length of the linked list
SC : O(1)

Approach : 

1) Start both hourglasses at the same time.

2) At 4 minutes 4 minutes hourglass runs out and flip it. 7 minutes hourglass is left with 3 minutes.

3) At 7 minutes 4 minutes hourglass is left with 1 minute. 7 minutes hourglass runs out and flip it.

4) At 8 minutes: 4 minutes hourglass runs out and 7 is filled with 6 minutes and 1 minute on the other side. Flip it as the sand is left with 1 minute.

5) At 9 minutes: 7 minutes hourglass becomes empty from above side.

15 people can sit around a circular table total in (14!) no. of ways . Out of these total ways only those ways favors for
the happening of the required event in which the two particular persons sit together , which can be done in

(13! ×2!) no. of ways . Hence the required probability = 13! × 2!/(14!) = 2/14 = 1/7 .

So odds in favor 1 : 6 and odds against 6 : 1 .

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.