Databases
StackOverflow2013
Postsdbo
POConstructing fractions Interview challenge
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POConstructing fractions Interview challenge
    primarykey
    data
    text
    <p>I recently came across the following interview question, I was wondering if a dynamic programming approach would work, or/and if there was some kind of mathematical insight that would make the solution easier... Its very similar to how ieee754 doubles are constructed.</p> <p><strong>Question:</strong> There is vector V of N double values. Where the value at the ith index of the vector is equal to 1/2^(i+1). eg: 1/2, 1/4, 1/8, 1/16 etc...</p> <p>You're to write a function that takes one double 'r' as input, where 0 &lt; r &lt; 1, and output the indexes of V to stdout that when summed will give a value closest to the value 'r' than any other combination of indexes from the vector V. </p> <p>Furthermore the number of indexes should be a minimum, and in the event there are two solutions, the solution closest to zero should be preferred.</p> <pre><code>void getIndexes(std::vector&lt;double&gt;&amp; V, double r) { .... } int main() { std::vector&lt;double&gt; V; // populate V... double r = 0.3; getIndexes(V,r); return 0; } </code></pre> <p><strong>Note:</strong> It seems like there are a few SO'ers that aren't in the mood of reading the question completely. So lets all note the following:</p> <ol> <li><p>The solution, aka the sum may be larger than r - hence any strategy incrementally subtracting fractions from r, until it hits zero or near zero is wrong</p></li> <li><p>There are examples of r, where there will be 2 solutions, that is |r-s0| == |r-s1| and s0 &lt; s1 - in this case s0 should be selected, this makes the problem slightly more difficult, as the knapsack style solutions tend to greedy overestimates first.</p></li> <li><p>If you believe this problem is trivial, you most likely haven't understood it. Hence it would be a good idea to read the question again.</p></li> </ol> <p><strong>EDIT (Matthieu M.):</strong> 2 examples for <code>V = {1/2, 1/4, 1/8, 1/16, 1/32}</code></p> <ul> <li><code>r = 0.3</code>, <code>S = {1, 3}</code></li> <li><code>r = 0.256652</code>, <code>S = {1}</code></li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMatthieu M.
    1. USXander Tulip
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POConstructing fractions Interview challenge
      1. USXander Tulip
      1. VTFavorite
    2. VO
      singulars
      1. POConstructing fractions Interview challenge
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POConstructing fractions Interview challenge
      1. USLi-aung Yip
      1. VTFavorite
    1. CONote that the general case of this problem (The vector is not `2^-(i+1)`, but arbitrary values) is NP-Hard, since it is a variation of the subset sum problem. However, with the `2^-(i+1)` restriction, I believe the problem can be solved efficiently.
      singulars
      1. POConstructing fractions Interview challenge
      1. USamit
    2. CO@amit: Actually, I think this is a simplified version of the knapsack problem.
      singulars
      1. POConstructing fractions Interview challenge
      1. USXander Tulip
    3. COSubset sum problem is Knapsack with `weight=value` for each item, so we are both correct :). Note that though subset sum is looking for a subset with value 0, it is easy to make the problems identical by adding an item of size `-W`, where `W` is the size of the bag.
      singulars
      1. POConstructing fractions Interview challenge
      1. USamit
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload