MTS 1 Nutanix interview experience | Kumar Rounak

Interview rounds

Round

Medium

Video Call

Duration50 Minutes

Interview date2 Dec 2021

Coding problem2

This round was in the morning (around 10 am). The environment was great and the interviewer made me feel comfortable by making some small talk before starting with the questions.

1. Merge k sorted lists

Hard

25m average time

65% success

0/120

Asked in companies

Given 'k' sorted linked lists, each list is sorted in increasing order. You need to merge all these lists into one single sorted list. You need to return the head of the final linked list.

For example:

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

Output:
1 2 4 5 6 7 8 9 

Explanation:
First list is: 4 -> 6 -> 8 -> NULL
Second list is: 2 -> 5 -> 7 -> NULL
Third list is: 1 -> 9 -> NULL
The final list would be: 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL

Problem approach

I gave the solution of Min Heap-based approach.I added first element of every sorted list to a min-heap using priority queue. Then, as long as the min-heap is not empty, I did the following:
Removed the top element of the min-heap (which is the current minimum among all the elements in the min-heap) and add it to the result list.
If there exists an element (in the same linked list) next to the element popped out in previous step, insert it into the min-heap.
Return the head node address of the merged list
Time Complexity: O(N * log k) , where, ‘N’ is the total number of elements among all the linked lists, ‘k’ is the total number of lists, and ‘n’ is the size of each linked list.
Insertion and deletion operation will be performed in min-heap for all N nodes which takes log k time for each one of them.
The. interviewer was happy with this solution.

Try solving now

2. OS Questions

Differences between process and thread
Necessary conditions for deadlock in a system
Differences between a user-level thread and a kernel-level thread

Problem approach

Tip 1 : Have thorough knowledge of OS and DBMS
Tip 2 : Try to brush up important topics before the interview

Round

Medium

Video Call

Duration60 minutes

Interview date7 Dec 2021

Coding problem2

This round was in the afternoon (around 2 pm). The environment was good and the interviewer was also helpful and made me comfortable before starting with the questions.

1. Sum root to leaf

Easy

10m average time

90% success

0/40

Asked in companies

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain integer value from 1 to 9. Consider each root to leaf path as a number.

For example:

       1
      /  \
     2    3

The root to leaf path 1->2 represents the number 12.
The root to leaf path 1->3 represents the number 13.

Your task is to find the total sum of all the possible root to leaf paths.

In the above example,

The total sum of all the possible root to leaf paths is 12+13 = 25

Note:

The output may be very large, return the answer after taking modulus with (10^9+7).

Problem approach

DFS from the root down to it's descendants:
I needed to keep current path (which stores elements in the path) so far. I also stored the remain targetSum so far (after minus value of elements in the path).
If I reached to leaf node:
Check if targetSum == 0 then we found a valid path from root to leaf node which sum equal to targetSum, so add current path to the answer.
Else dfs on left node and on the right node.

The interviewer was happy.

Try solving now

2. Longest Increasing Path In A 2D Matrix

Hard

10m average time

90% success

0/120

Asked in companies

You have been given a MATRIX of non-negative integers of size N x M where 'N' and 'M' denote the number of rows and columns, respectively.

Your task is to find the length of the longest increasing path when you can move to either four directions: left, right, up or down from each cell. Moving diagonally or outside the boundary is not allowed.

Note: A sequence of integers is said to form an increasing path in the matrix if the integers when traversed along the allowed directions can be arranged in strictly increasing order. The length of an increasing path is the number of integers in that path.

For example :

3 2 2
5 6 6
9 5 11 

In the given matrix, 3 →  5 →  6 and 3 →  5 →  9 form increasing paths of length 3 each.

Problem approach

I calculated the longest path beginning with every cell. Once computed longest for all cells, I returned the maximum of all longest paths.
I first gave the solution using recursion but it had many overlapping sub-problems. So, I then gave an optimal solution using Dynamic Programming.

Try solving now

Round

Medium

Video Call

Duration45 Minutes

Interview date10 Dec 2021

Coding problem1

This round was in the afternoon (around 3 pm). The environment was good and the interviewer made me comfortable before starting with the questions.

1. System Design Question

Design a video streaming service like Netflix where user can upload/view/search videos. The system should be scalable and will be storing and transmitting large volume of data.

Problem approach

Tip 1 : Focus on the basic requirements of the system presented by the interviewer
Tip 2 : Go through the lectures of system design presented by Gaurav Sen on youtube.

Round

Easy

HR Round

Duration30 Minutes

Interview date15 Dec 2021

Coding problem1

In this round, the hiring manager asked some questions regarding the experience in my previous company and why did i wanted to leave that organisation. Then, we had discussions regarding my roles and responsibilities that I will be carrying out in this company.