xAI Software Engineer Coding Questions

Background: At xAI, handling data efficiently is crucial, especially when aggregating usages or transactions that can be fragmented across different user sessions. This problem can relate to optimizing user experience in analytics.
Problem statement: Given an array of integers nums, return the maximum sum of non-adjacent elements. Specifically, if you choose an element, you cannot choose the elements immediately before or after it.
Function/class signature:

• def max_sum_non_adjacent(nums: List[int]) -> int:

Example 1:

• Input: nums = [2, 4, 6, 2, 5]


• Output: 13


• Explanation: We can choose 2, 6, and 5, which give the sum of 13.

Example 2:

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


• Output: 4


• Explanation: Choose 1 and 3.

Constraints:

• 1 <= len(nums) <= 100


• 0 <= nums[i] <= 400

Background: xAI often processes vast amounts of textual data from various sources. A trie-based tokenizer can efficiently manage and tokenize this data.
Problem statement: Implement a Tokenizer class that allows you to add words and tokenize sentences into a list of words. The tokenizer should be able to handle spaces and punctuation correctly. The key methods should utilize a trie data structure, which enables efficient storage and retrieval of words.
Function/class signature:

• class Tokenizer:


• def add_word(self, word: str) -> None:


• def tokenize(self, sentence: str) -> List[str]:

Example 1:
Input: tokenizer = Tokenizer()
tokenizer.add_word("hello")
tokenizer.add_word("world")
output = tokenizer.tokenize("hello world!")
Output: ['hello', 'world']
Explanation: The method returns a list of words in the given sentence, excluding punctuation.
Example 2:
Input: tokenizer.tokenize("xAI is amazing.")
Output: ['xAI', 'is', 'amazing']
Constraints:

• Words to be added will have a maximum length of 100 characters.


• Sentences to be tokenized will contain at most 1000 characters.


• The add_word and tokenize methods should operate efficiently for a large number of words.

Background: xAI's products may involve real-time processing of user-generated data streams. Efficiently handling large amounts of data in real-time is crucial for performance and user experience.
Problem statement: You need to implement a class KthLargest that keeps track of the kth largest element in a dynamically updating stream of integers. The class should support the method add(int val), which adds an integer to the stream and returns the current kth largest element.
Function/class signature:

• class KthLargest:


• def __init__(self, k: int, nums: List[int]) -> None:


• def add(self, val: int) -> int:

Example 1:
Input: k = 3, nums = [4, 5, 8, 2]
KthLargest kthLargest = KthLargest(k, nums)
kthLargest.add(3)
Output: 4
Explanation: After adding 3, the third largest number is 4. Example 2:
Input: kthLargest.add(5)
Output: 5
Explanation: The third largest number is 5. Constraints:

• 1 <= k <= 104


• 0 <= nums.length <= 104


• -104 <= nums[i] <= 104


• -104 <= val <= 104


• At most 104 calls will be made to add.

Background: In the field of AI and data processing, handling missing data is crucial for ensuring the integrity of models. xAI, which leverages vast datasets for its AI solutions, needs robust methods to detect and fill missing values efficiently.
Problem statement: Create a function to detect and list the indices of missing values (represented as None) in an input list of integers. The function should return the indices of the None values in ascending order.
Function/class signature:

• def find_missing_indices(data: List[Optional[int]]) -> List[int]:

Example 1:

• Input: find_missing_indices([1, None, 3, None, 5])


• Output: [1, 3]


• Explanation: The missing values (None) are found at indices 1 and 3.

Example 2:

• Input: find_missing_indices([None, None, 2, 4])


• Output: [0, 1]


• Explanation: The missing values are both found at the start of the list, at indices 0 and 1.

Constraints:

• data will have at most 10^4 elements.


• Each element can either be an integer or None.


• The function should run in linear time complexity O(n).

Background: xAI focuses on understanding and modeling social interactions. This problem is relevant for designing features that analyze and recommend connections between users based on their interactions.
Problem statement: Given a social network represented as an undirected graph where nodes are users and edges are friendships, implement a function to find the shortest path between two users. You are to return the number of edges in the shortest path or -1 if no path exists.
Function/class signature:

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

Example 1:
Input:
graph = [[1, 2], [0, 2, 3], [0, 1], [1]],
start = 0,
end = 3
Output:
2
Explanation: The shortest path is 0 → 1 → 3.Example 2:
Input:
graph = [[1], [0, 2], [1, 3], [2]],
start = 0,
end = 3
Output:
3
Explanation: The shortest path is 0 → 1 → 2 → 3.Constraints:

• 1 <= graph.length <= 1000


• 0 <= start, end < graph.length


• Each graph entry should have 0 <= graph[i].length <= 1000

In xAI's data processing systems, we often encounter large arrays of user-generated metrics. Finding the maximum subarray sum quickly becomes essential to understand user behavior efficiently.
Problem Statement: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

• int max_sub_array_sum(List<int> nums): returns the maximum sum of the contiguous subarray.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The contiguous subarray [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The contiguous subarray [1] has the largest sum = 1.
Constraints:

• 1 <= nums.length <= 3 * 10^4


• -10^4 <= nums[i] <= 10^4.

In xAI's recommendation system, we need to efficiently find the shortest path to similar items based on user interactions. This will help improve user engagement.
Problem Statement: Given a directed graph represented as an adjacency list, where each node represents an item and edges represent the relationship strength, implement a function that finds the shortest path from a start node to a target node using BFS. Return the list of nodes in the path from start to target, or an empty list if no path exists.

• List[int] bfs_shortest_path(int start, int target): returns the list of integers representing the path from start to target.

Example 1:
Input: start = 0, target = 4
Output: [0, 1, 2, 4]
Explanation: The shortest path from node 0 to 4 is through nodes 1 and 2.
Example 2:
Input: start = 0, target = 3
Output: []
Explanation: No path exists between node 0 and node 3.
Constraints:

• 1 <= start, target <= 10^4


• The graph can have up to 10^4 nodes and 2 * 10^4 edges.

For optimizing user interaction, xAI requires efficient routing through dialogue states in a conversation graph.
You have a directed graph where each node represents a dialogue state and edges represent possible transitions. Write a function to return the shortest path from the initial state to a target state.
Example method signature: def shortestPath(graph: Dict[int, List[int]], start: int, target: int) -> List[int]: returns a list of node values representing the shortest path.Example 1:
Input: graph = {0: [1, 2], 1: [3], 2: [3], 3: []}, start = 0, target = 3
Output: [0, 1, 3]
Explanation: One possible shortest path from the initial state (0) to target (3) is through state 1.Example 2:
Input: graph = {0: [1], 1: [2], 2: [3], 3: []}, start = 0, target = 2
Output: [0, 1, 2]
Explanation: This is a direct route from 0 to 2 passing through state 1.Constraints:

• 1 <= graph.length <= 1000


• Input graph is a directed acyclic graph (DAG).

In order to improve the efficiency of our AI models, xAI needs to analyze the time complexity of certain input sequences in real-time.
Given an array of integers nums, return the length of the longest increasing subsequence.
Example method signature: def lengthOfLIS(self, nums: List[int]) -> int: returns the length of the longest increasing subsequence found in nums.Example 1:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore its length is 4.Example 2:
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 2, 3], therefore its length is 4.Constraints:

• 1 <= nums.length <= 2500


• -10^4 <= nums[i] <= 10^4