Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Agorithm:
for each element determine the maximum index you may jump
maxInd=0;
for(i=0;i<n;i++)
{
if(maxInd<a[i]+i)
maxInd = a[i]+i;
if(maxInd>=n-1)
return true;
if(maxInd<=i)
return false;
}
u can test your solution over here https://oj.leetcode.com/problems/jump-game/
Not correct. this array: { 0, 4, 0, 0, 0, 1 } gives true where it should return false (you can't go nowhere when you start in the first element (0) since you have 0 moves to make....).
you have a small bug. the last condition should come first, so that the method should be:
public static boolean foo(int[] a) {
int maxInd = 0;
int n = a.length;
for (int i = 0; i < n; i++) {
if (maxInd < i)
return false;
if (maxInd < a[i] + i)
maxInd = a[i] + i;
if (maxInd >= n - 1)
return true;
}
return (maxInd >= n - 1);
}
Greedy alogirthm is enough....
c++:
public:
bool canJump(int A[], int n) {
// the maximum index range the people could reach at the current situation
int maxCover = 0;
for(int i = 0; i <= maxCover&&i<n; i++){
if(A[i] + i > maxCover) maxCover = A[i] + i;
if(maxCover >= n-1) return true;
}
return false;
}
Its a dynamic programming, O(n) space and time complexity O(sum of jumps)
public static boolean possible(int[] steps)
{
boolean[] pos = new boolean[steps.length];
pos[steps.length-1] = true;
for(int i = steps.length-2; i>=0; i--)
{
for(int j = 1; j<= steps[i]; j++)
{
if(i+j <= steps.length-1 && pos[i+j] == true)
{
pos[i] = true;
continue;
}
}
}
return pos[0];
}
public boolean canComeToEnd(int[] array) {
for (int i = 0; i <= array.size - 2; i++) {
if (array[i] == 0 && !canBePassed(int index, int[] array)) {
return false;
}
}
return true;
}
public boolean canBePassed(int index, int[] array) {
if (index == 0) {
return false;
}
int i = index -1;
while(i >= 0) {
if(array[i] > index - i) {
return true;
}
i ++
}
return false;
}
using System.IO;
using System;
class Program
{
int[] arr=new int[]{1,2,0,2,0,1};
bool pathexist=false;
public void FindPath(int ind)
{
if(ind==5)
{
Console.WriteLine("Path Exists");
pathexist=true;
return;
}
int val = arr[ind];
if(val==0)
return;
for(int i=1;i<=val;i++)
{
FindPath(ind+i);
}
return;
}
public static void Main()
{
Program p = new Program();
p.FindPath(0);
if(p.pathexist)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
Console.ReadLine();
}
}
//I am going to take a graph approach. Construct a DAG with the hops and using the BFS find out if the path to the last index(or node is possible). Sedgewick has the java implemenations available on the web and you can get the source for Digraph and DepthFirstDirectedPaths. Granted time complexity may be N2 (just for construction of Digraph) but one more creative exercise using graphs for me.
private static boolean isHopPossible(int [] hopArray) {
int hopArrayLength = hopArray.length;
Digraph digraph = new Digraph(hopArrayLength);
// convert hopArray into DAG
for(int i =0;i<hopArrayLength-1;i++) {
for (int j = 1; j <= hopArray[i]; j++) {
digraph.addEdge(i, i+j);
}
}
DepthFirstDirectedPaths depthFirstDirectedPath = new DepthFirstDirectedPaths(digraph, 0);
return depthFirstDirectedPath.hasPathTo(hopArrayLength-1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] hopArray = new int [] {1, 2, 0, 1, 1, 1};
System.out.println(isHopPossible(hopArray));
}
public static Boolean checkEnd(int [] input){
int index = 0;
int n = input.length;
Queue< Integer> queue = new LinkedList<Integer>();
queue.offer(index);
while(!queue.isEmpty()){
index = queue.poll();
int a = input[index];
for(int i=1; i<=a;i++){
if(index+a<n){
queue.offer(index+a);
}else{
return true;
}
}
}
return false;
}
public static boolean canReachEnd(int[] hops)
{
if (hops == null || hops.length == 0)
{
return false;
}
return canReachEnd(hops, 0, new Boolean[hops.length - 1]);
}
private static boolean canReachEnd(int[] hops, int start, Boolean[] cache)
{
if (start >= hops.length - 1)
{
return true;
}
if (cache[start] != null)
{
return cache[start];
}
boolean r = false;
for (int i = hops[start]; i > 0; i--)
{
if (canReachEnd(hops, start + i, cache))
{
r = true;
break;
}
}
cache[start] = r;
return r;
}
This method uses a stack to use a DFS on the hop permutations. It decrements the value of the currently examined node each time it is popped off the stack and used to "leap" forward by x until it is 0, at which point it will look at the previous node at the stack and so on.
//Written in Swift
var hops = [1, 2, 2, 0, 1, 1, 2];
func hops(input:Array<Int>) -> Array<Int> {
var hopStack:[Int] = []
var hop:Int = input[0]
var currentIndex = 0
do {
if (hop == 0 && hopStack.count > 0) {
hop = hopStack.removeAtIndex(hopStack.count - 1)
currentIndex -= hop
hop--
}
if (hop > 0) {
hopStack.append(hop)
currentIndex += hop
if (currentIndex < input.count) {
hop = input[currentIndex]
}
}
if (currentIndex >= input.count) {
return hopStack
}
} while (hopStack.count > 0)
return []
}
hops(hops)
public static boolean isReachable(int[] arr) {
return( isReachableInner(arr, 0));
}
public static boolean isReachableInner(int[] arr, int index) {
if (index == arr.length) {
return true;
}
if (index > arr.length) {
return false;
}
for (int i = 1; i <= arr[index]; i++) {
if (isReachableInner(arr, i + index, stack)) {
return true;
}
}
return false;
}
bool IsArrayConnectedToLast(int* startElem, int arraySize)
{
if (arraySize == 0)
return false;
// array with one element is connected to itself with zero hop
if (arraySize == 1)
return true;
// construct a secondary array to keep track of
// each entry in the array if it is connected to
// last element in the array
int* isConnected = new int[arraySize];
for (int idx = 0; idx < arraySize; idx++)
isConnected[idx] = 0;
// last element is always connected to itself
// with zero hops
isConnected[arraySize - 1] = 1;
int elementCount = 1;
// start from element before the last and
// traverse back to beginning of the array
// then see if by changing the number of hops
// connects to last element in the array. The
// number of hops is limited to elements remaining
// in the array and the value of the element at that
// position.
for (int idx = arraySize-2; idx >= 0; idx--)
{
int maxNumberOfHops = (startElem[idx] <= elementCount) ? startElem[idx] : elementCount;
for (int hops = 1; hops <= maxNumberOfHops; hops++)
{
if (isConnected[idx + hops] == 1)
{
//
// if this element is connected to end element of the array
// terminate the loop
//
isConnected[idx] = 1;
break;
}
}
elementCount++;
}
return isConnected[0]? true: false;
}
Here's my approach, I think we need some kind of a backtracking. Which is why I'm using recursion. I'm not very good at recursion, so please excuse me if the code isn't written optimally.
What we do is, we pass in the first index to the function Hop(), then we check if its zero, return false. If the number itself is the length of the array, return true. After the assertions, we simply grab the number at the index of the input array and make those many hops. If we get a false reply, we lower the index and continue. Its working for most samples provided in the above thread. Comments are welcome. Thanks!
private static boolean Hop(int value){
if(value >= input.length)
return true;
int hopValue = input[value];
if(hopValue == 0)
return false;
boolean waddup = Hop(hopValue + value);
if(waddup == false && hopValue>1)
waddup = Hop(--hopValue + value);
return waddup;
My approach is to move forward until a 0 is found, at that point, see if we can hope over the 0. if we can return false, else keep moving forward. I do not check the last element as we are already there. (C#)
public static bool CanHopeToTheLastElement(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == 0)
{
int counter = 1;
int j = i - 1;
bool canHop = false;
while (j >= 0 && canHop == false)
{
if (array[j] > counter) //we can hop over i using array[j];
{
canHop = true;
}
--j;
++counter;
}
if (!canHop)
return false;
}
}
return true;
}
public static boolean reachTheEnd(int[] a) {
return reachTheEnd(a, 0);
}
private static boolean reachTheEnd(int[] a, int i) {
if (i == a.length - 1) return true;
else if (i > a.length - 1) return false;
int hops = a[i];
while (hops > 0) {
if (reachTheEnd(a, i + hops--)) return true;
}
return false;
}
Can be solved in O(n) without extra array
public static bool IsPathExist(int[] array)
{
int minhop = 0;
for (int i = array.Length -1; i >= 0 ; i--)
{
if (array[i] == 0)
{
minhop++;
}
else if (array[i] > minhop)
{
minhop = 0;
}
else
{
minhop++;
}
Console.WriteLine(minhop);
}
return minhop == 0;
}
Dynamic Programming
public static Boolean reach(int[] hops)
{
Boolean[] reach = new Boolean[hops.length];
reach[hops.length -1 ] = true;
for(int i = hops.length-2; i>= 0; i++)
{
for(int j = hops[i]; j>0; j++)
{
if(i+j<= hops.length -1 && reach[i+j] )
{
hops[i] = true;
break;
}
}
}
return reach[0];
}
Do not why everyone goes iterative with this problem.
In my case I went recursive as is the way I could come up with an understandable solution.
static bool IsHopable(int[] array, int start = 0)
{
for(int i = array[start]; j > 0; i--)
{
if(array[start] >= (array.Length -1))
return true;
else if(IsHopable(array, start + i)
return true;
}
return false;
}
Note: This assumes the question meant that you must reach *past* the last element (i.e. if you get to the last element, and it's a 0, you didn't make it). To have it return true for simply reaching the last element, we just need to subtract 1 from the length.
bool canhop(uint data[], uint start, uint length)
{
for (uint i = data[start]; i > 0; --i)
{
if (start + i >= length || canhop(data, start + i, length))
{
return true;
}
}
return false;
}
<?php
$a = [1,2,0,1,0,1];
$n = count($a);
$dp = [];
for ($i = 0; $i < $n; $i++) {
$dp[$i] = 0;
}
if ($a[0] != 0) {
$dp[0] = 1;
}
for ($i = 0; $i < $n; $i++) {
if ($dp[$i] == 0 || $a[$i] == 0) {
continue;
}
for ($j = $i + 1; $j <= $i + $a[$i]; $j++) {
$dp[$j] = 1;
if ($dp[$n - 1] == 1) {
print 'TRUE' . PHP_EOL;
return;
}
}
}
print 'FALSE' . PHP_EOL;
public static boolean findIfLastIndexIsReachable(int[] arr){
if(arr.length<=1) return true;
int maxHops = 0;
int steps = 1;
for(int i=0;i<arr.length;i++){
steps--;
if(maxHops < (i+arr[i])){
maxHops = i+arr[i];
steps = arr[i];
}
if(steps==0&& i<arr.length-1){
return false;
}
}
return true;
}
Nice and clean
public static boolean isTheLastIndexReachableHelper(int[] list, int index) {
// the end is reachable with a smaller step
if (index >= list.length - 1)
return true;
// try the maximum step and go down
for (int i = list[index]; i > 0; i--) {
if (isTheLastIndexReachableHelper(list, index + i))
return true;
}
return false;
}
public class Hops {
public static boolean getHops(int[] a) {
if (a.length == 1)
return true;
if (a.length < 1)
return false;
int[] m = new int[a.length];
Arrays.fill(m, -1);
int n = a.length;
for (int i = n - 2; i >= 0; --i) {
for (int j = 1; j <= 3; ++j) {
if (i + j < n && m[i + j] != -1)
m[i] = i + j;
}
}
if (a[0] != -1)
return true;
return false;
}
}
public class Hops {
public static boolean getHops(int[] a) {
if (a.length == 1)
return true;
if (a.length < 1)
return false;
int[] m = new int[a.length];
Arrays.fill(m, -1);
int n = a.length;
for (int i = n - 2; i >= 0; --i) {
for (int j = 1; j <= 3; ++j) {
if (i + j < n && m[i + j] != -1)
m[i] = i + j;
}
}
if (a[0] != -1)
return true;
return false;
}
}
public class Hops {
public static boolean getHops(int[] a) {
if (a.length == 1)
return true;
if (a.length < 1)
return false;
int[] m = new int[a.length];
Arrays.fill(m, -1);
int n = a.length;
for (int i = n - 2; i >= 0; --i) {
for (int j = 1; j <= 3; ++j) {
if (i + j < n && m[i + j] != -1)
m[i] = i + j;
}
}
if (a[0] != -1)
return true;
return false;
}
}
Simple solution :-
static void isEndReachable(int arr[]) {
System.out.println(isEndReachable(arr, 0, arr.length-1));
}
static boolean isEndReachable(int arr[], int start, int goal) {
if(start > goal)
return false;
if(start == goal)
return true;
if(arr[start] == 0)
return false;
boolean isReachable = false;
for(int i=1; i<=arr[start]; i++) {
isReachable = isEndReachable(arr, start+i, goal);
if(isReachable)
return true;
}
return false;
}
Here is the best solutions using memoization which makes this problem way faster.
public static bool IsHopeable(int[] A)
{
return coreIsHopeable(A, 0, new Dictionary<int, bool>());
}
private static bool coreIsHopeable(int[] A, int start, Dictionary<int, bool> memo)
{
if(memo.ContainsKey(start))
{
return memo[start];
}
bool result = false;
// Assuming if you hope over it will be possible to hope to the end
if(start >= A.Length - 1)
{
result = true;
}
if(A[start] != 0)
{
for(int i = 1; i < A[start]; i++)
{
if(coreIsHopeable(A, start + i, memo))
{
result = true;
break;
}
}
}
memo.Add(start, result);
return result;
}
Here is the C++ version of solution using DFS;
#include <iostream>
using namespace std;
bool dfs(int* arr, int len, int pos)
{
cout<< pos <<endl;
if (pos >= len -1)
return (pos == len -1);
int hops = arr[pos];
for (int i = 1; i <= hops; i++)
{
if (pos+i < len)
{
pos+= i;
if (dfs(arr, len, pos))
return true;
pos-= i;
}
}
return false;
}
bool can_get_last(int * arr, int len)
{
return dfs(arr, len, 0);
}
int main()
{
int input[6] = {1,2,0,1,0,1};
cout <<"can hop to the last = " << can_get_last(input, 6);
return 1;
}
#include <stdio.h>
#include <string.h>
void hasPathFind(int *path, int size, int *possibility) {
int i, j;
for (i = size - 2; i >= 0; --i) {
int value = path[i] + i;
for (j = i + 1; j <= value && j < size; ++j)
if (possibility[j] == 1) {
possibility[i] = 1;
break;
}
}
}
int hasPath(int *path, int size) {
int possibility[size];
memset(possibility, 0, sizeof (int) * size);
possibility[size - 1] = 1;
hasPathFind(path, size, possibility);
return possibility[0];
}
int main(void) {
int path[] = {15, 2, 2, 0, 0, 1, 1, 2};
printf("%d\n", hasPath(path, sizeof (path) / sizeof (path[0])));
return 0;
}
#include <stdio.h>
#include <string.h>
void hasPathFind(int *path, int size, int *possibility) {
int i, j;
for (i = size - 2; i >= 0; --i) {
int value = path[i] + i;
for (j = i + 1; j <= value && j < size; ++j)
if (possibility[j] == 1) {
possibility[i] = 1;
break;
}
}
}
int hasPath(int *path, int size) {
int possibility[size];
memset(possibility, 0, sizeof (int) * size);
possibility[size - 1] = 1;
hasPathFind(path, size, possibility);
return possibility[0];
}
int main(void) {
int path[] = {15, 2, 2, 0, 0, 1, 1, 2};
printf("%d\n", hasPath(path, sizeof (path) / sizeof (path[0])));
return 0;
}
public boolean ifPathIsPossible(int[] arr) {
int currentTargetPosition = arr.length - 1;
for (int i = arr.length-2; i >= 0; i--) {
int stepThisPositionCanTake = arr[i];
if (currentTargetPosition - (stepThisPositionCanTake + i) <= 0)
currentTargetPosition = i;
}
return currentTargetPosition == 0;
}
O(n) time and O(1) space.
This is basically same approach as word break solution...
BOOL isPathPossibleArray(int array[], int n){
if (n <= 1) {
return YES;
}
int end = n-1;
int dp[n];
for (int i = 0; i < n; i++) {
dp[i] = 0;
}
dp[end] = 1;
for (int i = end; i >= 1; i--) {
for (int j = i - 1; j >= 0; j--) {
if (array[j] >= (i-j) && dp[i]) {
dp[j] = 1;
}
}
}
return dp[0];
}
Btw the time complexity is n^2 and space complexity is 1.... it could be optimized more probably... but i am excercising to solve this under 10 mins...
After thinking about it... there is an n complexity and 1 space complexity
- Samuel Kitono December 02, 2014