Move to LinkedList for same low value #PRIORITY VERY HIGH

[sharma-subendra-kr]

Move to linkedList for same low value

• less traversal for inserts/removals -> even in skewed tree
• some what less traversal for reads -> even in skewed tree

don't think trees would be useful since we are trying to find range. try to investigate

PRIORITY VERY HIGH

[sharma-subendra-kr]

trees will have duplicates problem (i.e. if there are exactly same 2+ intervals), will be implementing linked list for now, will come back if time complexity issues arise cuz there will if 3 level of DS if i move forward with tree.

[sharma-subendra-kr]

skiplist seems a good idea

[sharma-subendra-kr]

Since the data we have is very small i.e. number of boxes on the side, lets use plain old linked list first and then think of skip list

[sharma-subendra-kr]

in a skewed scenario there will be max 2m + 1 rects for the configuration max width 1920 and min wdth 150 + 2 (margin) there will me max 25 items in the list 1920/160 = 12 122+1 = 25 log2(25) = 4.64 in normal scenario (say 4 items make 9 rects) log2(9) = 3.1

cannot optimize findAll but insert and delete will be optimized skiplist will optimize log(n) + (m || m || m) to log(n) + (m || log(m) || log(m))

can lock the height of skip list to log(m)

[sharma-subendra-kr]

going with skip list cuz findAll, insert and delete operations are done very frequently