Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

After thinking about it... there is an n complexity and 1 space complexity

BOOL isPathPossibleArray(int array[], int n){
    

    int stepsCounter = array[0];
    
    int index = 0;
    
    while (stepsCounter > 0) {
        stepsCounter --;
        index++;
        
        if (index == n-1) {
            return YES;
        }
        int newSteps = array[index];
        
        if (newSteps > stepsCounter) {
            stepsCounter = newSteps;
        }
    }
    
    
    return NO;
}

- Samuel Kitono December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Excellent solution!

- Anonymous January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice approach!

But it fails for the following boundary case:
A[] = {0}

- mytestaccount2 March 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice!!

- CodeKnight November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

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/

- Abhay December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Matoy December 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Matoy December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The algorithm does return false you should check one more time ..:P

- Abhay December 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- ycwmike December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Stuart December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- chongguang December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kartik December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- naren December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Siddharth December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are the other questions you got in on site interview??

- Anonymous December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

+(BOOL)canReach2:(NSArray*)arr
{
  int maxReach = 0;
  
  for(int i = 0; i < [arr count]; i++)
  {
    maxReach = MAX (maxReach, [arr[i] intValue] + i);
    
    if(maxReach >= [arr count] - 1)
      return YES;
    
    if(maxReach <= i)
      return NO;
    
  }
  
  return NO;
}

- VK December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- voidet@nightgen.com December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Matoy December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- SilentWaters December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- parikksit.b December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- alonsomh December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool HasPath(int[] arr)
        {
            int idx = 0;
            while (true)
	        {
                int hop = arr[idx];
                if (hop == 0)
                    return false;
                idx += hop;
                if (idx > (arr.Length - 1))
                    return true;
                while (arr[idx] == 0)
                    idx--;
                if (hop == arr[idx])
                    return false;
                
	        }
        }

- yair.cohen1 December 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Douglas Leite December 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shanmuk December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shanmuk December 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- stuart December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nelson Perez December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isPossible(int index)
    {
        if(index==0)
            return true;
        for(int i=index-1;i>-1;i--)
        {
            if(array[i] == index-i)
            {
                return isPossible(i);
            }
        }
        return false;
    }

// usage
	
	int[] array = {1,2,0,1,1,1};
        isPossible(array.length-1);

- Akshat January 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nick January 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- rdo January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Resh January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- O(ren) :) January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hop(array, 0));

	private static boolean hop(int[] arr, int cur) {
		if (cur + arr[cur] >= arr.length - 1) return true;
		if (arr[cur] == 0) return false;
		for (int i = 1; i <= arr[cur]; i++) {
			if (hop(arr, cur + i)) return true;
		}
		return false;
	}

- mutahirqureshi February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Simply February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Simply February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Simply February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rohan February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nelson Perez March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isReachable(int a[], int n)
{
    int maxwecango = a[0];
    int i = 1;
    
    if (n == 1) return true;
    if (n < 1) return false;
    
    while (i <= maxwecango) {
        if (i == n-1) return true;
        
        if (i+a[i] > maxwecango) {
            maxwecango = i+a[i];
        }
        
        i++;
    }
    
    return false;
}

- mytestaccount2 March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isDestinationRechable(int[] input) {

		boolean isReachable = false;
		if (input != null && input.length > 0) {
			int i = 0;
			int len = input.length - 1;

			while (i < len && input[i] != 0) {
				i = i + input[i];
			}

			if (i == len) {
				isReachable = true;
			}
		}
		return isReachable;
	}

- Anonymous May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hankm2004 August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Previous one takes O(N^2), which is a shame.
This one takes O(N)

bool can_get_last(int * arr, int len)
{
	int pos = 0;
	int hops = arr[pos];
	while (hops)
	{
		pos++;
		hops--;
		if (pos == len -1)
			return true;
		if (hops < arr[pos])
			hops = arr[pos];		
	}
	return false;
}

- hankm2004 August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

function test(a){
  var v = a[0], ret;
  if (v>=a.length)
    return true;
  if (a.length==1)
    return false;
  for (var i=1; i<=v; i++)
  {
    if (test(a.slice(i)))
      return true;
  }
  return false;
}

var arr = [1, 2, 0, 1, 0, 1];
var x = test(arr);
console.log('xxx', x);

- Anonymous December 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def can_reach(a):
    s = [0]
    while s:
        e = s.pop()
        if e == len(a) - 1:
            return True
        if a[e] == 0:
            continue
        for i in range(1, a[e] + 1):
            s.append(e+i)
    return False

- Anonymous March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def can_reach(a):
    s = [0]
    while s:
        e = s.pop()
        if e == len(a) - 1:
            return True
        if a[e] == 0:
            continue
        for i in range(1, a[e] + 1):
            s.append(e+i)
    return False

- anon March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def can_reach(a):
    s = [0]
    while s:
        e = s.pop()
        if e == len(a) - 1:
            return True
        if a[e] == 0:
            continue
        for i in range(1, a[e] + 1):
            s.append(e+i)
    return False

- anonymous March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool CanReachLast(int[] a)
{
	int i = 0;
	int maxRange = a[i];
	while (i <= maxRange && i < a.Length)
	{
		int range = i + a[i];
		maxRange = Math.Max(maxRange, range);
		i++;
	}
	
	return maxRange >= a.Length -1;
}

- hnatsu December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Carlos June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Carlos June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

- Tiffany December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

- Samuel Kitono December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Samuel Kitono December 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Opps space complexity is n... coz it is Dynamic Programming afterall

- Samuel December 02, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More