Katkat
Back

Compress vertices into uniques and indices

Applied IntuitionSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to efficiently identify unique elements in a sequence while maintaining their original relative order, mapping them to integer indices to compress a large dataset.

Problem Statement

You are working with a geometric data pipeline where a 3D model is defined by a long sequence of vertices. Each vertex is represented as a tuple of three floating-point numbers (x, y, z). Many vertices in the input sequence are identical, leading to redundant memory usage.

Your task is to transform a list of vertices into a compressed format. Specifically, you need to return:

  1. A list of unique vertices, preserving the order in which they first appeared in the original sequence.
  2. A list of indices such that the original sequence can be reconstructed by mapping each index to the corresponding unique vertex.

Function Signature

def compress_vertices(vertices: list[tuple[float, float, float]]) -> tuple[list[tuple[float, float, float]], list[int]]:

Constraints

  • vertices length: 1 to 1,000,000.
  • Floating point precision: Assume standard IEEE 754 equality for identical inputs.

Examples

Example 1: Input: [(1.0, 2.0, 3.0), (4.0, 5.0, 6.0), (1.0, 2.0, 3.0)] Output: ([(1.0, 2.0, 3.0), (4.0, 5.0, 6.0)], [0, 1, 0])

Example 2: Input: [(0.0, 0.0, 0.0), (0.0, 0.0, 0.0)] Output: ([(0.0, 0.0, 0.0)], [0, 0])

Edge Cases

  • Empty input list.
  • All vertices are identical.
  • All vertices are unique.

Hints

Hint 1

Use a hash map (dictionary) to store the first-seen vertex as the key and its assigned index as the value.

Hint 2

Iterate through the input list once, checking if the current vertex exists in the map; if not, add it to the unique list and record its new index.

Hint 3

The space complexity will be proportional to the number of unique vertices, and the time complexity will be linear with respect to the input size.

Follow-up questions

  • How would your implementation change if the vertices were subject to minor floating-point inaccuracies (e.g., epsilon comparisons)?
  • If the sequence is massive and cannot fit in memory, how would you approach the compression using external storage or a distributed framework?
  • What is the impact of a poor hash function on the performance of this algorithm?