Logic/Programming Interview Questions - Page 2

On June 25 2011 09:45 Oracle wrote:

Yup, can't find a problem with it. I came across this solution too but didn't like it because most likely the observer would need a coding grammar to lookup which permutation refers to which.

There is only enough space on the table to arrange the cards vertically, side by side. All four cards must be at the table and cannot be re-ordered once set.

On June 25 2011 20:45 DeLoAdEr wrote:
5)

Let a_1, a_2, b_1, b_2, c_1, c_2, ... be the pairs and x the unique element.

^ = bitwise XOR:
(a_1 ^ a_2) ^ (b_1 ^ b_2) ^ (c_1 ^ c_2) ^ x = x because a ^ a = 0 and 0 ^ a = a. Since ^ is commutative and associative the order doesnt matter and to get the unique element we can just run in a loop over all elements and XOR them. Should work =)

On June 26 2011 00:22 BottleAbuser wrote:
1) I don't think this is possible. List and array-backed queues have linear time inserts, and heap-backed queues have logarithmic extracts. If we don't need constant time extracts, heaps would work fine.

4) Median of medians algorithm. God I love this one.

On June 26 2011 01:14 BottleAbuser wrote:
6) Initialize a counter k as 1, and save your current location as x. Go to the next node k times and check if its the same as your current location. Until it is, continue to save your current location as x, and increment k, and check if k hops ahead is the same as the current location.

This is O(n) because if we enter a loop, it is at most size of n. When k reaches a multiple of n, we are done, so it is O(n).

1) A min and a max heap of equal sizes. Ta-da.

On June 26 2011 01:39 BottleAbuser wrote:
Median of medians: group the elements into groups of 5, and sort the groups of 5 (n/5*5log5)=O(n). Take the median of these recursively (O(n), ok, that's cheating, because I don't remember and can't understand Wikipedia's proof... should do that ... later...).

Now you can split the array into an upper and lower half by comparison with our pivot. If the upper half's size is k-1, then we can return the median. If k>size/2-1, then k-=size/2+1, and we do it again for the lower half. If k<size/2-1, then we do it again for the upper half. This recursion is also O(n), somehow.

On June 26 2011 01:49 BottleAbuser wrote:
Yar, I forgot about that requirement and fixated on the hint algorithm. Shit me. And you're right, it's O(pn) or O(n^2) if the whole damn thing is a cycle. I have to go back to school.

I can still fix the algorithm I gave (O(n^2) still); you backtrack by k-1 steps, see if k steps ahead is the same as that node, and continue (backtrack by k-2, k-3, and so on and see if k steps ahead of that node is the same) until you reach one that isn't.

But then again, that only works for doubly linked lists. Grr.

On June 26 2011 02:07 BottleAbuser wrote:
If it is a doubly linked list, then my solution still works in O(n^2), because you're guaranteed to find the place where you jumped into the cycle. From there, you have at most k-1 nodes in between a definite non-cycle node and a definite cycle node, and you can check each one to see which is the first. I'll give these another crack tomorrow, it's drinkin time.

And what the heck is 0xabc and 0xabf? Those are different values, unless C++ has some really weird quirks...

On June 26 2011 23:07 BottleAbuser wrote:
Proof of median of medians linear runtime

Finding the median of medians takes a recursive call on the sets of 5, or T(n/5).

Partitioning into "this group of 5's median is less than/greater than median of set" takes linear time or O(n).

We are guaranteed that the elements of each goup of 5 in the groups whose median is less than set median are also less than the set median (transitivity of less than operator). Therefore, at least 3/5 of 1/2 of the set is less than the set median, and no more than 1-3/10. In the wost case, T(n*7/10).

Now, T(n*7/10)+T(n/5) <= T(n*9/10). Thus, worst case is T(n) <= O(n) + O(n*9/10) + O(n*(9/10)^2 + ...) = O(n) * (1 + 9/10 + (9/10)^2 + ...) which is O(n)*c for some constant c. Power series of 9/10^n for n in Z converges on 10, so c is truly asymptotically constant.

On June 25 2011 09:33 ptell wrote:
Solution to 7) :

First note that every card can be mapped to a number in the range of 1 to 52. Using the convention in bridge, the map is (from smallest to highest):

01 <--> Ace of Spades
02 <--> Ace of Hearts
03 <--> Ace of Diamonds
04 <--> Ace of Clubs
05 <--> Deuce of Spades
.
.
.
51 <--> King of Diamonds
52 <--> King of Clubs

Then the first four cards corresponds to a set of four number, e.g. {04, 13, 17, 31}. Then reindex the remaining 48 cards so that it starts from 01 and ends at 48.

Now there are 4! = 24 ways to arrange four distinct cards so we can map to indices 01 to 24. Next to represent the indices 25 to 48, flip the card with the smallest value.

1) Implement an integer Median Priority queue. That is, Peek has O(1) and Insert/Delete Median has O(logn). (Data structures course).

2) Suppose there is a street-race, with a total of k contestants. You start at intersection A, and finish at intersection C. For safety, you want to plan this so that no two contestants can possibly be on the same road together. (Their routes are unique) There are exactly k unique routes from A to B (by unique I mean no roads in any two routes are the same) and exactly k unique routes from B to C. Describe a method to find k unique A-C routes. (Graph theory course)

3) In OOP, how would you create/modify a class such that it can ONLY be allocated on the heap. That is, allocation onto the stack will error or fail. (Bloomberg)

class Base
{
	public:
		explicit Base () {}
		virtual ~Base () {}
};

class Derived :
public Base
{
	public:
		explicit Derived () {}
	protected:
		virtual ~Derived () {}
};

int main (int argc, char* argv[])
{
//	Derived x;	//	fails
	Base* base = new Derived();
	delete base;
	Derived* derived = new Derived();
	delete dynamic_cast<Base*>(derived);
}

class Test
{
	public:
		explicit Test () {}
		void destroy ()
		{
			delete this;
		}
	protected:
		virtual ~Test () {}
};

int main (int argc, char* argv[])
{
	Test* test = new Test();
	test->destroy();
}

4) Given an array of size n, implement a function which will find the kth largest element in O(n) time and O(1) space. Be careful to note that elements are not necessarily integers, but have the standard comparison operators (ie <=, <) defined, all of which are transitive. (Data structures course)

5) Given an integer array of size 2n+1 (odd length), where every element exists in pairs except for one unique element, find the unique element in O(n) time and O(1) space. (Google)

6) Find the start of a cycle in a C++ linked list in O( n ) where n is the number of nodes, and space complexity O(1). Elements in the array are not necessarily distinct, so searching for the first recurrence of an element does not work. You do not know n. (IBM)

7) Given a standard 52 card deck, you pull out 4 arbitrary cards. Now, you pull out the next card and memorize it before putting it back in the deck. Describe a method to arrange the first four cards in any order on a table so that someone who knows your system will be able to identify the 5th card you pulled. There is only enough space on the table to arrange the cards vertically, side by side. All four cards must be at the table and cannot be re-ordered once set.

Clarification: You may flip cards upside down, but note that the observer will not be able to see what the upside down cards are.