Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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];
}
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];
}
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??
can somebody please explain with example.. i m wondering how this can have multiple solutions unless we are changing the initial array?
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.
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.
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] ;
}
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
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];
}
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
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;
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));
}
}
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];
}
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;
}
#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;
}
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];
}
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.
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;
}
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));
}
}
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));
}
}
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)));
}
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.
Its the Array Hopper problem.
- Sidharth May 19, 2014