Skip to content

Latest commit

 

History

History
62 lines (53 loc) · 979 Bytes

README.md

File metadata and controls

62 lines (53 loc) · 979 Bytes
Raw

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 file format

# 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.