Oracle Medium Interview Questions

Background: Oracle often works with complex data structures and relies on graph representations in systems like Oracle Graph. Finding the longest path in a directed graph can be crucial for optimization tasks in database querying and data analysis.Problem statement: Given a directed graph represented as an adjacency list, write a function to determine the length of the longest path from a starting vertex to any other vertex. The graph may contain cycles, and you need to ensure the path does not revisit any vertices. Function/class signature:

• def longest_path(graph: List[List[int]], start: int) -> int:

Example 1:
Input: graph = [[1, 2], [3], [3], []], start = 0
Output: 3
Explanation: The longest path starts from vertex 0 to 1 to 3, resulting in a path length of 3.Example 2:
Input: graph = [[1], [2], [3], [1]], start = 0
Output: 3
Explanation: Although there is a cycle involving vertex 1, the longest acyclic path is still from 0 to 1 to 2 to 3, resulting in a path length of 3.Constraints:

• 1 <= len(graph) <= 1000


• 0 <= start < len(graph)


• Each sublist has at most 10 elements


• Graph may contain cycles

Background: Oracle manages vast amounts of data across distributed systems. Efficient routing of queries through networked databases is critical. This problem simulates such a routing challenge.
Problem statement: Given a directed graph representing the database nodes and the connections (edges) between them, write a function to find the shortest path from a source node to a destination node. If no path exists, return None.
Function/class signature:

• def shortest_path(graph: Dict[str, List[str]], source: str, destination: str) -> List[str]:

Example 1:

• Input: graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}, source = 'A', destination = 'D'


• Output: ['A', 'B', 'D']


• Explanation: The shortest path from A to D can be achieved through B.

Example 2:

• Input: graph = {'A': ['B'], 'B': ['C'], 'C': []}, source = 'A', destination = 'D'


• Output: None


• Explanation: There is no path from A to D.

Constraints:

• The graph can have a maximum of 1000 nodes.


• Each node's adjacency list can have up to 100 connections.

Background: In Oracle's data handling and analytics platforms, it is essential to efficiently store and retrieve tree structures representing hierarchical data. Serializing data structures ensures easy storage and quick innovation in applications.
Problem statement: Implement a class BinaryTreeCodec with methods to serialize and deserialize a binary tree. The serialized output should be a string that maintains the structure of the tree. For a given binary tree, the serialize(root) method should produce a string, and the deserialize(data) method should reconstruct the binary tree from that string.Function/class signature:

• def serialize(self, root: TreeNode) -> str:


• def deserialize(self, data: str) -> TreeNode:

Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: '1,2,3,null,null,4,5'
Explanation: The tree structure can be represented in this list format, and the serialized string maintains the tree hierarchy.Example 2:
Input: data = '1,2,3,null,null,4,5'
Output: TreeNode(1) with children TreeNode(2), TreeNode(3)
Explanation: The deserialized tree is reconstructed into the original binary tree structure.Constraints:

• The binary tree can have up to 1000 nodes.


• Values of nodes are integers between -10^4 and 10^4.


• The methods must handle edge cases, including empty trees.

Background: Oracle's cloud infrastructure often deals with vast and complex interconnected systems, such as airline flight networks. Efficient pathfinding algorithms are critical to optimize routing and minimize travel time.
Problem statement: Given a set of airports (represented as nodes) and flights (represented as edges with associated costs), implement a function to find the shortest path from a starting airport to a destination airport. Each airport is represented by a string, and the flights are represented by a list of tuples where each tuple contains the departing airport, the arriving airport, and the travel cost.
Function/class signature:

• def find_shortest_path(flights: List[Tuple[str, str, int]], start: str, destination: str) -> Tuple[List[str], int]:

Example 1:
Input:

flights = [('JFK', 'LAX', 300), ('JFK', 'SFO', 400), ('LAX', 'SFO', 100)]
start = 'JFK'
destination = 'SFO'

Output:

(['JFK', 'LAX', 'SFO'], 400)

Explanation: The shortest path is JFK → LAX → SFO with a total cost of 400.
Example 2:
Input:

flights = [('JFK', 'MIA', 200), ('MIA', 'SFO', 300), ('JFK', 'SFO', 600)]
start = 'JFK'
destination = 'SFO'

Output:

(['JFK', 'MIA', 'SFO'], 500)

Explanation: The optimal route is through MIA costing a total of 500, which is cheaper than the direct route.
Constraints:

• 1 <= len(flights) <= 1000


• Cost of flights is positive.


• All airport names are unique strings.

Background: Inverting a binary tree is a common operation needed in various algorithms and applications, including graphical representation and data structure manipulation. At Oracle, where efficiency and data management are crucial, mastering binary trees is essential for optimizing database queries and storage systems.Problem statement: Given the root node of a binary tree, your task is to invert the tree, meaning you need to swap the left and right child nodes at each level. The transformation should be done in place, meaning no additional data structures should be used besides the input tree itself.Function/class signature:

• def invert_tree(root: TreeNode) -> TreeNode:

Example 1:

• Input: root = [4, 2, 7, 1, 3, 6, 9]


• Output: [4, 7, 2, 9, 6, 3, 1]


• Explanation: The tree structure after inversion is 4, where the left child 2 becomes the right child 7, and all further inversions follow.

Example 2:

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


• Output: [2, 3, 1]

Constraints:

• The tree node count will be between 0 and 1000.


• Node values will be integers between -100 and 100.

2. Background: Oracle often processes large datasets where merging arrays efficiently is crucial for analytics and reporting tools. This problem simulates a common scenario encountered in database management systems.
3. Problem statement: Given two sorted arrays arr1 and arr2, merge them into a single sorted array. The merged array should also be sorted and must not require additional space for an output of size m + n, where m and n are the sizes of arr1 and arr2, respectively. You must return the merged array as your result.
4. Function/class signature:
- def merge_sorted_arrays(arr1: List[int], arr2: List[int]) -> List[int]:
5. Example 1:
- Input: arr1 = [1, 3, 5], arr2 = [2, 4, 6]
- Output: [1, 2, 3, 4, 5, 6]
- Explanation: The merged array maintains the order of the two input arrays.
6. Example 2:
- Input: arr1 = [0, 1, 2], arr2 = [3, 4, 5]
- Output: [0, 1, 2, 3, 4, 5]
7. Constraints:
- 0 <= arr1.length, arr2.length <= 100
- -1000 <= arr1[i], arr2[i] <= 1000