Round 0 - Online Codility round.
Questions were similar to
https://leetcode.com/discuss/interview-question/1112027/oa-microsoft-march-2021
Round 1 - Project Discussion and Problem solving round
1 - Given two strings check if both are anagrams are not. (Produciton level code quality was required)
2 - There is array of +ve integers (there can be dynamic addition / removal of array elements)
given a number k and n we need to find k from the array which is closest to the number n.
Data structure should support.
- Optimal Insert of new element
- Optimal Removal existing element
- Searching k nearest elements from the array
eg - array [10, 5, 30, 90, 101, 102, 115, 105]
case 1 - n = 100 and k = 2 -> [101, 102]
case 2 - n = 100 and k = 4 -> [90, 101, 102, 105]
Solved it using BST + Heap.Round 2 - Project Discussion + Design Round (HLD + LLD)
Design API rate limiter.
Both Fixed window and rolling window solution were discussed in detail (with trade offs)
HLD + LLD - class structure and interfaces were expected
Interviewer asked to implement one method of fixed window solution.
Round 3 - Project Discussion + Problem solving
1 - Custom Ds Design
Thread safety were reqeuired , there were many questions related to concurrency and synchronization [allow max k thread access for getRandom method]
2 - Given a dictionary and list of string we needed to list down all matching anagrams of strings which exists in dictionary.
We discussed few approaches then optimal anagram finding were required so solved it using Hashmap.
Preprocessed dictionary stored all anagrams against lowest (sorted value) of string .
eg - dict has words - abc, cab, def, random, domran, bac
HasmMap = {
abc -> [abc, cab, bac],
def -> [def],
admnor -> [random, domran]
}
Sort the input dictinary string and return one of values from hashmap if exists.
like if input string is [abc, fed, alpha]
return [[abc, cab, bac], [def], []] Round - 4 - HM Round (Project Discussion + System Design/Problem Solving + Some behavioural Quesitons)
1 - There are n files given having strings in it.Given a String you need to list down all the files which contains the string .
Pre processed the files
Solved it using Trie(for storing file paths in a BST at the end of the string )(BST were used for case where string exists multiple times in a file to avoid duplicate entry, in efficient manner)
Problem Extension - There can be addition/removal/updation of files that needs to be handled
Solved it by storing version of the file path with file path in Trie. We can have older version in our trie for one file if there is a new version of the file . removed older version by using some cron job from the trie.
More Extension - Some discussions around introduction of auth features of the search API.
Tips
1 - Take these interviews as a problem discussion session, always try to communicate your thoughts with the interviewer, they are very helpful.
2 - For design round try to list down all the requirements first then proceed with the solutioning.
3 - Try to write clean code(modular + suitable class/method/variable naming).