Other Algorithms Flashcards
Binary search tree runtime
Search
Average: O log n
Worst case: O n
Insert/delete
Avg O log n
Red-black tree
A binary search tree that balances it self
B-tree
A binary search tree used to store data in databases
Inverted index
A hash that maps words to locations
Uses of an inverted index
Commonly used in search
Fourier transform
Breaks down something into components.
Ie a song into frequencies and notes
Used for mp3 algorithm
Parallel algorithms
Running an algorithm across multiple cores/servers etc.
Challenges with parallel algorithms
-Overhead of managing parallelism
-Load balancing
MapReduce
A popular distributed algorithm used by Apache Hadoop
What is MApReduce useful for
Working with large data sets across multiple servers
Map function
Applies the same function to each element of an array
Reduce function
Transform an array to a single item
Probabilistic algorithms
Could give false positives but don’t give false negatives
Fast and use less data
Bloom filter
Probabilistic data structure
HyperLogLog
Approximates the number of unique elements in a set
