SDE Nagaaro interview experience | Piyush

Interview rounds

Round

Medium

Online Coding Interview

Duration180 minutes

Interview date16 Aug 2021

Coding problem5

It was a long round of around 3 hours divided into 2 parts
1. Aptitude(MCQ)
2. Coding(Subjective)

1. Maximum meetings

Easy

10m average time

90% success

0/40

Asked in companies

You are given the schedule of 'N' meetings with their start time 'Start[i]' and end time 'End[i]'.

You have only 1 meeting room. So, you need to return the maximum number of meetings you can organize.

Note:

The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting.

For example:

'N' = 3, Start = [1, 3, 6], End = [4, 8, 7].

You can organize a maximum of 2 meetings. Meeting number 1 from 1 to 4, Meeting number 3 from 6 to 7.

Problem approach

1. Sort all pairs(Meetings) in increasing order of the second number(Finish time) of each pair.
2. Select the first meeting of the sorted pair as the first Meeting in the room and push it into the result vector and set a variable time_limit(say) with the second value(Finishing time) of the first selected meeting.
3. Iterate from the second pair to the last pair of the array and if the value of the first element(Starting time of meeting) of the current pair is greater than the previously selected pair's finish time (time_limit) then select the currency pair and update the result vector (push selected meeting number into a vector) and variable time_limit.

Try solving now

2. Partition to K equal sum subsets

Moderate

40m average time

70% success

0/80

Asked in companies

You are given an array of 'N' integers, and a positive integer 'K'. You need to determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of elements of each subset is equal.

Note:

1. The array can have duplicate elements.

2. Each of the array elements must belong to exactly one of the 'K' subsets.

3. The elements chosen for a subset may not be contiguous in the array.

Problem approach

1. If K is 1, then we already have our answer, the complete array is only a subset with the same sum.
2. If N < K, then it is not possible to divide the array into subsets with an equal sum because we can’t divide the array into more than N parts.
3. If the sum of the array is not divisible by K, then it is not possible to divide the array. We will proceed only if k divides the sum. Our goal reduces to divide the array into K parts where the sum of each part should be array_sum/K

Try solving now

3. 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

A Simple Solution is to initialize the result as the first list. Now traverse all lists starting from the second list. Insert every node of the currently traversed list into the result in a sorted way.

Try solving now

4. Sort A “K” Sorted Doubly Linked List

Moderate

15m average time

85% success

0/80

Asked in companies

You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Let us consider K is 3, an element at position 4 in the sorted doubly linked list, can be at positions 1, 2, 3, 4, 5, 6, 7 in the given linked list because the absolute difference of all these indices with 4 is at most 3.

Note :

All elements are distinct.

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward.

Problem approach

Sort the given doubly linked list using the insertion sort technique. While inserting each element in the sorted part of the list, there will be at most k swaps to place the element to its correct position since it is at most k steps away from its correct position.

Try solving now

5. Duplicate Subtrees

Moderate

30m average time

70% success

0/80

Asked in companies

You have been given a binary tree, you are supposed to return the root values of all the duplicate subtrees. For each duplicate subtree, you only need to return the root value of any one of them.

Two subtrees are duplicate if and only if they have the same structure with the same node values.

For example:

In the below binary tree :

The duplicate subtrees are {{2, 3}, {3}} and we have to just return the root values of each duplicate subtree, so the output is {2, 3}.

Problem approach

The idea is to use hashing. We store in order traversals of subtrees in a hash. Since simple inorder traversal cannot uniquely identify a tree, we use symbols like ‘(‘ and ‘)’ to represent NULL nodes.

Try solving now

Round

Medium

Telephonic

Duration25 minutes

Interview date31 Aug 2021

Coding problem2

The technical Interview round was not at all difficult. The main focus of the interviewer was my projects and development fields.
He also asked some DS/Algo questions that were at a medium level, and some easy questions for database management.

1. DBMS Question

Explains the concept of keys.

2. Puzzle Question

How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn? We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of wire might burn in 10 minutes and 50 minutes respectively

Problem approach

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

Round

Easy

HR Round

Duration15 minutes

Interview date31 Aug 2021

Coding problem3

It took place on the same day as the technical round. It was quite the easiest round of all. The interviewer just asked me to introduce myself, projects I have worked on, my Internships experience, and were they internships paid.