C3 AI Software Engineer Onsite Coding Questions

I recently finished C3 AI Solutions Engineering Loop. The OA was medium/hard LC, failed test cases but still got invited to other rounds. - HM round was easy, asked weakness/strengths type questions +

LeetCode #322: Coin Change. Difficulty: Medium. Topics: Array, Dynamic Programming, Breadth-First Search. Asked at C3.ai in the last 6 months.

## Problem Find the longest subarray containing at most two distinct types of fruit, using a sliding window approach. ## Likely LeetCode equivalent LC 904 - Fruit Into Baskets (>80% confident) ## Tags sliding_window, hash_table, arrays

## Problem You are given a flat list of employees with `{id, name, manager_id}`. Build the org-chart tree and implement: - `depth(employee_id) -> int`: levels below root (root = 0). - `subtree_size(employee_id) -> int`: number of nodes in the subtree rooted at that employee (inclusive). - `lowest_common_manager(id1, id2) -> int`: the deepest manager who is an ancestor of both. - `serialize() -> str`: BFS-order JSON representation of the tree. ```python class OrgChart: def __init__(self, employees: List[dict]): ... def depth(self, employee_id: int) -> int: ... def subtree_size(self, employee_id: int) -> int: ... def lowest_common_manager(self, id1: int, id2: int) -> int: ... ``` **Example:** ``` employees = [ {"id": 1, "manager_id": None}, {"id": 2, "manager_id": 1}, {"id": 3, "manager_id": 1}, {"id": 4, "manager_id": 2} ] depth(4) -> 2 subtree_size(1) -> 4 lowest_common_manager(3, 4) -> 1 ``` ## Follow-ups 1. What is the time complexity of `lowest_common_manager`? Can you get it to O(log n)? 2. How would you rebalance the tree if the org chart is very deep (degenerate chain)? 3. How would you support moving a subtree to a new manager? 4. How does this change if one employee can have multiple managers (matrix org)?

## Problem Given equations like A/B = k, answer queries for the value of other division expressions using graph traversal. ## Likely LeetCode equivalent LC 399 - Evaluate Division (>80% confident) ## Tags graph, bfs, union_find

## Problem Generate all possible combinations of k numbers from 1 to n using backtracking. ## Likely LeetCode equivalent LC 77 - Combinations (>80% confident) ## Tags backtracking, recursion

## Problem Generate all combinations of n pairs of valid parentheses using backtracking. ## Likely LeetCode equivalent LC 22 - Generate Parentheses (>80% confident) ## Tags backtracking, recursion, strings

## Problem Determine if you can reach the last index of an array where each element represents the max jump length from that position. ## Likely LeetCode equivalent LC 55 - Jump Game (>80% confident) ## Tags greedy, arrays, dynamic_programming

## Problem Find the number of unique k-diff pairs in an array where a pair (a, b) has an absolute difference equal to k. ## Likely LeetCode equivalent LC 532 - K-diff Pairs in an Array (>80% confident) ## Tags hash_table, two_pointers, arrays

## Problem Find the length of the longest arithmetic subsequence in an array where consecutive elements have the same difference. ## Likely LeetCode equivalent LC 1027 - Longest Arithmetic Subsequence (>80% confident) ## Tags dynamic_programming, hash_table, arrays

## Problem You have a list of metal pieces, each with a `weight` and `value`. You can carry at most `W` kg. However, you must include at least one piece of each metal type in your selection (or none of that type at all - you cannot take a partial type). Return the maximum total value achievable without exceeding the weight limit. ```python def max_metal_value( pieces: List[dict], # [{"type": str, "weight": int, "value": int}] W: int ) -> int: ... ``` **Example:** ``` pieces = [ {"type": "gold", "weight": 3, "value": 9}, {"type": "gold", "weight": 2, "value": 5}, {"type": "silver", "weight": 4, "value": 6}, {"type": "silver", "weight": 1, "value": 2} ], W = 6 # Best: gold(2,5) + silver(1,2) = 3 kg, value 7 # Or: gold(3,9) = 3 kg, value 9 (skip silver entirely) Output: 9 ``` ## Follow-ups 1. How does adding the "all-or-nothing per type" constraint change standard 0/1 knapsack? 2. What is the time complexity of your solution? 3. How would you reconstruct which pieces were selected? 4. If there are 20 metal types with 100 pieces each and W=1000, how do you keep runtime practical?

## Problem Given a set of points, find the maximum number of points that lie on the same straight line. ## Likely LeetCode equivalent LC 149 - Max Points on a Line (>80% confident) ## Tags math, hash_table, geometry

## Problem Find the smallest window in a string that contains all characters of a target string using a sliding window with frequency counts. ## Likely LeetCode equivalent LC 76 - Minimum Window Substring (>80% confident) ## Tags sliding_window, strings, hash_table

## Problem Group all odd-indexed nodes together followed by even-indexed nodes in a linked list in-place. ## Likely LeetCode equivalent LC 328 - Odd Even Linked List (>80% confident) ## Tags linked_list, two_pointers

## Problem Given an array containing n+1 integers where each integer is between 1 and n, find the one duplicate number. ## Likely LeetCode equivalent LC 287 - Find the Duplicate Number (>80% confident) ## Tags hash_table, two_pointers, arrays

## Problem Design a data structure that supports set operations and snapshotting of an array state, with efficient querying of past snapshots. ## Likely LeetCode equivalent LC 1146 - Snapshot Array (>80% confident) ## Tags arrays, binary_search, design

## Problem Count pairs of songs whose total duration is divisible by 60, using modular arithmetic and a frequency map. ## Likely LeetCode equivalent LC 1010 - Pairs of Songs With Total Durations Divisible by 60 (>80% confident) ## Tags hash_table, math, arrays

## Problem Given an integer array `nums`, return all unique triplets `[a, b, c]` such that `a + b + c == 0`. The solution set must not contain duplicate triplets. ```python def three_sum(nums: List[int]) -> List[List[int]]: ... ``` **Example:** ``` Input: nums=[-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]] Input: nums=[0, 0, 0] Output: [[0, 0, 0]] Input: nums=[1, 2, 3] Output: [] ``` ## Approach Sort `nums`. For each index `i`, use two pointers `lo = i+1` and `hi = len-1`. Skip duplicates at each pointer. Move `lo` right or `hi` left based on whether the sum is too small or too large. Time: O(n^2). Space: O(1) excluding output. ## Follow-ups 1. Generalize to four-sum (4 elements summing to a target `k`). 2. How would you approach this if the array is a stream and you cannot sort it upfront? 3. What changes if the array contains duplicates and you must count all triplets (not unique)? 4. Can you solve 3-sum in better than O(n^2)? What is the lower bound?

## Problem Implement text justification or alignment logic that formats text into lines of a fixed width with proper spacing. ## Likely LeetCode equivalent LC 68 - Text Justification (>80% confident) ## Tags strings, simulation

## Problem Design a key-value store where each key can store multiple timestamped values, supporting retrieval of the latest value at or before a given timestamp. ## Likely LeetCode equivalent LC 981 - Time Based Key-Value Store (>80% confident) ## Tags binary_search, design, hash_table