Zynga Interview Question for Software Engineer / Developers


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 ?

- Wellwisher March 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typical dp

- Anonymous March 27, 2014 | Flag
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;		
	}

- m@}{ March 27, 2014 | Flag Reply
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;
}

- uuuouou March 27, 2014 | Flag Reply
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.

- kr.neerav March 27, 2014 | Flag Reply
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;
}

- ravio March 27, 2014 | Flag Reply
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

- kr.neerav March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ravio March 28, 2014 | Flag
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;
            }
        }
    }

- jiangok2006 March 27, 2014 | Flag Reply
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});
	}
}

- Anonymous April 18, 2014 | 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