Compress vertices into uniques and indices
Company: Applied
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an array of vertices (a 2D array). Each vertex may repeat. Implement a simple “compression” that produces:
1. `unique_vertices`: the list of unique vertices, **preserving the order of first appearance**.
2. `indices`: for each vertex in the original array, the index of its corresponding vertex in `unique_vertices`.
### Input
- `vertices`: a list of `n` vertices
- each vertex is a fixed-length list/tuple of integers (e.g., 3D vertex)
### Output
- `unique_vertices`: list of unique vertices in first-seen order
- `indices`: integer list of length `n`
### Example
Input:
```
[[2,2,2], [0,1,0], [2,1,2], [0,1,0]]
```
Output:
```
unique_vertices = [[2,2,2], [0,1,0], [2,1,2]]
indices = [0, 1, 2, 1]
```
### Notes / Constraints
- Treat two vertices as equal if all coordinates match.
- Aim for efficient time complexity (better than O(n^2) if possible).
Quick Answer: This question evaluates a candidate's ability to perform duplicate detection and compression of sequences of fixed-length tuples, exercising skills in data structures, mapping/hash concepts, array manipulation, and preserving first-seen ordering.