CareerCup

@aniket: What's n? There's no n anywhere in this problem. If you allocated an array of some size n through malloc and assigned the address of the start of this array to one of these pointers, the memory for the array would be on the heap and not on the stack, and it would still be the case that only the pointer would be on the stack. The answer as to the amount of on-stack memory used would still be what I said.

I think a good answer is sizeof (int*) + sizeof (char*), provided those declarations are not optimized away.

Neither of those is correct. Quite simply, if you allocated using new, you must de-allocate with delete. If it was new[], then use delete[]. If it was malloc, use free. No other combination of those operators is correct.

Use the rank algorithm. O(N) expected time.

F(1) = 1
F(2) = 2
F(3) = 4
F(n) = F(n-1) + F(n-2) + F(n-3)

It's not even so much a merge sort as just one pass of the merge sort. A simple merge operation.

Is the question supposed to be in O(log(K)) time with an assumption that all integers in the array are unique?

good one

Add the items to a set as you go and check to see if each item is already in the set. Every time you find a new item that isn't in the set, do array[numItemsFound] = array[currentIndex]; numItemsFound++; Complexity is O(n) and needs O(n) extra space. If you can't use extra space, an in-place sort might be the best bet, giving you O(n log n) or O(kn) if you use radix sort. If you can't use extra space AND you also can't re-order the original array, you're probably stuck checking every element with every element, O(n^2)

Do you know if there's a way to do it in a plane?

Some languages (I'm gathering this was probably a C++ question) also have functions that are non-virtual, in which case they wouldn't be included in the vtable.

If this is a multithreaded application, I would think it's a race condition. printf can be a little slow at times, so maybe the printf is changing the relative timing of the threads in a multithreaded application.

These types of bugs can be fiendish to track down. I would start by considering the thread that was delayed by the execution of the printf: are there variables that come after the printf, in particular pointers, that are set to a value by a different thread? If so, it's possible that the printf delays its thread enough that other threads are able to do their jobs and initialize variables appropriately, but when the printf is taken away, some of those pointers are dereferenced before other threads can initialize them. A segfault can easily be caused by dereferencing uninitialized pointers.

The best way to stop these bugs is by very careful design of synchronization from the get-go.

-1: Lack of clarity. How would the single for loop statement result in an infinite loop, and not result in this when the printf is applied? What exactly do you mean? Also, I take it that "crashing" is not "looping forever".

The third solution is particularly good.

By the way, using an extra on-stack variable is not using "extra space" because it wouldn't be possible to solve the problem if it were. When you do something like
System.out.println(n/((int)Math.pow(10, (int)Math.log10(Math.abs(n)))));
n= Math.abs( n%((int)Math.pow(10, (int)Math.log10(Math.abs(n)))) );

some of those intermediate values could be saved to the stack anyway.

Don't use Math.pow. It's likely to be slow because it's intended for doubles, and might possibly have weird associated roundoff errors (not saying it necessarily will in this case). I would recommend doing a loop to see what the greatest power of 10 less than n is, assigning it to a variable m, and then doing print (n / m) % 10; m = m / 10; in a loop until m drops to 0

I would think that there are other marks that can set off a sentence, such as ? and !. Also, not every . delimits a sentence, so perhaps I would ask my interviewer about that.

ex. So...what are you doing today?

Define "single instruction". If it means 1 assembly instruction, that's only possible if value's already in a register and either we know m and n at compile time so we can prepare the appropriate bitmask, or if a special "bit range extraction" instruction exists.

Oh yeah? How about -2^63, -2^63, 0? The "sum" of their absolute values (taking overflow into account) is 0.

No, it won't. Why would it? The sum could overflow.

Choose a random 64-bit integer. Scan through the list to check it's unused. With very, very small probability, you will need to go for a second choice of number (again random), or third, etc. Expected runtime is still O(n). Since the list is unsorted, O(n) is the best you can get.

This is called radix sort, not binary search. And how will you find a missing number after running this algo? You can, but you didn't specify.

Many of the earlier solutions are wrong because they don't properly update the count. The count variable has to be a single value that is shared among all copies of the same pointer. It should therefore be an int* allocated on the heap when the pointer is first created (via a T* object and not via copy constructor). Otherwise, old copies of the smart pointer won't know about new copies that may be floating around and may prematurely de-allocate the object.

Here's some code:

template <class T>
class shared_ptr
{
public:
shared_ptr(T* p):
ptr(p), 
count(new int(1)) {}

//copy constructor must copy the fields AND increment the reference count
shared_ptr(const shared_ptr<T>& other):
ptr(other.ptr),
count(other.count)
{
    incrementCount();
}

//destructor must decrement reference count
~shared_ptr()
{
    decrementCount();
}

//assignment operator must decrement the reference count of the 
//object the pointer no longer points to and increment the count
//of the object it now does point to
shared_ptr<T>& operator=(const shared_ptr<T>& obj)
{
    if(this->ptr != obj.ptr)
    {
        decrementCount();
        ptr = obj.ptr;
        count = obj.count;
        incrementCount();
    }
    return *this;
}

//not a bad idea to have these, as someone else suggested
T* operator->(){ return ptr; }
T& operator*() { return *ptr;}
T* get() { return ptr;}

private:
inline void incrementCount()
{
    (*count)++;
}

//when decrementing, we must free the underlying
//pointer if there are no more copies of it
inline void decrementCount()
{
    (*count)--;
    if (*count <= 0)
    {
        delete ptr;
        delete count;
    }
}

T* ptr;
int* count;
}

How would you avoid sorting the number?

I don't think it's like that. If you do, give an algorithm to reduce subset-sum to this problem.

Incorrect. Yields 500 for [200 -10 -10 -10 -10 -10 100] (instead of 300).

Can anyone do better than O(n^2) time? I've only thought about this for 5-10 minutes, but O(n^2) time and O(n) space is the best I have so far.

There's definitely not guaranteed to be a big difference in cache performance. I would prefer the two-pass approach because it more easily generalizes to more complicated cases.

If you're going to do that, might as well use an array. You know the keys will be from 1 to n anyway. In any event, the whole point of this problem was probably to try to solve it in a way that avoids O(n) extra memory. Otherwise, it's just trivial.