deepanshu
BAN USERHow about a HashMap where scientist is key and there is a linked list of black_holes for the value if the scientist can query multiple black holes.
And the black_hole can it self contain some information about its identity and a linked list of queries made:
HashMap<Scientist,List<BlackHole>>
Class BlackHole{
Identity;
List<Query>;
}
Class Query{
QueryType;
QueryResult;
}
Solution is complex so, please bear with me till the end.
There are 3 machines with capacity 100 and filled with 90 values(let's call percentages as one unit value).
Initial Condition:
M1: 90 (Unsorted)
M2: 90 (Unsorted)
M3: 90 (Unsorted)
Step 1:
Sort all 3 individual machines: 3 sort operations
Now, follow the process below:
1. Transfer top 30 from each machine to M1 (2 transfer operations as top 30 of M1 is already in M1)
2. Transfer bottom 30 from each machine to M3 (2 transfer operations)
3. Transfer middle 30 from each machine to M2 (2 transfer operations)
Current Status:
M1: top 30 values rest 60 unknown
M2: 90 unknown
M3: bottom 30 values rest 60 unknown
Operations so far: 3S + 6T (3 sorts and 6 transfer) (Every step will take exactly 9 operations until specified otherwise)
Now next time on wards we won't touch the known value only transfer unknown values.
Step 2:
Repeat Step 1 for value 20 instead of 30
Current Status:
M1: top 50 values rest 40 unknown
M2: 90 unknown
M3: bottom 50 values rest 40 unknown
Step 3:
Repeat Step 2 for value 10 instead of 20
Current Status:
M1: top 60 values rest 30 unknown
M2: 90 unknown
M3: bottom 60 values rest 30 unknown
Step 4:
Repeat Step 3 once more.
Current Status:
M1: top 70 values rest 20 unknown
M2: 90 unknown
M3: bottom 70 values rest 20 unknown
Step 5:
Repeat Step 4 for value 5 instead of 10
Current Status:
M1: top 75 values rest 15 unknown
M2: 90 unknown
M3: bottom 75 values rest 15 unknown
Step 6:
Repeat Step 5 once again
Current Status:
M1: top 80 values rest 10 unknown
M2: 90 unknown
M3: bottom 80 values rest 10 unknown
Step 7:
Repeat Step 5 once again
Current Status:
M1: top 85 values rest 10 unknown
M2: 80 unknown
M3: bottom 85 values rest 10 unknown
Operations so far: 7 * 9 = 63 (7 Steps, each took 9 operations)
Step 8:
1. Transfer 10 unknown from M1 and M3 to M2 (2T)
2. Sort M2.
3. Transfer top 5 to M1 and bottom 5 to M3(2T)
Total Operations: 63 + 5 = 68
I know it is hard to follow. Please let me know if there is any better solution or is there any thing I can amend in it.
What we can do is we can create permutation of all the strings which can be formed using the input string 'S':
Let's say the string 's' is "ab"
Permutations:
a, b, ab, ba
Now just search each permutation in the dictionary in log(n) time(binary search as it's a dictionary and sorted) this takes (no.of permutations)*log(n). if we say that the length of s is fixed to 4, then there can only be constant number of permutations and hence this will run in log(n) time.
I have an idea about dynamic programming. I was asking in context of this question. As the optimal solution is to divide the group into 3 sub-groups and again checking those and choosing another suitable sub-group and then searching in that group. So, this looks like a ternary search(like binary search but just dividing the input into 3 parts).
So, basically we are just dividing the input into sub-problems. What part of the above algorithm known as dynamic programming. And if this is a DP algorithm, then even binary search is a DP algorithm.
Please bear with me, I am very confused.
This looks like filling the sibling pointer problem.
1. In the Tree itself add one more pointer which point to the sibling on that level.
Filling the siblings can be done in o(n) when parent pointer is given.
2. Just make the right pointers null.
3. This has the resultant as a list.
How about using two count arrays
Count array: size 26 (holds frequency of each character from the string)
Generating count array for both the strings is O(n) and space is also constant(as for any length of input we will only create 2 arrays of size 26).
and then traversing the count arrays together to find the non-common characters which is again O(n).
It doesn't work. In a binary search tree all the nodes in the left sub tree should be lesser than root, and all the nodes in the right sub tree are greater than root.
For the test case
3
2 5
1 4
The function is called using isBST(3)
which in turn calls
isBST(2) and isBST(5)(this is true)
now isBST(2) calls
isBST(1) and isBST(4) which is also true
so this method actually returns true.
See, at any point in each level of recursive call you don't have any information about the ancestors of that node. Hence there is no way you can say whether the tree is BST using this method.
I think O(n) is very obvious solution. It should only take O(logn) as the array is sorted. We first find the number which violates the condition of an increasing sequence using binary search, and then we find the number which violates decreasing sequence...
The code for it will be very messy but yeah efficient.
Harsha,
Your solution works only when k is constant. But, as far as I understand "k" will be passed at run time. And for that we have to use a sorted array to access the kth maximum element in O(1). Also, the amortized time for inserting into the dynamically growing the array is also O(1). Hope this helps...
As I have mentioned that the insertion and deletion(push & pop) complexity will be O(n). So whenever a new element is pushed just insert the same element in the array also in sorted order(search for the position to insert and then shift the rest of the elements by one position), which will take O(n), and whenever an element is popped just delete is from the array also, which will also take O(n).
If you run into array size being small issues just use the dynamic growing array approach which will also not increase the complexity.
You can use a stack and an array which holds elements in sorted order. The only problem is the insertion and deletion complexity will be O(n), but finding maximum or kth maximum will always be O(1).
public class Stack{
int[] elements;
int top;
int[] sortedElements;
public void push(int ele){
//here just have to insert in the array "sortedElement" also. which will take O(n).
}
public int pop(int ele){
//here just have to delete from the array "sortedElement" also. which will take O(n).
}
}
We create a hash map with the numbers and have a bit value to each number. So when the number is added for the first time bit will be 1 and then every time we find that number again we will toggle the bit. Then once the hashMap is created will parse through array once again whichever element has bit as 0 will be our number.
- deepanshu February 20, 2016HashMap<Integer, boolean>
for each number in array{
if does not exists in hash map then add (num, true)
else toggle the bit associated(if 1 the 0, vice versa)
}
for each number in array{
if bit is 0 in hashmap then return number
}
The only reason I used bit is for storing the even not even part and as it occupies only one bit it saves space as well.