LinkedIn Interview Questions

Background: LinkedIn’s social networking platform allows users to connect, and understanding the shortest path of connections between two users can enhance recommendations and search functions.
Problem statement: Given a social network represented as an undirected graph, where each node represents a user and each edge represents a connection, write a function to find the shortest path between two users. You need to return a list of users representing the path from the start user to the target user. If no path exists, return an empty list.
Function/class signature:

• def shortest_path(graph: Dict[str, List[str]], start: str, target: str) -> List[str]:

Example 1:
Input: graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}, start = 'A', target = 'D'
Output: ['A', 'B', 'D']
Explanation: The shortest path from A to D is A → B → D.
Example 2:
Input: graph = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A'], 'D': []}, start = 'A', target = 'D'
Output: []
Explanation: There is no connection from A to D.
Constraints:

• 1 <= number of users <= 1000


• Each user name is a non-empty string, and there will not be any cycles in the graph.

1. Background: LinkedIn deals with user-generated content, including profile summaries, messages, and posts. Ensuring that strings are processed efficiently is key for enhancing features like search and user communication.
2. Problem statement: Given a string s, write a function that checks if s is a valid palindrome. A valid palindrome reads the same backward as forward after converting all uppercase letters to lowercase and excluding all non-alphanumeric characters.
3. Function/class signature:
- def isPalindrome(s: str) -> bool:
4. Example 1:
- Input: "A man, a plan, a canal: Panama"
- Output: True
- Explanation: Alphanumeric characters only are amanaplanacanalpanama, which is a palindrome.
5. Example 2:
- Input: "race a car"
- Output: False
- Explanation: After filtering, the characters do not form a palindrome.
6. Constraints:
- 0 <= s.length <= 2 * 10^5
- s consists of printable ASCII characters.

Background: LinkedIn handles vast amounts of data and user interactions, and analyzing these interactions is vital for understanding user behavior and improving products. The Maximum Subarray Sum problem is essential in optimizing queries and data analysis.
Problem statement: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. You must solve this problem in O(n) time complexity.
Function/class signature:

• def max_subarray_sum(nums: List[int]) -> int:

Example 1:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]


• Output: 6


• Explanation: The contiguous subarray [4,-1,2,1] has the largest sum = 6.

Example 2:

• Input: nums = [1]


• Output: 1


• Explanation: The only element is 1, so the largest sum is 1.

Constraints:

• 1 <= nums.length <= 10^5


• -10^4 <= nums[i] <= 10^4

1. Background: LinkedIn's user experience often involves processing user-generated content. Ensuring that usernames or comments meet certain criteria, like being a valid palindrome, helps maintain brand integrity and enhances user interaction.
2. Problem statement: Given a string s, your task is to determine if it is a valid palindrome, considering only alphanumeric characters and ignoring cases. A valid palindrome reads the same forward and backward when ignoring non-alphanumeric characters.
3. Function/class signature:
- def is_valid_palindrome(s: str) -> bool:
4. Example 1:
- Input: "A man, a plan, a canal: Panama"
- Output: True
- Explanation: Ignoring spaces and punctuation, reads the same backward.
5. Example 2:
- Input: "race a car"
- Output: False
- Explanation: After cleansing, it does not read the same backward.
6. Constraints:
- 1 <= len(s) <= 2 * 10^5
- The input string consists only of printable ASCII characters.
7. Additional Notes: Implement a function that can efficiently check for palindrome nature without extra space, utilizing pointers.

Background: LinkedIn matches professionals with similar interests, and ensuring data integrity is crucial. Determining if user-generated content, such as bios or posts, maintain certain properties (like palindrome) can enhance user experiences and prompt engagement.Problem statement: Given a string s, your task is to determine if it is a palindrome considering only alphanumeric characters (a-z, A-Z, 0-9) and ignoring cases. You may assume the input string only contains printable ASCII characters.Function/class signature:

• def is_palindrome(s: str) -> bool:

Example 1:

• Input: "A man, a plan, a canal: Panama"


• Output: True


• Explanation: When considering only alphanumeric characters and case insensitivity, the string reads the same backwards as forwards.

Example 2:

• Input: "race a car"


• Output: False


• Explanation: The string contains non-alphanumeric characters and does not read the same backward.

Constraints:

• 0 <= s.length <= 2 * 10^5


• The string s consists of printable ASCII characters.

Note: Use two-pointer technique for efficient checking.

Background: LinkedIn needs to ensure that user-generated content maintains quality and integrity. A common validation check is to verify if strings are palindromes, which can be relevant for features like username verification or content moderation.
Problem statement: Write a function that determines if a given string s is a valid palindrome, considering only alphanumeric characters and ignoring case. Return true if it is a palindrome, otherwise return false.
Function/class signature:

• def is_palindrome(s: str) -> bool:

Example 1:
Input: "A man, a plan, a canal: Panama"
Output: True
Explanation: The alphanumeric characters are amanaplanacanalpanama, which reads the same backward.
Example 2:
Input: "race a car"
Output: False
Explanation: The alphanumeric characters are raceacar, which does not form a palindrome.
Constraints:

• 1 <= len(s) <= 2 * 10^5


• The input string consists of printable ASCII characters.

Background: LinkedIn often displays user-generated content, such as posts and comments, where it's important to handle text evaluations accurately for features like content moderation. A valid palindrome check could assist in identifying formatted user inputs.Problem statement: Given a string s, return true if it is a palindrome, considering only alphanumeric characters and ignoring case. A palindrome reads the same backward as forward.Function/class signature:

• def is_palindrome(s: str) -> bool:

Example 1:

• Input: "A man, a plan, a canal: Panama"


• Output: true


• Explanation: When ignoring non-alphanumeric characters and case, it reads amanaplanacanalpanama which is the same forwards and backwards.

Example 2:

• Input: "race a car"


• Output: false


• Explanation: The string ignores the spaces and reads raceacar which is not the same backward.

Constraints:

• 0 <= s.length <= 2 * 10^5


• s consists of printable ASCII characters.

LinkedIn's algorithm can identify connections between users to enhance networking. We want to find all connected components given a list of connections between user profiles.
Problem statement: Given an integer n representing the number of profiles and a list of connections edges, return the connected components across profiles.

• Input: int n, edges defined as a list of pairs representing connections.


• Output: List[List[int]] — a list that contains all connected components, with each component being a list of profile IDs.

Example 1:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: [[0, 1, 2], [3, 4]]
Explanation: Profile 0 is connected to 1 and 2; profile 3 is connected to 4.Example 2:
Input: n = 4, edges = [[0, 1], [1, 0], [2, 3]]
Output: [[0, 1], [2, 3]]Constraints:

• 0 <= n <= 2000


• 0 <= edges.length <= n * (n - 1) / 2

LinkedIn users often write descriptive profiles, and analyzing these descriptions can help in improving user engagement. The goal is to identify the longest substring from a given profile description where no characters are repeated.
Problem statement: Given a string s, return the length of the longest substring without repeating characters.

• Input: string s


• Output: int — length of the longest substring without repeating characters.

Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.Constraints:

• 0 <= s.length <= 5 * 10^4


• s consists of English letters, digits, symbols, and spaces.

LinkedIn needs a feature similar to Twitter feeds, where users can see recent activities of their connections. This involves multiple classes coordinating data retrieval and display.
Problem statement: Design a class TwitterFeed that handles user activity feeds and allows users to follow/unfollow other users.

• Input: Methods to postTweet(userId: int, tweet: str), getNewsFeed(userId: int), follow(followerId: int, followeeId: int), and unfollow(followerId: int, followeeId: int).


• Output: List[str] for getNewsFeed, containing up to 10 most recent tweets from the user and their followed users.


• Constraints:


• UserIds are in the range of 1 to 10^4


• Tweet content can be up to 140 characters.

To enhance performance, LinkedIn requires a caching system that follows the LRU (Least Recently Used) principle for user profile data retrieval.
Problem statement: Design and implement a class LRUCache that supports the following operations:

• get(key: int) -> int: Returns the value of the key if the key exists, otherwise return -1.


• put(key: int, value: int): Update the value of the key if the key exists, or add the key-value pair if the key does not exist. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.


• Input: capacity - maximum number of items the cache can hold.


• Output: int for get, no output for put.

Example 1:
Input: ["LRUCache", "put", "put", "get", "put", "get", "get", "put", "get"], [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4], [1], [3]]
Output: [null, null, null, 1, null, 2, -1, null, 3]
Explanation: The cache operates under the mentioned rules and examples.Constraints:

• 1 <= capacity <= 3000


• 0 <= key, value <= 10^4