Ebay Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
keep track of the maximum point you can reach,say max,
update max as u iterate through the array,
if max crosses n then return 1(which says we can reach)
if the current pointer >max(return 0,which says we can't reach the end n),
for(i=0;i<n;i++)
{
max=MAX(i+arr[i],max);
if(max>n) return 1;
if(i>max) return 0;
}
The solution given above doesn't seem correct.
Here is my modification of the solution that was accepted in the OJ at LeetCode
#define UINT unsigned int
UINT MAX (UINT a, UINT b){
return ((a>b)?a:b);
}
class Solution {
public:
bool canJump(int A[], int n) {
UINT max = 0;
for(UINT i = 0; i <= max; i++){
if (max>=n-1){
return true;
}
max = MAX(i+A[i], max);
}
return false;
}
};
no,his/her solution is right,
max is initially a[0](0 in this case),hence it will return 0;
public static boolean reachEnd(int[] input){
int step = 0;
int lastIndex = input.length-1;
while(step < lastIndex){
if(input[step] == 0){
return false;
}
step += input[step];
}
return step == lastIndex;
}
The follow up question would be:
Find the minimum number of jumps to reach the end.
Any one?
Regarding the follow up question - I think it can also be done in O(n) worst-case complexity.
Note: The solution is for the case where the "last index" is outside the array. In other words - finding the minimum number of jumps required to jump out of the array. It should be easy to modify the algorithm if the last index means the last index in the array.
The main difficulty here is finding out the minimum number of jumps that are required in order to reach each index in the array. If we knew that, then the moment we reach an index from which we can jump out of the array we can return the minimum number of jumps required to reach this index incremented by 1 (notice that the minimum number of jumps increases as the index increases).
To do it efficiently we define a queue of pairs (end,jump). We iterate from the beginning of the array and maintain a max variable which holds the maximum reachable index. Whenever we encounter an element arr[i] from which we can jump further than the max (i+arr[i]>max), we update the max variable and add the element (i+arr[i],jumps+1) to the queue.
What is jumps? jumps+1 would be the minimum jumps required to reach i+arr[i] when the last jump is from i to i+arr[i].
How do we find jumps? We remove elements from queue until the element in the top of the queue - (end,jumps) satisfies end>=i. This means that jumps is the minimum jumps required to reach the index i.
Code:
public static int getMinimumNumOfJumps(int[] arr){
if ((arr==null) || (arr.length==0) || (!canJumpOut(arr))){
return -1;
}
Queue<Index> queue = new LinkedList<>();
queue.offer(new Index(0,0));
int max = 0;
for (int i=0;(i<arr.length) && (max<arr.length);i++){
while (queue.peek().getEnd()<i){queue.poll();}
if (i+arr[i]>max){
max = i+arr[i];
queue.offer(new Index(i+arr[i],queue.peek().getJumps()+1));
}
}
return queue.peek().getJumps()+1;
}
Notes:
canJumpOut() - returns true if it's possible to jump out of the array and false otherwise (the original question). It's implementation is similar only without the queue.
Index class - just a simple class which contains two int fields - end and jumps. The methods getEnd() and getJumps() return the corresponding end and jumps values. The constructor is Index(int end, int jumps).
Complexity: At most we can add 1 element to the queue per iteration. This means that we can remove at most n elements from the queue (in total). Thus the run-time complexity is O(n) worst-case. Space complexity is O(n) worst-case as well.
Hopefully I haven't missed something.
public int func( int [] a )
{
int i, j, k;
/* where i is curr index
j is prev indices
k is number of indices
needed to jump over 0 slot
*/
for (int i = 0; i < strlen(a); i++)
{
if ( i == strlen(a) - 1 )
return true;
if ( a[i] > 0 )
continue;
else //a[i] == 0
{
j = i - 1;
k = 1;
while ( a[j] <= k )
{
j--;
k++;
if ( j < 0 )
return false;
}
}
}
}
At any cell the maximum reachable position relative to the current cell (the max_jump) is the greater of one less than the max_jump of the previous cell, or the value in the current cell.
If the max_jump reaches zero before the end of the array is reached, the problem is unsolvable.
Python
def can_reach_end(data):
max_jump = 0
for n in data:
max_jump = max(max_jump - 1, n)
if max_jump == 0:
return False
return True
Some test data for you. Solvable examples:
[1, 3, 3, 0, 0, 2, 0, 4, 1, 3, 0]
[2, 0, 3, 5, 0, 0, 3, 0, 0, 6, 3]
[3, 1, 4, 3, 5, 0, 0, 0, 3, 1, 0]
Unsolvable examples
[4, 4, 0, 3, 0, 1, 2, 2, 1, 0, 0]
[3, 2, 0, 1, 4, 3, 1, 0, 0, 0, 0]
[5, 2, 0, 0, 1, 0, 6, 0, 0, 2, 9]
Well, need to ask the interview if "reach the last" mean land on top of it, or hurdle it and can go past it. Depending on that answer, the solution will be different. Assume that you have to land on it exactly, then:
bool landOnLast(int* arr, int len)
{
for(int i = 0; i < len; i++)
{
if (arr[i] == 0)
return false; // sorry, you're stuck
if ( (arr[i] + i) > len;
return false;// sorry, you're past the length of the array
i += arr[i];
}
return true;
}
If you can go past the end of the array, then it's like this:
bool landOnLast(int* arr, int len)
{
for(int i = 0; i < len; i++)
{
if (arr[i] == 0)
return false; // sorry, you're stuck
if ( (arr[i] + i) > = len;
return true; // you've hurdled the array or at the end.
i += arr[i];
}
return true;
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
/**
*
* @author midhulak
*/
public class findLastIndex {
public static int a[] = {1,1,4,3,1};
public static boolean getLastIndex(int i){
boolean flag = false;
if(i > a.length-1){
System.out.println("the position is > than the legth");
flag=false;
return flag;
}
else if(i == a.length-1){
flag=true;
return flag;
}
return getLastIndex(i+a[i]);
}
public static void main(String args[]){
System.out.println(getLastIndex(0));
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
/**
*
* @author midhulak
*/
public class findLastIndex {
public static int a[] = {1,1,4,3,1};
public static boolean getLastIndex(int i){
boolean flag = false;
if(i > a.length-1){
System.out.println("the position is > than the legth");
flag=false;
return flag;
}
else if(i == a.length-1){
flag=true;
return flag;
}
return getLastIndex(i+a[i]);
}
public static void main(String args[]){
System.out.println(getLastIndex(0));
}
}
package com.knowledgebase.company.ebay;
/**
* Leetcode: Jump Game.
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
* @author rachana
*
*/
public class JumpGame {
public static void main(String argv[]) {
// usecases
//int[] values = new int[]{1,2,0,3,1,0};
//int[] values = new int[]{1,1,1,1,1,1};
//int[] values = new int[]{1,1,1,1,1,0};
//int[] values = new int[]{1,1,0,1,1,0};
int[] values = new int[]{1,2,1,3,1,0};
if(canJump(values)) {
System.out.println(" Can jump");
} else {
System.out.println(" CANNOT jump");
}
}
private static boolean canJump(int[] values) {
//now check
for(int i=0;i<values.length-1;) {
if(values[i]>0) {
i = i+values[i];
} else if(i < values.length-2 && values[i]==0) {
return false;
}
if(i>=values.length-1) {
return true;
}
}
return false;
}
}
I think this is a bit complicated than the above solutions: Following would be the different ways:
lets take the array of size 10 with following elements:
2 2 0 1 1 1 1 1 1 1
Now,
1. if we take the first element 2 and jump to index 2 ( zero based index), the value at index 2 is 0 , so we would not be able to reach the end
2. So we need to try the second max of the first element which is 2-1 = 1, and jump to index 1.
3. At index 1 , we have 2 as max, so again we try to jump 2 from there which gives us an index 3 where the value is 1, and from there on we make 1 jump and reach the end.
4. So, the conclusion is whenever we get to an index, we need to decrement the value in that index to 1 so that if we do not make it till the end, we can iterate through the array again with the decremented values and try to reach the end using that.
The code is as below in Java:
public class JumpGame {
static Scanner scan = new Scanner(System.in);
public static boolean jumpGame(List<Integer> arr)
{
int temp = arr.get(0);
int position =0;
while(temp >0 && (temp + position) <arr.size())
{
if (arr.get(temp + position) !=0)
{
arr.set(position, arr.get(position)-1);
position=position+temp;
temp = arr.get(position);
}
else
{
arr.set(position, arr.get(position)-1);
position=0;
temp=arr.get(0);
}
}
if ( temp +position >= arr.size())
{
return true;
}
else if(arr.get(0)!= 0)
{
return jumpGame(arr);
}
return false;
}
public static void main(String[] args) throws IOException
{
System.out.println("Input the array elements which represent jumps: ");
List<Integer> arr = new ArrayList<Integer>();
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
arr.add(scan.nextInt());
boolean result = jumpGame(arr);
}
path = []
arr = [2,0,5,0,0,0,0];
def go(index):
global arr;
if(index == len(arr)-1):
path.append((index))
return True
if(index >= len(arr)):
return False
if (arr[index]==0):
return False;
step = arr[index]
while( step >0 ):
status = go(index+step)
if(status) :
path.append((index,step))
return True
step -= 1
else:
return False
print go(0)
print path[::-1]
path = []
arr = [2,0,5,0,0,0,0];
def go(index):
global arr;
if(index == len(arr)-1):
path.append((index))
return True
if(index >= len(arr)):
return False
if (arr[index]==0):
return False;
step = arr[index]
while( step >0 ):
status = go(index+step)
if(status) :
path.append((index,step))
return True
step -= 1
else:
return False
print go(0)
print path[::-1]
fun()
{
int canMove= arr[0];
for(int i=1; i++; i<arr.length)
{
if(score>0)
{
canMove--;
canMove = canMove>arr[i]?canMove:arr[i];
}
else
{
return false;
}
}
return true;
}
It is simple dynamic programming problem.
import java.util.Scanner;
public class Main {
/*
* input: First length of array then the values at the indexes.
* n
* a1 a2 ... an
*
* ex:
* 4
* 1 0 0 1
* */
private int[] input;
public void init(){
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
input = new int[size];
for(int i = 0 ; i < size; i++) input[i] = sc.nextInt();
sc.close();
}
public boolean[] process(){
int size = input.length;
boolean[] others = new boolean[size];
others[size-1] = true;
for(int i = 0 ; i < size-1; i++) others[i] = false;
if(size == 1) return others;
for(int i = size-2; i >= 0; i--){
int radius = input[i];
radius = Math.min(i + radius + 1, size) - i - 1;
for(int j = 1 ; j <= radius; j++){
if(others[i+j] == true) {
others[i] = true;
break;
}
}
}
return others;
}
public void run(){
init();
boolean[] result = process();
// for(int i = 0 ; i < result.length; i++)
// System.out.print(result[0] + " ");
//
// System.out.println();
System.out.println(result[0]);
}
public static void main(String[] args) {
new Main().run();
}
}
Output for the below program: true
public class JumpGame {
public boolean jumpPossible(int index, int[] array, int lastIndex ){
if(lastIndex==0){
return true;
}
else if(index<array.length&&array[index]!=0){
return jumpPossible(array[index]+index,array,lastIndex-array[index]);
}
else
return false;
}
public static void main(String args[]){
int[] array={2,3,1,1,2,0,0};
int index=0;
JumpGame list1=new JumpGame();
System.out.println(list1.jumpPossible(index, array, array.length-1));
}
}
Console.WriteLine("Enter the array size");
int n = Convert.ToInt32(Console.ReadLine());
int[] a = new int[n];
int max=a[0],count=0;
for(int i=0; i<n; i++)
{
a[i] = Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine("Given array is able to reach the last index?");
for(int i=1; i<a.Length; i++)
{
if(max<a[i])
{
max = a[i];
count++;
}
}
if(a[0]==count)
Console.WriteLine("True");
else
Console.WriteLine("False");
Modified the solution to print the shortest paths to the final index.
- sidproquo August 29, 2016//Scala code object JumpGame{ def shortestPath(ls: Array[Int]) = { val n = ls.length val lastIndex = n-1 require(ls.nonEmpty) require(ls.forall(_ >= 0)) def internalShortestPath(path: String = "0", curr: Int = 0, acc: List[String]= Nil):List[String] = curr == lastIndex match { case true if curr ==0 => acc:+path case true => val p = path+"-"+curr.toString acc:+p case _ => val jumps = (ls(curr) until 0 by -1).filter(_ + curr <= lastIndex) jumps.map{j => val p = if(curr!= 0) path+ "-"+curr.toString else path internalShortestPath(p, curr + j, acc) }.toList.flatten } val rawRes = internalShortestPath() rawRes match { case Nil => println("Not reachable!") case _ => val resWithLengths = rawRes.map(x=> (x, x.split('-').length)) val minLength = resWithLengths.minBy(_._2)._2 val res = resWithLengths.filter(_._2 == minLength).map(_._1) res } } }