This is an interesting exercise: implement a locking mechanism backed by a tree structure with parent pointers where a node can be locked if and only if none of his ancestors and descendants are locked.
Have the lock testing operation run in O(1) time, while the lock and unlock operations should run in O(H) time where H is the height of the tree.
The fact that we are given the desired runtimes is the hint we need to understand how to implement this and the parent pointer is also a key element.
A lock testing operation in constant time means we are definitely tracking the information we need on the node itself.
An O(H) lock and unlock operation means we are not scanning both branches of a node AND the ancestors every time we need to check whether any of those contains an already locked node.
The way we can accomplish this then, is if we are tracking an additional piece of information in each node and increase the complexity of both operations to maintain this information updated.
If in each node we track for example the number of locked descendants in both subtrees, we would only need to test if any ancestor is locked during the lock operation before performing the lock and we would need to reduce the count of locked nodes in our ancestors during the unlock operation.
You can check my implementation on my Gist along with some test cases in BSTLockJTests.
I was a bit lazy so I reused an existing BST implementation that is not even fully balanced, but I am expanding this code and do not like rewriting too much :)
14/11/2017
12/11/2017
[Java] Find duplicate element in array with binary search
Disclaimer: this solution comes from interviewcake, where they mention this as being easier to (I guess) derive than the ones we saw before using Floyd's and Brent's cycle detection algorithms, but to be honest I feel the other way around. Plus bonus points because the graph solution is marked as BEAST MODE which definitely makes us feel proud when the implementation is done :)
Anyway, we still want to keep space constant and not destroy the input, but we have no idea that graphs exist so what options are we left with?
When searching for something, a good idea is to perform a binary search. In our case though, the input structure is not really built in a way where we can safely apply the algorithm since the array is not ordered. But this problem is very specific: given a series of N+1 items in the range 1 to N, find one of the duplicates.
Anyway, we still want to keep space constant and not destroy the input, but we have no idea that graphs exist so what options are we left with?
When searching for something, a good idea is to perform a binary search. In our case though, the input structure is not really built in a way where we can safely apply the algorithm since the array is not ordered. But this problem is very specific: given a series of N+1 items in the range 1 to N, find one of the duplicates.
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Find duplicate element in array in constant space and linear time v2
Well a good night's sleep always helps apparently. Yesterday we saw how to find a duplicate element in a constrained array in linear time and constant space and based the implementation for the cycle detection on Floyd's algorithm.
Today we do the same, but use Brent's algorithm instead which supposedly should be overall faster.
You can find the implementation of findRepeatBrent on my Gist and I also provide some timings comparison in the compareFloydAndBrent method in my test cases FindRepeatJTests. Of course you need multiple runs and maybe a bigger input as well to appreciate the difference, but it appears that overall there is a small performance improvement with Brent's method.
You can also find here an implementation that is slower O(N log N) and still uses constant space, based on binary search.
Today we do the same, but use Brent's algorithm instead which supposedly should be overall faster.
You can find the implementation of findRepeatBrent on my Gist and I also provide some timings comparison in the compareFloydAndBrent method in my test cases FindRepeatJTests. Of course you need multiple runs and maybe a bigger input as well to appreciate the difference, but it appears that overall there is a small performance improvement with Brent's method.
You can also find here an implementation that is slower O(N log N) and still uses constant space, based on binary search.
Tag:
HowTo,
Java,
JUnit,
Source code
11/11/2017
[Java] Find duplicate element in array in constant space and linear time
Sooo.. spoiler alert: this one was way harder than it should be thanks to 0-index arrays.
Given an array of integers in the range 1..N and length N+1 find one of the possible duplicate elements in O(N) time and O(1) space WITHOUT altering the input.
Those constraints are quite strong since finding a duplicate in O(N) time and space is pretty easy: place all elements in a HashSet while iterating over the input and return as soon as a duplicate is found.
Finding a duplicate in O(N log N) time and O(log N) space is also easy: sort the input - using a kickass quicksort implementation otherwise good luck keeping those costs down - and then walk over it comparing elements in pairs until the duplicate is found.
Finding it without destroying the input and without using additional space is also easy in O(N^2) time: for each element, loop over the full array until a duplicate is found.
Given an array of integers in the range 1..N and length N+1 find one of the possible duplicate elements in O(N) time and O(1) space WITHOUT altering the input.
Those constraints are quite strong since finding a duplicate in O(N) time and space is pretty easy: place all elements in a HashSet while iterating over the input and return as soon as a duplicate is found.
Finding a duplicate in O(N log N) time and O(log N) space is also easy: sort the input - using a kickass quicksort implementation otherwise good luck keeping those costs down - and then walk over it comparing elements in pairs until the duplicate is found.
Finding it without destroying the input and without using additional space is also easy in O(N^2) time: for each element, loop over the full array until a duplicate is found.
Tag:
HowTo,
Java,
JUnit,
Source code
09/11/2017
[Sheet Music] Ludovico Einaudi - Divenire
A contemporary masterpiece, you can find here the full album.
Tag:
Music
07/11/2017
[Java] Convert expression to reverse polish notation
The closing chapter of my RPN journey, how to convert an infix notation expression to a postfix notation one, so from 3 + 4 we get 3 4 +
Here as well it appears immediately that a String is not the most comfortable input structure, so we stick to an array.
First idea was to scan the input and tokenize it in a left side portion and right side portion for each operator we found:
3 - 4 x 5
would become first:
3, 4 x 5, -
Then finally:
3, 4, 5, x, -
Here as well it appears immediately that a String is not the most comfortable input structure, so we stick to an array.
First idea was to scan the input and tokenize it in a left side portion and right side portion for each operator we found:
3 - 4 x 5
would become first:
3, 4 x 5, -
Then finally:
3, 4, 5, x, -
Tag:
HowTo,
Java,
JUnit,
Source code
05/11/2017
[Java] Evaluate reverse polish notation in constant space
Yes it is possible, yes it took me one full day research included, but the RPN can be evaluated in O(N) time and O(1) space, sacrificing the input in the process.
There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an in place algorithm.
Consider the following expression corresponding to 3 - (4 x 5): 3 4 5 x -
For RPN reading from left to right, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so 3 4 5 x - can be rewritten as 3 20 -
We can therefore recycle the processed space (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.
There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an in place algorithm.
Consider the following expression corresponding to 3 - (4 x 5): 3 4 5 x -
For RPN reading from left to right, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so 3 4 5 x - can be rewritten as 3 20 -
We can therefore recycle the processed space (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.
Tag:
HowTo,
Java,
JUnit,
Source code
Subscribe to:
Posts (Atom)