Status : 1 YOE as Software Engineer at MS, 2018 CS Grad

Telephonic Interview:
There is a magic word, and you have access to this method

getMagic(){

}

The method will return tuple of charater ('a','c') such that 'a' is before 'c' in magic word.
getMagic will always return a unique tuple.
Use this method to return actual magic word.

E.g.
getMagic() => ('c','a')
getMagic() => ('a', 't')
getMagic() => ('c', 't')

Return:
Magic word => 'cat'

** Disuss Ambigous magic words
** Come up with idea, and disussed it with the interviewer.
** spend most of time discussing solution/ambigious cases and optimizations and coded it in last few minutes

Onsite

Round 1
Given list of Ids on N players
Given rankList in ascending order of M tournament happened between players
Return overall rank of N Players, if it is ambigious/not possible to determine extact order then return -1.
E.g.

players = [4,1,2,3]
rankList1 = [4,1]
rankList2 = [3,2]
rankList3 = [4,3]
rankList4 = [2,1]

Return:
Rank = [4,3,2,1]

** Main disucssion revolves around how to tell if there is ambiguity or not.
** Not Sure, Maybe Expecting another problem to ask(recruiter feedback)

Round 2
Given List of N Integers, Can have -ve Numbers as well
Arr = [1,4,3,6,7] , N = 5

1. Return subsequence whose sum % N == 0
2. Return subarray whose sum % N == 0
3. Can you prove there always will be a subarray % N == 0 if a subsequence is there.

Return:

[3,7] or [4,6] or [4,3,6,7]
For subsequence [3,7] = 3 + 7 = 10 => 10 % 5 == 0
For subarray [4,3,6,7] = 20 % 5 == 0

** Spent some time on subsequence, unable to get come up with logic suggested bruteforce.
** Question changed to part 2, quickly come up with O(N) optimal solution, coded it.
** He asked to prove 3rd point.

Round 3
Googlyness and Leadership Principle

1. Tell me a time when you have hard time working with any collegues
2. When you lead some design/ project within team
3. Tell me a time when you when above and beyond to deliever better customer experience
   rest of them where general questions either hypothetical or past experience based

Round 4
Design an API classify which gets cpu usage from Machine and classify it as High, Low and Medium.
Note : classify API can get called 1-50(random) times in a second.
API :

classify (cpu_usage_inpercentage, timestamp){

}

This was open ended question, once discussion started. The idea is to classify in a way such that less toggling happens.

** Code should be configurable with values you assume
** Don't classify every second assume some window_time.
** I spend most of time with design, left with less time to code.

Round 5
You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks)

Example given N=3, L=2 the possible arrangments are:
{2, 1, 3} 
{1, 3, 2}
{2, 3, 1}

Return: 3

** Coded recursive bruteforce solution.
** Working most of the time to get optimised solution with dp/recurrence relations.
** Found some key observations and discuss it with interviews, unable to come up with optimized code

Overall It was good experience, but I am not sure if interviewer was expecting to ask another question in 1st and 5th round. I got major feedback completing code in time, and writing efficient code (maybe coz of 5th round)