vishalsahunitt
BAN USERWe can perform lookup in right and bottom direction from each mat[x][y]. To check number of '+' we have at top and left, we can use the memoized results from 2D matrix of pair<int, int>.
- vishalsahunitt November 21, 2016I have simple solution of bucket filling where we take array of size k+1. For interval I[si, ei], we do following:
for (int i = si; i <= ei; i++)
arr[i]++;
But this solution takes O(nk). Please let me know if O(n + k) algorithm is found.
- vishalsahunitt November 21, 2016This problem seems simplified version of finding minimum distance between those 2 words. Here since we need to find distance between first occurrences, just start from start of book and maintain idx = -1. If we encounter any of word, store it's index and look for next word.
// convert book into list of words
int idx = -1;
for (int i = 0; i < list.size(); i++) {
if (list[i] == w1 || list[i] == w2) {
if (idx != -1) {
if (list[i] != list[idx])
return i - idx;
}
else
idx = i;
}
}
return -1; // no pair found
This is classic example of QuickSelect algorithm.
- vishalsahunitt November 14, 2016This problem is trap. If you perform binary search for n and once found, going in left and right direction till we see n results in worst case O(n) time (when entire array is filled with n). We don't want that, however arriving it this way is normal and interviewer will ask if there is better way.
Lets denote array indexes as L and R. Once found at mid, we should continue binary searches for start index of n. Once found, say s then we look for index of last n using binary search once more.
Maintain a sorted array while traversing elements from right to left. Find what index the new element will be inserted at using binary search. Number of elements right to it is prepended into answer. The overall space complexity: O(n), time: O(nlogn).
- vishalsahunitt November 08, 2016Just maintain vector<pair<char, bool>> and map<char, int>.
char firstChar(string s) {
vector<pair<char, bool> > v;
map<char, int> m;
for (size_t i = 0; i < s.length(); i++) {
if (m.find(s[i]) != m.end())
v[m[s[i]]].second = false;
else {
m[s[i]] = v.size();
v.push_back({s[i], true});
}
}
for (auto p : v) {
if (p.second)
return p.first;
}
return '#';
}
One approach is to sort the intervals as per start time and then count the duration of all intervals(after considering overlaps). This is O(nlogn). Another approach is to take an bool array of size equal to max time and mark it on/off. This is O(n) time O(n) space approach.
- vishalsahunitt October 29, 2016Question seems incomplete. Are you asking for all possible(over-lapping) sub-arrays of size k? And minimum of what? Do we need to sum them? or min element in them?
- vishalsahunitt October 12, 2016This is 0-1 knapsack problem where the thief wants to steal maximum number of items. Max given is sack limit and the word lengths are items weight here.
for j from 1 to max:
for all i if array[i] < j:
sol[j] = max(sol[j], 1 + sol[j - array[i]])
return sol[max]
Resource allocation algorithm is used to detect the deadlock in given scenario. In your case since there is no cyclic dependency among p1, p2, p2 & r1, r2, r2, r3, the current scenario is deadlock free.
However, if p3 blocks on r2 before anyone else releases some resource, the system will deadlock.
The simple approach to maximize number of L length wooden logs would be to start with all logs, in increasing order of length, whose length is of form k*L where k > 1. For e.g., Say logs are of length 2,3,3,4,6,8,14,16 and L = 2 & S = 8 then we would start with 4,6,8,14,16 and will get 11 pieces of length 2 using 8 cuts.
- vishalsahunitt March 28, 2016Does rotate by 1 place solve it?
- vishalsahunitt March 28, 2016Inner loop should run from j = i +1 to length. Why would you want to look elements before ith element again. If they were similar, they would've been caught earlier itself. Also if array modification is allowed, delete subsequent matches if found one.
- vishalsahunitt January 27, 2016first & last element of given sequence are always part of it. perform 3 subtractions: 1-2, 2-3 & 3-4 and the majority is your difference. Finally Start traversing from beginning checking difference against the computed one. O(n)
- vishalsahunitt January 27, 2016M can reach to S either in atmost 2 steps or may never reach. Latter occurs when they are on diff colors. In first case, it can reach to S directly or may take first step to get on line diagonal to S.
- vishalsahunitt January 27, 2016search for these glitches (unordered elements in nearly sorted array) and insert them at appropriate place(insertion sort on few elements)
- vishalsahunitt January 25, 2016
The enemies don't have money, they've price. You can either fight with them at cost of your strength or buy their strength. For recursion suggested by chrisM,
But I am not clear how comparison happens for max. There are 2 quantities: power and money and how to decide what is optimal: ending war with more power or money?
- vishalsahunitt November 22, 2016