Design an algorithm for an Audio Search Engine
An audio search engine such as Shazam takes a 10 second clipping of a song and returns the original song.
A clipping is taken in a noisy environment, so the whole sound wave is not compared. The song is represented concisely as a set of interesting points: points with a high variation in amplitude, which survive the noise.
- Each interesting point is stored as a frequency and a time. The amplitude value is dropped.
- The offset of the clipping is not known, so two points are defined by their frequencies and the difference in time: F1, F3 and delta time.
- All pairs of n points come to about n square pairs. The song is broken into chunks of points instead: eight interesting points in chunks of three give six chunks and 18 pairs.
- The points in a chunk are converted into a single combinatorial hash, a key in a dictionary.
The client sends the clipping to the server as a set of hashes. The server returns the song with the maximum number of matches.
Online Judge
An online judge takes code from users across the world and tests whether it passes the test cases of a problem statement.
Each fix creates the next problem:
- The server executes an uploaded file immediately, checks its output against the known output, and stores accepted or rejected in the database. Thousands of users submitting together in a contest are more than it can handle.
- Rate limiting drops or blocks requests, which is not fair in a contest.
- A message queue makes the system asynchronous. The file goes to a distributed file system such as S3, the upload is acknowledged immediately, and an event with the user and the code URL is published. The server processes the events one by one. Malicious code can still run on the server.
- Virtualization runs the code in a virtual operating system. In the worst case that operating system crashes.
- A container does the same without an entire virtual operating system for every execution.
The core problem is a job scheduler, a container and security.