Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.

If the input array is empty, the function should return 0.

**Sample input**

[75, 105, 120, 75, 90, 135]

**Sample output**

330 = 75 + 120 + 135

**Solution**

Time Complexity: O(n)

Space Complexity: O(1)

static int maxSubsetSumNoAdjacent(int[] array) { int answer = 0; if (array.length == 0) { return 0; } else if (array.length == 1) { return array[0]; } int first = Math.max(array[0], array[1]); int second = array[0]; int current = 0; for (int i = 2; i < array.length; i++) { current = Math.max(first, second + array[i]); second = first; first = current; } answer = first; return answer; }

You’re given a non-empty array of positive integers representing the amounts of time that specific queries take to execute. Only one query can be executed at a time, but the queries can be executed in any order.

A query’s waiting time is defined as the amount of time that it must wait before its execution starts. In other words, if a query is executed second, then its waiting time is the duration of the first query; if a query is executed third, then its waiting time is the sum of the durations of the first two queries.

Write a function that returns the minimum amount of total waiting time for all of the queries. For example, if you’re given the queries of durations

[1, 4, 5], then the total waiting time if the queries were executed in the order of [5, 1, 4] would be (0) + (5) + (5 + 1) = 11. The first query of duration 5 would be executed immediately, so its waiting time would be 0, the second query of duration 1 would have to wait 5 seconds (the duration of the first query) to be executed, and the last query would have to wait the duration of the first two queries before being executed.

**Note**: you’re allowed to mutate the input array.

**Solution**

Use a map to store previous total waiting time per index.

Time Complexity: O(n log n)

Space Complexity: O(1)

Algorithm used: Greedy Algorithm

static int getMinimumWaitingTime(int[] queries) { /** * sort the array to help getting the minimum total waiting time */ Arrays.sort(queries); int size = queries.length; if (size <= 1) { return 0; } Map<Integer, Integer> map = new HashMap<>(); int totalWaitingTime = 0; for (int i = 0; i < queries.length; i++) { int currentWaitingTime = 0; int previousTotalWaitingTime = 0; if (i != 0) { currentWaitingTime = queries[i - 1]; previousTotalWaitingTime = currentWaitingTime + map.get(i - 1); } map.put(i, previousTotalWaitingTime); totalWaitingTime += previousTotalWaitingTime; } return totalWaitingTime; }

The Fibonacci sequence is defined as follows: the first number of the sequence is 0, the second number is 1, and the nth number is the sum of the (n – 1)th and (n – 2)th numbers. Write a function that takes in an integer n and returns the nth Fibonacci number.

I have a solution here.

Write a function that takes in a non-empty string and that returns a boolean representing whether the string is a palindrome.

A palindrome is defined as a string that’s written the same forward and backward. Note that single-character strings are palindromes.

**Solution**

Loop through half of the string. Compare each character from one half to the each character from the other half.

static boolean isPalindrome(String str) { for (int i = 0, x = str.length() - 1; i < str.length() / 2; i++, x--) { if (str.charAt(x) != str.charAt(i)) { return false; } } return true; }

Write a function that takes in a sorted array of integers as well as a target integer. The function should use the Binary Search algorithm to determine if the target integer is contained in the array and should return its index if it is, otherwise -1.

I have a solution here.