log-search
in memory logs search
Installation
git clone https://github.com/avinashb98/log-search
cd log-search
Usage
commands
ADD
- O(n) worst-case, n is the total number of logs
- O(1) best-case
ADD [key] [text]
SEARCH
Time Complexities
- O(n) worst-case, n is the total number of logs
- O(1) best-case
SEARCH [word] [limit]
# input.txt
n # number which is the maximum logs stored
.
.
command
.
.
END
Build and Run
cp input_sample.txt input.txt
# edit the sample commands file
go build .
./log-search
Test
go test -v ./...
Design
Inverted Index
The inverted index consists of 2 data structures.
KeyToEntries
It is a map of a word to a list of entryIds.
Used to optimally query entries corresponding to a word.
EntryToKeys
It is a map of an entryId to a list of keys.
Used to optimally unmap a deleted or updated entry.