PayPal Hard Interview Questions

Background: PayPal handles a vast number of transactions daily, and optimizing the transaction routing is crucial for efficiency and speed. This problem relates to optimizing how payment transactions traverse through multiple gateways.
Problem statement: Given a directed graph where nodes represent payment gateways and edges represent the transaction routes with associated costs, you need to find the shortest path from a source gateway to a destination gateway. Return the total cost of the shortest path and the path itself as a list of gateways.
Function/class signature:

• def find_shortest_payment_route(links: List[Tuple[str, str, int]], source: str, destination: str) -> Tuple[int, List[str]]:

Example 1:

• Input: links = [("A", "B", 1), ("A", "C", 4), ("B", "C", 2), ("C", "D", 1)], source = "A", destination = "D"


• Output: (4, ["A", "B", "C", "D"])


• Explanation: The shortest path is through B and C with a total cost of 4.

Example 2:

• Input: links = [("A", "B", 2), ("B", "D", 3), ("A", "C", 6), ("C", "D", 1)], source = "A", destination = "D"


• Output: (5, ["A", "B", "D"])


• Explanation: The optimal route is direct via B with a total cost of 5.

Constraints:

• 1 ≤ number of links ≤ 1000


• Cost of each route (edge weight) is positive and ≤ 1000


• All nodes (gateways) are unique strings.

Background: In financial systems like PayPal, it is essential to optimize payment routes to ensure efficient transaction handling. The maximum flow algorithm helps in managing the flow of transactions through various payment channels.
Problem statement: You are given a directed graph where nodes represent payment channels, and edges represent possible transaction flows with capacity limits. Your task is to implement a function that computes the maximum flow from a source node to a sink node. You need to return the total maximum flow achievable from the source to the sink.
Function/class signature:

• def maximum_flow(graph: List[List[int]], source: int, sink: int) -> int:

Example 1:

• Input: graph = [[0, 16, 13, 0, 0, 0], [0, 0, 10, 12, 0, 0], [0, 4, 0, 0, 14, 0], [0, 0, 9, 0, 0, 20], [0, 0, 0, 7, 0, 4], [0, 0, 0, 0, 0, 0]], source = 0, sink = 5


• Output: 23


• Explanation: The maximum flow from source (0) to sink (5) is 23.

Example 2:

• Input: graph = [[0, 10, 5, 15], [0, 0, 15, 5], [0, 0, 0, 10], [0, 0, 0, 0]], source = 0, sink = 3


• Output: 20


• Explanation: The maximum flow for this network is 20.

Constraints:

• 2 <= graph.length <= 100


• 0 <= graph[i][j] <= 1000


• source and sink are valid indices in graph, with source != sink.

Background: PayPal relies on robust data processing workflows that often involve directed acyclic graphs (DAGs) for transaction processing and workflow automation. Optimizing these workflows is crucial for efficiency and accuracy.
Problem statement: Given a directed acyclic graph represented as an adjacency list, write a function to determine the length of the longest path from any starting node to any ending node. Implement it with a focus on efficiency due to large transaction sets.
Function/class signature:

• def longest_path_dag(graph: List[List[int]]) -> int:

Example 1:

• Input: graph = [[1,2],[3],[3],[]]


• Output: 4


• Explanation: The longest path is 0 -> 1 -> 3, which has a length of 4.

Example 2:

• Input: graph = [[1],[2],[3],[]]


• Output: 3


• Explanation: The longest path is 0 -> 1 -> 2 -> 3, which has a length of 3.

Constraints:

• 1 <= graph.length <= 1000


• 0 <= graph[i].length <= 1000


• 0 <= graph[i][j] < graph.length


• No duplicate edges.