Mixed Companies Coding Interview Set 5Q

Interview Questions

Google – LFU Cache
coding
Title:
LFU Cache
Problem:
Design and implement a data structure for a Least Frequently Used (LFU) cache. It should support get(key) and put(key,value) operations. When the cache is full, it should remove the key with the lowest usage frequency. If multiple keys have the same frequency, remove the least recently used one among them.
Function Signature: class LFUCache: def __init__(self, capacity: int): pass def get(self, key: int) -> int: pass def put(self, key: int, value: int) -> None: pass
Input:
capacity: integer; operations: "get key" and "put key value"
Output:
For each get operation, output the value associated with the key or -1 if it does not exist
Sample Input:
capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2); get(3)
Sample Output:
[1, -1, 3]
Example:
After inserting key 3, key 2 is evicted since both 1 and 2 have frequency 1 but 2 is least recently used. Thus get(2) returns -1.
Constraints:
0 <= capacity <= 10^4; operations <= 10^5; keys and values are integers
Hints:
Use a frequency map combined with doubly linked lists to track least frequently and least recently used keys.
Follow-up:
Can you achieve O(1) operations? How would you handle the case where the cache needs to store additional metadata such as expiration times?
Uber – Serialize and Deserialize Binary Tree
coding
Title:
Serialize and Deserialize Binary Tree
Problem:
Design an algorithm to serialize and deserialize a binary tree. Serialize the tree into a single string so that it can be deserialized back to the original tree structure. You may use any delimiter and marker for null children.
Input:
class Codec: def serialize(self, root: Optional[TreeNode]) -> str: pass def deserialize(self, data: str) -> Optional[TreeNode]: pass
Output:
serialize: root of binary tree; deserialize: serialized stringserialize returns a string; deserialize returns the root of the reconstructed tree
Sample Input:
root = [1,2,3,null,null,4,5]
Sample Output:
"1,2,#,#,3,4,#,#,5,#,#"
Example:
Using preorder traversal, we record node values and '#' for null children: 1,2,#,#,3,4,#,#,5,#,#.
Constraints:
1 <= number of nodes <= 10^4; node values range between -10^5 and 10^5
Hints:
Use a pre-order traversal to serialize the tree, separating values with commas and using '#' to mark null children. During deserialization, rebuild the tree by reading values sequentially and reconstructing left and right subtrees when a non-null value is encountered.
Follow-up:
How would you modify the algorithm if the data structure was a general graph with potential cycles or if you needed to support lazy-loading subtrees?
Facebook – Number of Islands
coding
Title:
Number of Islands
Problem:
Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is formed by connecting adjacent lands horizontally or vertically. The grid's edges are surrounded by water. Return the number of distinct islands.
Function Signature: def num_islands(grid: List[List[str]]) -> int
Input:
grid: 2D list of characters '0' or '1'
Output:
An integer representing the number of islands in the grid
Sample Input:
grid = [["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0""1","1"]]
Sample Output:
In the sample grid, there are three islands: one 2x2 block of 1s at the top-left, one single cell island in the third row, and one 2-cell island at the bottom right.
Example:
3
Constraints:
1 <= m, n <= 300
Hints:
Use depth-first search or breadth-first search to traverse the grid. Mark visited land cells to avoid counting the same island multiple times.
Follow-up:
How would the solution change if diagonal adjacency (eight directions) also counted towards island connectivity?
Microsoft – Course Schedule
coding
Title:
Course Schedule
Problem:
There are numCourses courses labeled from 0 to numCourses-1. Each pair [a, b] in prerequisites means you must take course b before course a. Determine if it is possible to finish all courses given the prerequisites (i.e., determine if the directed graph has no cycles).
Function Signature: def can_finish(numCourses: int, prerequisites: List[List[int]]) -> bool
Input:
numCourses: integer; prerequisites: list of [course, prereq] pairs
Output:
Boolean indicating whether it is possible to complete all courses (True if possible, False otherwise)
Sample Input:
numCourses = 2, prerequisites = [[1,0]]True
Sample Output:
For numCourses = 2 and prerequisites = [[1,0]], you can take course 0 then course 1. For numCourses = 2 and prerequisites = [[1,0],[0,1]], there is a cycle, so you cannot complete all courses.
Example:
True
Constraints:
1 <= numCourses <= 10^5; 0 <= prerequisites.length <= 10^5
Hints:
Model the courses and prerequisites as a directed graph. Use topological sorting (Kahn’s algorithm) or a depth-first search to detect cycles. If a cycle exists, return False.
Follow-up:
Return one valid topological ordering of the courses if it exists; otherwise, return an empty list.
Netflix – Search in Rotated Sorted Array
coding
Title:
Search in Rotated Sorted Array
Problem:
Given a rotated sorted array 'nums' (no duplicates) and an integer 'target', return the index of target if found; otherwise, return -1. The array is originally sorted in ascending order but then rotated at an unknown pivot.
Function Signature: def search_rotated(nums: List[int], target: int) -> int
Input:
nums: list of integers; target: integer
Output:
Integer index of the target in nums, or -1 if not found
Sample Input:
nums = [4,5,6,7,0,1,2], target = 04
Sample Output:
In [4,5,6,7,0,1,2], the target 0 is at index 4. If target is 3, return -1.
Example:
1 <= len(nums) <= 10^4
Constraints:
1 <= len(nums) <= 10^4
Hints:
Use a modified binary search: compare the mid element with the first element and with the target to decide which half is sorted and which half to search.
Follow-up:
How would your solution change if the array could contain duplicate values?