rizhang
BAN USERThe code is kind of big to write, but I pretty much rewrote Merge sort and added a little extra so it wasn't too bad. Obviously I had the luxury of a IDE, but the interviewer should steer you in the right direction if you make any mistakes.
static public int maxQaz(int[] A) {
int[] max = new int[A.length];
return mergeQazUtil(A, max, 0, A.length - 1);
}
static public int mergeQazUtil(int[] A, int[] Max, int start, int end) {
if(start == end) return 0;
int mid = (start + end)/2;
int leftRes = mergeQazUtil(A, Max, start, mid);
int rightRes = mergeQazUtil(A, Max, mid + 1, end);
int merged = merge(A, Max, start, end, mid);
return Math.max(leftRes, Math.max(rightRes, merged));
}
static public int merge(int[] A, int[] Max, int start, int end, int mid) {
int[] AHelper = new int[A.length];
int[] MaxHelper = new int[Max.length];
for(int i = 0; i < A.length; i++) {
AHelper[i] = A[i];
MaxHelper[i] = Max[i];
}
int leftStart = start, leftEnd = mid, rightStart = mid + 1, rightEnd = end;
int index = start;
int max = 0;
while(leftStart <= leftEnd && rightStart <= rightEnd) {
int curMax = 0;
//this is assuming no numbers are equal
if(AHelper[leftStart] < AHelper[rightStart]) {
MaxHelper[leftStart] += (rightEnd - rightStart) + 1;
curMax = MaxHelper[leftStart];
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
leftStart++;
} else {
A[index] = AHelper[rightStart];
Max[index] = MaxHelper[rightStart];
rightStart++;
}
if(curMax > max) max = curMax;
index++;
}
if(index <= end) {
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
}
return max;
}
Since they want O(nlogn) they probably want something to do with sorting or divide and conquer. My solution is merge sort, but you have another array storing counts :
Lets call the original array A, and the max array Max
1. Recursively cut the array in half like in merge sort
2. Merge Process:
Let's assume leftIndex is the starting index of the left side and rightIndex is the starting of the right side. Lets say endRight is the end of the right and endLeft is end of left.
1. Check to see whether the starting index of the right side or left side is bigger.
2. If the left side is bigger, update Max[leftIndex] += endLeft - rightIndex. Then do the swapping in the same way you would for both arrays.
3. If the right side is bigger, just do the swapping for both array like you would normally.
Once you are done you can just search for the biggest number in Max[], which would take O(n). So the complexity is nLgn + n, or O(nLgn).
I wonder if there is a way to do this without an extra array. You can probably keep track of the max during the merge process so you can cut out the last O(n) operation. Let me know if I made any mistakes!
How would it be more interesting to solve the problem in O(nlogn + r)? r = n^2 so you are pretty much asking to solve this in nlogn + n^2 as opposed to n^2, both of which is O(n^2) except what you suggest is slightly worse than the solution we are commenting on.
- rizhang January 08, 2015@Anonymous Hashing with primes will work for most words, but again the example I posted will fail, even with a 64 bit int (I tested it).
@naren wow that's a good solution
@CT If we sort the chars and hash it, the total time complexity will be O(n*m*logm), where n = #words, m=avg # chars. If you write your own hash function, the complexity becomes O(n*m). Please let me know if you think I made a mistake
Good solution! You have a couple of minor bugs
1. the compare function should be:
public int compare(Event e1, Event e2){
return e1.startTime-e2.startTime;
}
and
public int compare(Event e1, Event e2){
return e1.endTime-e2.endTime;
}
Right now you have a max heap instead of a min heap
2. You need to do this check for the best flowrate right after you look through heap1 as well. If you run the example case your solution will return 500 instead of 600
The only problem with assigning numbers to chars is if all chars are in the list of strings. Let's say z = 101. If you have "zzzzzzzzzz" you'll have 101^10 which is a huge number. If all the strings must be a word from the dictionary, "Pneumonoultramicroscopicsilicovolcanoconiosis", which according to my google search is the longest word in the dictionary, will have a huge value
- rizhang December 14, 2014This question is impossible if you can have as many of the same characters as possible. if you have a string "wwwwwawwwww" then the only possible outputs from the getRandomTripplet() are "www", "aww", "waw", "wwa".
If you run the random function a billion times and count how often each instance shows up, statically you can eliminate "awwwwwwwwww", "wwwwwwwwwwa", "wawwwwwwwww", and "wwwwwwwwaw", but other than that there's no way to guess the correct string.
Basically I kind of do a binary search. I look at the middle of the array, and calculate the expected value if the array wasn't missing numbers from start to index, and end to index. If the values are what I expected for the left, then I don't check the left half. I do the same for the right. If it isn''t the expected value, I check the adjacent numbers to see if there is a gap and print out those numbers.
public static void main(String [ ] args)
{
Set<Integer> set = new HashSet<Integer>();
printMissingNumbers(8, 8, new int[] {1,3,5,9,10,11,15}, set);
Set<Integer> set2 = new HashSet<Integer>();
printMissingNumbers(8, 1, new int[] {1,2,3,4,5,6,7,8,9,11}, set2);
}
static public void printMissingNumbers(int n, int m, int[] arr,
Set<Integer> set) {
int start = arr[0];
int end = arr[arr.length - 1];
printMissingUtil(start, end, m, arr, set);
}
static public void printMissing(int startNum, int endNum,
Set<Integer> set) {
for(int i = startNum + 1; i < endNum; i++) {
System.out.println(i);
set.add(i);
}
}
static int num = 0;
static public int printMissingUtil(int start, int end,
int m, int[] arr , Set<Integer> set)
{
num++;
System.out.println("iteration: " + num);
int index = arr.length/2;
int expectedLeft = index + start;
int expectedRight = end - (arr.length - (index + 1));
int currentVal = arr[index];
if(expectedLeft < currentVal) {
if(currentVal - arr[index - 1] != 1) {
printMissing(arr[index - 1], currentVal, set);
m -= (currentVal - arr[index - 1] - 1);
}
if (m == 0) {
return 0;
}
int newend = arr[index - 1];
m = printMissingUtil(start, newend, m,
Arrays.copyOfRange(arr, 0,index ), set);
}
if(expectedRight > currentVal) {
if(arr[index + 1] - currentVal != 1) {
printMissing(currentVal, arr[index + 1] ,set);
m -= (arr[index + 1] - currentVal - 1);
}
if(m == 0)
return 0;
int newstart = arr[index + 1];
m = printMissingUtil(newstart, end, m,
Arrays.copyOfRange(arr, index + 1, arr.length ), set);
}
return m;
}
He's saying that in the worst case, when you have a sorted array, it will be O(n^2). This is because you are building a degenerate tree, where every node only has a right child or not children, or a tree with only left or no children. It's like building a linked list where you always start traversing from the head.
- rizhang January 28, 2015