Tasks:
-
find examples of using algos + data structures in the context of chatroom features
- chat history search
- word stats
- chat censoring
- word autocomplete
- list of users with their status
- friends - show 1st degree, 2nd degree
- group chat suggestion
-
migrate to typescript
data structures:
- trees
- lists
TODO:
- implement a list data structure
- store messages in a list (in a variable)
- implement methods:
- find
- map
- forEach
- first
- last
- prepend
- remove
try not to google
null
{data: 'bla', next: null}
{ data: 'bla', next: { data: 'blabla', next: null } }
{ data: 'bla', next: { data: 'blabla', next: { data: 'hello', next: null } } }
does not modify list, but creates a new list make it functional
TODO:
-
set up testing
-
reduce
-
make map not mutate the initial value
-
make list item generic (also complex types)
-
listToString uses reduce
-
pass callback to find, and not the item, and return list.data (not the list) https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find
-
remove should be not mutating!
-
reduce returns only the data, not the whole list
-
look at reduce refernce at MDN
-
do it TDD
expected prototype const <T, Acc>reduce(List: a, (acc: Acc, currentValue: T) => Acc, initialValue: Acc) => Acc
- refine the data types type List = ListItem | null type ListItem = { data: T, next: List }
test examples
- reduce([], sum, 0) => 0
- summing the length of items accumulator doesn't have to be the same type as the list item! test it! like so: reduce(['abc', 'cbd'], (acc, elem) => acc + elem.length, 0) -> 6
trees make some operations more efficient and some operations less efficient
a node in a tree has an arbitrary amount of children a tree with maxinum of two children per node is a binary tree
TODO:
- finish test for create tree
- implement methods (TDD!)
-
add items (nearest available insertion spot)
-
print tree
print like this: a
-
- e
- b
-
- c
- d
- make a .toString function instead of print function
- use the .toString function to test other functionalities (hide implementation details!)
- implement a
- null
- b
Homework
- Implement AVL or red-black (!) balancing
The idea: Store messages in a simple array Store words in a tree with arrays containing refences to the positions of messages in the words array In case of two words, perform two searches and then make an intersection of results to find messages that satisfy both searches
TODO:
-
change the way data is stored data.word data.positions not the key value thing
-
make the search function generic, not only for the key value thing search<K, T>(key: K, tree: <Tree<K, T>>, compare: () => number)
-
do the chat search implementation refer to the screenshot in root folder
improvement idea: get results for every word that starts with... then it's not word bound
// TODO:
- message position should be array
- pass messagePosition instead of message array to addMessage, return the added