SDE - Intern Nagaaro interview experience | Anonymous

Interview rounds

Round

Easy

Online Coding Interview

Duration180 minutes

Interview date1 Sep 2021

Coding problem4

1. Common Elements In Three Sorted Arrays

Moderate

35m average time

65% success

0/80

Asked in companies

You are given three arrays 'A', 'B' and 'C' of length 'N', 'M' and 'K' respectively. All the three arrays are sorted in non-decreasing order. Your task is to find all such elements which are present in all the three given arrays.

Note:

1. The output array should have the same ordering of elements as the original arrays.
2. Even if a particular element appears more than once in each of the three arrays, it should still be present only once in the output array.
3. If there are no common elements in the arrays, return an empty array.

For example:

Consider the three arrays A = [ 2, 3, 4, 7 ] , B = [ 0, 0, 3, 5 ] , C = [ 1, 3, 8, 9 ]
The output array should be [ 3 ] as 3 is the only element which is present in all the three arrays.

Problem approach

A Better Solution is to use Binary Search.
1) Iterate over all elements of A[],
a) Binary search for element just smaller than or equal to in B[] and C[], and note the difference.
2) Repeat step 1 for B[] and C[].
3) Return overall minimum.
Time complexity of this solution is O(nLogn)

Try solving now

2. Count Derangements

Moderate

25m average time

75% success

0/80

Asked in companies

Given a number ‘N', the task is to find the total number of derangements of a set of ‘N’ elements.

A ‘Derangement’ is a permutation of 'N' elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.

For example, 'N' = 2 , {0, 1} and {1, 0} are the only derangement therefore output will be 1.

Problem approach

Let countDer(n) be count of derangements for n elements. Below is the recursive relation to it.

countDer(n) = (n - 1) * [countDer(n - 1) + countDer(n - 2)]
How does above recursive relation work?

There are n – 1 way for element 0 (this explains multiplication with n – 1).
Let 0 be placed at index i. There are now two possibilities, depending on whether or not element i is placed at 0 in return.

i is placed at 0: This case is equivalent to solving the problem for n-2 elements as two elements have just swapped their positions.
i is not placed at 0: This case is equivalent to solving the problem for n-1 elements as now there are n-1 elements, n-1 positions and every element has n-2 choices

Try solving now

3. Shortest Path In A Binary Maze

Moderate

30m average time

75% success

0/80

Asked in companies

Given a maze in the form of a binary rectangular matrix of size M*N, where each element can either be 0 or 1, the task is to find the length of the shortest path in a maze from a given source cell to a destination cell.

The path can only be created out of a cell if its value is 1 and at any given moment, we can only move one step in one of the four directions. The valid moves are:

Up: (x, y) -> (x - 1, y)
Left: (x, y) -> (x, y - 1)
Down: (x, y) -> (x + 1, y)
Right: (x, y) -> (x, y + 1)

If there is no path from a given source cell to a destination cell, return -1.

For example :

consider the binary matrix below. If source = (0, 0) and destination = (3, 4), the shortest path from source to destination has length 11.

Problem approach

The idea is to uses Recursion:

Start from the given source cell in the matrix and explore all four possible paths.
Check if the destination is reached or not.
Explore all the paths and backtrack if destination is not reached.
And also keep track of visited cells using an array.
Valid Moves are:

left: (i, j) ——> (i, j – 1)
right: (i, j) ——> (i, j + 1)
top: (i, j) ——> (i - 1, j)
bottom: (i, j) ——> (i + 1, j )

Try solving now

4. Max GCD Pair

Moderate

35m average time

75% success

0/80

Asked in companies

You are given an array of positive integers. Find the GCD(Greatest Common Divisor) of a pair of elements such that it is maximum among all possible pairs. GCD(a, b) is the maximum number x such that both a and b are divisible by x.

For example: 
If the given array is {1, 5, 2, 3, 4}, the output will be 2 (which is GCD of 2 and 4, all other pairs have a GCD of 1)

Problem approach

An Efficient method is to make two arrays of size n and m for row and column respectively. And store the GCD of each row and each column. An Array of size n will contain GCD of each row and array of size m will contain the GCD of each column. And replace each element with maximum of its corresponding row GCD or column GCD.

Try solving now

Round

Easy

Video Call

Duration30 minutes

Interview date14 Sep 2021

Coding problem5

This was type of Rapid questions round. I have to answer questions very quickly. AFter this I was a DS algo question to solve

1. Collect Maximum Coins in Matrix

Moderate

0/80

Asked in companies

You are given a matrix of ‘M’ rows and ‘N’ columns. The cells of the matrix contain either a coin or are empty.

You are allowed to visit every boundary cell that has a coin in it and collects that coin apart from that, you are allowed to collect the coin in one of the four adjacent cells. Find the maximum number of coins that you can collect from the matrix.

For Example :

If Matrix of size 3 * 5 is: 
0 1 1 0 0
0 1 0 1 0
1 0 0 0 0


Then, out of the five coins in the matrix, you can collect a maximum of four coins. This is because the coin at (0, 1) lies on the boundary and after collecting the coin one can also collect the coin at (1, 1) as it lies in the adjacent cell. We can also collect the coin at (2, 0). But we cannot collect the coin at (1, 3), as this coin doesn’t lie on the boundary and it cannot be reached from one of the boundary coins.

Problem approach

Initial position is cell (0, 0) and initial direction is right.

Following are rules for movements across cells.

If face is Right, then we can move to below cells

Move one step ahead, i.e., cell (i, j+1) and direction remains right.
Move one step down and face left, i.e., cell (i+1, j) and direction becomes left.
If face is Left, then we can move to below cells

Move one step ahead, i.e., cell (i, j-1) and direction remains left.
Move one step down and face right, i.e., cell (i+1, j) and direction becomes right.
Final position can be anywhere and final direction can also be anything. The target is to collect maximum coins.

Try solving now