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 Design an antivirus scanning system. It should: - Accept a file (represented as a byte string or path). - Check against a signature database (each signature is a known malicious byte pattern). - Classify the file as `CLEAN`, `INFECTED`, or `SUSPICIOUS`. - On `INFECTED`, quarantine the file (move to isolated storage, log the event). - Support adding new signatures at runtime. ```python class AntivirusScanner: def load_signatures(self, signatures: List[bytes]): ... def scan(self, file_path: str) -> ScanResult: ... def quarantine(self, file_path: str, reason: str): ... def add_signature(self, signature: bytes): ... class ScanResult: status: str # "CLEAN" | "INFECTED" | "SUSPICIOUS" matched_signatures: List[bytes] scanned_at: datetime ``` **Example:** ``` scanner.load_signatures([b"\xDE\xAD\xBE\xEF", b"MALWARE_MARKER"]) result = scanner.scan("/tmp/suspicious.exe") # result.status -> "INFECTED" # result.matched_signatures -> [b"MALWARE_MARKER"] ``` ## Follow-ups 1. How would you use Aho-Corasick to scan for multiple signatures in a single O(n) pass? 2. How do you scan compressed/archived files? 3. How would you parallelize scanning across thousands of files? 4. How do you prevent a quarantine bypass where malware deletes itself before isolation?

## 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 You are given an `m x n` grid of integers. Starting at cell `(0, 0)`, reach cell `(m-1, n-1)` in the minimum number of jumps. From cell `(r, c)` with value `v`, you can jump to any cell `(r', c')` where `|r'-r| + |c'-c| <= v` and `grid[r'][c'] != -1` (blocked). Return the minimum number of jumps, or -1 if unreachable. ```python def min_jumps(grid: List[List[int]]) -> int: ... ``` **Example:** ``` grid = [ [2, 3, 1], [1, -1, 1], [1, 1, 0] ] Output: 2 # (0,0)->(0,1)->(2,2): jump 2 from (0,0) to (0,1) [val=3], jump up to (2,2) grid = [[0]] Output: 0 # already at destination ``` ## Approach BFS from `(0,0)`. For each cell at distance `d`, enqueue all reachable neighbors not yet visited. BFS guarantees minimum jumps. ## Follow-ups 1. What is the time complexity? How do you avoid revisiting cells inside the inner loop? 2. How does the problem change if jumping diagonally is also allowed? 3. If you need to find the actual path (not just count), how do you track it? 4. How would you solve this on a weighted grid where each jump has a cost?

## 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?