You got very interesting content. I don't think(or at least I'm not aware of) any tech videos has got ur kind of content mix. I guess ur combined experience with core tech and trading makes u stand apart from most design videos. Your videos definitely deserves lot more views. Hope you won't be disappointed by low views and keep producing interesting content..!
great video! I have this question coming up for an interview and didn't even think about making the nodes of the priority queues point to the heads of linked lists.
Nice video. Heap is definitely easy to reason about. However I think a "can we do better" follow up would for sure come, and the answer would be to use a vector (if we're talking C++). Most exchanges have a limit up and limit down value for any given day (which is rarely breached) which is effectively the entire range of valid prices, which is probably just a few hundred different values. A fixed-size vector for buys, a fixed size vector for sells, and a pointer to the best price of each gives us O(1) operations. (You need to store the "MinTick" value to know the price differential between two indexes of the vectors). But as the video states, the tricky part is the cancels.
For those unaware, if limitUp or limitDown are reached, the exchange either stops for the day, or some other period of time where the buy/sell vectors can be reprovisioned.
Thanks Paul, I really appreciate the insight! That's a great point with regards to just using a list of prices since there are fixed possibilities. I noticed that you're a former quant developer yourself, and if you'd be interested someday I'd love to have you come speak on the channel :). I'm sure we could all benefit by hearing about your experiences in finance. I requested you on LinkedIn if you're interested.
Hi Jordan, thank you for your video. Am I right that there is an assumption that heap has node-base implementation and we kinda store hints for removal in a hashmap(aka pointers to nodes)? This approach seems doesn't work with heaps built on top of continuous memory containers. In that case location of an element can be invalidated by swaps caused by insert/delete operations (yes we can implement own continuous mem container that tracks swaps and updates hashtable, but it looks like an overkill)
Actually, these should probably be run single threaded as that's how they mostly work in real life, but yeah one per stock ticker would be the way that you'd parallelize
@@jordanhasnolife5163 gotcha, also would you mind explaining how the hashmap orderMap works? is the value actual nodes/iterators in the linked list or something? im also a bit confused about the tiebreaker when there are multipe orders that break the spread. in that case, do we just order by timestamp for all orders that break the spread? or only for the price at the top of the heap? for example: if we have asks 100,101 with 101 coming before the 100, and a bid comes in at 120, all for qty 1, does the ask with value 101 get fulfilled, or the 100?
@@bobbyshmurda1365 It's price time priority - if an order breaks the spread then you'd take the order at the best price (hence the heap), and if there are many you take the earliest order (doubly linked hash list so that you can get the earliest order or remove an order in O(1) time from the list)
Could you comment on the following? I came up with the heap + doubly linked list (DLL) approach but also with a DLL+DLL approach. I am confused that Alex Xu in his chapter on Stock Exchanges, ch29 in his ebook, does not even discuss the heap option and goes straight to the DLL + DLL approach. Am I missing something obvious why he doesn't consider heap? My line of reasoning: -> Insertion: heap of DLLs: O(logN) DLL of DLLs: O(N) Removal: heap of DLLs: O(logN) DLL of DLLs: O(1) Argument in favour of HEAP + DLL: As N grows to very large, I think the difference in runtime for the two options grows significantly faster for insertion compared to removal. In other words: | log(N) - N | > | log(N) - constant |. Of course this depends on N and C, but assuming C is pretty small, for most values of N this should be true. So: to curb the growing runtime cost for insertions, choose the heap approach. -> Argument in favour of DLL + DLL In practise, orders might often get filled immediately, requiring us to do an insert only a fraction of the time. (I don't know if this is typically true for a regular exchange? In any case, it could be a custom business requirement). So in this case: RemovalCount is much larger than InsertionCount, i.e. the extra cost of the once-in-a-rare-while insertion in the bigger picture does not add significant runtime, so don't optimise for it, and stick with DLL + DLL. thoughts? Hope you had a great poo after making this video 💩
Always have great poos - yeah I think either solution that you named is fine, because you're able to name the tradeoffs. Alex Xu is a bum tho lol - no actually the best solution I've seen was a different comment to this video which said something like you should just use an array because a stock can only have a finite number of values in a day, and to be honest, I'm a pretty big fan of that one in retrospect haha
I am a bit confused about the while loop condition in the order matching part, where you do oppisiteBook.peek().peek().price=lowest ask. However, the condition in the while loop does not trigger because no bids are
You got very interesting content. I don't think(or at least I'm not aware of) any tech videos has got ur kind of content mix. I guess ur combined experience with core tech and trading makes u stand apart from most design videos. Your videos definitely deserves lot more views. Hope you won't be disappointed by low views and keep producing interesting content..!
Thanks man!
+1 to this. You certainly deserve a lot more views.
great video! I have this question coming up for an interview and didn't even think about making the nodes of the priority queues point to the heads of linked lists.
8:04 the time complexity for one insert and one pop is O(logn). When we consider all the elements, it is O(nlogn)
Yep, thanks!
Hi Jordan really liked the content you are making..It is fine if these videos are long as you are covering lot of information
Great video, super helpful, thank you so much!!!!
Could you do more of these quant design videos, this is super useful🙏
I appreciate it haha but there's not much else to cover truthfully!
Nice video. Heap is definitely easy to reason about. However I think a "can we do better" follow up would for sure come, and the answer would be to use a vector (if we're talking C++). Most exchanges have a limit up and limit down value for any given day (which is rarely breached) which is effectively the entire range of valid prices, which is probably just a few hundred different values. A fixed-size vector for buys, a fixed size vector for sells, and a pointer to the best price of each gives us O(1) operations. (You need to store the "MinTick" value to know the price differential between two indexes of the vectors). But as the video states, the tricky part is the cancels.
For those unaware, if limitUp or limitDown are reached, the exchange either stops for the day, or some other period of time where the buy/sell vectors can be reprovisioned.
Thanks Paul, I really appreciate the insight! That's a great point with regards to just using a list of prices since there are fixed possibilities.
I noticed that you're a former quant developer yourself, and if you'd be interested someday I'd love to have you come speak on the channel :). I'm sure we could all benefit by hearing about your experiences in finance.
I requested you on LinkedIn if you're interested.
What the actual fuck?! I wonder if there are people who can come up with this stuff on the spot lol
Thanks for breaking it down, G!
Haha probably some, but it ain't easy!
This was so so amazing. 🔥🔥
great video. thanks!
Google SWE sure.. sounds more like a Tata consultant
You're right I don't work at Google anymore I work in high frequency trading
Hi Jordan, thank you for your video.
Am I right that there is an assumption that heap has node-base implementation and we kinda store hints for removal in a hashmap(aka pointers to nodes)? This approach seems doesn't work with heaps built on top of continuous memory containers. In that case location of an element can be invalidated by swaps caused by insert/delete operations (yes we can implement own continuous mem container that tracks swaps and updates hashtable, but it looks like an overkill)
Yep that's a fair point removals from a heap implemented by an array are very hard, I think it's still linear time but it's still a pain in the ass.
Great video! How do we deal with concurrency or parallelism ?
Also, we have 1 of these data structures per stock ticker. right ?
Actually, these should probably be run single threaded as that's how they mostly work in real life, but yeah one per stock ticker would be the way that you'd parallelize
just wondering how do you remove node in heap? i didnt know std priority queue has support for that
Can't speak to c++, but I recall from DS&A that you like would just remove a node and then reformulate all the nodes below into a heap
@@jordanhasnolife5163 gotcha, also would you mind explaining how the hashmap orderMap works? is the value actual nodes/iterators in the linked list or something?
im also a bit confused about the tiebreaker when there are multipe orders that break the spread. in that case, do we just order by timestamp for all orders that break the spread? or only for the price at the top of the heap?
for example: if we have asks 100,101 with 101 coming before the 100, and a bid comes in at 120, all for qty 1, does the ask with value 101 get fulfilled, or the 100?
@@bobbyshmurda1365 It's price time priority - if an order breaks the spread then you'd take the order at the best price (hence the heap), and if there are many you take the earliest order (doubly linked hash list so that you can get the earliest order or remove an order in O(1) time from the list)
no one else would use heap to implement a trading book
:o
Could you comment on the following?
I came up with the heap + doubly linked list (DLL) approach but also with a DLL+DLL approach. I am confused that Alex Xu in his chapter on Stock Exchanges, ch29 in his ebook, does not even discuss the heap option and goes straight to the DLL + DLL approach. Am I missing something obvious why he doesn't consider heap?
My line of reasoning:
-> Insertion:
heap of DLLs: O(logN)
DLL of DLLs: O(N) Removal:
heap of DLLs: O(logN)
DLL of DLLs: O(1) Argument in favour of HEAP + DLL:
As N grows to very large, I think the difference in runtime for the two options grows significantly faster for insertion compared to removal. In other words: | log(N) - N | > | log(N) - constant |. Of course this depends on N and C, but assuming C is pretty small, for most values of N this should be true. So: to curb the growing runtime cost for insertions, choose the heap approach.
-> Argument in favour of DLL + DLL
In practise, orders might often get filled immediately, requiring us to do an insert only a fraction of the time. (I don't know if this is typically true for a regular exchange? In any case, it could be a custom business requirement). So in this case: RemovalCount is much larger than InsertionCount, i.e. the extra cost of the once-in-a-rare-while insertion in the bigger picture does not add significant runtime, so don't optimise for it, and stick with DLL + DLL.
thoughts?
Hope you had a great poo after making this video 💩
Always have great poos - yeah I think either solution that you named is fine, because you're able to name the tradeoffs. Alex Xu is a bum tho lol - no actually the best solution I've seen was a different comment to this video which said something like you should just use an array because a stock can only have a finite number of values in a day, and to be honest, I'm a pretty big fan of that one in retrospect haha
I am a bit confused about the while loop condition in the order matching part, where you do oppisiteBook.peek().peek().price=lowest ask. However, the condition in the while loop does not trigger because no bids are
Probably a typo on my end nice catch, use >