LinkedIn | SSE | 6 YOE | India
Summary
I recently interviewed at LinkedIn for an SSE role in India. The interview process covered a technical screening, two coding rounds, a system design challenge, and a behavioral discussion, focusing on a mix of data structures, algorithms, and system architecture.
Full Experience
My interview journey at LinkedIn for the SSE position in India involved several distinct rounds.
The Tech Screening started with theoretical questions about operating system concepts like processes vs. threads and virtual memory. Following this, I was asked to design a data structure capable of adding an element and removing a random element, both in O(1) time. I explained a solution involving an ArrayList where a random element is swapped with the last element before removal.
Coding Module 1 presented two problems. The first involved connected components of a graph, which I was able to solve. The second was the well-known Celebrity Problem. I could only come up with an O(n^2) brute-force solution, and an optimal solution was expected.
Coding Module 2 also had two problems. The first was to find the k closest elements to a target in a Binary Search Tree (BST) within O(n) time and O(k) space. I struggled with this, contemplating an in-order traversal with a k-size Deque but couldn't finalize it. The second problem was to design a data structure that supports incrementing/decrementing keys and retrieving keys with max/min frequency in O(1) time. I approached this using concepts similar to the LRU cache problem, and believe I provided a valid solution.
The Complex System Design round focused on designing a Metric Collection System, specifically emphasizing the data store component.
Finally, the Host Manager round was a general discussion about my past projects, diving deep into a recent one, my role, impact, and the challenges I faced.
Interview Questions (5)
Design a data structure that can perform the following operations in O(1) time:
- Add an element
- Remove a random element
Identify the 'celebrity' in a group of people, where a celebrity is someone who is known by everyone else but does not know anyone. The problem typically involves querying a knows(A, B) function to determine if A knows B.
Given a Binary Search Tree (BST) of integer numbers and a target value, find the k closest points (nodes) to the target. The target may not be present in the BST, and 'closest' refers to the absolute distance. The solution should aim for O(n) time complexity and O(k) space complexity.
Example:
10
/
5 20
/\ /
1 6 19 35
7
target=8, and k=3, it should return 6,7,10.Given
target=6, and k=3, it should return 5,6,7.Implement a data structure, AllForOne, that supports the following operations in O(1) time:
incrementKey(String key): Increments the frequency of a key by 1. If the key is not present, adds it with frequency 1.decrementKey(String key): Decrements the frequency of a key by 1. If its frequency becomes 1, removes the key. Do nothing if the key is not present.getMaxKey(): Returns one of the keys with the maximum frequency, or an empty string if no keys are present.getMinKey(): Returns one of the keys with the minimum frequency, or an empty string if no keys are present.
Design a system for collecting metrics, with a particular focus on the data storage component.