## AMD Interview Question for Developer Program Engineers

• 0

Country: India

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

Assuming that

- Ai-1 = 1 when i <0
- Ai+1 = 1 when i > A.length
- The array is unsorted and should not be sorted

One solution is to scan the entire array for the maximum coins, then pop that balloon until no balloons remain.

``````function maxCoins(arr) {
var coins = 0;
while(array.length > 0) {
// find balloon that would yield most coins
var i = findBalloonIndexWithHighestYield(arr); // This function name would probably be abbreviated on a whiteboard

coins += calculateYield(arr, i);
arr.splice(i, 1); // Pop balloon
}

return coins;
}

function findBalloonIndexWithHighestYield(arr) {
var maxIndex = 0;
for(var i = 1; i < arr.length; i++) {
if(calculateYield(arr, i-1) > calculate(arr, i)) {
maxIndex = i;
}
}

return maxIndex;
}

function calculateYield(arr, index) {
var left = 1;
var right = 1;
if (index > 0) {
left = arr[index-1];
}

if (index < arr.length-1) {
right = arr[index+1];
}

return left * right;
}``````

This algorithm would run in O(n^2) since every element is scanned n times in the worst case.

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

Information insufficient. If i-1 and i+1 become adjacent, how do we get the answer 20.

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

int ans(int arr[], int l, int r, int n)
{
int mscore = 0;
for (int i = l + 1; i < r; i++)
{
int cscore = ans(arr, l, i, n) + ans(arr, i, r, n);
if (l == 0 && r == n)
{
cscore += arr[i];
}
else
{
cscore += arr[l] * arr[r];
}
mscore = max(mscore, cscore);
}
return mscore;
}

int main(){

int n;
cin>> n;
int a[n+2];
a=1;
a[n+1]=1;

for(int i=1;i<=n;i++)
{
cin>>a[i];
}

cout<<ans(a,0,n+1,n+1);

}

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

int ans(int arr[], int l, int r, int n)
{
int mscore = 0;
for (int i = l + 1; i < r; i++)
{
int cscore = ans(arr, l, i, n) + ans(arr, i, r, n);
if (l == 0 && r == n)
{
cscore += arr[i];
}
else
{
cscore += arr[l] * arr[r];
}
mscore = max(mscore, cscore);
}
return mscore;
}

int main(){

int n;
cin>> n;
int a[n+2];
a=1;
a[n+1]=1;

for(int i=1;i<=n;i++)
{
cin>>a[i];
}

cout<<ans(a,0,n+1,n+1);

}

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.

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