Facebook Interview Question
Software Engineer / Developersyes this makes sense and is probably the least cost in all the given solutions given so far.
But if the array is sorted in reverse order already then I think, it would become more or less the same thing.
Check out the DP solution given here. Seems correct to me.
shashank7s. blogspot. com/2011/05/ wap-to-find-minimum-value-in-window-of . html
I have a O(n^2) solution to it. Though I guess that it can be improved to O(nlogn) somehow, I did not figure it out.
My method is DP. For your testing purpose, I copy the whole code to here. I will very briefly explain the logic later.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> Array;
int arrange (Array arr)
{
arr.push_back(*max_element(arr.begin(), arr.end()));
Array cost_arr(arr.size());
for (int i = 0; i < arr.size(); ++i)
{
int cur_extra_cost = 0;
int cur_upper_bound = arr[i], cur_lower_bound = 0;
int cur_min_cost = unsigned(-1)>>1;
for (int j = i - 1; j >= 0; --j)
{
if (arr[j] > cur_upper_bound)
{
cur_extra_cost += arr[j] - cur_upper_bound;
}else if (arr[j] <= cur_lower_bound)
{
cur_extra_cost += arr[j];
}else{
int cur_cost = cur_extra_cost + cost_arr[j];
cur_min_cost = cur_min_cost > cur_cost ? cur_cost : cur_min_cost;
cur_extra_cost += arr[j];
cur_lower_bound = arr[j];
}
}
cur_min_cost = cur_min_cost > cur_extra_cost ? cur_extra_cost : cur_min_cost;
cost_arr[i] = cur_min_cost;
}
return cost_arr[cost_arr.size() - 1];
}
int main()
{
int arr[] = {7, 5, 9, 3, 1, 8, 6};
//int arr[] = {7, 15, 19, 23, 31, 38, 46};
cout<<arrange(Array(arr, arr + sizeof(arr)/sizeof(int)));
}
The idea is: to compute cost_arr[i], you need to know all potential contributors. I will give a example.
7 2 5 2 8 3 1 6.
To compute cost_arr[7] (for 6), we nee to know these numbers:
5 3 1.
These numbers are computed in this way:
Eliminate all numbers greater than 6 before 6. we get: 2 5 2 3 1.
Then from RIGHT to LEFT, find the increasing sequence: 5 3 1
That's it.
cost_arr[indexof(6)] = min {
cost_arr[indexof(1)] + cost_between(indexof(1), indexof(6)) ,
cost_arr[indexof(3)] + cost_between(indexof(3), indexof(6)) ,
cost_arr[indexof(5)] + cost_between(indexof(5), indexof(6))
}
Whats the final answer.
Still using 7 2 5 2 8 3 1 6.
The final answer is from cost_arr value at these numbers:
8 6
These numbers are computed in this way:
Find from the very RIGHT the increasing sequence:
8 6
final_ans = min{cost_arr[indexof(8)] , cost_arr[indexof(6)]}
It is equivalent to compute cost_arr[last_index] for this sequence:
7 2 5 2 8 3 1 6 INFINITY
That's how it works. I do not want to try to prove its correctness, but we can see its correctness through how it works.
There is some problem in saying this equivalence relation
"The final answer is from cost_arr value at these numbers:
8 6
These numbers are computed in this way:
Find from the very RIGHT the increasing sequence:
8 6
final_ans = min{cost_arr[indexof(8)] , cost_arr[indexof(6)]}
It is equivalent to compute cost_arr[last_index] for this sequence:
7 2 5 2 8 3 1 6 INFINITY "
cost_arr[indexof(INFINITY)] = min {
cost_arr[indexof(6)] + cost_between(indexof(6), indexof(INFINITY)) ,
cost_arr[indexof(8)] + cost_between(indexof(8), indexof(INFINITY))
}
Now cost_between(indexof(6), indexof(INFINITY)) = 0 but cost_between(indexof(8), indexof(INFINITY)) = 3 + 1 + 6
So the above expression becomes
cost_arr[indexof(INFINITY)] = min {
cost_arr[indexof(6)],
cost_arr[indexof(8)] + 10
}
which is the not the same as part 1 of equivalence relation. I think cost_arr[indexof(INFINITY)] calculated above should be the right answer.
Apart from the small correction above the answer seems to be correct . A very good answer and awesome explanation.
I think the greedy strategy will work here.
Iterate from left to right.
For an element at index i, if there's an element at index j(j>i) with value(j)<value(i) , make value(i) = value(j). [cost incements by value(i) - value(j))
Worst case running time O(n^2)
Segment tree can reduce this to O(nlgn).
Wait I think I got it
1.Start from the last of the array (traverse array in reverse direction)
and put the last element in stack S1.
2.For all element a[i],
2.1 Till S1 is not empty or S1.top is lower than a[i], keep popping from S1 and push into Queue Q1.
2.2 If S2 is empty,then simply push a[i] into S1 (no element to the right of a[i] is less than it)
2.3 Otherwise There are two options.
2.3.1 Cost1: For deleting all the elements in the array which are in Q1.
2.3.2 or, Cost2: For reducing a[i] by k, where k=a[i]-Q1.top
Empty Q1.
2.4 Recursively call with either of the state and return whichever has minimum cost.
I now thw recursive call for lookahead with both the state make the solution exponential,
but I think somehow the two cost definition can be converted into DP solution.
Someone help..
OK..I used all that stack and queue trying to do O(n) solution but couldn't,
Here is O(n^2) solution.
Global Cost=0
1. Start traversing from the end in reverse direction.
2. For each element a[i]
2.1 Traverse to its right till a[i] is grater than the travered element
Lets say u reached j. keep the sum1 of all elements from a[i+1] to a[j]
2.2 If sum1=0, continue with the next iteration(step 2) for next left element.
Else go to step 2.3
2.3 Sum2=0
Traverse to its left till a[0], and for all these a[k],
if a[i+1]<a[k], Sum2+=a[k]-a[i+1]
2.4 If sum1<sum2
Global Cost+=sum1 (delete elements from a[i+1] to a[j])
else Global Cost+=(a[i]-a[i+1]) (decrement a[i] to the value of a[i+1])
For each element sum1 finds the cost of deleting all elements smaller than this and right to it.
and sum2 finds the cost, if this number is reduced to the smaller number next to it, then watever
extra cost we will have to add for the elements to the left of it, which now have to be decreased.
{3,2,4,1}
Start with 1, since there is no element smaller in right of it, nothing to do.
Start with 4
there are two options, delete 1 or decrement 4 to 1
option 1: delete 1, cost=1
option 2: If we decrement 4 to 1, we will also have to decrement all the elements
to the left of 4 to 1 in future.
so total cost=(4-1)+(2-1)+(3-1)=6
So we will take option 1 and delete 1. Global Cost=1.
Start with 2, there is no element smaller in right of it, nothing to do.
Start with 3
there are two options, delete 2 or decrement 3 to 2
option 1:delete 2, cost=2
option 2: decrement 3 to 2 (no element in the left of 3 to be considered in future)
so total cost=3-2=1
So we will take option 2. Gloval cost=1+1=2
return global cost=2.
@XYZ the solution you posted uses greedy ans is incorrect. Try it on {5, 3, 5, 3}. The correct way to solve this is DP.
I got an DP in N^2...
It is easy to notice that your maximum value of the solution will be A[i] where 'i' is an index from 0 to n-1;
You DP[i][j] must says the minimum cost considering the solution till n, where the maximum value has the same value of the index[j];
And j >= i
So:
if A[i] <= A[j]:
then
DP[i][j] = min(A[i]+ DP[i-1][j], DP[i-1][i]);
else
DP[i][j] = A[i]-A[j] + DP[i-1][j];
When A[i] <= A[j] you need to notice that you can continue with A[i] at your solution, or you can erase A[i] and then maybe it will be good for you...
Use DP. The following expression seems to work:
A is the input array.
OPT[i] is the optimal cost to generate a sorted array after having looked at the array elements from 0 to i.
OPT[i] = A[i-1] if (A[i] >= A[i-1]) else:
min (
(OPT(i-i) + A[i]),
(OPT[i-1] + (A[0]+A[1]+...A[i-1] - (i-1)*A[i]))
)
The first expression is the cost of deleting the element at position i. The second expression is the cost of decrementing all the elements from 0 to i-1 to make them equal to A[i].
This approach requires only one traversal of the array. You can keep track of A[0]+A[1]+...A[i-1] in a variable as the array A is traversed.
It seems it is still greedy, though looks like dp.
I don't see the array OPT is necessary in ur algorithm.We can simply rewrite it like opt =min{ opt + a[i], opt + (A[0] +...)}.
This is greedy, right?
You're right when you say that the array is not required. But, it is still a dynamic programming solution because
1) it uses the result of sub-problem(s) in order to calculate the final result.
2) We memoize the result of the smaller sub-problems in order to generate the result of bigger problems.
it is still wrong.
First of all, there is a typo, right?
"OPT[i] = A[i-1] if (A[i] >= A[i-1]) "
should be
"OPT[i] = OPT[i-1] if (A[i] >= A[i-1]) "
But it is still wrong:
"(OPT[i-1] + (A[0]+A[1]+...A[i-1] - (i-1)*A[i])) "
what if there exists A[some index] < A[i].
Though this can be fixed by adding some conditions,
it is still wrong:
The fundamental problem of this method is, when you try to compute OPT[i], you cannot only consider OPT[i-1] alone.
consider
7 5 3 1 4, when you compute OPT[4] (for 4), you should not only take OPT[3] into account. Now you get OPT like this:
7 5 3 1 4
0 2 5 6 ???
You got OPT[3] = 6, meaning, for a sorted array, ending at index 3, the min cost is 6, which is correct. But you neglect that, the resultant array at present is 5 5 _ _ (_ means deleted: cost is 7-5 + 3 + 1 = 6). Here comes 4. 4 cannot be appended to this array, since it ends with 5. You only compared 4 with its direct successor 1, but failed to compare with other potential numbers.
I will give my solution in the new post, which is DP too, but totally different ideas.
DP problem. can be solved in O(n*n).
#include <iostream>
using namespace std;
int main()
{
int f[100];
int newA[100];
int a[100] = {3, 2, 4, 1};
int n = 4;
a[n] = INT_MAX;
f[n] = 0;
newA[n] = INT_MAX;
for(int i = n - 1; i >= 0; i--)
{
f[i] = INT_MAX;
for(int j = i + 1; j <= n; j++)
if (a[i] > newA[j])
{
int sum = 0;
for(int k = i + 1; k < j; k++)
sum += a[k];
if (f[j] + sum + a[i] - newA[j] < f[i])
{
f[i] = f[j] + sum + a[i] - newA[j];
newA[i] = newA[j];
}
}
else
{
int sum = 0;
for(int k = i + 1; k < j; k++)
sum += a[k];
if (f[j] + sum < f[i])
{
f[i] = f[j] + sum;
newA[i] = a[i];
}
}
}
cout << f[0] << endl;
}
This can be solved in )(n) using DP and additional memory.
sum[0] = a[0];
numElements[0] = 1;
OPT[0] = 0;
for ( i = 1; i < n ; i++ ) {
if ( a[i] < a[i-1]) {
m1 = OPT[i-1] + a[i]; // delete current element;
m2 = sum[i] - numElem[i-1]*a[i]; // This is the amount we need to delete on all previous elements to be in sorted order;
if ( m1 < m2) {
OPT[i] = OPT[i-1] + m1;
numElements[i] = numElements[i-1];
} else {
OPT[i] = m2;
numElements[i] = numElements[i-1] + 1;
}
}
This is a discrete dynamic programming. See my code and comments
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
void main()
{
// 4, 3, 5, 6 -> 1
// 10, 3, 11, 12 -> 3
// 2, 1, 1, 4, 2, 4, 4, 3 -> 5
// 3,2,4,1-> 2
vector<int> a = { 3,2,4,1 };
vector<int> sorted(a);
sort(begin(sorted), end(sorted));
vector<unordered_map<int, int>> dp(a.size() + 1);
// dicrete dynamic programming
// f(i, j) denotes the sorted array containing a[0...i] with the max element being j.
// The possible values of j are the discrete set of a[i].
for(int j = 0; j < a.size(); ++j) {
for(size_t i = 1; i <= a.size(); ++i) {
// When a[i] >= j, f(i, j) = f(i - 1, j) + a[i] - j; decrement a[i] by a[i] - j. Decrementation must have a
// less cost than removing a[i]
if(a[i - 1] >= sorted[j]) dp[i][sorted[j]] = dp[i - 1][sorted[j]] + a[i - 1] - sorted[j];
// When a[i] < j, f(i, j) = min((f(i - 1, a[i]), f(i - 1, j) + a[i])); do not remove a[i] or remove a[i]
else dp[i][sorted[j]] = min(dp[i - 1][a[i - 1]], dp[i - 1][sorted[j]] + a[i - 1]);
}
}
cout << dp.back()[sorted.back()] << endl;
}
I will go with the following strategy O(n).
1.Start from the last of the array (traverse array in reverse direction)and put the last element in stack.
2.For all element a[i],
2.1 Till stack is not empty or stack.top is greater than a[i], keep popping from stack.
2.2 Now if stack is empty, then simply push a[i] (No element smaller then a[i] to its right)
2.3 Otherwise
2.3.1 If (a[i]-stack.top)>
F*** ,I am lost, either this is way difficult then I thought it to be or I am fu****g dumb.
Any help using Longest Increasing subsequence and then pointing those elements which are not in that LIS and then either:
- Anonymous June 09, 20111. decrement the to a value equal to their leftside or rightside?
2. delete it
which ever is minimal?