Quick Overview

A coding problem about resolving function calls: given a library of function signatures, some variadic in their last parameter, return every function that accepts each queried list of argument types. It tests precise matching rules, indexing signatures for many queries and deterministic output ordering.

Match Argument Type Lists Against Function Signatures with Variadic Parameters

Company: Confluent

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A function library stores function signatures. Each function has a unique name, an ordered list of parameter types, and a flag that says whether it is variadic. A non-variadic function accepts exactly its parameter list. A variadic function accepts its parameter list with the last parameter type repeated one or more times. Given the library and a list of queries, where each query is the ordered list of argument types at a call site, return for every query the names of all functions that accept that call. ### Function Signature ```python def find_matching_functions(names: list[str], param_types: list[list[str]], is_variadic: list[bool], queries: list[list[str]]) -> list[list[str]]: ``` Function `i` is named `names[i]`, has parameter types `param_types[i]` in order, and is variadic exactly when `is_variadic[i]` is `True`. ### Rules - A non-variadic function with parameter types `p` matches a query `q` exactly when `q == p`: the same length and the same type at every position. - A variadic function with parameter types `p` of length `m` matches a query `q` exactly when `len(q) >= m`, `q[j] == p[j]` for every `j < m - 1`, and `q[j] == p[m - 1]` for every `j >= m - 1`. In other words, the leading parameters match position by position, and the last parameter type fills every remaining position, at least once. - Types are compared as exact, case-sensitive strings. There is no subtyping or conversion between types. - For each query, list the names of the matching functions in ascending order by plain string comparison (the order Python's `sorted` produces). If no function matches, the list is empty. The result contains one list per query, in query order. ### Constraints - `1 <= len(names) <= 10^4`, and `len(param_types) == len(is_variadic) == len(names)`. - Names are unique and are 1 to 30 characters drawn from `A-Z`, `a-z`, `0-9` and `_`. - `0 <= len(param_types[i]) <= 20`, and `len(param_types[i]) >= 1` whenever `is_variadic[i]` is `True`. - Every type is 1 to 20 characters drawn from `A-Z`, `a-z`, `0-9` and `_`. - `1 <= len(queries) <= 10^4` and `0 <= len(queries[j]) <= 100`. - The total number of types across all queries is at most `2 * 10^5`. - The total number of names across all returned lists is at most `10^6`. ### Examples **Example 1** ```text Input: names = ["add", "sum", "format", "concat", "now"] param_types = [["int", "int"], ["int"], ["string", "int"], ["string"], []] is_variadic = [False, True, True, True, False] queries = [["int", "int"], ["string", "int", "int"], ["string"], [], ["int", "string"]] Output: [["add", "sum"], ["format"], ["concat"], ["now"], []] ``` - `["int", "int"]` matches `add` exactly, and `sum`, whose single `int` parameter repeats twice. - `["string", "int", "int"]` matches `format`: `string`, then `int` twice. It does not match `concat`, because every argument after the first would also have to be `string`. - `["string"]` matches `concat`. It does not match `format`, which needs at least two arguments. - `[]` matches only `now`, the non-variadic function with no parameters. A variadic function needs at least one argument for its last parameter. - `["int", "string"]` matches nothing. **Example 2** ```text Input: names = ["log", "logAll", "pair"] param_types = [["int", "string"], ["string"], ["int", "string"]] is_variadic = [True, True, False] queries = [["int"], ["int", "string", "string", "string"], ["int", "string"], ["string", "string"]] Output: [[], ["log"], ["log", "pair"], ["logAll"]] ``` - `["int"]` is too short for `log`, which needs at least two arguments, and does not start with `string` as `logAll` requires. - `["int", "string", "string", "string"]` matches `log`: `int`, then `string` three times. - `["int", "string"]` matches `log`, whose last parameter appears once, and `pair` exactly; `"log"` sorts before `"pair"`. - `["string", "string"]` matches `logAll`.

Overview: A coding problem about resolving function calls: given a library of function signatures, some variadic in their last parameter, return every function that accepts each queried list of argument types. It tests precise matching rules, indexing signatures for many queries and deterministic output ordering.

Read the full Confluent Software Engineer interview experience this question came from

A function library stores function signatures. Each function has a unique name, an ordered list of parameter types, and a flag that says whether it is variadic. A non-variadic function accepts exactly its parameter list. A variadic function accepts its parameter list with the last parameter type repeated one or more times. Function `i` is named `names[i]`, has parameter types `param_types[i]` in order, and is variadic exactly when `is_variadic[i]` is `True`. Each entry of `queries` is the ordered list of argument types at one call site. Return, for every query, the names of all functions that accept that call. ### Matching rules - A non-variadic function with parameter types `p` matches a query `q` exactly when `q == p`: the same length and the same type at every position. - A variadic function with parameter types `p` of length `m` matches a query `q` exactly when `len(q) >= m`, `q[j] == p[j]` for every `j < m - 1`, and `q[j] == p[m - 1]` for every `j >= m - 1`. In other words, the leading parameters match position by position, and the last parameter type fills every remaining position, at least once. A variadic function therefore never matches an empty query. - Types are compared as exact, case-sensitive strings. There is no subtyping or conversion between types. ### Output Return one list per query, in query order. Each list holds the names of the functions that match that query, in ascending order by plain string comparison (character-code order, the order Python's `sorted` produces). If no function matches a query, its list is empty. Only strings and booleans cross the function boundary, so no value can exceed 2^31 - 1. ### Constraints - `1 <= len(names) <= 10^4`, and `len(param_types) == len(is_variadic) == len(names)`. - Names are unique and are 1 to 30 characters drawn from `A-Z`, `a-z`, `0-9` and `_`. - `0 <= len(param_types[i]) <= 20`, and `len(param_types[i]) >= 1` whenever `is_variadic[i]` is `True`. - Every type is 1 to 20 characters drawn from `A-Z`, `a-z`, `0-9` and `_`. - `1 <= len(queries) <= 10^4` and `0 <= len(queries[j]) <= 100`. - The total number of types across all queries is at most `2 * 10^5`. - The total number of names across all returned lists is at most `10^6`. ### Example 1 ```text Input: names = ["add", "sum", "format", "concat", "now"] param_types = [["int", "int"], ["int"], ["string", "int"], ["string"], []] is_variadic = [False, True, True, True, False] queries = [["int", "int"], ["string", "int", "int"], ["string"], [], ["int", "string"]] Output: [["add", "sum"], ["format"], ["concat"], ["now"], []] ``` - `["int", "int"]` matches `add` exactly, and `sum`, whose single `int` parameter repeats twice. - `["string", "int", "int"]` matches `format`: `string`, then `int` twice. It does not match `concat`, because every argument after the first would also have to be `string`. - `["string"]` matches `concat`. It does not match `format`, which needs at least two arguments. - `[]` matches only `now`, the non-variadic function with no parameters. A variadic function needs at least one argument for its last parameter. - `["int", "string"]` matches nothing. ### Example 2 ```text Input: names = ["log", "logAll", "pair"] param_types = [["int", "string"], ["string"], ["int", "string"]] is_variadic = [True, True, False] queries = [["int"], ["int", "string", "string", "string"], ["int", "string"], ["string", "string"]] Output: [[], ["log"], ["log", "pair"], ["logAll"]] ``` - `["int"]` is too short for `log`, which needs at least two arguments, and does not start with `string` as `logAll` requires. - `["int", "string", "string", "string"]` matches `log`: `int`, then `string` three times. - `["int", "string"]` matches `log`, whose last parameter appears once, and `pair` exactly; `"log"` sorts before `"pair"`. - `["string", "string"]` matches `logAll`.

Constraints

  • 1 <= len(names) <= 10^4, and len(param_types) == len(is_variadic) == len(names).
  • Names are unique and are 1 to 30 characters drawn from A-Z, a-z, 0-9 and _.
  • 0 <= len(param_types[i]) <= 20, and len(param_types[i]) >= 1 whenever is_variadic[i] is True.
  • Every type is 1 to 20 characters drawn from A-Z, a-z, 0-9 and _.
  • 1 <= len(queries) <= 10^4 and 0 <= len(queries[j]) <= 100.
  • The total number of types across all queries is at most 2 * 10^5.
  • The total number of names across all returned lists is at most 10^6.

Examples

Input: (['add', 'sum', 'format', 'concat', 'now'], [['int', 'int'], ['int'], ['string', 'int'], ['string'], []], [False, True, True, True, False], [['int', 'int'], ['string', 'int', 'int'], ['string'], [], ['int', 'string']])

Expected Output: [['add', 'sum'], ['format'], ['concat'], ['now'], []]

Explanation: Source Example 1: exact and variadic matches, a too-short variadic call, the empty query matching only the zero-parameter function, and a query matching nothing.

Input: (['log', 'logAll', 'pair'], [['int', 'string'], ['string'], ['int', 'string']], [True, True, False], [['int'], ['int', 'string', 'string', 'string'], ['int', 'string'], ['string', 'string']])

Expected Output: [[], ['log'], ['log', 'pair'], ['logAll']]

Explanation: Source Example 2: tail repeated three times, a variadic and a non-variadic function both matching in sorted order, and a too-short query.

Hints

  1. Re-read the variadic rule: the last parameter type must fill every remaining position at least once, so a call with one argument fewer than the parameter list is never accepted, and an empty call fits only a zero-parameter non-variadic function.
  2. Types are exact, case-sensitive strings: Int and int differ, and a type that is a prefix of another type is still a different type.
  3. Each inner list is sorted by plain character-code comparison: digits come before uppercase letters, which come before _, which comes before lowercase letters, and a name sorts before any longer name it is a prefix of.

Loading coding console...

Show the approach

Approach

Index the library by signature. Two hash maps are keyed by a function's complete parameter list: one holds the names of the non-variadic functions with that list, the other the names of the variadic functions with that list. Let longest be the longest parameter list (at most 20).

For a query q of length L:

  1. The non-variadic matches are exactly the names stored under q itself in the non-variadic map. No such match exists when L > longest, so that lookup can be skipped.
  2. Let r be the length of the maximal run of equal types that ends q. A variadic function with parameter list p of length m matches exactly when p == q[:m] and m - 1 >= L - r. If it matches, the leading positions give q[:m - 1] == p[:m - 1], position m - 1 gives q[m - 1] == p[m - 1], and positions m - 1 .. L - 1 all hold p[m - 1], so they lie inside the final run. Conversely, if p == q[:m] and positions m - 1 .. L - 1 lie inside the final run, each of them equals q[m - 1] == p[m - 1], and the leading positions match by the prefix equality. So the variadic matches are the names stored under q[:m] for every m from L - r + 1 (at least 1 because r <= L) to min(L, longest).

Every function is stored under exactly one key of exactly one map, and the probed prefixes have distinct lengths, so no name is reported twice. Each query's names are then sorted by plain string comparison; names and types are ASCII, so code-point, UTF-16 and byte order coincide in every language.

Edge cases: the empty query matches only zero-parameter non-variadic functions, because the variadic step needs at least one argument; a variadic function with m parameters never matches m - 1 arguments; a non-variadic function rejects any extra or missing argument; a query longer than 20 can match only variadic functions; duplicate queries are answered independently and produce identical lists.

Complexity: with F library parameter types, T query types, Q queries, P <= 20 the longest parameter list and K returned names, building the maps costs O(F), scanning the queries O(T + Q * P^2) (each of at most P prefix keys has length at most P, and a type has at most 20 characters), and sorting O(K log K).

Time complexity:
O(F + T + Q * P^2 + K log K)
Space complexity:
O(F + K)