Google Backend Engineer Coding Questions

Google Play wants to provide the best app recommendations based on user preferences. The longest increasing subsequence can be used to find sequences of user interests.
Problem Statement: Given an integer array nums, return the length of the longest increasing subsequence. You need to implement a function that computes this efficiently.
Method Signature: def longest_increasing_subsequence(nums: List[int]) -> int: — returns an integer representing the length of the longest increasing subsequence.
Example 1:
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], so the length is 4.
Constraints:
- 1 <= len(nums) <= 2500
- -10^4 <= nums[i] <= 10^4.

Google Maps needs to find the shortest path between locations efficiently. Imagine you have a graph representing the streets of a city where the nodes are intersections and edges represent the road segments with weights signifying travel time.
Problem Statement: Implement a function that takes a graph represented as an adjacency list and returns the shortest path from a given starting node to all other nodes using Dijkstra's algorithm. The graph is represented as follows: graph: Dict[str, List[Tuple[str, int]]].
Method Signature: def dijkstra(graph: Dict[str, List[Tuple[str, int]]], start: str) -> Dict[str, int]: — returns a dictionary with the shortest distance from the start node to all other nodes.
Example 1:
Input: { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)] }, 'A'
Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Explanation: Starting from A, the shortest path to B is 1, to C is 3, and to D is 4.
Constraints:
- 1 <= len(graph) <= 10^4
- 1 <= number of edges <= 10^4
- All weights are positive integers.