as09
BAN USERWe can solve this by maintaining an unordered_map with key as hotel_id and value as a pair of {'sum_of_scores', 'count_of_scores'}. Once we have exhausted all scores, we go through each the unordered_map and get the average score for each hotel and put it in the result list if its greater than or equal to the min_avg_score
Time complexity is O(n) because we go through the list once. It changes to O(nlogn) if the result list needs to be sorted by hotel_ids
Space complexity is O(n) to store intermediate results and the final result list
For User C, after page 3 was visited after page 7 and page 1 was visited after page 3.
So link is from 7-> and 3->1 but 3->1 link was already there so duplicate link got ignored.
Here's how I think this can be implemented.
We maintain an unordered map to store last visited page for each user. So key for unordered map M1 is user and value is last visited page.
Then we have another unordered map, M2 with key as user and value as an map say M3.
For M3 the key is the starting page and value is a set, S4 of all pages linked to it.
We loop through the logs and fill in the above data structures for all link found.
Lets say there are m users and n pages, so the run time for this code would be
T = T1(m) + T2(m) + T3(n) + T4(n) = O(nlgn),as explained below
T1 - time to insert entry in M1 which would be O(1)
T2 - time to insert in M2 which would be O(1)
T3 - time to insert in M3 which would be O(nlgn)
T4 - time to insert in S4 which would be O(nlgn)
Space complexity in worst case would be
X = X1(m) + X2(m) * X3(n) * X4(n-1) = O(mn^2)
There are two problems that I think are there in the code.
1. Using above example, your code would return D as the deepest common ancestor, while tis the parent of D, that is B, which should be returned as the DCA, unless the question fails to mention that a node can be ancestor of itself too.
2. Your code would fail if either one or both nodes are not in the tree. This can be ignored if we already know that both nodes are in the tree.
The algorithm that I am suggesting is O(m) and the way the question has been framed I can understand that the total time should be m. But if its actually O(m) then here's my solution.
1. Pair all arrays such that we have k/2 arrays. Merge the arrays in each pair. Time complexity to merge each individual pair is O(n) (n comparisons). Time complexity to merge all such pairs is (n*k/2)
2. Repeat step 1 till we have got our final sorted array.
Total time complexity for all merges is:
= k/2*O(n) + k/4*O(n) + k/8*O(n) +.....
= O(n) * k *(1/2 + 1/4 + 1/8 + ...)
= O(n) * k * 1/2*(1/(1-1/2)) (Geometric series)
= O(n) * k
= O(n*k)
= O(m)
Using two bitmaps will solve the problem of negative numbers. Use one bitmap just for the positive numbers and another bitmap for the negative numbers. Also to know what should be the size of bitmaps, just find the largest positive element and smallest negative element in both arrays.
- as09 August 06, 2013For this particular question, the character with second max count can be found like this:
#include <iostream>
#include <string>
int main(int argc, char * argv[])
{
using namespace std;
int maxCount = 0, secondMaxCount = 0;
char maxChar ='\0', secondMaxChar = '\0';
int currentCount = 0;
char currentChar = '\0';
string stream = "aaaabbbbbbbbbbccccccjjjjjjjjjjjssssskkkkkkkllllllleeeeeeeeeooooppppppppp";
if(stream.length() > 0)
{
currentChar = stream[0];
currentCount = 1;
for(int i=1; i < stream.length(); ++i)
{
if(stream[i] == currentChar)
{
++currentCount;
}
else
{
if(maxCount < currentCount)
{
secondMaxCount = maxCount;
secondMaxChar = maxChar;
maxCount = currentCount;
maxChar = currentChar;
}
else if(secondMaxCount < currentCount)
{
secondMaxCount = currentCount;
secondMaxChar = currentChar;
}
currentChar = stream[i];
currentCount = 1;
}
}
if(maxCount < currentCount)
{
secondMaxCount = maxCount;
secondMaxChar = maxChar;
maxCount = currentCount;
maxChar = currentChar;
}
else if(secondMaxCount < currentCount)
{
secondMaxCount = currentCount;
secondMaxChar = currentChar;
}
}
cout << "max - char: " << maxChar << ", count: " << maxCount << endl
<< "second max - char: " << secondMaxChar << ", count: " << secondMaxCount << endl;
return 0;
}
If the interviewer ask to generalize the solution for kth max character, then we can create an array of size 256 to store count of each character that occurs in the string, sort this array (ascending sort) and then find the kth element in the sorted array.
- as09 July 21, 2013If by interval you mean the total minutes, then I guess you would have to create a chain of all appointments for that time interval. Also you will have to create a separate such hashtable for each day.
If the interval is the time frame, then you need to have a way to see if the given time interval collides with any other appointment times interval. k-d tree provides such a structure to find an interval with which a given key collides.
I agree with the idea of using hashtable. The hashtable will use the {year+month+date} as the key and the value as a k-d tree of the intervals. So if the interval for which you are trying to create the appointment overlaps with an interval in the kd tree, you will get the collision.
I agree with the sorting of arrival time and departure time separately. But I didn't understand the part where you are trying to find the maximum number of people present at any given time. Also I don't think we are given the specific time T. We have to find the maximum number of people present at any given time.
Here's what I think to be a possible solution:
1. Sort the arrival times and departure times separately and store them in two separate arrays.
2. Loop through the array of sorted arrival times.
3. For each arrival time in the array, get the corresponding departure time.
4. Now do a binary search on the departure time array to find the index if this departure time.
5. Get the number of entries before this departure time in the departure time array.
6. If this number is greater than current max then set current max to this value.
7. After coming out of loop, return the max.
Time complexity: O(nlogn)
Space complexity: O(n)
Here's my understanding of the problem.
Since the numbers in question are cheque numbers and we can very safely assume that the check numbers are of fixed length which would be around 10. The second thing that I can figure out from this is that the pattern can occur anywhere in the cheque. So it would mean that we cannot use a prefix tree, instead we'll use a suffix tree. The run time for search in a suffix tree is O(n).
Since the length of check is constant, it would be O(c), where c is a constant. And thus constant run time can be easily represented as O(1).
The run time would be O(n) only if the length of the cheque was not a constant, but that is not the case because cheque are of constant length.
We can do a preorder traversal on the binary tree.
Time compexity O(N), space complexity, O(log(n))
int findDistance(const Node * root, int val1, int val2)
{
// check if the tree is empty or not
if(root == NULL)
{
std::cout<<"Empty tree" << std::endl;
return -1;
}
// check if the two values are equal or not, if they are
// then the distance between the two is obviously zero
if(val1 == val2)
return 0;
// have a stack to hold the nodes for back traversal
std::stack<Node*> stack;
// For simplifying our code, we will make val1 < val2
if(val2 < val1)
{
val1 = val1 + val2;
val2 = val1 - val2;
val1 = val1 - val2;
}
// initial distance betwen nodes is -1
int distance = -1;
while(!stack.empty() || root != null)
{
// traverse to the left of the subtree at root
if(root != null)
{
if(root->val == val1)
distance = 0;
// if value of this node = val2, then we are done
// return distance calculated so far
else if(root->val == val2)
return distance;
stack.push(root);
root = root->left;
// this node might be on the path between val and val2
// increment distance
++distance;
}
// else go right
else
{
root = stack.pop();
// this node is not on the path between val and val2
// decrement distance
--distance;
root = root->right;
}
}
return distance;
}
Please let me know if I have missed any corner case or if the logic needs some change
- as09 February 09, 2013How about this approach:
let number to be find, key = 17
and the matrix M is
1 2 5 16 18
3 9 27 29 33
7 11 36 41 55
13 17 45 52 57
46 23 47 61 72
Algo:
We start with the last element of the first row
i := 0,
j := n-1
key_found := false
while(i < n && j >=0 && key_found == false)
do
if(M[i][j] == key)
key_found = true; // We have found the element in the matrix
else if (M[i][j] > key)
i <- i - 1; // We go back 1 element in the current row
else
j <- j + 1; // We go down 1 element in the current column
end while
if(key_found)
print (i, j)
else
print (key not found)
The run time of this algo is O(n). The maximum comparisons that we would need to make using this would be 2n - 1. Please let me know if you guys find any issues with the logic. Thanks
- as09 January 22, 2013
- as09 July 17, 2016