Function Signature Lookup with Exact and Variadic Parameter Matching
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
An IDE needs a lookup engine for function signatures. Each registered function has a name, an ordered list of parameter types, and a flag that says whether its last parameter is variadic (like `*args` in Python or `Type...` in Java). Given the argument types of a call, the engine returns the names of every registered function that can legally be called with those arguments.
The original task is a class `FunctionLibrary` with two methods: `register(name, params, is_variadic=False)` stores a signature, and `find_matches(query)` returns the matching names in any order. Here the same behavior is a single function: every signature is registered first, then each query is answered in order.
Signature `i` is `(names[i], params[i], is_variadic[i])`. Each query `queries[j]` is the list of argument types of one call.
### Function Signature
```python
def find_matches(names: list[str], params: list[list[str]], is_variadic: list[bool], queries: list[list[str]]) -> list[list[str]]:
```
### Rules
- Types are compared by exact, case-sensitive string equality. There is no subtyping, implicit conversion or generic matching: `"Integer"` does not match `"Number"`, `"integer"` or `"Long"`.
- **Non-variadic signature** (`is_variadic[i]` is `False`) with parameter list `p` of length `m`: it matches query `q` exactly when `len(q) == m` and `q[t] == p[t]` for every `t`. The number, types and order of the arguments must all agree.
- **Variadic signature** (`is_variadic[i]` is `True`) with parameter list `p` of length `m >= 1`: the first `m - 1` types are a fixed prefix, and `p[m - 1]` is the variadic type. It matches query `q` exactly when `len(q) >= m - 1`, `q[t] == p[t]` for every `t < m - 1`, and `q[t] == p[m - 1]` for every `t >= m - 1`. The variadic parameter accepts zero or more arguments, so `q` may end right after the fixed prefix.
- A non-variadic signature with no parameters matches only the empty query. A variadic signature with a single parameter matches every query whose arguments all have that type, including the empty query.
- Return one list per query, in query order. The list for `queries[j]` holds the names of all signatures that match it, sorted in ascending order by Python's default string comparison (code point order, so uppercase letters sort before lowercase letters). If no signature matches, that list is empty.
### Constraints
- `1 <= n <= 1000`, where `n = len(names) == len(params) == len(is_variadic)`
- `1 <= len(queries) <= 1000`
- Names are distinct. Each name is 1 to 20 characters drawn from ASCII letters, digits and `_`.
- Every type name, in `params` and in `queries`, is 1 to 20 ASCII letters or digits.
- `0 <= len(params[i]) <= 10`, and `len(params[i]) >= 1` whenever `is_variadic[i]` is `True`.
- `0 <= len(queries[j]) <= 20`
- The output holds at most 1,000,000 names in total, and every count involved fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: names = ["funcA", "funcB"]
params = [["String", "Integer"], ["String", "Integer", "Integer"]]
is_variadic = [False, True]
queries = [["String", "Integer"],
["String", "Integer", "Integer", "Integer"],
["String"]]
Output: [["funcA", "funcB"], ["funcB"], []]
```
`funcB` has the fixed prefix `["String", "Integer"]` followed by zero or more `"Integer"` arguments. The first query matches `funcA` exactly and matches `funcB` with zero variadic arguments. The second query has the wrong length for `funcA` and matches `funcB` with two variadic arguments. The third query is shorter than the fixed prefix of `funcB` and has the wrong length for `funcA`.
**Example 2**
```text
Input: names = ["foo", "bar"]
params = [["String", "Integer"], ["String", "Integer"]]
is_variadic = [False, True]
queries = [["String"],
["String", "Integer"],
["String", "Integer", "Integer"],
["String", "Boolean"],
["Integer", "String"]]
Output: [["bar"], ["bar", "foo"], ["bar"], [], []]
```
`foo` matches only `["String", "Integer"]`. `bar` has the fixed prefix `["String"]` followed by zero or more `"Integer"` arguments, so it matches the first three queries. `["String", "Boolean"]` fails both: the second type differs for `foo` and is not the variadic type of `bar`. `["Integer", "String"]` has the right types in the wrong order.
**Example 3**
```text
Input: names = ["now", "printAll", "pair"]
params = [[], ["String"], ["Integer", "Integer"]]
is_variadic = [False, True, False]
queries = [[], ["String", "String"], ["string"], ["Integer", "Integer"]]
Output: [["now", "printAll"], ["printAll"], [], ["pair"]]
```
The empty query matches `now`, which takes no parameters, and `printAll`, whose only parameter is variadic and receives zero arguments. `["string"]` matches nothing, because `"string"` and `"String"` are different types.
Overview: A coding question about an IDE-style signature lookup engine: given registered functions, some whose last parameter is variadic, return for each call the sorted names of every function that accepts its argument types. It tests exact type-sequence matching, zero-or-more variadic arguments and edge cases such as empty argument lists.
Read the full IBM Software Engineer interview experience this question came from