Amazon Interview Question Software Analysts
Country: India
Interview Type: In-Person
given : array a with index 0 to n-1 for n portal
a[i] = value on portal
lets x = portal being activated
int manaPoint = 0;
for(r=n-1,x=r-1,l=x-1; x>1 ; x--,l--){
manaPoint = a[l] * a[r];
}
ans is 12 for input {1,2,3,4}
no nothing is given about sorted array...it may be in any order
Consider test case
2 100 19 20 10 9 100
Output 15200
public static int max_score(ArrayList<Integer> unused, int[] values, int sum){
if(unused.size() <= 1){
return values[unused.get(0) - 1]*values[unused.get(0) + 1] + sum;
}
else{
int max = 0;
for(int i:unused){
System.out.println("The value of i is :" + i);
ArrayList<Integer> tmp = new ArrayList<>();
for (int j = 0; j < unused.size(); j ++){
if (unused.get(j) != i ){
tmp.add(unused.get(j));
}
}
System.out.println("The value of tmp(0) is :" + tmp.get(0));
int left = i - 1;
int right = i + 1;
System.out.println(tmp.contains(right));
while (tmp.contains(left) && left>0){
left --;
}
while (tmp.contains(right) && right < values.length - 1){
right ++;
}
System.out.println("The left is " + left + "; The right is " + right);
//System.out.println("The length of tmp is " + tmp.size());
int tmp_s = sum + values[left] * values[right];
int result = max_point.max_score(tmp, values, tmp_s);
if (result > max){
//System.out.println("The current max is: " + result);
max = result;
}
}
//Collections.sort(results);
return max;
}
}
Consider the problem reversely, you can image inserting elements between two existing elements, say at the very last, the ending two elements must be multiplied, so at the first step you insert one arbitrary element (the uninserted elements's indexes are stored in the unused list )between the two ending ones. Then recursively inserting unused elements, until the unused list is empty (in other words you restore the original list).
well..it looks like a simple backtracking..so here is what we should do.we select every possible permutation of doors 2 to n-1(since 1 and n cannot be opened so no point considering them) .so we have to find the permutations of n-2 doors excluding 1 and n.
#include<cstdio>
#include<iostream>
#include<vector>
#include<bitset>
#include<cstring>
#define UL unsigned long
using namespace std;
int a[100],n,maxi=0;
bool vis[100];
void dfs(int l,int val,int c)
{
if(c==n-2)
{
maxi=max(val,maxi);
return;
}
else
{
vis[l]=true;
int j,k;
for(int i=1;i<n-1;i++)
{
if(!vis[i])
{
for(j=i-1;vis[j] && j>=0;j--);
for(k=i+1;vis[k] && k<n;k++);
dfs(i,val+a[j]*a[k],c+1);
}
}
vis[l]=false;
}
}
int main()
{
int i,j;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
memset(vis,0,100*sizeof(bool));
for(i=1;i<n-1;i++)
{
if(!vis[i])
{
dfs(i,a[i-1]*a[i+1],1);
}
}
cout<<maxi;
return 0;
}
so here the function dfs maintains the current value(val) and the number of doors already activated(c).whenever c becomes n-2 ie all the doors have been activated we store the val in maxi(only if is greater than current maxi) and then we backtrack.Similarly we keep a track of the activated door numbers using a boolean array vis[] so that we donot activate the same door again.
all suggestions to improve the solution further are welcome.
I know its a DP problem but how to proceed ?
- ram188490 September 28, 2013