Coding Interview Question: Tower Hopper Problem

43 thoughts on “Coding Interview Question: Tower Hopper Problem”

1. zdanodron says:

On LeetCode: https://leetcode.com/problems/jump-game/

2. Eduard Ghandilyan says:

The next_step() approach is called a brut-force approach
In fact, this is simple, but very inefficient in case of very high towers and very long arrays. Particularly, in case of tower with high n, will take n trials until getting the optimal solution only for the first jump. Brut-force solution is always easy but mostly with really bad time complexity. In this particular case, the DP method works with O(n) time complexity, while brut-force approach takes it in O(n^2), which is too inefficient solution.

3. Dan K. says:

1) You've forgot to write `next_step` function.
2) I reckon your approach is called "greedy", not "simple".

4. Vikas Vishwakarma says:

Why don't you make such more videos? Btw thanks alot

5. shreyash joshi says:

Your videos are just amazing.love from india.

6. hbb says:

My brute force solution. I will try to optimize this;

function canHop(arr) {
if (arr[0] >= arr.length) {
return true;
}
if (arr[0] == 0) {
return false;
}
for (let i = 0; i < arr[0]; i++) {
let subArr = arr.slice(i + 1);
let done = canHop(subArr);
if (done) {
return true;
}
}
return false;
}

console.log(canHop([4, 2, 0, 0, 2, 0]));
console.log(canHop([1, 0]));
console.log(canHop([1, 1]));
console.log(canHop([0]));
console.log(canHop([3, 0, 0, 1, 2, 0, 2, 0]));

7. FengCun Li says:

Is this a fuel charging problem?

8. Raymond Linz says:

It seems to me that if you were to go left to right through the array and keep track of the current highest available amount of steps forward while checking for 0 and subtracting from the current highest 1 for every move forward, then you can just disprove false or break at false. It also gets rid of trying to see what the best next hop is. This should be just as optimal as finding next best hop without having to understand how to find next best hop. I can't think of an implementation of next best hop that would contain fewer operations than O(n). Here it is in powershell.

Function Can-IGetOut{

param(\$towers = @())

\$previousMaxDistance = 0

foreach(\$tower in \$towers){

\$previousMaxDistance -= 1

if(\$tower -gt \$previousMaxDistance){

\$previousMaxDistance = \$tower

}

if(\$previousMaxDistance -eq 0){

return \$false

}

}

return \$true

}

9. furkan ünsal says:

it begins from the end and checks if last tower is at least 1 block height. It is it saves that tower as checkpoint if last tower is at least 1 block height ,and does the same thing again. if last tower isn't at least 1 block height then it checks if the last but one tower is at least 2 block height. at the end if first tower saved as checkpoint then result is true and if it's not false.

———————————————————————-

def is_hoppable(array):

length = len(array)-1

array += [0]

checkpoint = length

i = 1

while True:

if (array[checkpoint – i] >= i):

checkpoint = checkpoint-i

i = 0

if (checkpoint == 0):

return True

elif (checkpoint == i):

return False

i+= 1

——————————————————————————

10. v krish says:

guys, what is the time complexity of the simple solution?

11. Cosimo Damiano Prete says:

Here there is my solution: https://ideone.com/jQusfi
it constructs kind of a graph (for the people who requested the graph approach), although it's not necessary to build a real graph once considered the constraints of the problem.

12. Parshant Dhall says:

def is_hoppable(lst):
length = len(lst) #length of list
l = 1
for i in lst:
if(i > length-l):
return True
l += 1
return False

13. Aleksa Jankovic says:

Here is my solution:

int current = towers.size();
for (int i=towers.size()-1;i>=0;i–){
if (towers[i] >= current -i) current =i;
}
if (current != 0) return false;
return true;

It won't make minimum number of hops, but it gives the right answer and it is O(towers.size()).

14. Tharun Gowrishankar says:

Hi Everyone, I wrote a simple code to solve this problem. Can anyone validate and let me know is this a better approach?

let a = [4,2,0,0,2,0];
flag = -1;
output = 0;
for(let i =a.length;i>0;i–){
if(a[i]+i>a.length && flag==-1)
{
flag = i;continue;
}
if(a[i]>=flag && flag!=-1){
output = 1;
}
}

15. Dale Carnegie says:

Is the simple approach faster than the dynamic?

16. Michael Archer says:

Can you jump over a "tower" with a greater height than your current tower?

17. jean RENé says:

I've done this in like 5 minutes tops, can anybody give me feedback please ? 🙂

towers = [4,0,0,2,0]

towers2 = [1,3,5,3,1]

def jump(lst):

arr = []

for i in range(len(lst)):

arr.append(False)

for i in range(len(lst)):

if lst[i] > len(lst)-1-i:

arr[i] = True

##FOR CLARITY PURPOSES

print(arr)

if arr[0]:

return True

else:

for i in range(len(lst)):

if arr[i]:

return jump(lst[:i])

return False

print(jump(towers))

18. Srinivasa praveen says:

Hi, I like your approach to solve a problem. Can you also make a video to solve "Largest rectangle area in histogram" problem. I saw many videos, but I am not really clear about that. Then I felt you might be the right guy. Thanks.

19. Amit Kabra says:

This is same as : https://www.geeksforgeeks.org/minimum-number-jumps-reach-endset-2on-solution/ ?

20. Andy Lam says:

According to your question "just hop out of the array"…. hop( array.length+1) Done!

21. l0calher0 says:

Just keep a count of the maximum distance you can travel from your current index and iterate for that length. If you encounter an index which increases that distance, increase your count and continue until it is greater than the array length, or until you reach the end of that distance. O(n)

for (int i = 0; i < arr.Length; i++) {
if (max >= arr.Length) return true;
max = Math.Max(arr[i] + i, max);
if (max <= i) return false;
}

22. Sai Panda says:

Please make this type of video as soon as you can. By the way we love your videos. Love From India.

23. Sahejpreet wahla says:

Do we need to just check whether its possible to go to other side , or we have to give a clear cut path . I havnt seen full video , just saw the question part

24. Justin X says:

If you want to use greedy solution, it's easier to understand if you start from the end index, and greedy always give you correct result in this case.
find the right-most tower that can reach to your destination e and update e, why always find the right-most tower? food for thought.
public boolean canHop(int[] nums) {
int n = nums.length;
int s = n-1;
int e = n;
while(s >= 0){
if(s+nums[s] >= e){
e = s;
}
s -= 1;
}
return e == 0;
}

25. Mario Ruiz says:

Hey YK, thanks for the analysis. Can you please explain in anothe video with more detail the next_step function…. For me that function seems is the tricky part….

26. Vsevolod Kalinin says:

Can't find it anywhere here… What's the Big O complexity of recursive/recursive+DP/"simple"?
Am I right assuming recursive is O(m^n) where m is the maximum height, recursive+DP is O(n) and "simple" is the same O(n)? :/

27. Giovani Chaves says:

Ended up with this algo below. I'd love to get considerations or optimizations.

The idea is always jumping to the farthest tower on each jump considering the position of the tower we are evaluating.
So in his example, there'd be a tie between tower 1 and tower 4 because they're both height 2. BUT tower 4 is bringing the jump to tower 6 (in this scenario, out of bounds – so return true)

public boolean isHoppable(int[] towers) {

int lastHop = nextHop(towers, 0);

return lastHop >= towers.length;
}

public int nextHop(int[] towers, int tower) {
int currentHop = tower + towers[tower];
int maxHop = 0;

if (currentHop >= towers.length) {
return currentHop;
}

for (int i = tower+1; i <= currentHop; i++) {
int hop = i + towers[i];

if (hop >= towers.length) {
return hop;
}

if (hop > maxHop) {
maxHop = hop;
}
}

if (towers[maxHop] == 0) {
return 0;
}

return nextHop(towers, maxHop);

}

28. José Yánez says:

The true greedy approach sorts all the distances from the goal and then it takes the furthest element back to the start as long as it's feasible. Runtime is O(N log N) though which is worse than DP.

29. Gavin Thomas Magee says:

#My python implementation!

def is_hoppable(buildings):
#buildings = [4,2,0,0,2,0]
jumps_needed = 1
for i in range(len(buildings),1,-1):
if buildings[i-1] < jumps_needed:
jumps_needed += 1
else:
jumps_needed = 1
if jumps_needed > buildings[0]:
return False
else:
return True

30. BeingYourself says:

function hop(int index)
{
if ( index > n-1)
print "yes";

for(int step=1; step <= array [index] ; step ++ )
hop ( step + index );
}

Is this correct?

31. Vojtěch Sejkora says:

I am not sure, that "simple algorithm" work.

Imagine this towers [4,2,0,3,1,0].
next_step(0,tower) = 4.
next_step(4,tower) = 5.

but
next_step(1, tower) = 6

and solution is to use tower 0,1,3, out.

32. Kate K says:

Python implementation of recursive solution:
def helper(arr, index):
if arr[index] == 0:
return 0
end_index = index + arr[index]
if end_index >= len(arr):
return 1
result = 0
for i in range(index + 1, end_index + 1):
result += helper(arr, i)
return result

def is_hoppable(arr):
if helper(arr,0) > 0:
return True
else:
return False

33. akshay Chopra says:

Where is the code for the next_step() method ?
DIdnt get this !

34. Martin Maneesh says:

Hey CS Dojo I have a doubt on your simple solution. I just checked a random case 4,2,0,4,1,0,1 . In this case there can be a solution by jumping form first tower to 4th tower and then from there jumping to outside but by your method when I've traced it, I'm getting false but actually I have a way to go out. Please clarify my doubt.

35. Research and Build says:

The next step function is almost like a derivative. We look at how much the change allows us to change.

36. Lens Liebe says:

Your approach fails for [4, 3, 0, 3, 1, 0]

37. Piotr Sarna says:

It's my solution in Python. Complexity: O(n). Code:
def is_hoppable(towers):
target_idx = len(towers)

for idx in reversed(xrange(0, target_idx)):
tower = towers[idx]
tower_range_idx = idx + tower

if tower_range_idx >= target_idx:
target_idx = idx

if target_idx == 0:
return True

return False

38. Shervil Gupta says:

this could've been solved using backtracking approach as well or not ?

39. Code Dreams says:

Go right to left. Keep track of minimum distance needed to escape. Each time you find a tower that meets that minimum distance, set the distance to 0 and keep going. If the left-most tower meets the distance, return true. 1 pass, O(n) time O(1) space. No fancy stuff needed.

40. Krishna Chanakya says:

Next_step() function ??

41. Govind Mallurwar says:

Why can't you come with android app for those videos

42. Zxymr says:

– Have an endpoint variable initialised as the index of the position after the last element.
– Loop from end to start of array.
– For each element, if (height + current position index – 1st position index) >= endpoint, assign that index to endpoint.
– At end of loop, if endpoint is at first index, return true. Otherwise, return false.

43. kennedy francis says:

Can someone write the next_step function plssss