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

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

Excellent solution!

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

Very nice approach!

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

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

Nice!!

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/

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

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

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

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

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

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

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

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

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

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

}
}``````

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++) {
}
}

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

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

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

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

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

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

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

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

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

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

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

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;

}
}``````

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

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

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

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

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

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

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

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

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

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

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

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

}``````

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

}

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

}

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

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

return result;
}``````

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

Comment hidden because of low score. Click to expand.
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...

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

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

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.