Google Interview Question
SDE1sCountry: United States
It's pretty good solution but requires a small fix I think.
This:
dp[i][j] = -1;
if (dp[i-1][j] < 0) continue;
needs to be replaces with this
dp[i][j] = int.MaxValue;
if (dp[i-1][j] == int.MaxValue) continue;
Otherwise,
min(dp[i][k], dp[i-1][j] + abs(A[i]- k));
always returns dp[i][k], which has just been set to -1;
I think the correct way should be DP
{{
int myAdjust(vector<int> A, int target) {
int n = A.size();
int** dp = new int*[n];
for(int i = 0; i < n; i ++) {
dp[i] = new int[101];
}
for(int i = 0; i < n; i ++) {
for(int j = 1; j <= 100; j ++) {
if(i == 0) {
dp[i][j] = abs(A.at(i) - j);
} else {
dp[i][j] = 999999; // Some Max Value
for(int m = 1; m <= 100; m ++) {
if(abs(m - j) > target)
continue;
int diff = abs(A.at(i) - j) + dp[i - 1][m];
dp[i][j] = min(dp[i][j], diff);
}
}
}
}
int minCost = dp[n - 1][1];
for(int i = 2; i <= 100; i ++) {
minCost = min(minCost, dp[n - 1][i]);
}
return minCost;
}
}}
I don't suppose you could provide the proof (or a blurb about) why this thing provides an optimal substructure and overlapping sub-problems?
I think the goal is to minimize the sum of all adjustments.
I have a feeling that this question can be solved with DP.
Lets look at conditions first:
min (Sum|A[i]-B[i]|) : the |A[i]-B[i]| be as close to zero as possible.
|B[i]- B[i+1]| <= T
Solution:
create a 2D array nxn.
create an array of size n.
we seed B[j] = A[j] and now according to this we fill in values in matrix at ith row i.e.
mat[j][i+1] = mat[j][i] + T if A[i+1] > mat[j][i] + T
= mat[j][i] - T if A[i+1] < mat[j][i] - T
= A[i+1] if B[i]-T < A[i+1] < mat[j][i] +T
we fill in matrix for each 0<j<n B[j] = A[j] and store sum(|A[j] - B[j]|) in array[j]
Once the matrix is completely filled we traverse sum array find min and according to its index find row in matrix. This will be our B array.
Total time complexity n^2.
//dp[i][j]: 把A[i] 的值修改为j,所需要的最⼩花费, 则dp[i][j] = min{dp[i-1][k] + |j-A[i]|} s.t. |k-j| <= target
#define MAXTARGET 100
int MinAdjustmentCost(vector<int> A, int target) {
if (A.empty())
return 0;
int cur = 0;
// dp[i][j]: 把A[i] 的值修改为j,所需要的最小花费, 则dp[i][j] = min{dp[i-1][k]
+ |j-A[i]|} s.t. |k-j| <= target
int dp[2][MAXTARGET + 1];
memset(dp, 0x00, sizeof(dp));
for (int i = 0; i < A.size(); i++) {
int next = cur ^ 1;
for (int j = 1; j <= MAXTARGET; j++) {
dp[next][j] = INT_MAX;
for (int k = max(j-target, 1); k <= min(MAXTARGET, j+target);
k++)
dp[next][j] = min(dp[next][j], dp[cur][k] + abs(A[i]-j));
}
cur ^= 1;
}
int ans = INT_MAX;
for (int i = 1; i <= MAXTARGET; i++)
ans = min(ans, dp[cur][i]);
return ans;
}
I was thinking of following approach:
calculate median m
find 2 number with min( |A[i]-m| ) for i=0..n-1
these 2 number work as a base for alteration.
E.q: 14 2 3 => median 2.5 => 2,3 closest number where 2 is at odd and 3 is at even position in series.
5 19 18 0 2 => median 8.8 => 5 closest number => base could be 4,5 or 5,6 but 6 is closer to median so 5 at odd and 6 at even place
Hi, If I understood your examples correctly, the solution for "5 19 18 0 2" you are suggesting is "5 6 5 6 5" (5 at odd and 6 at even place). So, adjustment cost is 35. This is not the minimum cost because there is a better solution: "5 6 7 6 5" in which the cost is: 33.
Also, you are assuming the "target = 1" all the time. The from the question, it seems like the target could be user input.
I hope I understood your post...
Here is my take... not quite sure if I have it right.
Given the input integer array, compute the median of the values. Then start working at the location of the median in the array - adjust all the elements forward and backward by adjusting them to be within target.
Step 1: compute the median m and it's position pos
Step 2: start at (pos+1) up to A.length,
if A[pos+1] is already within distance target from A[pos], do nothing
else
{
adjust A[pos+1] by increasing or decreasing it and pick the one which makes it within distance target from A[pos]
if both increasing and decreasing gives acceptable solution, look at A[pos+1] to decide which one to pick
}
Step 3: start at (pos-1) up to 0,
do similar as Step 2.
Example (borrowed from Gambler):5 19 18 0 2
Step 1: median = 5, pos = 0
Step 2: adjust forward 5 6 7 6 5
Step 3: do not need for this particular example.
What about the input sequence of : 1 2 3 4 5 6 7 8?
The return should be the same as input.
So we need to redistribute the values of an array of integers
in order to obtain all the adjacent values with less than N difference.
If A is the input array and B the output array we need to minimize the
sum of the difference between the elements of the two arrays:
|A[i]-B[i]|
without changing the total sum of the elements in the array.
sum(A) == sum(B)
Example 1:
A[]: 55,77,52,61,39,6,25,60,49,47
A[] Tot: 471
Target Diff for Adjacent Numbers: 10
B[]: 57,56,55,46,45,38,37,46,44,47
B[] Tot: 471
SUM(A[i]-B[i]): 110
Example 2:
A[]: 94,35,29,55
A[] Tot: 213
Target Diff for Adjacent Numbers: 10
B[]: 58,49,51,55
B[] Tot: 213
SUM(A[i]-B[i]): 72
Example 3:
A[]: 97,73,56,56,93,55,29,47,90,36
A[] Tot: 632
Target Diff for Adjacent Numbers: 3
B[]: 72,70,69,66,64,61,60,58,57,55
B[] Tot: 632
SUM(A[i]-B[i]): 180
Lets say that the input array is A and the input target number is N.
To balance the array I use the following approach:
I analyze 3 elements adjacent elements at the same time (A[i-1], A[i], A[i+1]);
I use 3 elements because if I take just 2 elements, by balancing 2 of them (A[i-1] and A[i])
we could make the balancing between A[i] and A[i+1] worse.
For each triplet if it is not balanced, I take the Min and the Max of the triplet, and try to make
the smallest modification possible that brings the difference between the two number smaller or
equal to N. So we need to take off a quantity X from the max and add a quantity Y to the min of
the three elements such as the difference between Max and Min become equal to N (smallest modification).
To find X and Y we can solve the following system of equations:
(Max+X)-(Min+Y)=N
(Max+X)+(Min+Y)=TOT
Where Max and Min are the maximum and minimum elements in the triplet, N the target difference, TOT the
sum of Max+Min before the modification (that we don't want to change); using these two equations we can find
X and Y. I left the equation to find X and Y not simplified in the code for the sake of clarity.
So we keep balancing three numbers for each i between 1 and A.length-1, until we don't need to make any more
changes in the triplets. When there are no more modifications to do we return the modified array.
If the array are just two elements balance them doing the smallest modification to achieve a difference of N and again
not changing the total sum between the two elements.
The time complexity should be O(NlogK), where N is the number of elements in the array (inside for in the code), and K the range of the elements (as
we are balancing the values of the elements, external while in the code).
Here is the code to implement this solution, you can use "int[] genArray(int n, int range)" to generate a random
array of N integers between 0 and range, void printArray(int[] a) to print the input and output array,
int[] distribute(int[] a, int n) to generate the balanced array with a target difference of N:
import java.util.Random;
public class DistributeArray {
public static int tot(int[] a) {
int tot=0;
if(a!=null) {
for(int n: a) {
tot+=n;
}
}
return tot;
}
public static int[] genArray(int n, int range) {
int[] a = new int[n];
Random r = new Random();
for(int i=0;i<n;i++) {
a[i] = r.nextInt(range);
}
return a;
}
public static int[] distribute(int[] A, int n) {
int avg,tot,oldmax,oldmin;
int[] a= new int[A.length];
System.arraycopy( A, 0, a, 0, a.length );
boolean adj = false;
if(a==null) {
System.out.println("Null input array.");
return null;
}
if(n<=0) {
System.out.println("N must be a positive number.");
return a;
}
// Special case a.length<2
if(a.length<2) {
return a;
}
// Special case a.length==2
if(a.length==2) {
if(Math.abs(a[0]-a[1])>n) {
int sum = a[1]+a[0];
if(a[0]<a[1]) {
a[0]=((a[1]+a[0])/2)-(n/2);
a[1]=sum-a[0];
}
else {
a[1]=((a[1]+a[0])/2)-(n/2);
a[0]=sum-a[1];
}
}
return a;
}
while(!adj) {
adj=true;
//printArray(a);
for(int i=1;i<a.length-1;i++) {
if(Math.abs(a[i-1]-a[i])>n || Math.abs(a[i]-a[i+1])>n) {
tot = a[i-1]+a[i]+a[i+1];
//System.out.println(a[i-1]+","+a[i]+","+a[i+1]+" KO - TOT="+(a[i-1]+a[i]+a[i+1]));
int max, min, med;
if(a[i-1]>a[i] && a[i-1]>a[i+1]) {
max = i-1;
if(a[i+1]<a[i]) {
min = i+1;
med = i;
}
else {
min = i;
med = i+1;
}
}
else if(a[i]>a[i+1]){
max = i;
if(a[i+1]<a[i-1]) {
min = i+1;
med = i-1;
}
else {
min = i-1;
med = i+1;
}
}
else {
max = i+1;
if(a[i-1]<a[i]) {
min = i-1;
med = i;
}
else {
min = i;
med = i-1;
}
}
int tot2=a[max]+a[min];
oldmax = a[max];
oldmin = a[min];
a[max] = a[max]+(-a[max]-(n/2)+(tot2/2)+n);
a[min] = a[min]+(-a[min]-(n/2)+(tot2/2));
int diff = tot2-(a[max]+a[min]); //readd the rest to not change the sum
if(oldmin != a[min]+diff) {
a[min] = a[min]+diff;
}
else if(oldmax != a[max]+diff){
a[max] = a[max]+diff;
}
else {
a[med] = a[med]+diff;
}
//System.out.println(a[i-1]+","+a[i]+","+a[i+1]+" AFTER KO TOT="+(a[i-1]+a[i]+a[i+1]));
adj=false;
}
}
}
return a;
}
public static void printArray(int[] a) {
if(a!=null && a.length>0) {
for(int i=0;i<a.length-1;i++) {
System.out.print(a[i]+",");
}
System.out.println(a[a.length-1]);
}
}
public static void main(String[] args) {
int[] a = genArray(10,100);
//int[] a = new int[]{57,67,45,87};
System.out.print("A[]: ");
printArray(a);
int diff = 10;
System.out.println("A[] Tot: "+tot(a));
System.out.println("Target Diff for Adjacent Numbers: "+diff);
int[] b = distribute(a,diff);
System.out.print("B[]: ");
printArray(b);
System.out.println("B[] Tot: "+tot(b));
int diffAB = 0;
for(int i=0;i<a.length;i++) {
diffAB=diffAB+(Math.abs(a[i]-b[i]));
}
System.out.println("SUM(A[i]-B[i]): "+diffAB);
}
}
"without changing the total sum of the elements in the array.
sum(A) == sum(B) "
This is not accurate. Take example 1 3 1 (sum = 5) with target difference of 1. The optimal solution will be 1 2 1 (sum = 4).
The problem is to redistribute the values in order to have adjacent values with difference less or equal to target N, but keeping the total sum of the array. In your solution you do not keep the total sum.
If you take the example:
1 3 1 with target difference of 1
one possible solution will be:
1 2 2
in this way you keep the total value of the array, 1+3+1=5, 1+2+2=5
First, it seems to me that this problem has the property of optimal sub-solutions. Consider this -
Given a position i in the given array and a 'pick' p (i.e. the current value chosen for the selected position in the final array), then we have a range of values we could pick for position i+1, ranging from p - k, to p + k where k is the specified difference target.
For each sub solution 'pick' p + j, where j ranges from -k to k, and position i+1 let's assume we've somehow computed the optimal (i.e. smallest adjustment cost) for the sub-array from position i+1 to n.
What is the adjustment cost for 'pick' p and position i then? That should be -
abs(p - arr[i]) + min( sub solutions with picks p + j where j ranges from -k to k ).
Given this equation, it seems to me that optimal sub-solutions can be combined to produce a global optimal solution. If this weren't the case, then there should be a sub optimal sub solution that when combined with abs(p - arr[i]) somehow produces an optimal global solution. This however doesn't seem possible as the value of abs(p - arr[i]) is fixed irrespective of the nature of the sub solution.
Second, given that the numbers are restricted to being >0 and <100, we only have at best 100 (ish) choices for each number in the final array.
I can't seem to prove this but it seems to me that the number with the minimum value in the original array cannot decrease in the final array, and only either increases or stays the same, and the number with the maximum value in the original array cannot increase in the final array. This further limits the possibilities for each number in the final array, as it seems to me (I can't generate a counterexample but somebody could help me with a proof here), that a number in the final array can only lie between the range min and max (more or less).
A back of the envelope proof for this assertion is that if we're raising a number above the maximum number in the original array, we're not bringing that number closer to any other number in the array (which is one way we can view the act of achieving the difference target) because that number is already the largest in the array. Therefore, increasing a maximum number can only raise the adjustment cost. However, if the target difference is very large, then we may be forced to raise the maximum number to achieve the required target difference, or do we? Since the constraint is that the difference between any two numbers be less than the target difference, I think our range constraint still holds. (I still have a feeling that a better range constraint might be min-k to max+k, but can't prove it. However, it is easy enough to affect this change in code).
Given this range of possible values for each number in the final array, and given optimal sub solutions, we can define an array of sub-solutions of size n x (max-min+1+2k) where the (i,j)th element is defined as the optimal adjustment cost for pick value j + min - k (realigning our indexing so that the smallest possible number will be at pick index 0) and position i.
The running time of this algorithm would be O(n*m) where m = (max - min), (or if somebody could prove it.. (max - min + 2*k) ), because the size of my solution space is n*m which helps me trim off large swathes of the recursion space.
Here's working code. I have also included the exponential version of the solution that doesn't use saved solutions, to compare the accuracy of my approach. Be warned - the exponential solution runs very slow given large values of k (and n), which is unsurprising given that it has a running time of O(k^n)
Pardon my butchering of OOP here. I'm not really a Java guy, but OOP related rearchitecting suggestions are welcome.
import java.io.*;
import java.util.*;
public class ArrayAdjust {
private static ArrayList <Integer> array;
private static int [][][] picks;
private static int minSum;
private static int min;
private static int max;
private static void findSolutionExp(int pick, int position, int k, int sum, int [] savedSolution) {
savedSolution[position] = pick;
if( position == ArrayAdjust.array.size() - 1) {
sum += Math.abs( pick - ArrayAdjust.array.get(position) );
if( sum < minSum ) {
minSum = sum;
/* for( int num: savedSolution ) {
System.out.print(num + "\t" );
}
System.out.println(sum);*/
}
return;
}
sum += Math.abs( pick - ArrayAdjust.array.get(position) );
//we try all possible picks//
for( int i = -k; i <= k; i++ ) {
//we skip those picks that go below min or max because I don't think they can
if( i!= 0 && pick + i >= ArrayAdjust.min - k && pick + i <= ArrayAdjust.max + k ) {
ArrayAdjust.findSolutionExp( pick + i, position + 1, k, sum, savedSolution );
}
}
}
private static int findSolution( int pick, int position, int k) {
if( position == ArrayAdjust.array.size() - 1) {
//we've reached one end
return Math.abs( pick - ArrayAdjust.array.get(position) );
}
//search index = pick - min
int pickIndex = pick - min + k;
if( ArrayAdjust.picks[position][pickIndex][0] != -1 ) {
return ArrayAdjust.picks[position][pickIndex][0];
}
int curDiff = Math.abs( pick - ArrayAdjust.array.get(position) );
//proof that optimal subsolutions can be combined
//since the value of curdiff i.e. the addition factor to the sub solution is fixed
//there is no way a suboptimal subsolution could become globally optimal,
//because a suboptimal sub solution could be substituted with the optimal sub solution and we would
//have a better solution
int minSolution = 101*ArrayAdjust.array.size();
int minPick = -k;
for( int i=-k; i<=k; i++ ) {
if( i != 0 && pick + i >= min - k && pick + i <= max + k ) {
int curSolution = ArrayAdjust.findSolution( pick + i, position + 1, k );
if( curSolution < minSolution ) {
minSolution = curSolution;
minPick = i;
}
}
}
ArrayAdjust.picks[position][pickIndex][0] = curDiff + minSolution;
ArrayAdjust.picks[position][pickIndex][1] = pick + minPick - min + k;
return curDiff + minSolution;
}
public static void main( String [] args ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayAdjust.array = new ArrayList<Integer>();
String line;
line = br.readLine();
int k = Integer.parseInt( line );
ArrayAdjust.min = 101;
ArrayAdjust.max = -1; //since we've been assured that no number is larger than 100
while( (line = br.readLine()) != null ) {
//check if this line has multiple number elements
String [] parts = line.split("\\s");
for( String part: parts ) {
if( part.matches("\\d+") ) {
int intPart = Integer.parseInt( part );
ArrayAdjust.array.add( intPart );
if( intPart < ArrayAdjust.min ) {
ArrayAdjust.min = intPart;
}
if( intPart > ArrayAdjust.max ) {
ArrayAdjust.max = intPart;
}
}
}
}
int n = ArrayAdjust.array.size();
//I'm going ahead with my hunch and setting range to max - min + 2k
ArrayAdjust.picks = new int[n][max - min + 1 + 2*k][2];
//the extra factor of two because in addition to storing the optimal subsolution cost, I'm also storing the pick made so that we can retrace the solution later
//set default
for( int i=0; i<picks.length; i++ ) {
for( int j=0; j<picks[i].length; j++ ) {
picks[i][j][0] = -1;
}
}
//this to keep track of the current solution for the exponential case
int [] savedSolution = new int[n];
ArrayAdjust.minSum = 101*n;
int minSol = 101*n;
int minPick = min - k;
for( int i=min-k; i<=max+k; i++ ) {
int sol = ArrayAdjust.findSolution( i, 0, k );
if( sol < minSol ) {
minSol = sol;
minPick = i;
}
//ArrayAdjust.findSolutionExp( i, 0, k, 0, savedSolution );
}
System.out.println("");
/*for( int i=0; i<picks.length; i++ ) {
for( int j=0; j<picks[i].length; j++ ) {
System.out.print( ArrayAdjust.picks[i][j] + "\t" );
}
System.out.println("");
}*/
//System.out.println("Exponential solution (correct hopefully): " + ArrayAdjust.minSum);
System.out.println("DP solution: "+ minSol);
//Let's retrace the solution using the min pick value
int curPick = minPick - min + k;
for( int i=0; i<n; i++ ) {
System.out.print( (curPick + min - k) + "\t" );
curPick = ArrayAdjust.picks[i][curPick][1];
}
System.out.println("");
}
}
Using gigi84's example, I get a better solution with an adjustment cost of 75 -
printf "10\n55 77 52 61 39 6 25 60 49 47" | java ArrayAdjust
DP solution: 75
55 62 52 49 39 29 30 40 49 47
The DP solution I've described is contained in the method
findSolution
, while the non-DP exponential solution is contained in the method
findSolutionExp
Hi Loneranger!
I like your approach of using subsolutions and also limiting the number of solutions by taking into account that the range of the numbers is included between 0 and 100; anyway I still think that the solution to the problem is to "redistribute" the values of the array in order to have the difference between adjacent number less or equal to a target number, but also you need to keep the total sum of the array. If you check the example in the initial stating of the problem, they transform the array:
[1,4,2,3] and target=1
in the array
[2,3,2,3]
as you can see [1+4+2+3]=10 and [2+3+2+3]=10.
so you need to "redistribute" the values, not add nor subtract values from the total sum.
In your solution you solve the problem of having the adjacent number with a difference of 10 or less, but you are changing the total value of the array:
55+77+52+61+39+6+25+60+49+47=471
55+62+52+49+39+29+30+40+49+47=452
so I think this is not the complete solution to the problem
Hi gigi84,
I don't see that constraint mentioned in the question, i.e. keeping the sum of the initial array equal to the sum of the final array. But if that is indeed a constraint, then of course you're right and my solution won't work. Maybe OP can clarify.
Use Dynamic programming approach to solve this problem.
Assume the difference of min/max values is small.
On each number from the first to last, calculate the total cost up to this number with the ending number. Thus we calculate a matrix with column as the order of the number, row as ending number, cell value as a pair of total cost so far and row number of previous column to reach this cell(for path). The cell with the lowest cost in the last column is the result. From that cell, we can get the cell on each column to reach this last cell. The row and column indices for cells on the path make the result sequences.
For example:
input : 1, 4, 2, 3
matrix:
1 2 3 4
1 (0, -1) (3, 1) (4, 1) (6, 1)
2 (1, -1) (2, 1) (2, 2) (3, 2)
3 (2, -1) (2, 2) (3, 2) (2, 2)
4 (3, -1) (2, 3) (4, 3) (4, 3)
So the last cell[3,4] has lowest cost of 2, the previous cell is [2,3] with cost 2, then previous is [2,2] with cost 2 and then [1,1]. The result sequence is ( 1, 2, 2, 3) . This result has the same cost as the sequence of (2,3,2,3)
It is very easy to write code to implement this algorithm.
Wouldn't a regular hill climbing algorithm work, especially if it iteratively grows the search space (ie: considers positions 0..1 then 0..2 then 0..3, etc) and the moves are constrained as the moving of 1 between values with only valid moves considered? The cost for each move could simply be
|A[0..i-1] - B[0..i-1] | + ( |B[i] - B[i-1]| > maxDelta ? | B[i] - B[i-1] | : 0 )
and each iterative search could terminate when
| A[i] - B[i] | <= maxDelta
public static int smoothArray(int[] arr, int maxDelta){
if(arr == null){
throw new NullPointerException();
}
if(maxDelta < 1){
throw new IllegalArgumentException();
}
if(arr.length == 0 || arr.length == 1){
return 0;
}
Worker worker = new Worker(arr, maxDelta);
worker.execute();
return worker.getResults();
}
static class Worker{
int[] origArr;
int[] workingArr;
int maxDelta;
Worker(int[] arr, int maxDelta){
this.origArr = arr;
this.workingArr = Arrays.copyOf(this.origArr, this.origArr.length);
this.maxDelta = maxDelta;
}
void execute(){
for(int i = 1; i < this.origArr.length - 1; i++){
executeLocal(i);
}
}
void executeLocal(int index){
int diff = this.workingArr[index -1] - this.workingArr[index];
boolean decrement = diff < 0 ? true : false;
while(Math.abs(diff) > maxDelta){
this.workingArr = bestMove(index, decrement);
diff = this.workingArr[index -1] - this.workingArr[index];
}
}
int[] bestMove(int index, boolean decrement){
int[] moveWorkspace = Arrays.copyOf(this.workingArr, this.workingArr.length);
int[] bestMove = null;
int bestCost = Integer.MAX_VALUE;
if(decrement){
moveWorkspace[index] --;
for(int i = 0; i < index; i++){
moveWorkspace[i]++;
if(isValid(moveWorkspace, index-1)){
int cost = getCost(moveWorkspace, index);
cost += getLocalValidCost(moveWorkspace, index);
if(cost < bestMove){
bestMove = Arrays.copyOf(moveWorkspace, moveWorkspace.length);
}
}
moveWorkspace[i]--;
}
}
else{
moveWorkspace[index] ++;
for(int i = 0; i < index; i++){
moveWorkspace[i]--;
if(isValid(moveWorkspace, index-1)){
int cost = getCost(moveWorkspace, index);
cost += getLocalValidCost(moveWorkspace, index);
if(cost < bestMove){
bestMove = Arrays.copyOf(moveWorkspace, moveWorkspace.length);
}
}
moveWorkspace[i]++;
}
}
return bestMove;
}
int getResults(){
return this.getCost(this.workingArr, this.workingArr.length);
}
int getCost(int[] arr, int length){
int sumDiff = 0;
for(int i = 0; i < length; i++){
sumDiff += Math.abs(this.origArr[i] - arr[i]);
}
return sumDiff;
}
int getLocalValidCost(int[] arr, int index){
//( |B[i] - B[i-1]| > maxDelta ? | B[i] - B[i-1] | : 0 )
int diff = Math.abs(arr[index] - arr[index -1]);
return diff > this.maxDelta ? diff : 0;
}
boolean isValid(int[] arr, int length){
for(int i = 1; i < length; i++){
if(Math.abs(arr[i-1] - arr[i]) > this.maxDelta){
return false;
}
}
return true;
}
}
#include<iostream>
int b[4];
void insert()
{
b[0]=1;b[1]=4;b[2]=2;b[3]=3;
}
void print(vector<int> a,int index,int changes)
{
for(unsigned int ii=0;ii<a.size();ii++)
if(a[ii]==-10) return;
cout<<"\n";
for(unsigned int ii=0;ii<a.size();ii++)
cout<<"\t"<<a[ii];
cout<<"\t index\t"<<index;
cout<<"\t Changes\t"<<changes;
int k=0;
for(unsigned int ii=0;ii<a.size();ii++)
if(a[ii]!=b[ii])k++;
cout<<"\tActual Changes::"<<k;
}
int target(int currentIndex,vector<int> a,int changes,int currentValue,int n )
{
if(currentIndex<0) {return 0;}
if(currentIndex>=n) {return 0;}
print(a,currentIndex,changes);
currentValue++;
if(currentIndex-1>=0 && a[currentIndex-1]==-10){
a[currentIndex-1]=currentValue;
if(b[currentIndex-1]!=currentValue)changes++;
target(currentIndex-1,a,changes,currentValue,n);
a[currentIndex-1]=-10;}
if(currentIndex+1<n && a[currentIndex+1]==-10){
a[currentIndex+1]=currentValue;
if(b[currentIndex+1]!=currentValue)changes++;
target(currentIndex+1,a,changes,currentValue,n);
a[currentIndex+1]=-10;
}
currentValue--;
currentValue--;
if(currentIndex-1>=0 && a[currentIndex-1]==-10 && currentValue>0){
a[currentIndex-1]=currentValue;
if(b[currentIndex-1]!=currentValue)changes++;
target(currentIndex-1,a,changes,currentValue,n);
a[currentIndex-1]=-10;}
if(currentIndex+1<n && a[currentIndex+1]==-10 && currentValue>0){
a[currentIndex+1]=currentValue;
if(b[currentIndex+1]!=currentValue)changes++;
target(currentIndex+1,a,changes,currentValue,n);
a[currentIndex+1]=-10;}
currentValue++;
return 0;
}
int main()
{
int l[]={-10,-10,-10,-10};
//int b[]={3,2,1,3};
insert();
vector<int> l123(b,b+sizeof(b)/sizeof(int));
cout<<"\n Start:";
print(l123,0,0);
cout<<"\n-----------------------\n";
vector<int> base(l,l+sizeof(l)/sizeof(int));
for(unsigned int ii=0;ii<sizeof(l)/sizeof(int);ii++)
{
base[ii]=b[ii];
target(ii,base,0,b[ii],sizeof(l)/sizeof(int));
base[ii]=-10;
}
}
First, it seems like minimizing sum(|A[i]-B[i]|) is just the same as minimizing adjustment cost. It's, basically, just rephrasing the condition.
Second, I think it could be solved by BFS. Here's the working Java code:
public int adjust(int[] arr, int target) {
Set<String> visited = new HashSet<>();
visited.add(Arrays.toString(arr));
Map<String, int[]> parents = new HashMap<>();
parents.put(Arrays.toString(arr), null);
Queue<int[]> queue = new LinkedList<>();
queue.offer(arr);
int cost = 0;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
boolean adjusted = false;
for (int i = 0; i < curr.length-1; i++) {
if (Math.abs(curr[i] - curr[i+1]) > target) {
int[] A = Arrays.copyOf(curr, curr.length);
A[i] += (curr[i] - curr[i+1] > 0) ? -1 : 1;
if (visited.add(Arrays.toString(A))) {
parents.put(Arrays.toString(A), curr);
queue.offer(A);
}
A = Arrays.copyOf(curr, curr.length);
A[i+1] += (curr[i] - curr[i+1] > 0) ? 1 : -1;
if (visited.add(Arrays.toString(A))) {
parents.put(Arrays.toString(A), curr);
queue.offer(A);
}
adjusted = true;
}
}
if (!adjusted) {
System.out.println(Arrays.toString(curr));
while (parents.get(Arrays.toString(curr)) != null) {
cost++;
curr = parents.get(Arrays.toString(curr));
}
break;
}
}
return cost;
}
In terms of complexity, in a worst case at the each iteration we will put into our queue all increments and decrements (element-wise incremented and decremented arrays) for the each pair of consecutive elements in current array (O(n)) and we will do it "cost" number of times. As serialization of an Array is also linear we'll get O(n*n*cost). Maybe it's not the fastest but what I like here is that it's comparably easy to code, especially during the interview.
This can be solved as a sort of hill climbing search algorithm. This approach can be simplified by obtaining an optimal solution within the overall problem by slowly increasing the problem size. Ultimately, however, this approach will take O (n ^2 * m) where n is the size of the array and m is the sum of the values of the array).
public static int getNumMoves(int[] arr, int k){
if(arr == null){
throw new NullPointerException();
}
if(arr.length < 2 || k < 1){
throw new IllegalArgumentException();
}
Worker worker = new Worker(arr, k);
return worker.execute();
}
static class Worker{
int[] arr;
int[] workingArr;
int maxDelta;
Worker(int[] arr, int maxDelta){
this.arr = arr;
this.maxDelta = maxDelta;
this.workingArr = Arrays.copy(arr, 0, arr.length);
}
int execute(){
int count = 0;
for(int i = 1; i < this.arr.length - 1; i++){
count += executeLayer(i);
}
}
int executeLayer(int index){
int diff = workingArr[index] - workingArr[index-1];
int diffRange = Math.abs(diff);
int count = 0;
while(diffRange > k){
//get and set the best next move
this.setMove(this.getBestMove(index, diff > 0))
count++;
diff = workingArr[index] - workingArr[index-1];
diffRange = Math.abs(diff);
}
return count;
}
void setMove(int[] newWorkingArr){
this.workingArr = newWorkingArr;
}
int[] getBestMove(int index, boolean decrease){
int value = -1;
if(decrease){
value = 1;
}
int bestScore = Integer.MAX_VALUE;
int[] bestMove = null;
for(int[] move : generateMoves(index, value)){
int moveScore = getScore(index, move);
if(moveScore < bestScore){
bestMove = move;
}
}
return bestMove;
}
Collection<int[]> generateMoves(int index, int value){
ArrayList<int[]> results = new ArrayList<int[]>();
for(int i = 0; i < index; i++){
int[] newMove = Arrays.copy(this.workingArr, 0, this.workingArr.length);
newMove[index] -= value;
newMove[i] += value;
if(isValid(index, newMove)){
results.add(newMove);
}
}
return results;
}
boolean isValid(int index, int[] arr){
for(int i = 1; i < index; i++){
if(Math.abs(arr[i-1] - arr[i]) > this.k){
return false;
}
}
return true;
}
int getScore(int index, int[] testMove){
int score = 0;
for(int i = 0; i < index; i++){
score += Math.abs(this.workingArr[i] - this.arr[i]);
}
return score;
}
}
I will propose a dynamic programming solution which assumes each number is less than k = 100. (as given in the problem).
I create a metrix of size k * n = S[k][n]
S[i][j] = the best optimal solution for A[0] to A[j] when then the A[j] = i ;
in other words jth column in this metrix represents all possible solution for A[0] to A[j] given all possibilities of different value of A[j].
We populate this metric by moving column to column ( fill all the entries in one column and then move to next one).
for ( int j = 0 j < n; j++)
for ( int i = 0; i < 100; i++)
...........................
........... // so we are assuming A[j] = i here.
----------- S[j][i] = infinity;
.......... for each ( int p = 0; p < 100 ; p++)
------------ // lets see whats the best solution we can get if assume A[j-1] = p.
............... // if ( | p - i | <= Target)
................................. ..... if ( S[j-1][p] < S[j][i]) S[j][i] = S[j-1][p];
----------------- else // we will have to incur some cost to bring p within the range of i
........................ .............if ( ( S[j-1][p] + ( | p - i | - Target) ) < S[j][i] ) S[j][i] = S[j-1][p] + ( | p - i | - Target);
}
}
Finally we pick the min value from the last column.
Answer = Min { S[][n] };
complexity would be k*k*n; = pseudo linear.
I am offcourse assuming that in final array B , all the elements will be less than 100.
I am not sure if we can have a polynomial solution for this ( Just a thought not sure)
there is some indexing issue above . I used i instead of j and vice versa in metric.
for ( int j = 0 j < n; j++)
for ( int i = 0; i < 100; i++)
...........................
........... // so we are assuming A[j] = i here.
----------- S[i][j] = infinity;
.......... for each ( int p = 0; p < 100 ; p++)
------------ // lets see whats the best solution we can get if assume A[j-1] = p.
............... // if ( | p - i | <= Target)
................................. ..... if ( S[p][j-1] < S[i][j]) S[i][j] = S[p][j-1];
----------------- else // we will have to incur some cost to bring p within the range of i
........................ .............if ( ( S[p][j-1] + ( | p - i | - Target) ) < S[i][j] ) S[i][j] = S[p][j-1] + ( | p - i | - Target);
}
}
package google;
public class integer_array {
public static void main(String args[])
{
int[] a = new int[] {1,4,2,3};
int p=1;
int cost=0;
for(int i=0;i<a.length;i++)
{
int q=Math.abs(a[i]-a[i+1]);
if(q<=p)
{
break;
}
else
{
q=q-p;
cost=cost+q;
for(int j=1;j<=q;j++)
{
if(j%2==0)
{
a[i+1]=a[i+1]-1;
}
else if(j%2!=0)
{
a[i]=a[i]+1;
}
}
}
}
for (int i=0; i<a.length; i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
System.out.println("cost is=="+cost);
}
}
#define MAXTARGET 100
int MinAdjustmentCost(vector<int> A, int target) {
if (A.empty())
return 0;
int cur = 0;
// dp[i][j]: the minimal adjustment for change A[i] into j; dp[i][j] = min{dp[i-1][k] + |j-A[i]|} s.t. |k-j| <= target
int dp[2][MAXTARGET + 1];
memset(dp, 0x00, sizeof(dp));
for (int i = 0; i < A.size(); i++) {
int next = cur ^ 1;
for (int j = 1; j <= MAXTARGET; j++) {
dp[next][j] = INT_MAX;
for (int k = max(j-target, 1); k <= min(MAXTARGET, j+target); k++)
dp[next][j] = min(dp[next][j], dp[cur][k] + abs(A[i]-j));
}
cur ^= 1;
}
int ans = INT_MAX;
for (int i = 1; i <= MAXTARGET; i++)
ans = min(ans, dp[cur][i]);
return ans;
}
I'm not the writer of the code, but let me try to explain the code because it seems what I thought.
Consider slightly modified problem:
Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target. In addition, the last integer of the array should be "k".
If you have solution for all possible k (say 0-200 as the target is less than 100), you can find the solution of the original problem by checking the solution with all possible k.
Now, DP is quite easy. Given the solution for the sub-array [0..i] of A (for all possible k). Then, how would you compute the solution for the sub-array [0..i+1] of A (for all possible k) using the given solution?
This problem can be solved by dynamic programming.
Let the input be A[0, ..., n - 1] and target. Let the DP[n][100], where DP[i][j] means the minimal adjust sum for A[0], ..., A[i] with the requirement and the last element is j, i.e., A[i] = j, where 0 <=j <=100.
The recursive formula is DP[i][j] = min(DP[i-1][k] + | j- A[i]|), where j - target <= k < = j + target and k > =0. That is the previous adjustment sum can be DP[i-][k] and the current adjustment sum is |j - A[i]|, and we have to make sure j - target <= k <= j + target and k >=0.
The return value is ret = min DP[n-1][j] for 0 <= j <= 100.
Examples:
1 4 2 3 => 2 3 2 3 [2]
1 4 1 3 => 2 3 2 3 [3]
1 4 1 4 => 2 3 3 4 [4]
Algo:
initially converged set to false
While the adjusted array is not converged:
gapFound flag re-set to flase for each whole array check round
check each pair of adjacent elements B[i], B[i+1] (0<=i<n-1)
if their gap>distance, gapFound set to true
if B[i]<B[i+1] B[i] increments by 1
if B[i]>B[i+1] B[i] decreases by 1
if (gapFound is false) converged set to true
calculate the minimum movement distance and return.
*/
void minDist(int* A, int size, int dist) {
bool converged = false;
bool gapFound;
int* B = new int[size];
for (int i=0; i<size; i++)
B[i] = A[i];//duplicate B for modification
while (!converged)
{
gapFound=false;
for (int i=0; i<size-1; i++)
{
if (abs(B[i+1]-B[i])>dist)
{
gapFound=true;
if (B[i]<B[i+1])
B[i]++;
else if (B[i]>B[i+1])
B[i]--;
}
}
if (!gapFound) converged=true;
}
cout << "The original array A is:\n";
for (int i=0; i<size; i++)
cout << A[i] << " ";
cout << "\n";
cout << "The adjusted array B is:\n";
for (int i=0; i<size; i++)
cout << B[i] << " ";
cout << "\n";
int minDist=0;
for (int i=0; i<size; i++)
minDist +=abs(B[i]-A[i]);
cout << "The minimum distance is: " << minDist <<"\n";
}
int main() {
int A[4] = {1,4,1,4};//{1,4,1,3}; //{1,4,2,3};
int distance=1;
minDist(A,4,distance);
}
int id5207197178920960(int[] array, int target){
int[][] dp = new int[array.length][101];
for(int i=1;i<=100;i++){
dp[0][i] = Math.abs(array[0]-i);
}
for(int i=1;i<array.length;i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
for(int i=1;i<array.length;i++){
for(int j=1;j<=100;j++){
for(int k=Math.max(j-target, 1);k<=Math.min(j+target, 100);k++){
dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+Math.abs(j-array[i]));
}
}
}
int res = Integer.MAX_VALUE;
for(int i=1;i<=100;i++){
res = Math.min(res, dp[array.length-1][i]);
}
return res;
}
you can edit this solution at ideone.com/iu9EEK
... don't mind the odd syntax highlighting, it's valid python that runs fine
i had initially used avg, then i found i needed to recalculate the avg, then i found that it wasn't able to find optimal solution if there was an extreme outlier in the array, median seems to work best
comments welcome!
#O(n)
def median(A):
#since we know universe of values in A
maxValue = 100
vals = [0]*(maxValue+1) #we'll ignore index 0
#build histogram of values
n = len(A)
for i in xrange(n):
vals[A[i]] += 1
#build sorted list from histogram
sorted = [0]*n
ptr = 0
for i in xrange(1,(maxValue+1)): #ignoring index 0
for j in xrange(vals[i]):
sorted[ptr] = i
ptr += 1
if n%2==0: #compute median value
return (sorted[n/2] + sorted[n/2 -1])/float(2)
else: #get median value
return sorted[n/2]
#O(n)
def adjust(A, target):
adj = 0
n = len(A)
if n>1:
med = median(A)
for i in xrange(n-1):
diff = abs(A[i] - A[i+1])
if diff>target:
first = abs(A[i]-med)
second = abs(A[i+1]-med)
if first > second:
newadj = diff-target
adj +=newadj
A[i] = A[i]+newadj if A[i]<med else A[i]-newadj
else: #second > first
newadj = diff-target
adj +=newadj
A[i+1] = A[i+1]+newadj if A[i+1]<med else A[i+1]-newadj
return adj
#test it
print adjust( [1,4,2,3] , 1) # 2
print adjust( [1,2,3,2,1] , 1) # 0
print adjust( [1,2,4,2,1] , 1) # 1
print adjust( [3,7,4,2,5,1] , 2) # 4
print adjust( [1,1,1,90] , 2) # 87
print adjust( [3,7,4,2,5,90], 2) # 86
[0,0,0,0,4,5,6,0,6] can be solved as [0,1,2,3,4,5,6,5,6] (cost 11) - your code yields 16...
Pretty similar to smooth array problem. DP solution:
static int count(int[] a, int t, int i, int p, List b) {
if (i == a.length)
return 0;
int m = Integer.MAX_VALUE;
int lo = p - t;
lo = lo > 0? lo: 1;
int hi = p + t;
hi = hi > 100? 100: hi;
if (i == 0) {
lo = 1;
hi = 100;
}
List list = null;
for (int k = lo; k <= hi; ++k) {
List l = new ArrayList();
l.add(k);
int v = count(a, t, i + 1, k, l);
v += Math.abs(k - a[i]);
if (v < m) {
m = v;
list = l;
}
}
b.addAll(list);
return m;
}
vector<int> slew_path(const vector<int>& a, int k) {
size_t n = a.size();
vector<vector<int>> c(n);
auto mn = *min_element(a.begin(),a.end());
auto mx = *max_element(a.begin(),a.end());
int m = mx-mn+1;
for (auto& v : c) v.resize(m);
vector<vector<int>> pi(n);
for (auto& v : pi) v.resize(m);
//fill in last row
for (int j = 0; j < m; j++) {
c[n-1][j] = abs(a[n-1]-j-mn);
pi[n-1][j] = j;
//cout << c[n-1][j] << ',';
}
cout << endl;
for (int i = n-2; i >= 0; i--) {
for (int j = 0; j < m; j++) {
auto x = min_element(c[i+1].begin()+max(0,j-k),c[i+1].begin()+min(m,j+k+1))-c[i+1].begin();
//cout << max(0,j-k) << ',' << x << ',' << min((int)n,j+k+1) << endl;
c[i][j] = abs(a[i]-j-mn)+c[i+1][x];
pi[i][j] = x;
cout << pi[i][j] << ',';
}
cout << endl;
}
auto mxx = min_element(c[0].begin(),c[0].end())-c[0].begin();
cout << '*' << mxx << endl;
vector<int> ret(n);
ret[0]=mxx+mn;
mxx = pi[0][mxx];
for (int i = 1; i <n;i++) {
ret[i] = mxx+mn;
mxx=pi[i][mxx];
}
return ret;
}
O(n*k*m)...could be improved to O(n*m) by using a smart queue to do the windowed min, but uh...lazy.
Since each number in the array is positive integer and no more than 100, we can simply solve this problem straightforwardly.
We can use a 2D matrix for DP.
res[i][j] = sum(|A[k] - B[k]|) where k is from 0 to i, and B[i] equals j which means we change A[i] to j.
For example, res[3][10] = |A[0] - B[0]| + |A[1] - B[1]|+|A[2]-B[2]|+|A[3]-B[3]|. Also, B[3] = j
Then the DP function is:
res[i][j] = min(res[i-1][k] + |A[i] - j|) where |j - k| <= target
After you have finished the matrix, you can get the answer: min(res[A.size()-1][j]) where j from 0 to 100
Let's restate in mathematical term. Assume array A with size of N and array B has the same size and the minimal optimization problem can be stated as,
Objective function: Min(Sigma(|Ai - Bi|)),
where i is within [0, N-1]
Constraint: |Bj - Bj-1| <= TARGET,
where j is within [1, N-1]
Known: A and TARGET
I have crafted a dynamic programming solution. View the details from the following link: cpluspluslearning-petert.blogspot.co.uk/2015/01/dynamic-programming-minimize-sum-of.html
Tests:
void TestCases()
{
{
std::vector<ptrdiff_t> testVec = { 50, 50, 50, 50, 50, 50, 50, 50, 50, 50};
ptrdiff_t target = 5;
assert(MinAbsDiff(testVec, target) == 0);
}
{
std::vector<ptrdiff_t> testVec = { 48, 53, 51, 50, 49, 53, 52, 48, 49, 50 };
ptrdiff_t target = 5;
assert(MinAbsDiff(testVec, target) == 0);
}
{
std::vector<ptrdiff_t> testVec = { 56, 50};
ptrdiff_t target = 5;
assert(MinAbsDiff(testVec, target) == 1);
}
{
std::vector<ptrdiff_t> testVec = { 56, 50, 50 };
ptrdiff_t target = 5;
assert(MinAbsDiff(testVec, target) == 1);
}
{
std::vector<ptrdiff_t> testVec = { 56, 50, 50, 56 };
ptrdiff_t target = 5;
assert(MinAbsDiff(testVec, target) == 2);
}
{
std::vector<ptrdiff_t> testVec = { 55, 77, 52, 61, 39, 6, 25, 60, 49, 47 };
ptrdiff_t target = 10;
assert(MinAbsDiff(testVec, target) == 75);
}
{
std::vector<ptrdiff_t> testVec = { 94, 35, 29, 55 };
ptrdiff_t target = 10;
assert(MinAbsDiff(testVec, target) == 65);
}
{
std::vector<ptrdiff_t> testVec = { 97, 73, 56, 56, 93, 55, 29, 47, 90, 36 };
ptrdiff_t target = 3;
assert(MinAbsDiff(testVec, target) == 157);
}
}
- simon.zhangsm January 18, 2015