Creator of DiceDB, ex-Google Dataproc, ex-Amazon Fast Data, ex-Director of Engg. SRE and Data Engineering at Unacademy. I spark engineering curiosity through my no-fluff engineering videos on YouTube and my courses
In the mysterious Grand Library of Alexandria (which secretly still exists!), historians discovered an ancient library containing some sacred knowledge in the form of books. The books were so holy that each one was kept in a vault and each unique vault was locked by a unique pattern, an n-dimensional vector.
Young apprentice librarian Maya found a set of keys lying on the floor along with a scroll. The scroll contained a spell that could work on a set of keys and generate all possible keys to open all possible vaults of the library. The spell combines the keys in a linear way.
Help Maya find if the set of keys she found is sufficient enough and also fewest possible to generate all possible keys and unlock all the vaults of the library. Help Maya write a program that checks this.
Note: Since the ancient mechanism works with real numbers, your solution should handle floating-point arithmetic carefully.
from typing import List
def can_unlock_library(keys: List[List[float]], tolerance: float = 1e-10) -> bool:
"""
Args:
keys: List of n vectors, each being a list of n floating-point numbers
precision: Threshold for numerical calculations (default: 1e-10)
Returns:
bool: True if keys can unlock the library, False otherwise
"""
pass
Example:
keys = [
[1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0]
]
result = can_unlock_library(keys) # Returns True
Explanation:
The set of provided keys are fewest possible keys that can generate all possible keys in 3-dimensional space when combined linearly and hence can unlock all the vaults of the library.
keys = [
[2, 0, 0],
[0, 2, 0],
[4, 4, 0]
]
result = can_unlock_library(keys) # Returns False
Explanation:
The set of provided keys cannot represent the key [0, 0, 1]
. Hence all possible keys required to unlock the library.
Here’s the code for reference and some notes on the solution below.
Each key is an n-dim vector. The set of keys should be
This means we need to check if the provied set of vectors form a basis.
A set of vectors are linearly independent when none of these vectors can be expressed as a linear combination of the others. Following set of vectors are linearly independent
v1 = (1, 0, 0)
v2 = (0, 1, 0)
v3 = (0, 0, 1)
and
v1 = (1, 1, 0)
v2 = (1, 0, 1)
v3 = (0, 1, 1)
and even
v1 = (3, -4, 7)
v2 = (-2, 5, 1)
v3 = (6, 2, -3)
none of these vectors can be expressed as a linear combination of the others. But the following are not independent as one is double the other.
v1 = (1,1)
v2 = (2,2)
We can use QR decomposition to test for linear independence.
Here’s an example of three vectors that span the 3-dimensional space
v₁ = (1, 0, 2)
v₂ = (0, 1, -1)
v₃ = (2, 1, 0)
You can reach any point (x, y, z) in 3-dim space using some combination of these vectors. i.e. c1(1,0,2) + c2(0,1,-1) + c3(2,1,0) = (a,b,c)
This system will always have a solution for any (a,b,c), proving these vectors span the space. Another simple example is
e₁ = (1, 0, 0)
e₂ = (0, 1, 0)
e₃ = (0, 0, 1)
Arpit's Newsletter read by 100,000 engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.