Geek asks and answers

Building Fractions Interviews

I recently came across the following interview question, I was wondering if a dynamic programming approach would work, and / or if there was some mathematical understanding that would make the solution easier ... Its very similar to how the ieee754 doubles are constructed.

Question: There is a vector V of N double values. Where the value in the i-th index of the vector is 1/2 ^ (i + 1). e.g. 1/2, 1/4, 1/8, 1/16, etc.

You must write a function that takes one double input "r", where 0 <r <1, ​​and displays the indices V in stdout, which when summed will give the value closest to the value "r" than any other combination of indices from the vector V.

In addition, the number of indices should be minimal, and if there are two solutions, the solution should be closest to zero.

void getIndexes(std::vector<double>& V, double r)
{
 .... 
}

int main()
{
   std::vector<double> V;
   // populate V...
   double r = 0.3;
   getIndexes(V,r);
   return 0;
}

Note: There seem to be several SO'ers who are not able to fully read the question. Therefore, let's note the following:

  • A solution, since the sum can be greater than r - therefore, any strategy, step-by-step subtraction of fractions from r, until it reaches zero or almost zero, is incorrect

  • There are examples of r where there will be 2 solutions, that is | r-s0 | == | r-s1 | and s0 <s1 - in this case, you need to choose s0, which complicates the task, since knapsack style decisions are prone to greedy reevaluation in the first place.

  • If you think this problem is trivial, you most likely did not understand it. Therefore, it would be nice to read the question again.

EDIT (Matthieu M.): 2 examples forV = {1/2, 1/4, 1/8, 1/16, 1/32}

  • r = 0.3, S = {1, 3}
  • r = 0.256652, S = {1}
+5
9

r F {1/2, 1/4, ... 1/(2^N)}. 1/(2^N) P.

:

S = P * round(r/P)

S , , P. err = r - S ± 1/2 * 1/(2^N). , 1/(2^N), F.

F P = 1/(2^N), P F. , , round(r/P) 1 kth " kth ".

:

r = 0.3 F {1/2, 1/4, 1/8, 1/16, 1/32}.

  • 32.

    r = 9.6 F {16, 8, 4, 2, 1}.

  • r .

    r = 10.

  • 10 ( )

    10 = 0b 0 1 0 1 0    ( 8 + 2 )
        ^ ^ ^ ^ ^
        | | | | |
        | | | | 1
        | | | 2
        | | 4
        | 8
        16

  • .

       = 0b 0 1 0 1 0    ( 1/4 + 1/16 = 0.3125 )
        ^ ^ ^ ^ ^
        | | | | |
        | | | | 1/32
        | | | 1/16
        | | 1/8
        | 1/4
        1/2

Proof

, , 2**N, .

:

r 0 < r < 1 {1/2, 1/4, .... 1/(2**N). , S, , error = r - S .

( 2**N):

r 0 < r < 2**N {2**(N-1), 2**(N-2), ... , 4, 2, 1}. , S, , error = r - S .

, ( ), . .

  • : r, 0 < r < 2**N, .
  • : - ±0.5. ( ±0.5 * 1/2**N.)
  • : ( ) , , . ( 0.5= . .)

(Python)

, r , r .

def conv_frac (r,N):
    # Convert to equivalent integer problem.
    R = r * 2**N
    S = int(round(R))

    # Convert integer S to N-bit binary representation (i.e. a character string
    # of 1 and 0's.) Note use of [2:] to trim leading '0b' and zfill() to
    # zero-pad to required length.
    bin_S = bin(S)[2:].zfill(N)

    nums = list()
    for index, bit in enumerate(bin_S):
        k = index + 1
        if bit == '1':
            print "%i : 1/%i or %f" % (index, 2**k, 1.0/(2**k))
            nums.append(1.0/(2**k))
    S = sum(nums)
    e = r - S

    print """
    Original number        `r` : %f
    Number of fractions    `N` : %i (smallest fraction 1/%i)
    Sum of fractions       `S` : %f
    Error                  `e` : %f
    """ % (r,N,2**N,S,e)

:

>>> conv_frac(0.3141,10)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500
8 : 1/512 or 0.001953

    Original number        `r` : 0.314100
    Number of fractions    `N` : 10 (smallest fraction 1/1024)
    Sum of fractions       `S` : 0.314453
    Error                  `e` : -0.000353

>>> conv_frac(0.30,5)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500

    Original number        `r` : 0.300000
    Number of fractions    `N` : 5 (smallest fraction 1/32)
    Sum of fractions       `S` : 0.312500
    Error                  `e` : -0.012500

: 0.5

r * 2**N 0.5, . , .

, , , , (.. 1 ), , .

+11

, ...

, , , (1/2)^(i+1) i [0..n), n , 1. , (1/2)^i sum (1/2)^j j [i+1, n), n.

, , , . i = 0

  • r 2^-(i+1),
  • , , 2^-(i+1) OR sum 2^-j j [i+2, N] ( )

, , - , ( ).

// The resulting vector contains at index i the sum of 2^-j for j in [i+1, N]
// and is padded with one 0 to get the same length as `v`
static std::vector<double> partialSums(std::vector<double> const& v) {
    std::vector<double> result;

    // When summing doubles, we need to start with the smaller ones
    // because of the precision of representations...

    double sum = 0;
    BOOST_REVERSE_FOREACH(double d, v) {
        sum += d;
        result.push_back(sum);
    }

    result.pop_back(); // there is a +1 offset in the indexes of the result

    std::reverse(result.begin(), result.end());

    result.push_back(0); // pad the vector to have the same length as `v`

    return result;   
}

// The resulting vector contains the indexes elected
static std::vector<size_t> getIndexesImpl(std::vector<double> const& v,
                                          std::vector<double> const& ps,
                                          double r)
{
  std::vector<size_t> indexes;

  for (size_t i = 0, max = v.size(); i != max; ++i) {
      if (r >= v[i]) {
          r -= v[i];
          indexes.push_back(i);
          continue;
      }

      // We favor the closest to 0 in case of equality
      // which is the sum of the tail as per the theorem above.
      if (std::fabs(r - v[i]) < std::fabs(r - ps[i])) {
          indexes.push_back(i);
          return indexes;
      }
  }

  return indexes;
}

std::vector<size_t> getIndexes(std::vector<double>& v, double r) {
    std::vector<double> const ps = partialSums(v);
    return getIndexesImpl(v, ps, r);
}

( ) ideone. , 0.3 :

0.3:
   1: 0.25
   3: 0.0625
=> 0.3125

.

+7

downvotes . , V, , . , .

( , ):

void getIndexes(std::vector<double>& V, double r)
{
  double v_lower = 0;
  double v_upper = 1.0 - 0.5**V.size();
  std::vector<int> index_lower;
  std::vector<int> index_upper;

  if (v_upper <= r)
  {
    // The answer is trivial.
    for (int i = 0; i < V.size(); i++)
      cout << i;
    return;
  }

  for (int i = 0; i < N; i++)
  {
    if (v_lower + V[i] <= r)
    {
      v_lower += V[i];
      index_lower.push_back(i);
    }

    if (r <= v_upper - V[i])
      v_upper -= V[i];
    else
      index_upper.push_back(i);
  }

  if (r - v_lower < v_upper - r)
    printIndexes(index_lower);
  else if (v_upper - r < r - v_lower)
    printIndexes(index_upper);
  else if (v_upper.size() < v_lower.size())
    printIndexes(index_upper);
  else
    printIndexes(index_lower);
}

void printIndexes(std::vector<int>& ind)
{
  for (int i = 0; i < ind.size(); i++)
  {
    cout << ind[i];
  }
}

!: D

( , , , V ...)

+4

, , . .

1] exp: given 1/2^i, find the largest i as exp. Eg. 1/32 returns 5.
2] max: 10^exp where exp=i.
3] create an array of size max+1 to hold all possible sums of the elements of V.
   Actually the array holds the indexes, since that what you want.
4] dynamically compute the sums (all invalids remain null)
5] the last while loop finds the nearest correct answer.

:

public class Subset {

public static List<Integer> subsetSum(double[] V, double r) {
    int exp = exponent(V);
    int max = (int) Math.pow(10, exp);
    //list to hold all possible sums of the elements in V
    List<Integer> indexes[] = new ArrayList[max + 1];
    indexes[0] = new ArrayList();//base case
    //dynamically compute the sums
    for (int x=0; x<V.length; x++) {
        int u = (int) (max*V[x]);
        for(int i=max; i>=u; i--) if(null != indexes[i-u]) {
            List<Integer> tmp = new ArrayList<Integer>(indexes[i - u]);
            tmp.add(x);
            indexes[i] = tmp;
        }
    }
   //find the best answer
    int i = (int)(max*r);
    int j=i;
    while(null == indexes[i] && null == indexes[j]) {
        i--;j++;
    }
      return indexes[i]==null || indexes[i].isEmpty()?indexes[j]:indexes[i];
}// subsetSum

private static int exponent(double[] V) {
    double d = V[V.length-1];
    int i = (int) (1/d);
    String s = Integer.toString(i,2);
    return s.length()-1;
}// summation

public static void main(String[] args) {
    double[] V = {1/2.,1/4.,1/8.,1/16.,1/32.};
    double r = 0.6, s=0.3,t=0.256652;
    System.out.println(subsetSum(V,r));//[0, 3, 4]
    System.out.println(subsetSum(V,s));//[1, 3]
    System.out.println(subsetSum(V,t));//[1]
}
}// class

:

For 0.600000  get 0.593750 => [0, 3, 4]
For 0.300000  get 0.312500 => [1, 3]
For 0.256652  get 0.250000 => [1]
For 0.700000  get 0.687500 => [0, 2, 3]
For 0.710000  get 0.718750 => [0, 2, 3, 4]
+2

, , ...

(, )

, OP, , , . -, - , , .

. , r , . , r , V, . - , r.

Python, . , , , OP. , return , , .

def estimate(V, r):
  lb = 0               # under-estimation (lower-bound)
  lbList = []
  ub = 1 - 0.5**len(V) # over-estimation = sum of all elements of V
  ubList = range(len(V))

  # calculate closest under-estimation and over-estimation
  for i in range(len(V)):
    if r == lb + V[i]:
      return (lbList + [i], lb + V[i])
    elif r == ub:
      return (ubList, ub)
    elif r > lb + V[i]:
      lb += V[i]
      lbList += [i]
    elif lb + V[i] < ub:
      ub = lb + V[i]
      ubList = lbList + [i]
  return (ubList, ub) if ub - r < r - lb else (lbList, lb) if lb != 0 else ([len(V) - 1], V[len(V) - 1])

# populate V
N = 5 # number of elements
V = []
for i in range(1, N + 1):
  V += [0.5**i]

# test
r = 0.484375 # this value is equidistant from both under- and over-estimation
print "r:", r
estimate = estimate(V, r)
print "Indices:", estimate[0]
print "Estimate:", estimate[1]

: , . !

+2

. .

#include <math.h>                                                                                                                                             
#include <stdio.h>                                                                                                                                            
#include <vector>                                                                                                                                             
#include <algorithm>                                                                                                                                          
#include <functional>                                                                                                                                         

void populate(std::vector<double> &vec, int count)                                                                                                            
{                                                                                                                                                             
    double val = .5;                                                                                                                                          
    vec.clear();                                                                                                                                              
    for (int i = 0; i < count; i++) {                                                                                                                         
        vec.push_back(val);                                                                                                                                   
        val *= .5;                                                                                                                                            
    }                                                                                                                                                         
}                                                                                                                                                             

void remove_values_with_large_error(const std::vector<double> &vec, std::vector<double> &res, double r, double max_error)                                     
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, err;                                                                                                                                      

    min_err = 1.0;                                                                                                                                            
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        err = fabs(*iter - r);                                                                                                                                
        if (err < max_error) {                                                                                                                                
            res.push_back(*iter);                                                                                                                             
        }                                                                                                                                                     
        min_err = std::min(err, min_err);                                                                                                                     
    }                                                                                                                                                         
}

void find_partial_sums(const std::vector<double> &vec, std::vector<double> &res, double r)                                                                    
{                                                                                                                                                             
    std::vector<double> svec, tvec, uvec;                                                                                                                     
    std::vector<double>::const_iterator iter;                                                                                                                 
    int step = 0;                                                                                                                                             

    svec.push_back(0.);                                                                                                                                       
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        step++;                                                                                                                                               
        printf("step %d, svec.size() %d\n", step, svec.size());                                                                                               
        tvec.clear();                                                                                                                                         
        std::transform(svec.begin(), svec.end(), back_inserter(tvec),                                                                                         
                       std::bind2nd(std::plus<double>(), *iter));                                                                                             
        uvec.clear();                                                                                                                                         
        uvec.insert(uvec.end(), svec.begin(), svec.end());                                                                                                    
        uvec.insert(uvec.end(), tvec.begin(), tvec.end());                                                                                                    
        sort(uvec.begin(), uvec.end());                                                                                                                       
        uvec.erase(unique(uvec.begin(), uvec.end()), uvec.end());                                                                                             

        svec.clear();                                                                                                                                         
        remove_values_with_large_error(uvec, svec, r, *iter * 4);                                                                                             
    }                                                                                                                                                         

    sort(svec.begin(), svec.end());                                                                                                                           
    svec.erase(unique(svec.begin(), svec.end()), svec.end());                                                                                                 

    res.clear();                                                                                                                                              
    res.insert(res.end(), svec.begin(), svec.end());                                                                                                          
} 

double find_closest_value(const std::vector<double> &sums, double r)                                                                                          
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, res, err;                                                                                                                                 

    min_err = fabs(sums.front() - r);                                                                                                                         
    res = sums.front();                                                                                                                                       

    for (iter = sums.begin(); iter != sums.end(); ++iter) {                                                                                                   
        err = fabs(*iter - r);                                                                                                                                
        if (err < min_err) {                                                                                                                                  
            min_err = err;                                                                                                                                    
            res = *iter;                                                                                                                                      
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("found value %lf with err %lf\n", res, min_err);                                                                                                   
    return res;                                                                                                                                               
}                                                                                                                                                             

void print_indexes(const std::vector<double> &vec, double value)                                                                                              
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    int index = 0;                                                                                                                                            

    printf("indexes: [");                                                                                                                                     
    for (iter = vec.begin(); iter != vec.end(); ++iter, ++index) {                                                                                            
        if (value >= *iter) {                                                                                                                                  
            printf("%d, ", index);                                                                                                                            
            value -= *iter;                                                                                                                                   
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("]\n");                                                                                                                                            
}                                                                                                                                                             

int main(int argc, char **argv)                                                                                                                               
{                                                                                                                                                             
    std::vector<double> vec, sums;                                                                                                                            
    double r = .7;                                                                                                                                            
    int n = 5;                                                                                                                                                
    double value;                                                                                                                                             
    populate(vec, n);                                                                                                                                         
    find_partial_sums(vec, sums, r);                                                                                                                          
    value = find_closest_value(sums, r);                                                                                                                      
    print_indexes(vec, value);                                                                                                                                
    return 0;                                                                                                                                                 
}
+1

, r. , r r. r, .

:

0.3 - 0,25. ( 2). 0,05

0,05 - 0.03125 - 0.01875

.

... - O (logN) . O (logN), O (logN ^ 2).

0

ints (indexes),

0-2 , :

A) , r0 (r-index ) 1/2

B) r0 double :

x (1- ) = -Exponent;// , ( x 1/2 ^ (x), )

float : ( / ) 

{
  if (bit is 1)
    output index x;
  x++;

} >

, O (n), n - .

0

, r ( )? N - "", .

Cish

for (int i=0; i<N; i++) {
  if (r>V[i]) {
    print(i);
    r -= V[i];
  }
}

r == 0, .

, , "r", , "" .

If the N-th digit was one, you need to add '1' to the received "binary" number and check both for the original "r". (Hint: build vectors a [N], b [N] from “bits”, set “1” bits instead of “print” above. Set b = a and enter manual addition, digit by digit from the end of 'b', while you don’t stop transferring, convert to double and choose which is closer.

Note that a [] <= r <= a [] + 1/2 ^ N and that b [] = a [] + 1/2 ^ N.

"The smallest number of indices [sic]" is a red herring.

0
source

More articles:


All Articles