Coderpad with 2 questions:
Find a second smallest number in a list
Dynamic programming one:
Traverse a chess board only by moving up and right to get to top left, don’t remember exactly what was the ask like mix moves but it was one of those dynamic programming where you do recursion
After that, I got to the main interview which was in person:
4 rounds:
1 algorithms
2 Data structures
3 system design
4 discussion on your cv with the team lead
Algorithms:
Asked 2 problems, all pseudo code:
First one I think it’s a classic but I did not know it:
You have 100 doors, you pass first time through each of them and open the door,
2nd pass you pass and close every other door, 3rd pass you pass every 3rd door and open
So on, after 100 passes how many doors are open?
Didn’t know, solved after they helped me. They had obvious pointers, like how about do it for 10 doors and see if you see a pattern. After I did some examples I could solve it
2. You have a number, 10 I think you want to reach 1:
You can only do 3 operations: subtract 1, divide by 2, divide by 3. When you divide you can only divide if the number is divisible by that number. Find out min number of operations to get to 1.
It’s a dynamic programming one again, do recursion. Knew how to do this.
3. Data structures, they talked about hashes , linked lists, array lists.
They also asked 2 difficult questions, one was helped and figured out:
Like how to traverse a linked list and find next to last element in one traversal? How about the k to last element?
Second, let’s say you want to do an autocomplete for smth which can be numbers and letters, forgot what, how would keep those objects so that you can give suggestions based on the prefix the user enters? Did not know, answer is to keep them in a tree
System design:
Design me a shortening url service that can scale, to be able to do 1 mil in requests per day, how about 1 billion?
This one just said I’ll probably save in db, shard the data, use a cache, scale pods in kubernetes etc
Final round:
The boss was tough, did not like my cv as I had a lot of jobs on old technologies up until 4 years ago, when I got into the microservices world, so I had the usual stuff like Kafka, kubernetes, spring, jpa…but he was interested into Apache spark, snowflake, a bit of react or angular as they do a bit of everything
Passed about 10 days, have not heard back yet.