Microsoft Interview Question
SDE-2sTeam: Office
Country: India
Interview Type: In-Person
About this problem could you share with us if recruiter gave you hint. Did hi mentioned how many are approximately the images. I see two approaches actully - dynamic programming and brute force soluiton with backtrack. The problem in my dynamic approach is the my state is too big - all possible configurations of pictures (visited, not visited(. Is there a way to decrease state?
As it's mentioned maximum number of images you can see. So considering Landscape and Portrait Image cost, Portrait Image costs least. So we will be able to find maximum number of images only if there are only Portrait images. Now let's consider mathematical equations :-
Cost of Viewing say 3 Portrait images would be = Vp+m+Vp+m+Vp --> Basically 3(Vp)+2(m)
We could consider Vp+m as one combination.
Max Images = IntegerOf(x/(Vp+m)) + y
y is calculated as follows :-
if( (x- IntegerOf(x/(Vp+m)) * (Vp + m) ) = Vp) // Remaining amount is equal to Cost of one Portrait Image
then y = 1
else
y = 0
Is this right solution to calculate. Please comment this is my first answer on CareerCup.
The approach is to go through the list mark the starting element with the value of MAX cost. Now at every image specify the reduction in the amount that you have. Once you have attributes all images with the cost.
It's a two pointer problem where you track two pointers where expanding the second pointer till the amount difference > X. Else move the first pointer. You do not need to double iterate. So this is O(n) problem now.
I tried to make the equation where
n => No of total images which can be viewed which we want to maximize
X = m*(n-1) + (n-a)Vp + a(Rp + Vp)
X => Total cost given in problem
a => No of landscape images that can be viewed
n-a => No of portrait images
But now I am not getting how to proceed further.
public int findMax(int m, int R, int V, int x, char[] arr){
int count = 0, sum =0;
for(char c: arr){
sum+= getCost(c);
}
count += x/sum*arr.length;
x=x%sum;
if(count>0)
x+=m;
if(x < V)
return count;
sum = 0;
int b =0;
for(char c: arr){
if(getCost(c)+sum < x){
sum+=getCost(c);
count ++;
}
else {
sum= sum -getCost(arr[b])+getCost(c);
b++;
}
}
return count;
}
private int getCost(char c, int R, int V, int m){
int cost = V+m;
if(c == 'L')
cost+= R;
return cost;
}
We basically have to find out the subarray with maximum P's such that the total cost of the subarray is < than X. We can solve this using sliding window and try to maximize the number of P's in the window.
- aragorn2308 May 10, 2016