Adobe Interview Question for Software Engineer / Developers






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

Use Dynamic Programming.

Let say the given matrix is A, where A[i,j] is the # of coins at [i,j] position and S[i,j] is the maximum number of points for the part of matrix A which is in right-top of [i,j].

Then we have
S[i,j] = A[i,j] + max(S[i+1,j], S[i,j+1])

start from i=1,j=1 and take care of boundary conditions.
That will give a O(n^2) solution.

Without using DP it is O(2^n).

- Anil August 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anil Yes correct solution.

- Anonymous January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

0 9 0
0 0 2
0 2 1
1 1 0

What about this? i am assuming that we are starting from 3,0.

- Harmit January 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int collectMax(int A[][], int x, int y){
       if(x<0|| x>A[].length || y<0 || y > A[].length) return 0;
       int sum = 0;
       sum = A[x][y];
       return sum+ (int)Math.max(collectMax(x+1,y), collectMax(x,y+1));
}

- Ritesh May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working code:
Use the function
a[i][j]+max(a[i-1][j],a[i][j+1]);


public class CoinsCollect {

static int[][] coins={{1,5,3},{4,5,2}};

static int rows=2;
static int columns=3;
private static int max(int i,int j)
{
if(i<0 || j>=columns)
return 0;
else
return coins[i][j]+Math.max(max(i-1,j),max(i,j+1));
}
public static void main(String[] args)
{
System.out.println(max(rows-1,0));
}
}

- y so serious May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mathematical formula for this type of problem could be the number of ways of reaching from bottom right to the top left. Allowed directions are two, that is up and right.
For M rows, N columns, number of ways:
(M + N)! /( M! * N!)

It of course, doesn't consider the constraint of picking maximum gold coins. It is just the number of ways possible.

- catlover August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dict={}
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        left_neighbor = (dict[(i,j+1)] if dict.has_key((i,j+1)) else 0)
        down_neighbor = (dict[(i+1,j)] if dict.has_key((i+1,j)) else 0)
        # last row & last col
        if i == (n-1) and j == (n-1): dict[(i,j)] = A[i][j]
        # last row
        elif i == (n-1):
                dict[(i,j)] = A[i][j] + left_neighbor
        # last col
        elif j == (n-1):
            dict[(i,j)] = A[i][j] + down_neighbor
        # general case
        else:
            dict[(i,j)] = A[i][j] + max(left_neighbor,down_neighbor)

print "max possible coins =", dict[0,0]

- dynamic programming solution in o(n^2) (no recursion) November 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dynamic programming solution in o(n^2) - without using a recursive function:

dict={}
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        left_neighbor = (dict[(i,j+1)] if dict.has_key((i,j+1)) else 0)
        down_neighbor = (dict[(i+1,j)] if dict.has_key((i+1,j)) else 0)
        # last row & last col
        if i == (n-1) and j == (n-1): dict[(i,j)] = A[i][j]
        # last row
        elif i == (n-1):
                dict[(i,j)] = A[i][j] + left_neighbor
        # last col
        elif j == (n-1):
            dict[(i,j)] = A[i][j] + down_neighbor
        # general case
        else:
            dict[(i,j)] = A[i][j] + max(left_neighbor,down_neighbor)

print "max possible coins =", dict[0,0]

- gadi.sirota November 06, 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