Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Its the Array Hopper problem.

- Sidharth May 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

Dynamic Programming
C[i] = for all j->[0,i) & i-j > Arr[j] min{C[j] + 1}

int MinSteps(vector<int> vecNum)
{
	int size = vecNum.size();
	vector<int> vecSteps(size);
	vecSteps[0] = 0;
	for (int i = 1; i < size; i++)
	{
		int min = i;

		for (int j = 0; j < i; j++)
		{
			if (i - j <= vecNum[j])
			{
				if (min > vecSteps[j] + 1)
					min = vecSteps[j] + 1;
			}
		}

		vecSteps[i] = min;
	}
	return vecSteps[size - 1];
}

- Brandy May 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Dynamic programming (one additional array to remember on position i the lower number of hops needed to reach the end) or naive recursive approach witm memoization dictionary (which is actually very similar to dynamic programming).. both cases O(N^2) time, O(N) space.

- tpcz May 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

Naive Recursion

public static int minJums(int [] a , int i){
	if (i == a.length-1) return 0;

	int min = a.length;
	for (int k = i+1; k<=a.length && k < = i + a[i] ; k++)
		min = Math.min (min, minJumps (a,k));

	return min+1;
}

Dynamic Programming: Time: O(N^2). Space: O(N)

int minJump(int [] a){
	int [] = new jump [n];
	jump [n-1] = 0;

	for (int i=n-2; i>=0; i--){
		int min = a.length;
		for (int j=i+1; j<n && j<=i +a[i]; j++)
			min = Math.min (min, jumps[j]);
		jumps[i]=min+1;
	}
	return jumps[0];
}

- Bhaskar May 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the included in the method header in the recursion method??
and how can I develop a method that is recursive and using the dynamic programming in the same time??

- Amr Talaat November 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the i ...*

- Amr Talaat November 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

can somebody please explain with example.. i m wondering how this can have multiple solutions unless we are changing the initial array?

- Viky May 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Got it.. for every a[i] 1 to a[i] are the jump option i can have.
Cool.

- Viky May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I'm looking at this as a graph problem (shortest path in unweighted DAG). It can be solved in O(V + E) by running a topological sort and then BFS. Even better, the nodes are already topologically sorted.
Worse case scenario is a graph where all first V - 2 vertices point to the second to last and that one point to the last one. The array for this case would be

V-2, V-3, V-4,..., 2, 1, 1, x

. This graph will have O(V^2) edges and that is going to dominate the running time complexity.

- george May 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this question lacks of key information. For example, is that I can only follow the steps that a value gives me or I can safely ignore it is not a optimal choice; is there negative values in the array, meaning I could be set back; is there any value that is larger than the size of the array, if so, should I ignore it as invalid steps or should I take it and claim I reach the end of the array.

It could be DP, there might be a greedy way, or it could be just a sequential traverse. It depends on the attributes of those values and the rule of moving.

- Avaln May 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public int jump(int[] A) {
		 if (A.length == 0) {
	    		return 0 ;
	    	}	    	
	    	if (A[0] == 0 || A.length == 1) {
	    		return 0 ;
	    	}	    	
	       int [] dp = new int [A.length] ;
	       dp[0] = 0;
	       if (A[0] >= A.length){
	    	   dp [A.length - 1] = 1;
	       } else {
	    	   dp [A[0]] = 1;   
	       }
	       
	     int maxSpan = 0;	     	    
	     for (int i = 1; i < A.length ; ++i) {
	    	 if (A[i - 1] + i - 1 <= maxSpan ){
	    		 continue ;
	    	 }	    	 
	    	 maxSpan = A[i -1] + i - 1 >= A.length ?  A.length -1 : A[i -1] + i - 1;
	    	 for (int j = i ; j <= maxSpan ; ++j) {
	    		 if (dp[j] == 0) {
	    			 dp[j] = dp[i - 1] + 1 ;
	    		 }else {
	    			 dp[j] = dp[i - 1] + 1 < dp[j] ? dp[i - 1] + 1 :  dp[j];	 
	    		 }	    		 
	    	 }	    	
	     }	    
	       return dp[A.length - 1] ;   
	 }

- Anonymous June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Remember to check for Cycles

def reach_the_end(path):
    visited = {}

    def start_moving(path, current_location):
        if current_location >= len(path):
            print "moved beyond the path"
            return 0
        elif current_location == len(path) - 1:
            print "Reached the end"
            return 0
        else:
            moves = path[current_location]
            if current_location + moves in visited:
                print "Looks like we have visited this before, path has cycle"
                return 0
            visited[current_location + moves] = current_location
            start_moving(path, current_location + moves)
    start_moving(path, 0)
    return visited

- byteattack May 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What happens if array : {2,2,-2,1,1}.
your program will return cycle where as the solution is 2 steps? Still trying to understand the problem. Does it have to start from beginning? whats the point?

- AlgoAlgae May 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int minStepCount(int[] arr)
	{
		int[] S = new int[arr.length];
		S[0] = 0;
		for (int i = 1; i < arr.length; i++) {
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				if (arr[j] + j >= i && S[j] < Integer.MAX_VALUE && S[j] + 1 < min ) {
					min = S[j] + 1;
				}
			}
			S[i] = min;
		}
		return S[arr.length -1];
	}

- Afaque May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

minSteptoEnd(int[] arrays){
if(arrays==null || arrays.length==0){return 0;}
if(arrays.length=1) return 1;
return minSteptoEndIn(0, arrays.length-1,arrays,0);
}

int minStepToEndIn(int start, int end, int[] arrays, int steps){
if(start>=end){
return steps;}
}

int min=Integer.MIN_VALUE;
for(int i =1;i<arrays[start];i++){
int curMin=minStepToEndIn(start+i,end,array,step+1);
if(min<curMin){
min=curMin;
}
}

return curMin

- ZhouZhou May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

minSteptoEnd(int[] arrays){
if(arrays==null || arrays.length==0){return 0;}
if(arrays.length=1) return 1;
return minSteptoEndIn(0, arrays.length-1,arrays,0);
}

int minStepToEndIn(int start, int end, int[] arrays, int steps){
if(start>=end){
return steps;}
}

int min=Integer.MIN_VALUE;
for(int i =1;i<arrays[start];i++){
int curMin=minStepToEndIn(start+i,end,array,step+1);
if(min<curMin){
min=curMin;
}
}

return curMin;

- ZhouZhou May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Dynamic Programming.
Establish a DP record array:
min[] to represent how many min steps it needs to reach the current position.
steps[] is the input array.

We get the recurrence formula
min[i] = min{min[k] where k = 0, 1, 2, ..., i-1 if k+steps[k] >= i} + 1

Base condition:
min[0] = 0;

DP gives O(n^2) time complexity and O(n) space complexity.

2. Greedy
Every time we make the greedy decision:
for example we have steps[] = {2, 0, 1, 4}
when we are at index = 0, we can reach index 0, 1, 2.
Check each index and find they can reach 2, 1, 3 respectively. The last one can reach farthest. So we make a greedy decision to jump to index 2. We continue the jumping process til we reach the end of the array.

Greedy method takes O(n) time and O(1) space

Here's the Java code:

import java.util.Arrays;

public class MinSteps{
    public int minSteps(int[] steps){
        int[] min = new int[steps.length];
        Arrays.fill(min, Integer.MAX_VALUE);
        min[0] = 0;
        for (int i = 1; i < min.length; i++){
            for (int j = 0; j < i; j++){
                if (j + steps[j] >= i){
                    min[i] = min[j] + 1;
                    break;
                }
            }
        }
        return min[min.length-1] == Integer.MAX_VALUE ? -1 : min[min.length-1];
    }

    public int greedyMinSteps(int[] steps){
        int idx = 0;
        int minStep = 0;
        while (true){
            int maxReach = -1;
            int maxIdx = idx;
            for (int i = 0; i <= steps[idx]; i++){
                int curIdx = idx + i;
                int reach = curIdx + steps[curIdx];
                if (reach > maxReach){
                    maxReach = reach;
                    maxIdx = curIdx;
                }
            }
            if (idx == maxIdx) return -1;
            idx = maxIdx;
            minStep++;
            if (idx >= steps.length-1) break;
        }
        return minStep;
    }

    public static void main(String[] args){
        int[] steps = {2, 0, 1, 4};
        MinSteps ms = new MinSteps();
        System.out.println(ms.greedyMinSteps(steps));
    }
}

- njuprincerain May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes greedy works for this problem. Theres no need for extra memory

- james.porcelli@stonybrook.edu September 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int minMoves(int[] moves) {
        if (moves.length <= 1) {
            return 0;
        }
        int[] count = new int [moves.length];
        count[0] = 0;
        for (int i = 1; i < moves.length; i++) count[i] = Integer.MAX_VALUE;
        for (int i = 1 ; i < moves.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + moves[j] >= i)
                    count[i] = Math.min(count[i], count[j] + 1);
            }
        }
        return count[moves.length - 1];
    }

- rajniconnect June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ program for the solution to this problem:

#include<iostream>
using namespace std;
int main()
{
    int n,A[100];
    cin>>n;
    int max=-9999999;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        if(A[i]>max)
        {
            max=A[i];
        }
    }
    //cout<<max<<endl;
    cout<<"The given array is:\n";
    for(int i=0;i<n;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
    int B[100]={0};
    for(int i=0;i<n-1;i++)
    {
        B[i]=A[i];
    }
    for(int i=n-2;i>=0;i--)
    {
        if(i+A[i] >= n-1)
        {
            B[i]=1;
        }
        else
        {
            int min=max;
            bool inside = false;
            for(int j=i+A[i];j>i;j--)
            {
                if(B[j]!=0 && B[j]<=min)
                {
                    min=B[j];
                    inside = true;
                }
            }
            if(inside)
            {
                B[i]=min+1;
            }
        }
    }
    cout<<"The distance array is:\n";
    for(int i=0;i<n;i++)
    {
        cout<<B[i]<<" ";
    }
    cout<<endl;
}

- Sourabh Das June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main(){
	int n;
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int dp[n];
	if (n == 0 || a[0] == 0){
		printf("Not Possible\n");
	}
	else{

		for(int i=0;i<n;i++)dp[i]=0;
		for(int i=1;i<n;i++){
			for(int j=0;j<i;j++){
				if(j+a[j]>=i){
					//get the first j to reach till i and break
					dp[i]=dp[j]+1;
					break;
				}
			}
		}
		printf("%d\n",dp[n-1]);
	}
	return 0;
}

- for.the.sake.92 June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int solve(int arr[]) {
		int n = arr.length;
		int sol[] = new int[n];
		Arrays.fill(sol, Integer.MAX_VALUE);
		sol[0] = 0;
		for (int i = 0; i < n; i++) {
			int k = i + arr[i];
			for (int j = 0; j <= k && j < n; j++)
				sol[j] = Math.min(sol[j], sol[i] + 1);
		}
		return sol[n - 1];
	}

- KhadarBasha June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int minJumps(int[] arr)
	{
		int minArray[]=new int[arr.length];
		Arrays.fill(minArray,Integer.MAX_VALUE);
		for(int i=arr.length-2;i>=0;i--)
		{
			if(arr[i]+i >= arr.length-1)
				minArray[i]=1;
			else
			{
				for(int j=i+1; j-i <= arr[i];j++)
					minArray[i]=Math.min(minArray[i], minArray[j]+1);
		
			}
			
		}
		return minArray[0];	
	}

- dinesh June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm assuming this is the description:

From: https: //github . com/ rohitsinha54/ ArrayHopper
Problem Description

You are given an array of integers with values greater than or equal to 0, for example:

[5, 6, 0, 4, 2, 4, 1, 0, 0, 4]

You will develop and implement an algorithm to traverse the array in the shortest number of “hops” starting at index 0, where traversal is defined as follows:

Start at the first (0th) index of the array, look at the array value there, and you can hop forward to any array index that is no farther than that value away. So in this example, you start at index 0 containing the value 5 and can now consider hopping to any of indices 1 through 5 inclusive.
If you choose to hop to index 3, it contains the value 4 and you can next hop up to 4 more spots from your current index (3)—so you now consider indices 4 through 7 as next steps in your sequence.
Once you can legally hop beyond the last array element, you have successfully traversed the array.

Your job is to compute the minimum-length sequence of hops that successfully traverses the array starting from index 0, or determine that there is no such sequence.

Your algorithm must identify a minimum-hops solution, but can choose arbitrarily among solutions with the same number of hops.

- cool.fire.ra July 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int jump(int[] A) {
	        int jd = A[0];
	        int i = 0;
	        int jmps = 1;
	        int m = 0;
	        
	        if(A.length == 1){
	            return 0;
	        }
	        
	        if(i + jd >= A.length - 1){
	            return 1;
	        }
	        
	        //O(n)
	        while(i < A.length - 1){
	            int n = i;
	            int j = i + 1;
	            for(; j <= jd && j < A.length - 1; j++){
	                if((A[j] + j) > m){
	                    m = A[j] + j;
	                    n = j;
	                }
	                
	                if(m >= A.length - 1){
	                    return jmps + 1;
	                }
	            }
	            jd = m;
	            m = 0;
	            jmps++;
	            i = n;
	        }
	        return jmps;

}

- james.porcelli@stonybrook.edu September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no need for extra memory. O(N) time, O(1), space

- james.porcelli@stonybrook.edu September 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinHop {

static int arr[]={6,5,1,6,8,2,3};


public static int DP(int a1[]){

int minHop[]=new int[a1.length];
Arrays.fill(minHop, Integer.MAX_VALUE);

minHop[0]=0;
for(int i=0;i<a1.length-1;i++){

for(int j=i+1;j<a1.length;j++){

if(a1[i]==j-i){
minHop[j]=Math.min(minHop[j],1+minHop[i])==0?1:Math.min(minHop[j],1+minHop[i]);
}else

minHop[j]=Math.min(minHop[j],minHop[j-1]+1);
}}





return minHop[a1.length-1];
}


public int Greedy(int a2[]){


return 0;
}




public static void main(String[] args){

System.out.println(DP(arr));

}

}

- Prakhar Asthana September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinHop {

	static int arr[]={6,5,1,6,8,2,3};
	
	
	public static int DP(int a1[]){
		
		int minHop[]=new int[a1.length];
		Arrays.fill(minHop, Integer.MAX_VALUE);
		
		minHop[0]=0;
		for(int i=0;i<a1.length-1;i++){
			
			for(int j=i+1;j<a1.length;j++){
				
				if(a1[i]==j-i){
				minHop[j]=Math.min(minHop[j],1+minHop[i])==0?1:Math.min(minHop[j],1+minHop[i]);
				}else
					
				minHop[j]=Math.min(minHop[j],minHop[j-1]+1);
			}}
			
			
		
		
		
		return minHop[a1.length-1];
	} 
	
	
	public int Greedy(int a2[]){
		
		
		return 0;
	}
	
	
	
	
	public static void main(String[] args){
		
		System.out.println(DP(arr));
	
	}

}

- Prakhar Asthana September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution

int array_hopper(int* a, const int n)
{
    if (nullptr == a || n <= 1) return 0;
    int ei = 0, nei = 0, count = 0;
    for (auto i = 0; i < n; ++i)
    {
        if (i + a[i] >= n - 1) { ++count; break; }
        if (i + a[i] > nei) nei = i + a[i];
        if (i == ei)
        {
            if (ei == nei) return -1;
            ++count;
            ei = nei;
        }
    }
    return count;
}

void test_array_hopper()
{
    int a[] = { 2, 4, 1, 2, 3, 2, 4, 2 };
    assert(3 == array_hopper(a, sizeof(a) / sizeof(int)));
    int b[] = {1, 2, 0, 4, 2, 4, 1, 0, 0, 4};
    assert(4 == array_hopper(b, sizeof(b) / sizeof(int)));
    int c[] = { 1, 2, 0, 2, 2, 3, 1, 0, 0, 4 };
    assert(-1 == array_hopper(c, sizeof(c) / sizeof(int)));
}

- Omri.Bashari June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Question is either stupid or incomplete but in system level , actually you don't know the array length.

I mean array in general does not have bound checking . Its just a simple mathematical calculation of base_address + number_of_hope * data_type.

So Question can be subjective here.. In Assembly Language.. it would be
1> LD M1[number_of_hops]
2> LD M2[data_type]
3> MUL M1 M2
4> LD M2[base_address]
5> ADD M1 M2
6> RET

However, in application level its just one step

Languages like java usage different memory management which basically is vector so it internally track the member variable called length to give an impression that it does have the information about the last position.

- hprem991 May 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a algorithm question.

- oceanmaster.wang May 26, 2014 | Flag


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