Daily Coding Problem: Problem #9 [Hard]- Sum of Adjacent Numbers

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.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

Suggested Solution:

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.

code:

def adjacent_sum(arr):
    sum = 0
    if len(arr) < 0 or len(arr) == 2:
        return 0
    elif len(arr) == 1:
        return arr[0]
    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