SDE - Intern

Approach :

1 )We will use a map data structure that will store the height of fired arrows.

2) Start a loop from i = 0 to i = N - 1 and for the i’th balloon if the map contains the value ARR[i] then it
means this balloon will get hit by the previous arrow.
2.1) Therefore decrease the count of ARR[i] in the map and if it becomes 0 remove the key from the
map.
2.2) Increase the count of ARR[i]-1 in the map because there is an arrow at this height available.

3) If the map does not contain the ARR[i] then We will need to fire a new arrow to increase the count of
ARR[i] in the map.

4) Now at the end find the sum of all the arrows present in the map and return it.


TC : O(N)), where N is the number of balloons.
SC : O(N)

Approach : I solved this problem using Multisource-BFS as I had solved questions similar to this while preparing for
my interviews.

Steps :

1) Initialize ‘TIME’ to 0.

2) Declare a Queue data structure and a 2D boolean array ‘VISITED’.

3) Push all cells with rotten orange to the queue.

4) Loop till queue is not empty
4.1) Get the size of the current level/queue.
4.2) Loop till the 'LEVEL_SIZE' is zero:
i) Get the front cell of the queue.
ii) Push all adjacent cells with fresh oranges to the queue.
iii) Mark the cells visited which are pushed into the queue.
4.3) Increment ‘TIME’ by 1.

5) Iterate the grid again. If a fresh orange is still present, return -1.

6) Return maximum of ‘TIME’ - 1 and 0.


TC : O(N * M), where N and M are the numbers of rows and columns of the grid respectively.
SC : O(N*M)

Approach : 

1) We can store the minimum element encountered at any point of time in a variable, say ‘MINELE’.

2) To handle the case when the minimum element is removed, we would need to store the previous minimum element.

3) This can be done by storing the value 2 * 'DATA' - ‘MINELE’ when a new minimum value is added to the stack.

4) Now, when we need to push a number in the stack : 

4.1) We first need to check if the stack is empty or not. 
4.2) If the stack is empty, we simply push the integer in the stack and make the ‘MINELE’ as ‘DATA’. 
4.3) Otherwise, if the data is greater than or equal to the top value of the stack, simply push the data into the stack. 
4.4) Else, push 2 * 'DATA' - ‘MINELE’ in the stack and update the value of ‘MINELE’ as data.


5) For ‘POP’ : 

5.1) We need to check if the stack is empty. 
5.2) If the stack is empty, we return ‘-1’. 
5.3) Otherwise, if the top value of the stack is greater than or equal to the ‘MINELE’ of the stack, simply pop the top value of the stack, the minimum value here would remain the same. 
5.4) Else, the top is the minimum element and hence we need to retrieve the previous minimum element in the stack. 
5.5) So update the ‘MINELE’ = 2 * ‘MINELE’ - ‘TOP’.


6) For ‘TOP’ : 

6.1) We need to check if the stack is empty. 
6.2) If the stack is empty, we return ‘-1’. 
6.3) Otherwise, if the top value of the stack is greater than or equal to the ‘MINELE’ of the stack, simply return the top value of the stack. 
6.4) Else we need to return the minimum value in the stack, ‘MINELE’.


7) For ‘GETMIN’, we need to check if the stack is empty. If the stack is empty, we return ‘-1’. Otherwise, we return the minimum value in the stack, ‘MINELE’.

8) For ‘ISEMPTY’, we just need to check if the stack is empty.



TC : O(1)

For push(): O(1)
For pop(): O(1)
For top(): O(1) 
For getMin(): O(1)
For isEmpty(): O(1) 


SC : O(1)

Approach :

1) Recursively traverse the entire linked list to get the last node as a rightmost node.

2) When we return from the last recursion stack. We will be at the last node of the Linked List. Then the last node
value is compared with the first node value of Linked List.

3) In order to access the first node of Linked List, we create a global left pointer that points to the head of Linked List
initially that will be available for every call of recursion and the right pointer which passes in the function parameter of
recursion.

4) Now, if the left and right pointer node value is matched then return true from the current recursion call. Then the
recursion falls back to (n-2)th node, and then we need a reference to the 2nd node from head. So we advance the left
pointer in the previous call to refer to the next node in the Linked List.

5) If all the recursive calls are returning true, it means the given Linked List is a palindrome else it is not a palindrome.


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

1) OOPs is very helpful in solving very complex level of problems.
2) Highly complex programs can be created, handled, and maintained easily using object-oriented programming.
3) OOPs, promote code reuse, thereby reducing redundancy.
4) OOPs also helps to hide the unnecessary details with the help of Data Abstraction.
5) OOPs, are based on a bottom-up approach, unlike the Structural programming paradigm, which uses a top-down approach.
6) Polymorphism offers a lot of flexibility in OOPs.

If you are a user, and you have a problem statement, you don't want to know how the components of the software work, or how it's made. You only want to know how the software solves your problem. Abstraction is the method of hiding unnecessary details from the necessary ones. It is one of the main features of OOPs. 
For example, consider a car. You only need to know how to run a car, and not how the wires are connected inside it. This is obtained using Abstraction.

Overloading is a compile-time polymorphism feature in which an entity has multiple implementations with the same name. For example, Method overloading and Operator overloading.

Whereas Overriding is a runtime polymorphism feature in which an entity has the same name, but its implementation changes during execution.

Access specifiers, as the name suggests, are a special type of keywords, which are used to control or specify the accessibility of entities like classes, methods, etc. Some of the access specifiers or access modifiers include “private”, “public”, etc. These access specifiers also play a very vital role in achieving Encapsulation - one of the major features of OOPs.

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.