Good morning! Here’s your coding interview problem for today.
This problem was asked about by Airbnb.
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be
0 or negative.
[2, 4, 6, 2, 5] should return
13, since we pick
[5, 1, 1, 5] should return
10, since we pick
Follow-up: Can you do this in O(N) time and constant space?
Let us figure out what non-adjacent numbers are, because, am neither a genius, english nor maths major. So according to Merriam webster :
What is non-adjacent? : not adjacent: such as. a: not having a common endpoint or border nonadjacent buildings/rooms. b of two angles: not having the vertex and one side in common.
So, in simpler terms, there must be a number in between to make two numbers adjacent to each others.
def adjacent_sum(arr): sum = 0 if len(arr) < 0 or len(arr) == 2: return 0 elif len(arr) == 1: return arr else: if len(arr) % 2 == 0: for i in range(0, len(arr), 3): sum += arr[i] else: for i in range(0, len(arr), 2): sum += arr[i] return sum# print(adjacent_sum([2, 4, 6, 2, 5]))print(adjacent_sum([5, 1, 1, 5, 2, 4, 6, 2, 5]))
The time complexity for this solution is 0(n)
An alternative solution has been written here in Java: https://divyabiyani.medium.com/daily-coding-problem-february-24th-2020-given-a-list-of-integers-write-a-function-that-89b68076b0fb