Kamy
BAN USERTo get O(n log n * log n) complexity it means that we have to solve the problem by doing a sorting and organizing an array as a tree , to be able to search next in log n time.
My idea is to sort and organize the array of rectangles creating a structure for each node to be formed of : min x , max x, min y, max y. Next search in Log n time for each point if it fits in a rectangle.
O(nlogn log n) time and O (length of the rectangle array)
What if u start from the middle ? Tree number 3. If you shoot at tree 3 . Then you have 3 posibilities :
-- you killed the monkey
-- the monkey is in the tree 1 or 2. Next shooting will be at tree 2.
-- the monkey is in the tree 4 or 5. Next shooting will be at tree 4.
So the maximum number of times you will have to shoot will be 3. When you start with tree 3 the monkey will be scared to jump through tree number 3.
Obviously to find the result we have to go through all the data . So lets consider that the result will be kept in the first array. Start from the position n in the first and second array with 2 iterators: first = n and second = n;
while (second >=0 && first>=0){
if(B[second] == A[first]) first--;
second--;
}
remove(A,0,first); // remove all the elements in A from index 0 to first
go do the same for the first and third array, first and fourth and so on.
At the end return A (the first array).
First approach: O(n^2)
Global variables : maxProfit, maxSellValue, maxBuyValue
- start from the end , and for each index j(consider it selling value) find the max profit by computing a[j] - a[i] where i < j. Put in maxProfit the max profit found if bigger than maxProfit and store in maxSellValue the value from index j and in maxBuyValue the value from index i.
- return maxSellValue and maxBuyValue.
Example:
array = [150 ,149 ,155, 157, 137, 150, 167]
j = 6 : maxProfit = 30 maxSellValue = 167 maxBuyValue = 137
j = 5: the three values are the same
j = 4: the three values are the same
j = 3: the three values are the same
j = 2: the three values are the same
j = 1: the three values are the same
j = 0: the three values are the same
return the three values.
1 2 3 25
4 23 20 88
7 82 90 100
8 83 91 101
Sort the matrix =>
1 2 3 4
7 8 20 23
25 82 83 88
90 91 100 101
k = 2;
rows = 4
cols = 4
r = 4 -1- (2/4) = 3 - 0 = 3;
c = 4 - (2%4) = 4 - 2 = 2;
the result is element m[3][2] = 100
P.s. When I asked how is the matrix sorted and u said left-> right & top to bottom.. that means that your matrix is already sorted as I reorganized it. If not than it will take time to do it .
Better solution is this : http://www.quora.com/How-can-you-efficiently-determine-the-k-th-maximum-element-in-a-MxN-sorted-matrix
Whenever we have to insert a node into a sorted single linked list we have to take care of these cases:
1. the node we want to insert is null?
2. the list is empty (==null)?
3. the node to be inserted will fit before the head of the linked list?
4. and ask the interviewer what to do if the linked list contains values == node.value
after checking the 3 things :
Node temp = root;
while(temp.next!= null){
if(temp.next.value < node.value) temp = temp.next;
else break;
}
node.next = temp.next;
temp.next = node;
We can create a class HashMap_Element that will have 2 variables Key and Value. And then we will create another class myHashMap that will contain an array of HashMap_Elements. In the second class we will have to make sure that when the array becomes almost full we will create a new array with a doubled size then the last one and move all the elements from the last one into the new one.
- Kamy January 26, 2013Lets say we have 2 arrays: in and out. In is the input and out is the output of size k. At the end array out will have :
- at position 0 the maximum value for the first k values in the array in.
- at position 1 the maximum value for the second k values in array in
.....
and so on.
int idx ; // index to go over the in array
int idx_K; // index to go over the out array
idx_K = idx / k;
so if (in[idx] > out[idx_K]) out[idx_K] = in[idx];
return out;
if the numbers are not very large we can use an array of length = the max of the numbers.
for each element in the given array increment the value from the position "element" in the new array. Now go 3 times and pick the max value from our array, putting an invalid value in its place and memorizing the position of the max.
return those 3 positions.
First idea:
If the common bst has to start with the root of the smallest tree :
first put the biggest tree in A, and the other one in B.
maxLength = Integer.MIN_VALUE;
tree max;
Search in tree A the root of B. When you find it:
---- call a function that goes deep in A and check what's the match, storing the match in a temporary tree. if the length of the temporary tree is greater than maxLength then maxLength = temporary tree.length and max = temporary tree.
Keep searching in A the root of B until you finish seeing all the nodes in A.
At the end if the maxLength==Integer.MIN_VALUE return 0; else return maxLength!
Second idea:
Find the inorder traverse of A and B .. find the longest match between them.
-sort the points based on the distance between them and (0,0). Now start with two pointers: one = 0, and two = k; Compute the total distance between one and two , if its < min then store it in min. increment one and two , the new distance is D = previous_distance - distanceBetween(point[one-1], point[one]) + distanceBetween(point[two], point[two-1]); if distance < min store it in min and so on till two goes over the point.length.
Each time we store a new value in min we also store in 2 variables the values of "one" and "two" . At the end we return all the points betweeen one and two.
Hi!
What about a BFS?
I would mark the empty nodes with some standard value. And than do a BFS : when I reach the level with the given data , I will check for the left most right position which should be the cousin .. and if it is a standard value of mine then return null else return the data from the node.
(Correct. I mean BFS)
store the string into an array: str
start with two indexes : idx=0 and k=0
while(k < str.length){
if(str[k] == ' '){
if(str[idx] != ' '){
str[idx] = str[k];
idx++;
}
} else { str[idx] = str[k]; idx++;}
k++;
}
reconstruct the string from the array between positions : 0 and < idx
- Kamy January 04, 2013First i would think of what operation will be done in a car parking:
--- add a car in the first empty parking space
--- delete a car from a given index in the parking lot
--- check if there are any empty spaces available
I would use a hasmap to map the parking spot to the car parked on it.
I would use another hashmap to keep track of te empty slots in order.
I think this : "
IsBST(Root->Left, MIN, Root->Info+1) &&
IsBST(Root->Right, Root->Info-1, MAX) );"
Should be :
IsBST(Root->Left, MIN, Root->Info) &&
IsBST(Root->Right, Root->Info, MAX) );
Because BST doesn't allow for the nodes to have the same value.
What do you think?
We can do better then O(max(n log n,m log m))
Put all the elements from A in a HashMap (key = element, value = 1)
for each element in B if exists in the HashMap (this check is done in O(1)) then added to the returned structure.
Complexity : time :O(max(n,m)) ; space: O(min(n,m)). // we assume ^_^ that A.length < B.length.
Are you sure this is O(n)? I am asking because I know that you can't access the char from position j in a string using : str[j]. And you can't do str[j] = str[i], you will have to do : str = str.substring(0,j) +str.charAt(i)+str.substring(j+1). This will take O(n) . Including this in an iteration throw each character gives an O(n^2) algorithm.
- Kamy December 20, 2012First of all if we draw the figure:
----for the starting station: we will see that for each station on the circle there are two possible ways clockwise or counter-clockwise. So lets say we are at station one, we get here gas for C1 distance, so now we can either go to station 2 or station n. (If C1 < D1 then we can only choose Sn, and if C1 < Dn then we can only choose S1, otherwise you can try either of them).
---- I think that analyzing this, the best solution is to do something like this :
foreach currentStation = 1..n{
clockDirection = -D[ getNextStation (currentStation) ] + C[ currentStation ];
counterClockDirection = C[ currentStation ] - D[ getLastStation (currentStation) ];
int gas = -1;
if(clockDirection > 0){
gas = goToNextStation(currentStation, getNextStation(currentStation), true, clockDirection);
}
if(counterClockDirection > 0){
gas = Math.max(gas, goToNextStation(currentStation, getLastStation(currentStation), false,counterClockDirection);
}
if(gas>=0) return currentStation;
}
return -1; // there is no valid station to start from
-----------------------------------------------------------------------------------
int getLastStation(in station){
if(station==1) return n;
return station-1;
}
-----------------------------------------------------------------------------------
int getNextStation(int station){
if(station==n) return 1;
return station+1;
}
-----------------------------------------------------------------------------------
int goToNextStation(Station startedFrom, Station stationToGo, boolean clockWise, int availableGas){...}
- so if we arrive at startedFrom then return availableGas
- if not , then check which way we are going and add the clockWiseDirection or the counterClockDirection value to the available gas, and call goToNextStation(startedFrom, getNext /getLast Station(stationToGo), clockWise, theNewAvailableGas).
What I am trying to say is that we should make like a preview for each station to see if it will fit as a starting station. We cannot choose a station to be the starting one unless we know for sure that if we run the alg starting from it , we will get a valid result. So we don't know that unless we check it first.
My first approach would be to create a HashMap<key = page number, value = number of times the page is opened>. This will be done in O(n).
Next, create an array of size 3 which we will return as a solution (at the end).
We will initialize the array with the first 3 keys from the HashTable.
Ex: A: 1, 2, 3
Now for every other key K in HashMap:
- compute the minimum value between the values assigned to those 3 keys stored in HashMap, and remember the key assigned to the min in Min_key
- check to see if the min is greater or equal to HashMap.get(K) ; if so.. ignore
else replace the Min_key with K
This will be done in O(5 * 3) = O(15)
So the total time : O(n) + O(15) = O(max(n,15)) = O(n)
At the end we have obtained in O(n) time complexity the 3 pages which were frequently used by the users.
Of course we can check , and reorder the values of the array to have in A[0] the most visited page, A[1] less visited, A[2] the least visited page, without changing the complexity.
This is a good solution : O(n) time complexity and O(1) space if not consider the stack call, in stead of the InOrder solution which uses O(n) time and O(n) space.
Here is the java version:
public static boolean isBst(TreeNode root, int min , int max){
if(root==null) return true; //modified
if(root.d < min || root.d >max) return false;
return isBst(root.left, min, root.d-1) && isBst(root.right, root.d+1, max);
}
I think avikodak's solution would be a good choice if would be important to not use any additional space.
But since the important thing is minimum time complexity .. we can do it in O(n * w) where word is the length of the word : we would use the same logic as in avikodak's algorithm, but in stead of using a n log n sorting alg. I would recommend counting alg which we'll involve additional space , but we'll decrease the time complexity.
isn't switch as running through an array of constant dimension K , looking for the correct match? If so the complexity of what you wrote in O(n * k) where n is the size of the string.
- Kamy February 27, 2013