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
I assume we should print number 1 as well. For large values, we should use a hash table and be careful with overflow in integers multiplication.
#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;
}

Miguel Oliveira
July 29, 2013 To deal with duplicates, you can use a hash table.
About the missing 4, it should be a mistake. 4 must be in the sequence (note that 8 is there)
Your code is finding the longest nondecreasing subsequence. The statement says strictly increasing. A valid result for the example is 3, 4, 8, 9.
 Miguel Oliveira July 29, 2013pA = 6 / 7;
pB = 4 / 5;
pC = missing in the statement.
We can pick (A,B), (A,C), (B,C), so answer = (pA*pB + pA*pC + pB * pC) / 3
The key here is to use a heap (aka priority queue). Start with number 1 and add it to the heap. Then, do a loop
a) Pop the minimum value from the heap
b) Print this minimum
c) Add minimum*2, *3, *5 and *7 to the heap
If we want N numbers, the complexity will be O(N log N).
Note that since i,j,k,l >=0, the first number should be 1, not 2.
Exactly. I'm pretty sure this is what the interviewer wanted to hear.
 Miguel Oliveira July 25, 2013Your code does not work if the array only have negative values. The answer is not 0, but the largest negative. Just a minor change needed.
 Miguel Oliveira July 25, 2013If the values on the array are reasonably small, use an array as a hashmap, otherwise use the unordered_map available in C++11 standard.
int v[], size; // input
int count[MAX_VAL], best, best_count = 0;
for (int i = 0 ; i < size; ++i)
if (++count[v[i]] > best_count) {
best_count = count[v[i]];
best = v[i];
}
printf("%d\n", best);
// Or
#include <unordered_map> // new C++11 standard
std::unordered_map<int,int> hash_map;
int v[], size; // input
for (int i = 0 ; i < size; ++i) {
int cnt = ++hash_map[v[i]]; // inserts if it does not exist
if (cnt > best_count) {
best_count = cnt;
best = v[i];
}
}
printf("%d\n", best);

Miguel Oliveira
July 25, 2013 map operations work in O(log n) so your algorithm works in O(n log n).
To make it O(n), use a hash map instead (now available in the new standard c++11 as unordered_map)
Apply dynamic programming. The game state can be described by the left and right endpoints. States are only valid where left <= right. For each possible state, find out how many points player A gets and B gets (when you change turn, you need the B value).
There are O(N^2) states with O(1) processing for each one (either pick left or right boxes), therefore the solution has a time complexity of O(N^2).
Hi,
First of all, congratulations!
About the question "2) Given a function isGreater, compare user defined objects and then return the object that is greater than all other objects.", can you do better than O(N^2)? Since there is no transitivity, I think we can't do something like sorting..
With just one egg, we have to throw it at the highest floor it doesn't break to be sure about it. So, we can't skip floors because if it breaks, we don't know anything about the floors we skipped.
I don't see how you can do better with just one egg. Maybe the interviewer wanted you to justify properly why you can't optimize it further.
The "find for each set bit its index" does not make much sense given this function declaration. A first approach could be
int find_set_bits(uint8 *from, int size) {
int result = 0;
for (int i = 0 ; i < size; i++) {
for (int j = 0; j < 8; j++) {
if (*from & (1<< j )) {
result++;
// save the indices?
}
}
from++;
}
return result;
}
For counting the number of set bits, we should use a lookup table. Again, this can be extended to get the indices, but it doesn't match the function declaration.
const int TABLE_SIZE = 1 << 8;
uint8 set_bits_table[TABLE_SIZE];
void preprocess() {
int i , j;
for (i = 0 ; i < TABLE_SIZE; i++) {
set_bits_table[i] = 0;
for (j = 0 ; j < 8 ; j++) {
if ( i & (1 << j )) {
set_bits_table[i]++;
}
}
}
}
int find_set_bits(uint8 *from, int size) {
int result = 0;
for (int i = 0 ; i < size; i++) {
result += set_bits_table[*from];
from++;
}
return result;
}

Miguel Oliveira
July 24, 2013
There are C(3,2) = 3 ways to pick 2 out of 3 people, disregarding order. Then, there's a 1/3 chance of picking one of those 3 cases.
 Miguel Oliveira July 29, 2013