Fundamental Problem Table of Content

 

Easy Medium Hard
Two Number Sum Max Subset Sum No Adjacent  
Three Number Sum    
Quick Sort    
Binary Search    
Palindrome Check    
Nth Fibonacci    
Minimum Waiting Time    
Class Photos    
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     



Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Max Subset Sum No Adjacent

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

 

Source code on Github

February 16, 2019

Minimal Waiting Time

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

 

Source code on Github

February 12, 2019

Nth Fibonacci

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.

February 11, 2019

Palindrome Check

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

 

February 11, 2019

Binary Search

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.

February 10, 2019