CareerCup

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.

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;
}

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 non-decreasing subsequence. The statement says strictly increasing. A valid result for the example is 3, 4, 8, 9.

pA = 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.

Your 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.

If 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);

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;
}