Zynga Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
/**
* 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;
}
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;
}
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.
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;
}
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.
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;
}
}
}
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});
}
}
This link has DP solution and it works.
- Wellwisher March 27, 2014onestopinterviewprep.blogspot.com/2014/03/traverse-array-in-shortest-number-of.html
What other questions were asked ?