Miguel Oliveira
BAN USER
I 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
do you mean that the upper case letters remain unchanged or that they permute only among the positions of upper case letters?
- Miguel Oliveira September 25, 2013Instead of checking all numbers between 45 and 4578, we can do a sort of N choose K approach. In this case, choose 2,3 or 4 digits out of the 10 digits.
bool used[10];
void Print(int cur_number) {
if (cur_number >= 45)
printf("%d\n", cur_number);
for (d = cur_number == 0; d < 10; d++) // if number is 0, we start at digit 1
if (!used[d]) {
new_number = cur_number * 10 + d;
if (new_number <= 4578) {
used[d] = true;
Print( new_number );
used[d] = false;
}
}
}
// call Print(0)
it's on CtCI book and repeated many times
careercup.com/question?id=10442525 (switch 0 to 1)
careercup.com/question?id=302724
etc
It's possible to do it in O(n^2) time and O(1) extra memory.
explanation: book errata page 182, ex 1.7
docs.google.com/spreadsheet/pub?hl=en_US&hl=en_US&key=0AuwEKO7o6mrAdFdhZHRlN1JUc3dEVFRNMDJzWlE1VXc&output=html
code: github.com/gaylemcd/ctci/blob/master/java/Chapter%201/Question1_7/Question.java
this is not correct. detonating a bomb j does not detonates the bombs within its range (and so on recursively), it just destroys them which is different (we're not able to get their value).
- Miguel Oliveira September 24, 2013just add
sb.append(count);
sb.append(s.charAt(i-1));
after the cycle
C++ solution using the STL's output string stream class. You didn't specify what to do when there is a single letter. I think the common way is to make it "1a" (it gets bigger).
string Compress(const string& s) {
ostringstream oss;
for (size_t j, i = 0; i < s.size(); i = j) {
for (j = i+1; j < s.size() && s[j]==s[i]; j++)
; // all the work is done in the previous line
oss << j-i << s[i]; // add the count and letter
}
return oss.str(); // return the string representation
}
it does not work if the count is larger than 9
- Miguel Oliveira September 24, 2013Yes. weird question to ask on careercup though..
- Miguel Oliveira September 23, 2013you can take advantage of default values and write it like this
for(int i =0; i < size; i++) {
cnt = ++m[a[i]];
if(cnt > NoOfOccurences) {
MajorityElement = a[i];
NoOfOccurences = cnt;
}
}
likewise with a hash map
- Miguel Oliveira September 23, 2013ehsan, you still denote the complexity as O(n+m). m is at most n^2, but the preferred big-O notation remains O(n+m) because it is a tighter bound than O(n^2)
- Miguel Oliveira September 22, 2013yes, this code was done like this to be easy to understand
- Miguel Oliveira September 22, 2013As discussed in other posts, this kind of approach does not seem to work. You lose information about the circle part. few cases where you solution fails (you can use my semi-brute force given above to find more):
v: 6 8 3
r: 7 3 1
Answer is 8, your code gives 9
v: 1 4 3
r: 9 0 3
Answer is 7, your code gives 5
v: 7 2 3 4 10 4 5 5 3 8
r: 5 5 2 6 6 1 2 4 3 3
Answer is 18, your code gives 19
No, you just need some patience. There are lots of reasons that may delay the process, I recommend you apply to other companies as well while you wait for some replies you'll continue the process with the others.
- Miguel Oliveira September 20, 2013Some of the previous solutions are wrong as discussed in the comments. Since the order matters, I'm not seeing a very efficient (polynomial) solution.
However, we can still use dynamic programming. We can pick bombs step by step, marking the bombs that we already used. Before we pick a bomb, we need to check if any of the previous chosen bombs affects it. We can use bitmasks with bit i set to 1 if we already picked bomb i, 0 otherwise.
This leads to 2^N possible states.
int N, v[22], r[22], dp[ 1 << 22 ]; // init dp to -1 == not done
bool Contains(int mask, int i) { return mask & (1 << i); }
bool Conflicts(int i, int j) { // j affects i
return (abs(i-j) <= r[j] || abs(i+N-j) <= r[j] || abs(j+N-i) <= r[j]);
}
int Go(int used_mask) {
if (dp[used_mask] != -1) // already done before?
return dp[used_mask];
dp[used_mask] = 0;
for (int i = 0; i < N; i++)
if ( ! Contains(used_mask, i) ) {
bool ok = true;
for (int j = 0 ; j < N ; j++)
if (Contains(used_mask, j) && Conflicts(i,j)) {
ok = false;
break;
}
if (ok)
dp[used_mask] = max( dp[used_mask], v[i] + Go(used_mask | (1<<i)));
}
return dp[used_mask];
}
int main() {
int i;
scanf("%d", &N);
for (i = 0 ; i < N ; i++)
scanf("%d %d", &r[i], &v[i]);
memset(dp, -1, sizeof dp);
printf("%d\n", Go(0));
return 0;
}
This takes O(2^N * N^2) time and O(2^N) memory. It's ok for N up to 20~22.
To make it O(2^N * N) we can just use hashing instead of the nested loops. But it does not make a big difference here.
sorry, the order does matter. i misunderstood the problem
- Miguel Oliveira September 20, 2013I had assumed that we had to pick a set of "non-overlapping" bombs, like if they were detonated at the same time.
That was the most natural "dynamic programming" way for me to solve this question.
In this case, the above python solution does not work. I don't have an efficient solution for this, i'll think about it :)
Breadth first search + hashing the visited states.
- Miguel Oliveira September 19, 2013hashmap supposes (key,value) pairs. here we just need hash tables.
- Miguel Oliveira September 19, 2013Yes. We can apply Binary Search only in a monotonic function (increasing, decreasing, non-increasing or non-decreasing function).
We're applying Binary Search to the function F(x) = x^2. This function is strictly increasing (for x >= 0), so we know that for any 3 values A, B, C, with A < B < C, F(A) < F(B) < F(C)
So if F(mid) is larger than the number, we need to go for values less then mid. Go for larger values otherwise.
To do both operations efficiently, I would go for a Binary Indexed Tree (also known as Fenwick Tree). This supports operations 1 and 2 in O(log N) time, O(N) space.
int tree[MAX], N; // indices 1..N
void Update(int x, int value) {
for (; x <= N; x += (x & -x))
tree[x] += val;
}
void GetSum(int x) {
int sum = 0;
for (; x > 0; x -= (x & -x))
sum += tree[x];
return sum;
}
Check community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
- Miguel Oliveira September 18, 2013when a bomb explodes, is the circle readjusted? I don't see anything pointing to that in the question but someone asked it and now that i checked the example it seems the order to explode the bombs matter.
If that's the case, then the problem is even much harder and the DP[i][j] solution above does not work.
If you are refering to the one that sorts intervals, order O(n log n) is not better than O(n) like this one.
- Miguel Oliveira September 18, 2013You are doing the same thing because node.next = newnode; is the same as sd's method to insert the new nodes into the list.
- Miguel Oliveira September 18, 2013in this question, it seems safe to assume the time is given by the minute, otherwise the intervals would be defined in a different way
- Miguel Oliveira September 18, 2013There are only 6h = 360 minutes to consider. We can just mark the arrivals and departures in 2 arrays. Checking how many glasses are needed during arrivals and releasing glasses in departures.
The time complexity is O(N) for marking the arrivals and departures.
int MinGlasses(int* guest_arrival, int* guest_departure, int n) {
int arrivals[600], departures[600], i;
for (i = 0 ; i < 600; i++)
arrivals[i] = departures[i] = 0;
for (i = 0 ; i < n ; i++) { // format the time into the interval [0, 559]
arrivals[guest_arrival[i] - 1800]++;//we could format into an interval
departures[guest_departure[i] - 1800]++; // [0, 359] to save space
}
int res = 0, available_glasses = 0;
for (i = 0 ; i <= 559; i++) {
available_glasses += departures[i];
if (arrivals[i] > available_glasses) {
res += arrivals[i] - available_glasses;
available_glasses = 0;
} else
available_glasses -= arrivals[i];
}
return res;
}
@karaamaati no, it's not. Bomb 2 affects bomb 6, so we can't take both. Bomb 4 affects bomb 5, so we can't take both as well.
- Miguel Oliveira September 17, 2013thanks for pointing it out
- Miguel Oliveira September 16, 2013We can use dynamic programming for a O(N) solution with extra O(N) space.
We must have Buy - Sell - Buy - Sell in this order and they are disjoint. So, there is a time in the given day we can split the first transaction (Buy - Sell) to the left and the second transaction to the right.
Thus, my approach would be to create an array best_right[i] which contains the best profit we can make with a transaction using the prices i..N-1 (0-indexed). To do this, we process the prices from right to left, keeping the maximum price seen so far. Then, we compare the profit made by buying at time i and selling with that maximum.
After this, do something similar from left to right to find the profit from the left part.
int FindProfit(int * prices, int n) {
int* best_right = new int[n];
int i, max_price = prices[n-1];
best_right[n-1] = 0;
for (i = n-2; i >= 0 ; i--) {
best_right[i] = max(max_price - prices[i], best_right[i+1]);
max_price = max(max_price, prices[i]);
}
int min_price = prices[0], result = 0;
for (i = 1; i+1 < n ; i++) { // i'm assuming we'll always do 2 transactions
result = max(result, prices[i] - min_price + best_right[i+1]);
min_price = min(min_price, prices[i]);
}
return result;
}
The alphabet size is usually considered a constant.
Since you want Theta(n) with constant space, you can loop through all characters of the alphabet and count the number of occurrences in each string. The running time is Theta(n*alphabet_size) = Theta(n), under the above assumption, and this uses constant space.
For example:
v = { 1, 3, 1, 1, 1, 1 }
r = { 1, 2, 1, 1, 0, 0 }
The best is 4 by taking the 2nd and 5th bombs with value 3 and 1 (it affects the last bomb, so we can't add that one). However, following your description,
d = { 1, 3, 3, 3, 4, 5 } because for the last bomb, you have no way to check that that value 4 actually includes a bomb that affects the last bomb.
I would implement an Abstract class which will contain those changes made to B.
Then, both A and B extend this abstract class.
I see the observer design pattern related to information exchanged in runtime.
This seems to be about attributes of classes before compile time.
Let M = K*N be the total amount of numbers.
Your algorithm runs in O(M * K), while the heap version runs in O( M * log K ).
Note that your "for(int i = 0; done == 0; i++)" cycle runs M times, not N. And then you have a nested cycle search in each of the K arrays.
Your step 1 runs in O(k). Using a heap allows to speed it up to O(log k) that's the reason.
- Miguel Oliveira September 15, 2013I would use Ternary Search to find the pivot and then a normal Binary Search, knowing the pivot. The time complexity is O(log n) if the values are distinct
int FindPivot(int v[], int size) { // ternary search to find the pivot
int left = 0, right = size-1;
while (left+1 < right) {
int c1 = (left*2 + right) / 3;
int c2 = (left + right*2) / 3;
if (v[c1] < v[c2])
right = c2;
else
left = c1;
}
if (left < right)
return v[left] < v[right] ? left : right;
return left;
}
int SearchRot(int v[], int size, int number) {
int left = 0, right = size-1, mid;
int pivot = FindPivot(v, size);
while (left <= right) {
mid = (left + right) / 2;
int pos = (mid + pivot) % size;
if (v[pos] == number)
return pos;
else if (v[pos] < number)
left = mid+1;
else
right = mid-1;
}
return -1;
}
"set of integers with repeated occurences of elements" this is mathematically incorrect. A set does not have repeated elements. A Multiset does.
Anyway, we can shrink the input in pairs: (number, n_occurrences) and generate the power set with a recursive function. Sample code in C++:
void PowerSet(int i, const vector<pair<int,int> >& vo, vector<int>& cur) {
if (i == vo.size()) {
if (cur.size() == 0)
cout << "NULL" << endl;
else {
for (size_t i = 0; i < cur.size(); i++)
cout << cur[i] << " ";
cout << endl;
}
} else {
size_t cur_size = cur.size();
PowerSet(i+1, vo, cur); // don't use any of these numbers
for (size_t k = 1; k <= vo[i].second; k++) {
cur.push_back(vo[i].first); // use this number k times
PowerSet(i+1, vo, cur);
}
cur.resize(cur_size); // get cur vector to previous size
}
}
void PowerSet(int v[], int n) {
sort(v, v+n);
vector<pair<int,int> > voccur;
for (int i = 0; i < n ; i++) {
int num = 1;
for (; i+1 < n && v[i] == v[i+1]; i++)
num++;
voccur.push_back(make_pair(v[i], num));
}
vector<int> cur_set;
PowerSet(0, voccur, cur_set);
}
An easy and reasonably fast approach is to use binary search to the required precision
const double EPS = 0.0001;
double sqrt(double number) {
double left = 0.0, right = max(1, number), mid;
while (left + EPS < right) {
mid = (left + right) / 2.0;
if (mid * mid > number)
right = mid;
else
left = mid;
}
return left;
}
I know there is a method to find the square root by hand but I don't know the details. That method might be more efficient, but I think binary search is probably the intended answer in an interview.
- Miguel Oliveira September 14, 2013If you describe your application of MCM, you might get the votes up
- Miguel Oliveira September 14, 2013+1
very creative!
After copying the list based on the next pointer, when you try to copy the random pointers, you don't know that is the correct element pointer by the random pointer in the cloned list.
- Miguel Oliveira September 14, 2013(++i) = x;
compiles fine with g++ 4.2.1 on mac os
See the python solution posted above. Besides "i" you also need an "up_to_j" variable because positions j+1..N-1 were affected before.
- Miguel Oliveira September 13, 2013the "min(j, N + i - ei)" does it
- Miguel Oliveira September 13, 2013you can just edit your first post
- Miguel Oliveira September 13, 2013That makes it more difficult. Did you ask the limit on N, the number of bombs?
- Miguel Oliveira September 13, 2013This does not work because the array is circular, meaning that when you consider position N-1 you must not take into account positions 0..r[N-1] because they are neighbors
- Miguel Oliveira September 13, 2013Bomb N-1 is neighbor to bomb 0?
- Miguel Oliveira September 13, 2013The question asks if "Amazon" is present in the filename. So we need to check if there is a substring "Amazon" anywhere in the name. If the name has length N, this will take O(N), not O(1)
Total complexity is O(number_files * filename_length + number_folders)
This won't work. Simple counter-example:
1110
0000
0010
0010
no, you don't. you can just use the first row and column of the matrix. O(1) extra space. You have the code in the link given above. It has 2 solutions i think, one of them is this one.
- Miguel Oliveira September 25, 2013