The difference between two sequences of the same length {a1, a2, a3, ..., an} an

Question

The difference between two sequences of the same length {a1, a2, a3, ..., an} and {b1, b2, b3, ..., bn} can be defined as the sum of the absolute differences between their respective elements:

diff(a, b) = { |a1 –b1|, |a2– b2|, |a3 –b3|, ..., |an –bn| } For the given sequences a and b (not necessarily having the same lengths), find the subsequence a’ or a and subsequence b’ of b such that diff(a’, b’) is minimal. Return the difference.

Example:

A= {1, 2, 6}, b = {0, 1, 3, 4, 5}, the output should be smallestDifference(a, b) = 2, where the bestsubsequence will be b’ = {1, 3, 5}

1.Implement a recursive version of the smallestDifference function in the smallestDifference_recursive_utility function. There is no time restriction on this solution

2.Implement an amortized version of the smallestDifference function in the smallestDifference_amortized_utility function. The maximum timefor this function to identify the solution is 500ms (regardless of input size).

3.Implement a loop-based version of the smallestDifference function in the smallestDifference_optimized function. The maximum time for this function to identify the solution is 500ms (regardless of input size).

4.The length of a will be in the range [3, 1000].

5.The length of b will be in the range [a.length, 1000]

6.The values in each array will be in the range [-1000, 1000]

#include <climits>
#include <cmath>
#include "smallest_difference.h"

int smallestDifference_recursive_utility(const std::vector<int>& a, const std::vector<int>& b, int aPos, int bPos)
{

}

int smallestDifference_recursive(const std::vector<int>& a, const std::vector<int>& b)
{
   return smallestDifference_recursive_utility(a, b, a.size(), b.size());
}

int smallestDifference_amortized_utility(const std::vector<int>& a, const std::vector<int>& b, int aPos, int bPos, std::vector<std::vector<int> >& results)
{
  
}

int smallestDifference_amortized(const std::vector<int>& a, const std::vector<int>& b)
{
   std::vector<std::vector<int> > results(a.size(), std::vector<int>(b.size(), -1));
   return smallestDifference_amortized_utility(a, b, a.size(), b.size(), results);
}

int smallestDifference_optimized(const std::vector<int>& a, const std::vector<int>& b)
{
  
}

Explanation / Answer

int closestSequence2(std::vector a, std::vector b) {     int al = a.size();     int bl = b.size();     std::vector matrix (al, std::vector (bl, INT_MAX));     for(int i = 0; i = (al -i))             {                 int temp;                 if(i == 0 and j == 0)                     matrix[i][j] = abs(a[i] - b[j]);                 else                 {                        if(i == 0 || j == 0)                         temp = abs(a[i] - b[j]);                     else                         temp = abs(a[i] - b[j]) + matrix[i-1][j-1];                     matrix[i][j] = std::min(temp, matrix[i][j-1]);                 }             }         }     }     return matrix[al-1][bl-1]; }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---