Re: [algogeeks] Google Question--Suggest Algo
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg wrote: > You have an array with *n* elements. The elements are either 0 or 1. You > want to *split the array into kcontiguous subarrays*. The size of each > subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that > k << n. After you split the array into k subarrays. One element of each > subarray will be randomly selected. > > Devise an algorithm for maximizing the sum of the randomly selected > elements from the k subarrays. Basically means that we will want to split > the array in such way such that the sum of all the expected values for the > elements selected from each subarray is maximum. > > You can assume that n is a power of 2. > > Example: > > Array: [0,0,1,1,0,0,1,1,0,1,1,0] > n = 12 > k = 3 > Size of subarrays can be: 2,3,4,5,6 > > Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] > Expected Value of the sum of the elements randomly selected from the > subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 > > Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] > Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 > > > Source -> > http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Google Question--Suggest Algo
You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k << n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source -> http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Question--Suggest Algo
Can u provide a pseudo code for the same and c if it works On Thu, Nov 17, 2011 at 2:37 AM, sravanreddy001 wrote: > Start with counting sort of the input. > Use shuffling algorithm on it. > > Store index as cumulative sums of counts. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/0Uoq_OqBLn8J. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Google Question--Suggest Algo
Start with counting sort of the input. Use shuffling algorithm on it. Store index as cumulative sums of counts. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0Uoq_OqBLn8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Google Question--Suggest Algo
Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
How to approach this question ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
