We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This problem took me longer than I had hoped to solve, basically because a lot of the write-ups are not necessarily clear on a few points. To solve this you need to use a Treap with implicit indexing. Various comments below have cited resources for learning about a Treap and how to implement it, the challenge for me was implicit indexing.
In my initial solution I created a Treap using a key, value pair, where the key was the index of the array (zero based), and the value was whatever value was at that index. I then implemented a lookup method based upon the key, so for instance I could look up at index five and get whatever the value was. When I implemented implicit indexing I had an incorrect understanding of what was an implicit index. When you split a tree with implicit indexes you do it based upon sub-tree sizes, in this case the size of the left sub-tree. When I was doing the split I was passing in the key, not the implicit index. Consider the following example:
{ 1, 2, 3, 4, 5, 6, 7, 8 }
For this problem if you implement a query of “1 2 4” that means you want to take values { 2, 3, 4 } and put them at the front of the array, giving you:
{ 2, 3, 4, 1, 5, 6, 7, 8 }
Now you have a second query of “2 3 5.” My initial misunderstanding was that given I needed to split based upon the second position in the array, I would look up the key at value “3” and then use it. That’s wrong. For implicit indexing you don’t do that at all, because your tree is in a state that you may not find the key as it could be out of order. With implicit indexing you assume that risk, and instead simply pass in the index of where you want to split. So instead of whatever the key was at value three, I instead just said split based upon a key of one (zero based indexing, so 2-1 is 1), as we want the following result:
Left tree = { 2, 3 }
Right tree = { 4, 1, 5, 6, 7, 8 }
With the above we are now set to do another split, this time at position two. That is calculated by taking the end value of five, minus the start value of three, giving us the position of two (again, zero based) that we want to do the split off of. The result there is:
Unchanged left tree = { 2, 3 }
Middle tree = { 4, 1, 5 }
Right tree = { 6, 7, 8 }
That was the breakthrough moment, once I understood that with implicit indexing keys don’t matter, and it really is relative to position, everything else made sense.
I got a 100% completion rate for my solution that used C#. I’ve cleaned up my code, made a bunch of comments, and created a GitHub repository so that others can read my solution and learn from it. Once you understand how it works this really is a useful concept and I’m glad I did it. But a lot of the write-ups on this are heavy in academia and lacking in practical walkthroughs, save for the following YouTube video: https://youtu.be/erKlLEXLKyY, which gave a reasonable explanation of things, but glossed over the fact an implicit index really is just the index, and not a key.
Array and simple queries
You are viewing a single comment's thread. Return to all comments →
This problem took me longer than I had hoped to solve, basically because a lot of the write-ups are not necessarily clear on a few points. To solve this you need to use a Treap with implicit indexing. Various comments below have cited resources for learning about a Treap and how to implement it, the challenge for me was implicit indexing.
In my initial solution I created a Treap using a key, value pair, where the key was the index of the array (zero based), and the value was whatever value was at that index. I then implemented a lookup method based upon the key, so for instance I could look up at index five and get whatever the value was. When I implemented implicit indexing I had an incorrect understanding of what was an implicit index. When you split a tree with implicit indexes you do it based upon sub-tree sizes, in this case the size of the left sub-tree. When I was doing the split I was passing in the key, not the implicit index. Consider the following example:
{ 1, 2, 3, 4, 5, 6, 7, 8 }
For this problem if you implement a query of “1 2 4” that means you want to take values { 2, 3, 4 } and put them at the front of the array, giving you:
{ 2, 3, 4, 1, 5, 6, 7, 8 }
Now you have a second query of “2 3 5.” My initial misunderstanding was that given I needed to split based upon the second position in the array, I would look up the key at value “3” and then use it. That’s wrong. For implicit indexing you don’t do that at all, because your tree is in a state that you may not find the key as it could be out of order. With implicit indexing you assume that risk, and instead simply pass in the index of where you want to split. So instead of whatever the key was at value three, I instead just said split based upon a key of one (zero based indexing, so 2-1 is 1), as we want the following result:
Left tree = { 2, 3 }
Right tree = { 4, 1, 5, 6, 7, 8 }
With the above we are now set to do another split, this time at position two. That is calculated by taking the end value of five, minus the start value of three, giving us the position of two (again, zero based) that we want to do the split off of. The result there is:
Unchanged left tree = { 2, 3 }
Middle tree = { 4, 1, 5 }
Right tree = { 6, 7, 8 }
That was the breakthrough moment, once I understood that with implicit indexing keys don’t matter, and it really is relative to position, everything else made sense.
I got a 100% completion rate for my solution that used C#. I’ve cleaned up my code, made a bunch of comments, and created a GitHub repository so that others can read my solution and learn from it. Once you understand how it works this really is a useful concept and I’m glad I did it. But a lot of the write-ups on this are heavy in academia and lacking in practical walkthroughs, save for the following YouTube video: https://youtu.be/erKlLEXLKyY, which gave a reasonable explanation of things, but glossed over the fact an implicit index really is just the index, and not a key.
C# solution built using Visual Studio 2017 Community edition can be found at https://github.com/MrAngry52/Treap.