CareerCup

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.

do you mean that the upper case letters remain unchanged or that they permute only among the positions of upper case letters?

Instead 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).

just 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

Yes. weird question to ask on careercup though..

you 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

ehsan, 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)

yes, this code was done like this to be easy to understand

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

Some 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

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

hashmap supposes (key,value) pairs. here we just need hash tables.

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

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

You are doing the same thing because node.next = newnode; is the same as sd's method to insert the new nodes into the list.

in this question, it seems safe to assume the time is given by the minute, otherwise the intervals would be defined in a different way

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

thanks for pointing it out

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

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

If you describe your application of MCM, you might get the votes up

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

(++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.

the "min(j, N + i - ei)" does it

you can just edit your first post

That makes it more difficult. Did you ask the limit on N, the number of bombs?

This 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

Bomb N-1 is neighbor to bomb 0?

The 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