Biru
BAN USERThe solution is simple - take any row or column, and look for what words in dictionary match that pattern. e.g. if a row contains b***ch, then there might be 4-5 words possible in the dictionary. Do this for all row, columns, and see which row/column has the lowest number of words in the dictionary matching that pattern. Now, lets say the lowest number of words matching a row/ column is 2 (bitch, batch), we fill this row/column with word 1. Now, we have reduced the problem size, and the same problem can be solved recursively. Once we are done with word1, we solve the sub problem again with word 2. and then with word 3 (if any, and so on). Keep on memoizing the intermediate results so that it an be looked upon later.
Its a DP problem.
@iyupku2000, yes you can just check either of birth time or death time. Both will give correct solution. The assumption is that, the duration when the maximum dinosaurs were alive, will correspond to [birth time of some dinosaur, death time of some other dinosaur]. So, if we check with birth time, or death time, we will get correct solution in both cases.
- Biru February 02, 2013I don't get this qn. Can you please clarify with an example? What I make out is, byte[] img is a 2D array whose width is 8 (8 bits). In this 2D array, we have to set x1->x2 in row r as 1. Right? If this is the case, then length and width are not required. My solution for this case would be -
void drawLine(byte[] img, int len, int wid, int r, int x1, int x2) {
byte[r] = 0; // let x1 = 3, x2 = 5;
byte[r] << (x2-x1+2); // byte[r] = 00001000
byte[r] = byte[r] - 1; // byte[r] = 00000111
byte[r] = byte[r] << (8-x2); //byte[r] = 00111000
}
There is a similar problem - Activity selection problem, which has start times and end times of n activities. We have to tell what is the maximum number of non-overlapping activities. A greedy solution to Activity selection problem exists.
This is similar to activity selection problem, so I assume a greedy solution exists. My soln is O(N^2), couldn't improve it.
Soln -
1. Just check for each death time or birth time, how many other dinosaurs were alive at that year only.
The assumption is, at least 1 death time or birth time will be present when the maximum number of dinosaurs were alive.
I think the only catch here is, the shifting of characters-
Str = [a][b][b][c]
Pass 1 - [0][c][b][c]. now shift to left -> [c][b][c]
Pass 2 - [0][a][c]. now shift to left -> [a][c]
Pass 3 - [0][b]. shift to left -> [b]
return number of chars in the string - 1
But, this is an inefficient way of doing, since it will take O(n^2) time (traversing and shifting, both n).
There is a way to prevent the shift thing -
1. first reverse the string
2. start from right
Str = [c][b][b][a]
Pass 1 - [c][b][c]
Pass 2 - [c][a]
Pass 3 - [b]
return the number of chars left - 1
If it's strictly not allowed to start from right in any instances, then just do this (without any shifts) -
Str = [a][b][b][c]
Pass 1 - [0][c][b][c]
Pass 2 - [0][0][a][c]
Pass 3 - [0][0][0][b]
return the number of non 0 chars - 1
There is 1 way of doing this - in-place count sort - en.wikipedia.org/wiki/In-Place_Count_Sort . But, the problem here is, in-place count sort won't work with duplicates. So, we will have to find an alternate way of in-place count sort. This is as follows -
Let's say N=10, numbers are (in each pass, we are swapping A[i] and A[A[i]], if A[i] and A[A[i]] are same, then A[i] = -1)
5, 6, 10, 8, 9, 5, 7, 6, 5, 10
Pass 1 - 9, 6, 10, 8, 5, 5, 7, 6, 5, 10
Pass 2 - 9, 5, 10, 8, 5, 6, 7, 6, 5, 10
Pass 3 - 9, 5, -1, 8, 5, 6, 7, 6, 5, 10
Pass 4 - 9, 5, -1, 6, 5, 6, 7, 8, 5, 10
Pass 5 - 9, 5, -1, 8, 5, 6, 7, 8, -1, 10
after this pass the values will be the same
Now, repeat the process once more, ignoring A[i] = -1 cases.
Pass 1 - -1, 5, -1, 8, 5, 6, 7, 8, 9, 10
Pass 1 - -1, -1, -1, 8, 5, 6, 7, 8, 9, 10
Pass 1 - -1, -1, -1, -1, 5, 6, 7, 8, 9, 10 (after this pass, the values will be same)
Now, the array will be sorted, with occasional -1 between elements. Now, apply the regular O(N) algorithm to find the sum as N, with slight modifications to skip -1 elements.
Or, -1 elements can be completely removed from the array in O(N) time, and then apply O(N) algorithm to find the sum as N.
So, the time complexity is O(N) and space complexity O(1).
@Abhi, since you don't know the size of the array, when you do A[2^k] might throw an exception. So, here is a better version, with LogN complexity -
1. Keep on looking for A[2^(K-1)] - A[2^K]. If A[2^K] throws an exception, then size of the array is 2^(K-1) to 2^K. Keep on looking from mid = (2^(K-1)+2^K)/2 to 2^K or 2^(K-1) to mid to find the first occurrence of 1. If A[2^K] is 1 and A[2^(K-1)] is 0, then let 2^K = max, 2^(K-1) = min.
2. When the first occurrence of 1 is found using the variation of Binary search above, let min be the index where we found 0, and max be the index where we found 1.
3. Perform a binary search for the string "01'. If the mid is "00", then take right half, and if mid is "11", take left half. Keep on taking halves until you find "01". mid + 1 index will be the solution.
This is better than the vector approach, since the length of array is not known.
It's a set problem. The algorithm is -
1. Create a set S1 as union of [min1, max1], [2*min1, 2*max1], [3*min1, 3*max1] ... note that after some point (LCM of min1, max1), the set would be - [LCM, +inf]. e.g. for min1 = 3, max1=4, the set would be - [3,4]U[6,8]U[9,12]U[12,+inf].
2. Create set S2, S3, etc as unions as in step 1 (replace min1, max1 with mini, maxi).
3. Just see if there is any overlap of [m,n] with S1, S2, S3. If there is overlap, return true, otherwise false.
4. An additional check can be added at the beginning if n < min1, min2, min3 then return false to reduce complexity.
Use BFS search with small modification - get the direction of search, i.e. if first cell is (5,5) and second cell is (10,10), then don't search all (5,4), (4,4), (4,5), (4,6), (5,6), (6,6), (6,5), (6,4). Rather search elements only in the direction like - (5,6), (6,6) (6,5). Then recurse for the elements in that direction.
If in a particular direction, you are not able to find the node, then change direction. This algo is sort of a mix of BFS and DFS (DFS giving direction)
Pseudocode for easier understanding -
public ArrayList<Integer> getVerticalSums(TreeNode root) {
if (root = null) {
lists.add(0);
return lists;
}
lists = getVerticalSums(root.left); // check if left != null
lists.addAll(getVerticalSums(root.right)); // check if right ! null
for (sum in lists) {
sum += root.data;
}
return lists;
}
Easiest way to do is count the number of numbers which will have 4s-
(all integer divisions)
diff = (n+6)/10 + ((n+60)/100)*9 + ((n+600)/1000)*81 + ((n+6000)/10000)*9^3 .......
number = n-diff
e.g. 3 -> 3 (diff = 0)
4 -> 3 (diff = 1)
5 -> 4 (diff = 1)
13 -> 12 (diff = 1)
15 -> 13 (diff = 2)
33 -> 30 (diff = 3)
35 -> 31 (diff = 4)
39 -> 35 (diff = 4)
50 -> 36 (diff = 5 + 9)
... and so on
This is the simplest solution I could think of.
Tell me how does it work for "Abcde", "Acdef".
All the if conditions will fail, and the control will come to
return check(s1.substring(1),s2.substring(1));
Which will return true (check("A", "A")), which I think is wrong. Correct me if I am wrong.
Also, the * implementation is buggy
Repmalloymirna65, Developer Advocate at 247quickbookshelp
I am Mirna Timekeeping clerks distribute and collect timesheets, timecards or work charts either as hard copies or electronically to ...
Repjasmineouzts765, Apple Phone Number available 24/7 for our Customers at 247quickbookshelp
JasmineOuzts and I am a web designer and freelance fashion blogger. I love writing about the latest trends in the ...
Repathenajbarnarda, Android Engineer at ABC TECH SUPPORT
I am a graduate in Civil Engineering with nearly 7 years of experience in planning and implementing technical solutions for ...
RepEllaScotz, abc at A9
I am a creative designer with innovative ideas and a unique approach to visuals. I am also a skilled painter ...
This can be achieved using post-order traversal -
- Biru January 22, 2014