zd
BAN USERO(nlogn) solution:
We're given an array of ranges.
We sort the ranges by lower range number with quicksort in O(nlogn) time and O(1) memory
Keep a counter of how many elements we will traverse
Then we pull the lowest range, increment counter by 1 and increment the lower range by 1. If that range's low > high then remove that array.
We then insert the new range back into the sorted array of arrays in O(n) time (most likely O(1) time because we pulled the lowest so we know it's probably one of the lowest still)
Stop when our counter is the kth element.
I have an O(nlogn) solution.
Scan through the string and count character occurrences.
Build a max heap with the character occurrences.
Build a string with the top character.
Then loop: pull the top character and check if its the same as the previous character. If so, check the heap left or heap right to get the next highest occurrence. This means that we need to have access to the heap node internals.
Sort start times with an nlogn sorting algorithm and store it.
Sort end times with an nlogn sorting algorithm and store it.
We traverse sorted start times and add to an accumulator, but after traversing one start time, we traverse as many end times as needed to "catch up" to the start time and we subtract that from the accumulator. Take the max of accumulator vs the current max at each traversal.
O(nlogn)
Pop the flight boarding passes one at a time. Create a hash table of String to Integer. We're going to map the city to the net in and out. For departure, decrease value of net in and out, for arrival, increase value of net in and out. At the end, scan through the hash table to find +1, which is the destination, and -1, which is the departure.
- zd September 06, 2015public static int findMatches(String source, String target) {
if(source.length() == 0) {
return 1;
}
if(target.length() == 0)
return 0;
int num = 0;
for(int i = 0; i < target.length() - source.length() + 1; i++) {
if(source.charAt(0) == target.charAt(i)) {
num += findMatches(source.substring(1), target.substring(i+1));
}
}
return num;
}
I have an O(log n) solution.
- zd June 29, 2016Binary search the middle row. Now you know the x and y of the middle 1. We break the matrix into four rectangular sections. Everything on the upper left of the middle 1 must be a 0. Everything on the bottom right of the middle 1 must be a 1. This leaves the bottom left and the upper right. Those two sections are smaller versions of the original problem so we recurse on those sections. Performing the binary search takes (log n), and since we are breaking the problem in half each time, there will be (log n) recursions. The next recursions perform a binary search taking time (log n/2), (log n/4), etc. This results in O( log n + log n/2 + log n/4 + ...) which amortizes to O(log n).