## 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.

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];
}``````

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.

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];
}``````

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

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??

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

what is the i ...*

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?

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

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

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.

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.

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] ;
}``````

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``````

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

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?

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];
}``````

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

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;

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));
}
}``````

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

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

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];
}``````

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;
}``````

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;
}``````

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];
}``````

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];
}``````

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.

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;``````

}

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

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

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));

}

}

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));

}``````

}

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)));
}``````

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
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.

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

This is a algorithm question.

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.