Miguel Oliveira
BAN USERI enjoy algorithms, puzzles and programming competitions :)
- 1 Answer Interview "red flags"
Hi,
- Miguel Oliveira September 09, 2013
In the beginning of CtCI book, Gayle talks about the case of a student which she referred but had too many "red flags".
Could you elaborate more on the "red flags"? Maybe with a few more examples of these kind of mistakes that we should avoid in an interview?| Flag | PURGE
The problem is that LCS works in O(N^2) so it will be too slow with those limits. There should be another solution taking advantage of k.
- Miguel Oliveira August 28, 2013I think the LCS method works. Annonymous, can you give a counter-example?
- Miguel Oliveira August 28, 2013You want a number smaller than the one given. So "src[i]<=given_num" is incorrect, should be "src[i]<given_num".
For 1 query, you can't do better than that in the worst case. However, if there are many many queries, think about optimizing the CountOnes part. There are many interview questions about that.
We need to find the highest card which has higher cards before it.
[3, 4, 2, 1, 5] -> 2 is the highest misplaced card (3,4,5 are in the right order)
[1, 2, 4, 5, 3] -> 3 (has 4 and 5 before it)
Finding this card can be done in O(n): traverse the array from left to right and keep the highest card seen so far. If the current card is smaller than the highest seen so far, then it is misplaced.
Afterwards, we need to place this card correctly. To do so, we need to put it on top of all cards. Hence, all cards smaller than this card will be misplaced as well.
So we need to put all cards smaller of equal to the highest misplaced card on top of the pile. Do this in decreasing order and we are done. The number of moves is equal to the highest misplaced card.
[3, 4, 2, 1, 5] -> 2. Move 2 = [2,3,4,1,5]. Move 1 = [1,2,3,4,5]
[1, 2, 4, 5, 3] -> 3. Move 3 = [3,1,2,4,5]. Move 2 = [2,3,1,4,5]. Move 1 = [1,2,3,4,5]
rephrase in readable english? :/
- Miguel Oliveira August 26, 2013I see 2 possibilities:
a) (most likely) It was their way of rejecting you without interview feedback. Companies don't usually provide proper feedback.
b) Your performance in the interviews was similar to another candidate which had more experience than you. Hence, they picked the other candidate.
Yes, it's 665, i prefer to put it as 26*25^4. My code also gives 665, I made a mistake putting the 142.
i edited the post
@MrA, I was talking about king's 4th point which refers O(n) *additional* memory. Your "k" is the additional part, same as my O(range).
- Miguel Oliveira August 17, 2013the insertion will take O(log m) per element, so the time complexity will be O(m log m) which is worse than (k*n log k)
- Miguel Oliveira August 14, 2013Alex, lets say we have only one slot: M = 1. The values are always hashed in the same slot. So, we have only 2 possible results: probability = 1 if i = N and 0 otherwise.
N = i, leads to (1-1/M)^(N-i) = 0^0 = 1 by convention
N != i leads to 0
the formula gives the expected values
Exactly, you can't beat O(N^2) in the worst case.
- Miguel Oliveira August 13, 2013PC, the problem statement says clearly "continuous subsequences"
- Miguel Oliveira August 13, 2013implement multiplication and division like we learnt in primary school. it's the same, you just use carries of mod 26, instead of mod 10.
- Miguel Oliveira August 09, 2013I've seen the problem before where only 1 number was missing and the solution is trivial.
The solution using 2 equations makes sense to me but what if the interviewer asks "why does that (using 2 equations) work?". for 3 missing numbers we would need 3 equations.. how do we prove this will work in general?
Convert from base 26 to base 10 -> multiply/divide -> convert result to base 26 seems the easiest option.
- Miguel Oliveira August 08, 2013yes, Helo are the only distinct characters in the string and they appear in that order.
- Miguel Oliveira August 08, 2013N = 1000, answer = 385875
N = 2000, answer = 7077888
N = 3000, answer = 50176000
N = 4000, answer = 228614400
This is clearly an exponential growth..
you're mixing 2 different Ns: the n-th number we want and the magnitude (say M) of this number. While the above approaches state the time complexity in terms of "n". Your algorithm is O(M)
- Miguel Oliveira August 07, 2013A greedy like this does not work. Simple counter-example:
arr[] = {2,5,0,0,0};
Answer is 2, this code says "no jumps are there". You need to check all N positions to jump, not just the furthest away at each step.
We start at position 0.
[1 5 4 6 9 3 0 0 1 3]
1) Jump to position 1 (v[1] = 5)
2) Jump to position 4 (v[4] = 9)
3) Now we're able to jump to position 9 and finish.
[2 8 3 6 9 3 0 0 1 3]
1) Jump to position 1 (8)
2) Now we're able to jump to position 9 and finish.
I prefer to approach this kind of problems backwards - from the end to the beginning.
We can use DP with N states. dp[i] means the minimum amount jumps to go from position i to the end of the array (position N).
A BFS is also perfectly fine here. The time complexity of both algorithms will be the same - O(N * Max_Jump).
// I will assume there is always a valid solution
int minJumps(int jumps[], int n) {
vector<int> dp(n+1, n*2);// n*2=infinity: n*2 is more than any valid solution
dp[n] = 0;
for (int i = n-1; i >= 0; i--)
for (int j = 1; j <= jumps[i] && i+j <= n; j++)
dp[i] = min(dp[i] , 1 + dp[i+j]);
return dp[0];
}
I believe we need to reach position "n", meaning jump through all the array.
- Miguel Oliveira August 05, 2013You can delete a char in the middle, and the search would have to use like "s" + "at" after deleting a 't' in "stat". So I don't think this approach works.
- Miguel Oliveira August 04, 2013That preprocessing is not O(M^2) but O(M^2 * L^2) because you're testing all pairs of words and to check if one word is only missing 1 letter from the other takes O(L^2).
This can be reduced to O(M * L^2) using a hash table. For every word, check all possibilities to remove 1 letter and check if the resulting string appears in the dictionary (using the hash table). Checking all possibilities takes O(L^2) for all M words.
You can check codes in other posts. It's not really DP but rather mark what you already computed (a bit different because if you already computed a state (i,j) it means it failed).
So it's really about not using strings for recursion but the indices i (text) and j (pattern) currently to start from
As I told you on the other question, this code is incorrect. Examples:
Answer to "ccc" is 291, your code gives 294
Answer to "ddd" is 941, your code gives 944
Answer to "abbc" is 25, your code gives 26
Answer to "zzzzz" is 665, your code gives 796
Yes, the reply was for you, my bad.
The point is that the matching between the blocks in the pattern without '*' and the given text is not easily done in O(N), but it's possible of course.
Example: "aaabaaaabaabaaaaaabacacacaacc" and "*aaaaab*aac*". To match the subblocks "aaaaab" and "aac" you'll need a sort of needle in a haystack algorithm like KMP or Aho-Corasick to keep it O(N) and not O(N*P), thus contradicting the "simply" and "greedily" in "We can simply match this greedily,"
Regular Expression matchers work in linear time. Since this problem uses simple RE, there is also a linear time solution. However, these algorithms are complex. I don't think any interviewer is expecting a candidate to be able to code this in an interview.
I don't think that simple approach works. Consider this example
s: "abcabdcd"
p: "ab*d"
you'll greedily match the 'd' in the pattern with the first 'd' in the string, which is incorrect. even if you make a quick fix for this case, i think it still won't work in more complex cases where '*' shall skip several characters (not necessarily the first match)
A few test cases:
Answer to "ccc" is 291, your code gives 294
Answer to "ddd" is 941, your code gives 944
Answer to "abbc" is 25, your code gives 26
Answer to "zzzzz" is 665, your code gives 796
please rephrase the question. that english is not clear at all
- Miguel Oliveira August 01, 2013This is wrong. For example, for "bbb" your code returns 1 and the answer is 650 (a[a-z][a-z])
- Miguel Oliveira August 01, 2013"A string is called sstring if it consists of lowercase english letters and no two of its consecutive characters are the same."
- Miguel Oliveira July 31, 2013I suppose that no interviewer is expecting a truly efficient regular expression matcher. One improvement to your approach is to mark the states we already processed. The search state can be described by the position i in the search string and position j in the pattern string from which we are trying to find the matching.
This leads to a O(|S| * |P|) algorithm.
const int MAXS = 1000, MAXP = 100;
string s, p; // text, pattern
int slen, plen;
char visited[MAXS][MAXP];
char go(int i, int j) {
if (visited[i][j]) // already processed this pair (i,j)
return visited[i][j];
if (i == slen) {
// we reached the end of the text, remaining chars of the pattern must be '*'
for ( ; j < plen; j++)
if (p[j] != '*')
return visited[i][j] = -1;
return visited[i][j] = 1;
}
if (j == plen) // end of the pattern but there are still chars in S
return visited[i][j] = -1;
if (p[j] != '*') {
if (p[j] != '?' && p[j] != s[i])
return visited[i][j] = -1;
return visited[i][j] = go(i+1, j+1);
}
// '*' can consume any number of characters
if ( (go(k, j+1) == 1) || (go(k+1, j) == 1) )
return visited[i][j] = 1;
return visited[i][j] = -1;
}
int main() {
getline(cin, s);
getline(cin, p);
slen = s.size(), plen = p.size();
cout << (go(0,0) == 1) << endl;
return 0;
}
Yes that would guarantee O(n log n), but I don't think it's possible to pick the median in O(1) throughout the algorithm without some special knowledge about the input.
- Miguel Oliveira July 31, 2013it's a heap (priority queue), not a queue. The heap will get the minimum value, not the FIFO order
- Miguel Oliveira July 30, 2013what is the size limit on the strings that we're given?
- Miguel Oliveira July 30, 2013This is incorrect. It fails with 22 for example - it is divisible by 2 but we can't get it through 2^i * 3^j * 5^k * 7^l
This question is about factorization strictly by 2, 3, 5 *and* 7.
those 4 letters i,j,k and l mean that the exponents don't need to have the same value
2 = 2^1 * 3^0 * 5^0 * 7^0
3 = 2^0 * 3^1 * 5^0 * 7^0
4 = 2^2 * 3^0 * 5^0 * 7^0
etc
Rohit made some mistakes, 1 and 4 are missing from the sequence
Quick sort has a worst-case running time of O(n^2), no matter how good your partition function is (unless the number distribution is known in advance). Good partition functions can decrease the probability of hitting O(n^2) on a random input.
- Miguel Oliveira July 30, 2013exponents >= 0, not >= 1
- Miguel Oliveira July 30, 2013Did you test this? This doesn't even answer the sample "bcd" -> 653, your code gives 731
- Miguel Oliveira July 30, 2013~ operator is, by definition, the operator to negate all bits, so it's the most appropriate answer.
FFFF is 16 bits, Xor with 0xFFFFFFFF would work
1) I don't think a k-way merge sort has O(n log n) like a traditional one.
4) Not O(n) space but O(range), where range is 50 000 000 - 50 000
We should ask how many values are in the array. If we have millions of elements, counting sort is the way to go since the range fits easily in memory. Otherwise, I would pick quick sort.
- Miguel Oliveira July 30, 2013We don't need to use only the letters of the input string. The problem asks for *all* sstrings lexicographically smaller or equal than the input. Example "aba" or "abc" are 2 of 653 sstrings smaller or equal than "bcd"
- Miguel Oliveira July 30, 2013The explanation is correct but the probability is 0.6%, so 0.006, not 0.6
- Miguel Oliveira July 29, 2013First, we need to realize that the number of sstrings of size N is 25^N - at each step, we can pick any of the 25 different letters than the last one.
Then we can apply dynamic programming knowing the current index and the previous letter used.
Say we have "bcd". Pick 'a' for the first letter - since it's smaller than the first letter 'b', we sum the number of sstrings of size 2 (2 remaining characters). Do this for all letters less than the given letter at index i because all subsequent strings are lexicographically smaller.
After this step, add the number of sstrings with the same first 'i' letters as the given string.
const int MAX = 102, MOD = 1009;
int dp[MAX][27], len, sstrings[MAX];
char str[MAX];
int solve(int i, int prev) {
if (i == len)
return dp[i][prev] = 1;
if (dp[i][prev] == -1) {
dp[i][prev] = 0;
for (int c = 'a'; c < (int)str[i]; c++)
if (c-'a' != prev)
dp[i][prev] += sstrings[len-i-1];
if (prev != str[i]-'a')
dp[i][prev] += solve(i+1, str[i]-'a');
dp[i][prev] %= MOD;
}
return dp[i][prev];
}
int main() {
scanf("%s", str);
len = strlen(str);
sstrings[0] = 1;
for (int i = 1; i <= len; i++) // sstrings[i] = 25^i % MOD
sstrings[i] = (sstrings[i-1] * 25) % MOD;
memset(dp, -1, sizeof dp); // -1 meaning not calculated yet
printf("%d\n", solve(0, 26)); // 26 is a non-existing letter before the start
return 0;
}
Although this solution is easier to understand, vgeek's solution is O(N), thus better than this one.
- Miguel Oliveira July 29, 2013Why 4^N? It's O(N), this is a sample implementation for small values. Note that we ignore repeated values and we could also ignore values to the heap when we already have N values in the heap.
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int primes[] = {2, 3, 5, 7};
char seen[1000000]; // for large values, use a hash table instead
int main() {
int N, i, j, next, minimum;
cin >> N;
priority_queue<int, vector<int>, greater<int> > heap;
heap.push(1);
for (i = 0; i < N; i++) {
minimum = heap.top();
heap.pop();
cout << minimum << endl;
for (j = 0; j < 4; j++) {
next = minimum * primes[j]; // careful with overflow
if (!seen[next]) { // for large values
seen[next] = 1;
heap.push(next);
}
}
}
return 0;
}
The question asks if we can transform the given string S into its reverse deleting at most K letters.
We could modify the traditional Edit-Distance algorithm, considering only deletions, and check if this edit distance is <= K. There is a problem though. S can have length = 20,000 and the Edit-Distance algorithm takes O(N^2). Which is too slow.
(From here on, I'll assume you're familiar with the Edit-Distance algorithm and its DP matrix)
However, we can take advantage of K. We are only interested *if* manage to delete K letters. This means that any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions.
Since we are comparing the string with its reverse, we will do at most K deletions and K insertions (to make them equal). Thus, we need to check if the ModifiedEditDistance is <= 2*K
Here's the code:
We only process 2*K+1 columns per row. So this algorithm works in O(N*K) which is fast enough.
- Miguel Oliveira August 29, 2013