Q1: The Two Sneaky Numbers of Digitville

In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to appear exactly once in the list, however, two mischievous numbers sneaked in an additional time, making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any order), so peace can return to Digitville.

Thoughts

• seems pretty simple, i think i’ll just use a hashset or something

Solution

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        HashSet<Integer> hs = new HashSet();
        int[] ans = new int[2];
        int ansNum = 0;

        for (int i : nums) {
            if (!hs.add(i)) {
                ans[ansNum] = i;
                ansNum++;
                if (ansNum == 2) return ans;
            } 
        }
        return ans;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

Conclusion

ezpz hashset solution. I think there may be a better way though.

Q2: Maximum Multiplication Score

You are given an integer array a of size 4 and another integer array b of size at least 4.

You need to choose 4 indices i<sub>0</sub>, i<sub>1</sub>, i<sub>2</sub>, and i<sub>3</sub> from the array b such that i<sub>0</sub> < i<sub>1</sub> < i<sub>2</sub> < i<sub>3</sub>. Your score will be equal to the value a[0] * b[i<sub>0</sub>] + a[1] * b[i<sub>1</sub>] + a[2] * b[i<sub>2</sub>] + a[3] * b[i<sub>3</sub>].

Return the maximum score you can achieve.

Thoughts

• best solution i could come up with was a brute force, I’m almost certain there is a way to do this with dynamic programming

Solution

class Solution {
    public long maxScore(int[] a, int[] b) {
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < b.length - 3; i++) {
            for (int j = i + 1; j < b.length - 2; j++) {
                for (int k = j + 1; k < b.length - 1; k++) {
                    for (int l = k + 1; l < b.length; l++) {
                        long temp = a[0] * b[i] + a[1] * b[j] + a[2] * b[k] + a[3] * b[l];
                        if (Long.compare(temp,ans) > 0) ans = temp;
                    }
                }
            }
        }

        return ans;
    }
}

Time Complexity: O(n^4)
Space Complexity: O(1)

Conclusion

Definitely should learn some more dynamic programming because this is (I think) a dynamic programming problem and my brute force solution is too slow to complete all of the test cases.

Overall Conclusion

Yea I really need to work on my DP knowledge, otherwise I am going to keep hitting performance walls like this.