Google Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
6
of 6 vote

//dp[i][j]: the minimal adjust cost on changing A[i] to 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 dp[A.size()][MAXTARGET+1];
    for (int i = 0; i <= MAXTARGET; ++i)
        dp[0][i] = abs(i-A[0]);

    for(int i=1; i<A.size();i++){
        for(int j=0;j<=MAXTARGET;j++){
            dp[i][j] = -1;
            if (dp[i-1][j] < 0) continue;
            for (int k = max(j-target, 0); k<=min(MAXTARGET, j+target); ++k) {
                dp[i][k] = min(dp[i][k], dp[i-1][j] + abs(A[i]- k));
            }
        }
    }
    int ret = -1;
    for (int i = 1; i <= MAXTARGET; i++) {
        ret = min(ret, dp[A.size()-1][i]);
    }
    return ret;
}

- simon.zhangsm January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Alex M. April 26, 2016 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

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;
}
}}

- Gaoshi December 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't suppose you could provide the proof (or a blurb about) why this thing provides an optimal substructure and overlapping sub-problems?

- Anonymous December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brilliant !

- Vaidyanathan January 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Do you need to minimize the adjustment cost or minimize |A[i]-B[i]| ?

- Anonymous December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the goal is to minimize the sum of all adjustments.
I have a feeling that this question can be solved with DP.

- zg911 December 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The sum of |A[i] - B[i]| *is* the adjustment cost.

- Jeff December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Mohit December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

//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;
}

- Anonymous January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sounds like the perfect problem to apply A* algorithm. They even give you the heuristic function.

- Alb_Erc December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the goal is to minimize sum(|Ai-Bi|) where 0 <=i<n

- rjrush December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Gambler December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- ssorower December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

- ssorower December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the input sequence of : 1 2 3 4 5 6 7 8?
The return should be the same as input.

- Jay December 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I might be missing something, but What difference does it make to start from the middle or from the beginning?

- alonsomh December 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- gigi84 December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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).

- Dot December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gigi84 December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- loneranger December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The DP solution I've described is contained in the method

findSolution

, while the non-DP exponential solution is contained in the method

findSolutionExp

- loneranger December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gigi84 December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- loneranger December 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Loneranger, the time complexity, don't you think it should be O(m * n * target), since you have a inner loop to find the min value for each m, n?

- imlyc December 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jay December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- zortlord December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}
}

- bjovi December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- andreytim December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- zortlord December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Adiser December 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}
}

- Adiser December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
    

}

- Davi_singh December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we constraint the target number zero, this problem turns to find the median. I believe there is a certain way relating median.

- allen.lipeng47 December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
    }

- simon.zhangsm December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the algorithm.
Thanks!

- Charu Mehndiratta January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Someone else, January 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Polarcodes February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

- Kevin February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- dshao3@asu.edu June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- dereknheiley December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

[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...

- Anonymous December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good counter example!

- dereknheiley December 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
	}

- lainexperiment December 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- IdeaHat January 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- southern9cross January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Peter Tang January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
    }
}

- Peter Tang January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int cnt=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]-arr[i-1]>target)
{
arr[i]=arr[i-1]-target;
cnt++;
}
else
{
arr[i]=arr[i-1]+target;
cnt++;
}
}
return cnt;

- Anonymous January 18, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More