Software Developer

Approach : 

1) First, iterate through the array “points” and find the minimum and maximum X coordinates over the array and store them in "minimumX" and "maximumX".

2) Find the X coordinate of the reflection line and store it in variable 'reflectionX'. reflectionX = (minimumX + maximumX) / 2.

3) Store X coordinate of all the points into the set that have the same Y coordinate. To do so, create a map that stores the Y coordinate as the key and the set of X coordinates as the value.

4) Now, iterate over the array "points"
4.1) For each point, consider value [X1, Y1], find its reflection of the point in the set containing the same Y coordinate, which means find the set whose key is Y1 in the map and then find value (2 * reflectionX) - X1 in the set.

4.2) If the set does not contain the value, there is no reflection of the point [X1, Y1].

5) If we find at least one reflection for each point, Return true

6) Else, Return false.

TC : O(N * log(N)), where N = number of points.
SC : O(N)

Approach (Using Flood-Fill Algo) :

1) We create two arrays, dx, and dy, in which we store the unit vectors for all eight directions. Thus, when we are at a given cell, we can easily check for all its adjacent cells by simply looping over the two arrays, adding their values to the current position, and checking for this new position recursively.

2) We will also create a 2D boolean array of the same size as the input array that will keep track of whether a cell has been visited. Initialize an ans variable as 0.

3) Iterate through the input array. For every cell that is equal to 1 and not visited, first increase ans by 1 and use the flood fill algorithm to mark that cell and every other connected cell that is equal to 1 as visited so we don't count them again.

4) Return the ans variable.

TC : O(N*M), where N and M are the dimensions of the matrix.
SC : O(N*M)

Approach (Using Stack) : 

1) Create an empty stack.

2) Start from the first histogram bar, and do the following for every bar ‘heights[i]’ where ‘I’ varies from 0 to ‘N’-1.

3) If the stack is empty or heights[i] is higher than the bar at top of the stack, then push ‘I’ to the stack.

4) If this bar is smaller than the top of the stack, then keep removing the top of the stack while the top of the stack is greater. Let the removed bar be heights[tp]. Calculate the area of the rectangle with heights[tp] as the smallest bar. For heights[tp], the ‘left index’ is the previous (previous to tp) item in the stack and the ‘RIGHT_INDEX' is ‘I’ (current index).

5) If the stack is not empty, then one by one remove all bars from the stack and do step 4 for every removed bar.


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

Approach : 

1) Declare a character stack.

2) Now traverse the expression string
2.1) If the current character is a starting bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to stack .

2.2) If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.

3) After complete traversal, if there is some starting bracket left in the stack then “not balanced”.

4) Otherwise, the string is balanced.

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

ACID properties is the combination of Atomicity, Consistency, Isolation, and Durability properties. These properties are very helpful in allowing a safe and secure way of sharing the data among multiple users.

1) Atomicity: This is based on the concept of “either all or nothing” which basically means that if any update occurs inside the database then that update should either be available to all the others beyond user and application program or it should not be available to anyone beyond the user and application program.

2) Consistency: This ensures that the consistency is maintained in the database before or after any transaction that takes place inside the database.

3) Isolation: As the name itself suggests, this property states that each transaction that occurs is in isolation with others i.e. a transaction which has started but not yet completed should be in isolation with others so that the other transaction does not get impacted with this transaction.

4) Durability: This property states that the data should always be in a durable state i.e. any data which is in the committed state should be available in the same state even if any failure or restart occurs in the system.

The process of hiding irrelevant details from users is known as data abstraction. Data abstraction can be divided into 3 levels : 

1) Physical Level : It is the lowest level and is managed by DBMS. This level consists of data storage descriptions and the details of this level are typically hidden from system admins, developers, and users.

2) Conceptual or Logical level : It is the level on which developers and system admins work and it determines what data is stored in the database and what is the relationship between the data points.

3) External or View level : It is the level that describes only part of the database and hides the details of the table schema and its physical storage from the users. The result of a query is an example of View level data abstraction. A view is a virtual table created by selecting fields from one or more tables present in the database.

Approach (Using Union-Find Algo) : 

1) We initialise two arrays ‘PARENT’ and ‘RANK’ to keep track of the parent and rank of the subsets. Here rank denotes the depth of the tree (subset).

2) Now we will iterate through all edges of the graph:
2.1) Find the parent of both vertices (say ‘PARENT1’ and ‘PARENT2’).

2.2) If ‘PARENT1’ == ‘PARENT2’
Return “Yes”. Here, ‘PARENT1’ == ‘PARENT2’ represents that both subsets are initially connected and now we have another edge connecting them. Hence a cycle exists.

2.3) Else If ‘PARENT1’ != ‘PARENT2’
Union both subsets into a single set. We are doing this because we have two subsets and an edge connecting them. Now both subsets combine and become a single subset.

3) Finally, return “No”.


TC : O(M * logN), where N is the number of vertices and M is the number of edges in the graph.
SC : O(N)

Approach : 

1) Create a variable currentColum initialized to M-1.

2) Create another variable row initialized to -1.

3) Now traverse for every row from i = 0 to i = N, and for each row, perform the following steps:
3.1) Till the value of currentColumn is greater than or equal to 0 and ARR[i][currentColumn] = 1 then perform following steps:
i) Decrement currentColumn by 1.
ii) Update the row with i.

4) Finally, return row as the answer.


TC : O(N+M), where N = number of rows and M = number of columns
SC : O(1)

If we light a stick, it takes 60 minutes to burn completely. What if we light the stick from both sides? It will take exactly half the original time, i.e. 30 minutes to burn completely.

1) 0 minutes – Light stick 1 on both sides and stick 2 on one side.
2) 30 minutes – Stick 1 will be burnt out. Light the other end of stick 2.
3) 45 minutes – Stick 2 will be burnt out. Thus 45 minutes is completely measured.

Collision doesn’t happen only in following two cases
1) All ants move in counterclockwise direction.
2) All ants move in clockwise direction.

Since every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting), there are total 23 possibilities.

Out of 23 possibilities, only 2 don’t cause collision. So, the probability of collision is 6/8 or 3/4 and the probability of non-collision is 2/8 or 1/4.