3 ms·
Take a large unordered text file and then create an ordered index in a separate file of word ==> line write a brief binary search algo to search the index. Co
by tonymet 5y ago
Take a large unordered text file and then create an ordered index in a separate file of word ==> line
write a brief binary search algo to search the index.
Compare searching the words with a "table scan" on the first file using grep, vs the binary search on the index.
You will find the table scan is O(n) and your binary search is roughly O(log n)
In 60 minutes you'll understand more about indexing than reading stack overflow.
- tonymet 5y agobonus points your interview skills will improve on both coding & system design
- zaphirplane 5y agoNow picture someone is updating the file at the same time you are searching and someone updating the index while you are searching and return to step 1 Lol
- tonymet 5y agogood follow up exercise. set up a mutex between reader and writer.