|
So we all know all the big names ask hard questions on interviews so I've made it a hobby to look for the challenging ones and time myself solving them.
Most of the ones on the internet are fairly well known so I'm not going to bother posting any of those. In fact, I'll post precisely those which I found the most challenging, and feel free to share yours.
After each question I will attempt to provide an origination for the question. (I have not interviewed at all these companies, but friends have)
In order of increasing difficulty,
1) Implement an integer Median Priority queue. That is, Peek has O(1) and Insert/Delete Median has O(logn). (Data structures course).
+ Show Spoiler [Hint] +
+ Show Spoiler [Solved] +http://www.teamliquid.net/blogs/viewblog.php?topic_id=237090¤tpage=2#26
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)
+ Show Spoiler [Hint] +Observe that this scenario can be modeled as a undirected unweighted graph, with intersections being vertices, and roads being edges. You want to k pairwise edge-disjoint paths from A to C. Transitivity of Mengers (edge) theorem
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)
+ Show Spoiler [Hint] +No hint or else this would be too easy
+ Show Spoiler [Solved] +http://www.teamliquid.net/blogs/viewblog.php?topic_id=237090#11
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)
+ Show Spoiler [Hint] +Related to median priority queue
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)
+ Show Spoiler [Hint] +Associativity, Commutativity
+ Show Spoiler [Solved] +http://www.teamliquid.net/blogs/viewblog.php?topic_id=237090¤tpage=2#22
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)
Example of a cycle in a linked list
+ Show Spoiler [Hint] +Pointers. Make sure your understanding of them is most up-to-date with recent gcc C++ compilers. More specifically, 0xabf points to the same place as 0xabc.
+ Show Spoiler [Additional Hint] +We know we can use two pointers, lets label them A and B. A simple algorithm which, in every iteration, increments A = A->Next and B=B->Next->Next (with NULL checkers) will eventually yield A=B if there is a loop or B=NULL if there is no loop. This algorithm is trivial, also known as "The turtle and the hare algorithm." Now, try to do this using only ONE pointer
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.
+ Show Spoiler [Hint] +In mathematical terms, you are to find an onto mapping M: A -> B where A is {a, b, c, d} (the first four cards you pulled) to B = {all 52 cards} \ A. So |B| = 48. Note that rearranging the cards in any order only leaves 4! = 24 permutations. So M may not be one-to-one.
+ Show Spoiler [Solved] +http://www.teamliquid.net/forum/viewpost.php?post_id=9964122
|
#1. Never heard of a MEDIAN priority-queue and don't feel like googling the difference between it and a regular priority queue. Otherwise, like you said this is also a relatively easy question. The difficulty could be increased based on the underlying data-structure used for the queue (dynamic array, heap, etc.) Then it just comes down to arranging the data-structure each time an element is inserted based on its priority classification so the higher priority gets popped off first.
#2. This is probably a good one to study. CBA to do it at the moment.
#3. I imagine this is answered by saying have a watcher that triggers if data tries to be put on the stack? Not sure in what context it is being refered to, to be honest. Is it talking about the default operating system stack or a custom user built one in an OO language?
#4. This is way to easy for O(n). Just do a linear search comparing each element to each other and storing the current largest in a variable. A better question would be concerning binary search after you ask them what sort method they would use. And give a dataset size, because some sort methods are crappy for small data sets while others are obviously better.
#5. Again, O(n) is too easy. A linear search and you're good to go.
#6. Not sure about the cycle syntax, but based on the hint and how you should build a linked-list in C++ (where each node connects to another node through a pointer to that node), I'd image it is a simple memory search.
#7. CBA for this one either. I'd say in the interview though that I would google the trick to solving this and then implement that trick with an algorithm to do it :D
|
#1 A median priority queue is a regular priority queue where priority is given to the median element.
#3 Sounds fine but what exactly is the watcher? Youre skipping the essence of the question.
#4 We want kth largest not max
#5 O(1) space so you cant store elements which have occured
#6 Not so simple actually. A cycle is simply whenever node->next points to an element which you have previously traversed.
|
Hmm... I stopped reading at "Transitivity of Mengers (edge) theorem."
It depresses me to read things like this because I plan on learning programming and suddenly I realize how much of my life I have to spend learning this shit just to be on par with an average programmer.
Meh. Maybe I should just figure out a way to take stupid people's money and get rich. Like offering people enlightenment and then charging them for copy-pasted sections of the Tao Te Ching.
|
On June 25 2011 06:49 Oracle wrote:Show nested quote +On June 25 2011 06:48 Horuku wrote:
#4 is way to easy for O(n). Just do a linear search comparing each element to each other and storing the current largest in a variable. A better question would be concerning binary search after you ask them what sort method they would use. And give a dataset size, because some sort methods are crappy for small data sets while others are obviously better. 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.
Well still, for kth largest then you would just sort the array and then choose the element [k-1] lol
|
On June 25 2011 06:57 Horuku wrote:Show nested quote +On June 25 2011 06:49 Oracle wrote:On June 25 2011 06:48 Horuku wrote:
#4 is way to easy for O(n). Just do a linear search comparing each element to each other and storing the current largest in a variable. A better question would be concerning binary search after you ask them what sort method they would use. And give a dataset size, because some sort methods are crappy for small data sets while others are obviously better. 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. Well still, for kth largest then you would just sort the array and then choose the element [k-1] lol
Comparison based sort is lower bound nlogn
Radix/Counting sort are O(k) where k is the largest element in the array. But those work for integers (or some equivalent hashing function). Still if k > n then this doesn't work. In this problem you are not allowed to assume n <= k.
|
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: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.
Clarification 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.
And you do not know the value of 'n', sorry i should have explicitly said that.
#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. Empty spaces aren't allowed, sorry forgot to mention. You must use all 4 cards.
#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 07:46 Oracle wrote:Show nested quote +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.
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.
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:01 Siniyas wrote:Show nested quote +On June 25 2011 07:46 Oracle wrote: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.
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. 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?
I misunderstood some of your points so I edited my explanation, see above.
#7 You can assign a "value" to each of the four cards you drew. (ie a=1, b=2, c=3, d=4) But your scheme doesn't work if we do not allow the empty space. (Its close though, i definitely tried that) The fifth card (and also first four) are completely arbitrary and unrelated.
#4 k is not a constant (it is in terms of n). k is chosen by the algorithm. Of course k<=n, but k changes based on what value we choose. For example, if we want k= n-1, then we have to do n*(n-1) loops! thats definitely not linear.
#2 There sure is (Q3)
|
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 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;
}
That works. Of course there are many ways to implement it, but the gist is to make the constructor private (hence no stack allocation) and a public function (or friend to constructor or w.e) which returns a heap pointer.
|
Oh for 3. Only make a private constructor and have a static method that gives back a pointer to an object on the heap?
Edit: Meh. Just saw it was already posted.
|
Ive added an additional hint to Q6
|
On June 25 2011 06:43 Oracle wrote: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 at any time. + Show Spoiler [Hint] +In mathematical terms, you are to find an onto mapping M: A -> B where A is {a, b, c, d} (the first four cards you pulled) to B = {all 52 cards} \ A. So |B| = 48. Note that rearranging the cards in any order only leaves 4! = 24 permutations. So M may not be one-to-one.
So for this question, is our friend only allowed to observe the cards? I have ideas for an encoding that places cards face up/down, but I'm not sure if our observer is allowed to flip them face-up or not.
|
Yes the friend is only allowed to observe the cards. Face up/face down is fine, but note that your friend cannot know which card is which if there is more than one upside down card. So essentially, just think you can only label the face side with an 'a', 'b', 'c', or 'd'.
You're on the right track though. This isnt really an interview question, but a question a friend gave to me at lunch once. He said he didnt know the solution, and he heard it months back.
I encourage you to really think about it and then post, to ensure youre not missing any cases.
|
Here's a sketch of a solution to 7, I hope it works...
First, let's define an 'order' for cards of each color: Hearts < Diamonds < Spades < Clubs. This plus numerical order gives a mapping of cards of each color to the integers 1-26 by value, and it also gives us a strictly less-than operator for cards, so the lowest card can be called A, the next lowest can be called B, etc.
In your 4 cards, you will have either a majority color, or 2 red & 2 black cards. In this case, you will leave all cards face up, and use the 24 permutations of the face-up cards to correspond to 1-24, which correspond to the (at most 24) cards of the majority color (use red as the majority in the case of a 2/2 split). Our friend knows which cards in the majority color to leave out of the sorted list (because they're face-up on the table), so he can just map permutations (by lexicographic order or something) to the correct card.
For the remaining 24-26 cards, we turn some cards face-down (at most 2, so we never turn down a card in the minority color), and map the permutations of the face-up cards to cards in the minority color as follows (F = face-down card):
F A B C = 6 permutations of A, B, and C
A F B C = 6 more.
A B F C = 6 more
A B C F = 6 more
F F A B = 2 more, for 26 total permutations.
We turn at most 2 face-down, so we always leave our minority color cards face-up, and again our friend knows which ones to leave out of the sorted list.
Here's an example, because it's kinda sketchy just explaining it...
Let's say I pull the following 4 cards:
Ace of Hearts
Seven of Spades
Ten of Spades
Six of Diamonds.
In order, they are
Ace of Hearts = A
Six of Diamonds = B
Seven of Spades = C
Ten of Spades = D
Let's say the 5th card is the King of Spades.
It's in our minority color, and it's the 11th card out of 24, because we don't count the seven/ten of spades.
We thus give it the following mapping, where F is D, face-down.:
C F A B.
Our friend sees the 11th permutation for the minority color, and also sees the seven/ten of spades, so he knows to skip those. The 11th smallest black card, not counting the seven/ten of spades, is the King of Spades.
Let's say the fifth card is the Ace of Diamonds instead. Not counting the 4 cards we have on the table, it's the 13th smallest red card. We thus put down the 13th red permutation, CABD (all face up). Our friend sees the 13th permutation, and all cards face up, so he counts up to the 13th smallest red card, skipping the Ace of Hearts, because it's already on the table. This gives the Ace of Diamonds.
That post was far longer than I expected it would be, so much for a solution sketch... 
Anyway, feel free to point out any terrible flaws in my system, I think works okay.
|
I didnt read the example, and as soon as you mentioned "majority element" I knew what was going to come next. Looks right, and its completely different from my solution.
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.
|
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: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.
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.
|
|
|
|
|
|
EPT
