linkedin logo
LinkedIn· SDE II

LinkedIn | SSE | 6 YOE | India

Location
india
Experience
6 years
Posted
22 Nov 2024
398 reads

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.

How it went

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.

Questions asked (5)

  1. 01

    Design Data Structure with O(1) Add and Random Remove

    Data Structures & Algorithms · Medium

    Design a data structure that can perform the following operations in O(1) time:

    1. Add an element
    2. Remove a random element

  2. 02

    Celebrity Problem

    Data Structures & Algorithms · Medium

    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.

  3. 03

    K Closest Elements in BST to Target

    Data Structures & Algorithms · Hard

    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
    Given target=8, and k=3, it should return 6,7,10.
    Given target=6, and k=3, it should return 5,6,7.

  4. 04

    Design Data Structure for O(1) Max/Min Frequency Key (AllForOne)

    Data Structures & Algorithms · Hard

    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.
    Example usage is provided in the input, demonstrating key increments, decrements, and queries for max/min frequency keys.

  5. 05

    Design a Metric Collection System

    System Design · Hard

    Design a system for collecting metrics, with a particular focus on the data storage component.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at LinkedIn recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!