Verily Interview Questions

Background: Verily needs a solution to optimize resource allocation, which can often resemble the N-Queens problem where we must place queens on a chessboard such that no two queens threaten each other. This is analogous to ensuring that no two processes compete for the same resource, optimizing the system's overall efficiency.
Problem statement: Given an integer n, represent an n x n chessboard, and your task is to return all distinct solutions where n queens can be placed on the board such that no two queens attack each other. A solution is represented as a list of strings, where each string is n characters long, and each character is either 'Q' (representing a queen) or '.' (representing an empty space).
Function/class signature:

• def solve_n_queens(n: int) -> List[List[str]]:

Example 1:
Input: n = 4
Output: [['.Q..',
'...Q',
'Q...',
'..Q.'],
['..Q.',
'Q...',
'...Q',
'.Q..']]
Explanation: These are the two possible configurations to place 4 queens on a 4x4 board.
Example 2:
Input: n = 1
Output: [['Q']]
Explanation: There is only one queen and one position available.
Constraints:

• 1 <= n <= 10


• The output list must contain all possible configurations, and no duplicate configurations should exist.

Background: Verily processes a variety of nested structures in medical data, making it essential to accurately traverse and extract depth information from nested lists in analytics.
Problem statement: Given a nested list of integers, return the maximum depth of the list. A nested list is defined as a list that can contain integers or other nested lists. The depth of a nested list is the number of lists that must be traversed to reach the most deeply nested integer.
For example, the depth of the list [1, [2, [3, 4]], 5] is 3 because 1 is at depth 1, 2 is at depth 2, and 3 and 4 are at depth 3.
Function/class signature:

• def maxDepth(nestedList: List[Union[int, List]]) -> int:

Example 1:
Input: [[1, 1], [2, 2], [3, 3]]
Output: 2
Explanation: All integers are at depth 1, hence the maximum depth is 2.Example 2:
Input: [1, [4, [6]]]
Output: 3
Explanation: The integer 1 is at depth 1, and 4 is at depth 2, while 6 is at depth 3.Constraints:

• The list may contain between 1 and 1000 elements.


• The integer values will be between -100 and 100.


• The maximum nested depth will not exceed 100.

Notes: This function may be useful in analyzing patient data by understanding the hierarchical structure of nested medical records.

Background: In Verily's health monitoring applications, it's essential to analyze patient data efficiently, including graphical representations. This problem simulates the need to determine the capacity of areas, potentially for visual data representation.
Problem statement: You are given an array of integers, where each integer represents the height of a vertical line. Your goal is to find two lines that together with the x-axis form a container that holds the most water. The amount of water that can be held is determined by the height of the shorter line multiplied by the distance between the lines.
Write a function named maxArea that returns the maximum amount of water that can be held.

• Function signature: def maxArea(heights: List[int]) -> int:

Example 1:

• Input: heights = [1,8,6,2,5,4,8,3,7]


• Output: 49


• Explanation: The container with height 8 and width 7 holds 49 units of water.

Example 2:

• Input: heights = [1,1]


• Output: 1


• Explanation: The only container formed holds 1 unit of water.

Constraints:

• 2 <= heights.length <= 3 * 10^4


• 0 <= heights[i] <= 10^4

Background: In medical research, Verily may need to store and transmit complex patient data structures using tree data formats. By serializing and deserializing binary trees, Verily can manage hierarchical medical data efficiently.
Problem statement: Implement the methods to serialize a binary tree into a string format and deserialize it back into a binary tree. The string must represent the structure of the tree, allowing reconstruction without loss of information.
Function/class signature:

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


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

Example 1: Input: root = [1,2,3,null,null,4,5]
Output: '1,2,#,#,3,4,#,#,5,#,#'
Explanation: The tree structure is flattened to a string representation efficiently.
Example 2: Input: root = []
Output: '#'
Explanation: An empty tree should be serialized to a marker indicating its absence.
Constraints:

• The number of nodes in the tree is in the range [0, 10^4].


• Node values are integers in the range [-1000, 1000].

Background: In Verily's health technology products, managing a sequence of patient records efficiently is crucial. A common operation involves reversing subsets of patient entries to reflect certain analysis views.
Problem statement: Given a linked list, you need to reverse the nodes in groups of a given size k. If the number of nodes is not a multiple of k, then the remaining nodes at the end should remain as is. Please implement this in a function that modifies the linked list in-place.
Function/class signature:

• def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:

Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: The list is reversed in groups of 2.Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Explanation: The first three nodes are reversed, and the last two remain.Constraints:

• 1 <= k <= 100


• The length of the linked list is between 1 and 1000.


• Each node's value is in the range [1, 1000]

Note: Ensure you handle the in-place reversal without using extra space for additional nodes.

Background: In Verily's health analytics platform, navigating complex healthcare data relationships is crucial for providing insights. A depth-first search can help find a specific path through a data graph representing patient records and treatment histories.
Problem statement: Given a graph represented as an adjacency list where each node is a patient represented by an integer ID, and a target patient ID, implement a function that uses Depth-First Search (DFS) to determine if there exists a path from a given patient ID to the target patient ID. The function should return true if the path exists and false otherwise.
Function/class signature:

• def has_path(graph: Dict[int, List[int]], start: int, target: int) -> bool:

Example 1:

• Input: graph = {1: [2, 3], 2: [4], 3: [], 4: []}, start = 1, target = 4


• Output: True


• Explanation: There is a path from 1 to 2 to 4, so the output is True.

Example 2:

• Input: graph = {1: [2], 2: [3], 3: []}, start = 1, target = 5


• Output: False


• Explanation: There is no path to 5 from 1, hence the output is False.

Constraints:

• The graph has at least one node and at most 1000 nodes.


• The graph is directed and may contain cycles.