## Zynga Interview Question for Software Engineer / Developers

• 1

Country: United States
Interview Type: In-Person

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

This link has DP solution and it works.
onestopinterviewprep.blogspot.com/2014/03/traverse-array-in-shortest-number-of.html

What other questions were asked ?

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

typical dp

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

``````/**
* time: O(N^2)
* space: O(N)
*/
int findMinHopes( int[] arr ){

if( arr == null ){
throw new IllegalArgumentException();
}

if( arr.length == 0 ){
return 0;
}

int[] res = new int[arr.length];

Arrays.fill(res, 1, arr.length, Integer.MAX_VALUE);

for( int i = 0; i < arr.length; i++ ){

for( int j = 1; j <= arr[i]; j++ ){
int index = i+j;

if( index >= arr.length ){
return res[i]+1;
}

res[index] = Math.min(res[index], res[i]+1);
}
}

return -1;
}``````

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

``````int jump(int i, int arr[], int n, int step[])
{
if(i >= n) return 0;
if(arr[i] <= 0) return -1;
if(step[i] > 0 ) return step[i];

for(int dis = arr[i]; dis > 0; --dis){
int tmp = jump(i + dis, arr, n, step);
if(tmp >= 0){
step[i] = step[i] < 0 ? 1 + tmp : min(step[i], 1 + tmp);
}
}
return step[i];
}
int jump(int arr[], int n)
{
if(n == 1) return arr[0] > 0 ? 1 : -1;

int* step = new int[n];
memset(step, 0xff, sizeof(int) * n);
int res = jump(0, arr, n, step);
delete[] step;
return res;
}``````

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

Can be solved through recursion in O(n^2)

Simply put where current index + arr[current index] > n then it can escape the array. So lets add the index of each number to arr[current index].
Scan from left to right and stop at the first occurance of value >= n. From this cell we can escape the array in 1 jump. Now we have to find the min number of jumps to reach this cell, a very obvious case of recursion.

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

This is an incremental question. We can solve it easily in O(n)

``````int minHop(int* array, int length){
int* dp = new int[length];
memset(dp, -1, sizeof(dp));
dp[0] = 0
for(int i = 0; i < length; ++i){
if(dp[i] >= 0){
if(dp[i + dp[i]] == -1 || dp[i + dp[i]] > dp[i] + 1){
dp[i + dp[i]] = dp[i] + 1;
}
}
}
int result = dp[length - 1];
delete dp;
return result;
}``````

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

am not sure how it works, you are not even using the int*array

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

Sorry for the confusion, I misspell the dp , it should be the following. The idea is that we can build the dp array from left to right. But here I made an assumption that all the elements in the array are not negative. Am I right?
For example we have an array
1 2 1 1 1
The index are
0 1 2 3 4
Then dp[0] = 0, dp[0 + array[0]] = dp[1] = -1 initially, then we update it to dp[1] = 1 because we can get to index 1 throught dp[0] + array[0]. Here dp[i] means the minimum steps we need to get to index i.

``````int minHop(int* array, int length){
int* dp = new int[length];
memset(dp, -1, sizeof(dp));
dp[0] = 0
for(int i = 0; i < length; ++i){
if(dp[i] >= 0){
if(i + array[i] < length){
if(dp[i + array[i]] == -1 || dp[i + array[i]] > dp[i] + 1){
dp[i + array[i]] = dp[i] + 1;
}
}
}
int result = dp[length - 1];
delete dp;
return result;
}``````

Actually, this algorithm is not right because we can jump less than array[i] according to the question. But I am assuming that we can only jump exactly array[i]. I am sorry.

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

``````class Hops
{
static int[] arr = { 1, 3, 5, 2, 4 };

public static void mainFunc()
{
int i=0;

while (i < arr.Length)
{
Console.WriteLine(i);

if (i + arr[i] > arr.Length - 1)
{
return;
}

int max, maxInd;
max = maxInd = -1;
for (int j = 1; j < Math.Min(arr.Length-i, arr[i]+1) ; ++j)
{
int step = j + arr[i + j];
if (step > max)
{
max = step;
maxInd = j;
}
}

i += maxInd;
}
}
}``````

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

This can be solved using DP bottoms up approach. Time complexity O(n^2) and Space O(n)

``````public class MininumHopsArrayEnd {

private static int findMinimumHops(int a[])
{
int hops[] = new int [a.length];
Arrays.fill(hops, -1);

hops[0] = 0 ;

for(int i =0; i < a.length; ++i)
{
for(int j = i + 1; j < Math.min(i + a[i] + 1, a.length); ++j)
{
if(hops[j] == -1 || hops[j] > hops[i] + 1)
hops[j] = hops[i] + 1;
}
}

System.out.println("array     :" + Arrays.toString(a));
System.out.println("Hops array:" + Arrays.toString(hops));
System.out.println("Max Hop   :" + hops[a.length - 1]);
return hops[a.length -1];
}

public static void main(String[] args) {
findMinimumHops(new int[]{4,3,2,1,2});
}
}``````

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.