EPTBut given the way the question is worded, we have no guarantee about the current state of the pointers, as an adversary could defeat you every time on the first node.
Logic/Programming Interview Questions - Page 3
| Blogs > Oracle |
|
BottleAbuser
Korea (South)1888 Posts
But given the way the question is worded, we have no guarantee about the current state of the pointers, as an adversary could defeat you every time on the first node. | ||
|
Oracle
Canada411 Posts
I will post a diagram for Q2 soon BottleAbuser, your proof of the O(n) running time of k-select is fine with me now  I have a different solution: You turn the array into a heap and then find the k-th largest. I'll post a detailed solution soon. 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. | ||
|
Oracle
Canada411 Posts
A: an array 1. n ← size(A) − 1 2. for i ← floor(n/2) to 0 do 3. bubble−up(A, i) Builds a max-heap in linear-time, given the assumption that the 2i'th index is the left child, and 2i+1'th index is the right child of an element. Then its a simple o(k) time to find the kth largest | ||
|
Hamster1800
United States175 Posts
| ||
|
Oracle
Canada411 Posts
| ||
|
Hamster1800
United States175 Posts
| ||
|
Oracle
Canada411 Posts
We traverse only k-1 edges, and every time we traverse an edge we will effectively be eliminating a greater element than k. But we only traverse the edge with the child with the greatest key. Hence we place each key in a priority queue, and traverse the greatest key out of all the "active" nodes. But since we only traverse k-1 edges, we are done at the kth iteration. In Pseudocode, activenode <- root initialize Maxheap Q for 0 to k-1 put children of activenode into Q activenode <- get max of Q return activenode Actually i guess this is O(klogk) but I believe theres an analysis which shows its within n so i'll think about it for a bit. (Something to do with Q's size being at most n/2 iirc, guess I shouldve done the problems before posting them ) | ||
|
Hamster1800
United States175 Posts
| ||
|
Oracle
Canada411 Posts
| ||
|
Frigo
Hungary1023 Posts
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. Well it's settled then. We just need to set a bit in the "next" pointer to mark a node visited. And technically, the algorithm uses only an O(1) space overhead, not O(n), made possible by the special structure of the list. Frigo, your answer to Q7 doesn't seem right with me, you can refer to the post I made before regarding a similar method. Well, I have only shown that we convey enough information to tell the 5th card, I left the ordering and indexing of the cards, and the method to calculate the index of the 5th from the possible arrangements, implicit. Other than that, I forgot the case when all cards are upside down: 0 upside down, 4 visible: 4 choose 0 * 4! = 1 * 24 = 24 1 upside down, 3 visible: 4 choose 1 * 3! = 4 * 6 = 24 2 upside down, 2 visible: 4 choose 2 * 2! = 6 * 2 = 12 3 upside down, 1 visible: 4 choose 3 * 1! = 4 * 1 = 4 4 upside down, 0 visible: 4 choose 4 * 0! = 1 * 1 = 1 65 possible arrangements | ||
|
BottleAbuser
Korea (South)1888 Posts
Should read whole thread heh. I meant "what frigo said" | ||
|
iaretehnoob
Sweden741 Posts
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. 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? | ||
|
Oracle
Canada411 Posts
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? The 1st card I pulled out is mapped to hearts, regardless if it is a black-suited card. So we map the ordering not the suit. 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" Right, I love this one | ||
| ||
