SDE - 1

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

Ninja has two strings ‘s’ and ‘t’ of same length, he knows that both strings are equivalent strings which means s[i], t[i] will follow all rules of any equivalence relation that are:

Reflexive : s[i] = t[i]

Symmetric: s[i] = t[i] => t[i] = s[i]

Transitive: if s[i] = t[i] and t[i] = s[j] then s[i] = s[j]

Ninja wants your help to find the lexicographically smallest equivalent string of a given string ‘str’.

Note:

1. String ‘s’, ‘t’ and ‘str’ consist of only lowercase English letters from ‘a’ – ‘z’.
2. String ‘s’ and ‘t’ are of same length.

For example:

Let s = “abc” , t = “xyz” and str = “xbc” then all strings that we can generate are “abc”, “abz”, “ayc”,”ayz”, “xbc”, “xbz”, “xyc”, “xyz” and smallest of all these is “abc”. 

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.

A story based question which was asked in terms of threads and tasks.

Detailed discussion about current work and tech stack.

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists.

The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit.

Calculate the sum of the two numbers and return the head of the sum list.

Example :

Input:
'num1' : 1 -> 2 -> 3 -> NULL
'num2' : 4 -> 5 -> 6 -> NULL

Output: 5 -> 7 -> 9 -> NULL

Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.

You are given a 2D board('N' rows and 'M' columns) of characters and a string 'word'.

Your task is to return true if the given word exists in the grid, else return false. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring.

Note:

The same letter cell should not be used more than once.

For Example:

For a given word “design” and the given 2D board 
[[q’, ‘v’, ‘m’, ‘h’],
 [‘d’, ‘e’, ‘s’, ‘i’],
 [‘d’, ‘g’, ‘f’, ‘g’],
 [‘e’, ‘c’, ‘p’, ‘n’]]

The word design can be formed by sequentially adjacent cells as shown by the highlighted color in the 2nd row and last column.

Discussion on Multi-Threading, Mutual Exclusion, Design Patterns in Java, Inheritance vs Interfaces, Synchronization, Producer-Consumer problem

This round also started off with introduction followed by prior experience. Then Interviewer asked me an LLD question where I needed to design and code one of the Microsoft Product's features. Used SOLID principles and factory pattern in designing which impressed the interviewer. (Thanks to my current company's project where I learnt and used SOLID principles + various design patterns in production). Then I wrote code for my design. Interviewer told me that it is correct solution but can still be improvised with additional design patterns. Then I was asked two programming questions.

Ninja is given an integer ‘N’ . One day Ninja decides to break the integer into K positive parts (K>=2) such that the sum of all parts is equal to ‘N’.Ninja wants to maximize the product of all the ‘K’ parts.

Help Ninja in helping what maximum possible product it can obtain by breaking the integer ‘N’ into ‘K’ positive parts where ‘K’ can be any integer greater than 2.

Why do you want to join Microsoft?

How was your previous work experience?

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .

Return true if the given string 'S' is balanced, else return false.

For example:

'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.