## Ebay Interview Question for Software Engineer Interns

• 0

Country: United States
Interview Type: Phone Interview

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

Modified the solution to print the shortest paths to the final index.

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

}
};``````

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

no,his/her solution is right,
max is initially a[0](0 in this case),hence it will return 0;

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

Lpook is correct

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

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

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

Take this input: 3 9 0 0 0 0
It's endless loop.

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

add the test to take care of this

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

The follow up question would be:
Find the minimum number of jumps to reach the end.

Any one?

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

I am not sure if I understand it. There is only one, determined, way to jump

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

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

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

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

}

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

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

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

1. Build directed graph
2. Find the shortest path (if exists)

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

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

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

boolean canJump(int array[]){
int length=array.length,i=0;//i is the index
while(i<=length-1){
if(array[i]==0) return false;
if (i==length-1) return true;// Returns True If i is in the last index.
}
return false;
}

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

/*
* 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));
}

}

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

/*
* 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));
}

}

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

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

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

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

boolean result = jumpGame(arr);

}

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

which of the above solutions are correct?

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

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]

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

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

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

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;

}

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

small change in the above code [score == canMove]

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

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

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

``````static boolean canJumpToGoal (int[] array) {

int jump = 0;
int index = 0;

while (true) {

jump += array[index];
index = array[index];
if (jump == array.length -1) return true;

if (jump > array.length - 1) break;

}
return false;

}``````

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

``````static boolean canJumpToGoal (int[] array) {

int jump = 0;
int index = 0;

while (true) {

jump += array[index];
index = array[index];
if (jump == array.length -1) return true;

if (jump > array.length - 1) break;

}
return false;

}``````

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

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

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

``````Console.WriteLine("Enter the array size");
int[] a = new int[n];
int max=a[0],count=0;
for(int i=0; i<n; i++)
{
}
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");``````

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.