SDE - Intern

You have been given a binary matrix ‘MAT’ of size ‘N’ * ’N’. Let ‘i’, ’j’ denote the row and column of the matrix, respectively. If ‘MAT’[i][j] is equal to 0, flip every 1 in the ‘i’th row and ‘j’th column i.e., in the same row and the column as 0.

Your task is to return the total number of flips done over all the elements of the matrix.

Note:

1. Each element in the matrix 'MAT' is either a ‘0’ or ‘1.’

2. The flip operation is performed only for the 0s in the original matrix, and not for the new 0s formed as a result of flipping 1s in the original matrix.

3. If a cell is already flipped, don’t flip it twice.

4. Return the minimum number of flips needed.

For example:

Let the matrix be:

Then we return 6. As shown in the figure, the cells marked in red will be counted as they lie in the same row or column as 0 and will be flipped.

You have been given an array 'ARR' of ‘N’ integers. You have to return the minimum number of jumps needed to reach the last index of the array i.e ‘N - 1’.

From index ‘i’, we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] .

'ARR[i]' represents the maximum distance you can jump from the current index.

If it is not possible to reach the last index, return -1.

Note:

Consider 0-based indexing.

Example:

Consider the array 1, 2, 3, 4, 5, 6 
We can Jump from index 0 to index 1
Then we jump from index 1 to index 2
Then finally make a jump of 3 to reach index N-1

There is also another path where
We can Jump from index 0 to index 1
Then we jump from index 1 to index 3
Then finally make a jump of 2 to reach index N-1

So multiple paths may exist but we need to return the minimum number of jumps in a path to end which here is 3.

I was asked to write a query to select all the people who are below the age of 75 from a set of people.

What is the diamond problem?

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

First I was asked to introduce myself wherein I spoke about my hometown and my earlier education and also included my hobbies. Then I was asked why I wanted to work in that particular company to which I answered that I wanted to because of a few reasons (Know about the company beforehand). I was also asked which was my dream company and why was it my dream company. The interviewer then asked me about my future plans...if I wanted to go for further studies etc. I was also asked what drives me in life. I was also questioned on "cloud" as that was the technology being used by the company recently.

I was asked to introduce myself and about my hobbies and hometown. They were very general questions. It was a fun and relaxed round.