Logic/Programming Interview Questions

On June 25 2011 06:49 Oracle wrote:


Sorry, youre right, i forgot to add that you have O( 1 ) space complexity.
but also, your solution finds the largest, not the kth largest.

On June 25 2011 06:57 Horuku wrote:


Well still, for kth largest then you would just sort the array and then choose the element [k-1] lol

On June 25 2011 07:35 Siniyas wrote:
For the cycle

If the list is n elements long, isnt the n+1 element always the start of the cycle?


For the cards thing.
We could just have an order for the cards,that card a is bigger than b
depending on the value ex. K>Q and also for the suits if cards are double.
We start with cards 1>2>3>4, for the first highest remaining card in the deck.
then change 3 and 4 then go 1 further and change 2 and 4, 3 and 4 and then 3 and 4 again and so on and so on.
Also if we can leave an empty space we get enough permutations, so that we can distinctly map each element.


for 4

We can just copy the array and run through it k times, picking out the biggest element and deleting it from the array.


For 2.

I dont see the difficulty here. First route from A to B goes with first route from B to C or any other as long as we dont use the chosen routes after that.

On June 25 2011 07:46 Oracle wrote:



For the cycle, it doesnt have to loop back to the beginning. The cycle can contain only a subset of the elements. So the first portion doesnt have to be contained in the cycle.

#7 You cant re-order the cards multiple times. Pick a configuration, set it on the table, and someone should know which card you are mapping to.

#4 That is O(kn) and not O(n)

#2 What if the routes from B to C are not pairwise edge disjoint from the A to B paths? That is, routes frmo B to C intersect some roads which are part of routes from A to B.

On June 25 2011 08:01 Siniyas wrote:


It doesnt matter if the cycle loops back to the beginning or any other element.
But to loop back we need to have gone through all n elements of the list once.
Example.
A->B->C->D->B
4 elements 5 element is the start of the cycle.

7
Dont understand your point exactly. Do we need to to pick a fixed ordering for the 4 cards based on certain characteristics that never change?
Doesnt really make sense to me. If we cant change the order of the cards in accordance to the 5 card that we drew, than it would be totally random. Unless the scheme that the 4 cards are ordered buy have conditions in it that pertain to the 5 card. Is that what you mean?

4
Okay usually constants are not factored into O Notation, but if you want it exactly n or less, then i will think about it again.

2
If thats the case, is there even a garantuee that we can find k A to C paths that dont cross?

On June 25 2011 08:22 HowitZer wrote:
3.)

class HeapOnly
{
private:
HeapOnly(){}

public:
static HeapOnly* Allocate() { return new HeapOnly(); }
};

int main()
{
HeapOnly p; // error

HeapOnly * p = HeapOnly::Allocate(); // ok

return 0;
}

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.

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.

On June 28 2011 05:42 Oracle wrote:
For Q6:
You can assume that node->next modulo 4 == 0 for every node in the list. You guys are actually really close to the answer.

Frigo, your answer to Q7 doesn't seem right with me, you can refer to the post I made before regarding a similar method.

On June 25 2011 09:32 Oracle wrote:
Here's mine:

We think of a card as a {0,1}-bit. A card represents 0 if it is face up and 1 if it is face-down.

So then we get a binary string of length four. So we can represent 2^4 - 1 = 15 possibly values with a string of 4 bits. But there are really only 13 distinct values. Hence we will never get the string 1111. So we will always have a face-up card.

So we assign 'a' = Hearts, 'b' = Diamonds, 'c' = Spades, 'd' = Clubs. The card which is face-up and leftmost denotes the suit.


So for example A F F F can be read as 0111 = 7. The A says its the 7 of Hearts.
FBDF can be read as 1001 = 9. The B says its the 9 of Diamonds.

On June 28 2011 21:15 iaretehnoob wrote:

Maybe I'm just misunderstanding your method, but doesn't this assume you actually get at least one other card of the same suit as the fifth card? For example how would you represent the 7 of Hearts if the other 4 cards are black?

On June 28 2011 20:15 BottleAbuser wrote:
Well, we can simply increment each traversed node's next pointer to mark it as visited then. If the next node'spointer mod 4 is 1 then that's the start of the loop.

Should read whole thread heh. I meant "what frigo said"