Microsoft | O365 team (experienced)

Phone interview (2 rounds), screen share (e.g., share your vscode):

• median of two sorted array
• zombie cluster problem
• find the minimal number in a bst which is just larger than given number K

Onsite interview (4 rounds), white board:

• design a datastructure for stream event storage, and implement a method called top(int n, timestamp xx:xx:xx), that it should quickly returns top N hostest events (by event type) in a given timerange withoud modify the datastructure, the number of events is in range of 1 ~ 1M
• convert digit numbers into english (e.g.: input 111 -> output "one hundred and eleven")
• design a tour system with multi-threads, with a map, one guide and many tourists, it should traverse every spot in map by only once and can handle tourists questions (with anwsers) and it shold be able to terminate the tour in emergency situations
• binary tree iterator
• sort colors (dutch flag problem)
• slot machine problem (got rejected on this, the interviewer said to hr that i didn't get in deep enough of the problem. cannot find similar question, tried to google it many times)

the slot machine problem is like this:

• imagine a slot machine with 3 slots, and you can only roll one slot at a time in turns, that slot1 -> slot2 -> slot3 -> slot1 -> slot2...
• each slot got A ~ Z, and a slot can be rolled in both up and down directions by ONLY ONE letter (e.g.: A -> B or A -> Z), and once any slot has been rolled (in any direction), consider it as ONE operation
• with a give target (e.g.: AAA) and a initial random state (e.g.: EFJ), find the minimal number of rolls to achieve the target and display all states (e.g. EFJ -> FFJ -> FGJ -> FGK -> ... AAB -> AAA)
• AND, with a given block list (e.g.: [ABC, EFG, XYZ, ...], that you cannot roll the slot machine into any one of the blocked patterns (e.g.: state is ABB and this turn you should roll slot 3, then you cannot roll ABC, you can only roll slot 3 down for ABA, etc.)
• i consider this as "really hard", cannot solve this