Grokking Oracle Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
C

CaptainKidd

· 4 years ago

Lack of visual explanation for these problems continues to be a point of contention imo.

For those wondering why we aren't advancing the i value on swaps for '2' we have no idea what number took the place of the '2'. So if we don't advance the pointer it covers the edge case where the swap brings in a 0 that needs to be addressed.

Show 1 reply
Rudy Peralta

Rudy Peralta

· a year ago

So for this problem the wording is a bit weird and doesn't convey the spirit of the problem.

Here's a clearer description for what we want to achieve and why using arr.sort() is both not allowed and wouldn't fully solve the problem:

You are given an array that contains only three types of elements: 0, 1, and 2.

Your task is to sort the array in-place (i.e., without using extra space for another array), such that:

  • All 0s come first,
  • Followed by all 1s,
  • Followed by all 2s.

You cannot just count the number of 0s, 1s, and 2s and then overwrite the array — you must sort the array in one pass (the two pointers technique lends itself quite well to this type of in place sort.

Example:

Input: [2, 0, 2, 1, 1, 0]

Output: `[0, 0, 1, 1, 2, 2

S

Smoke

· 4 years ago

it would help if the solution is explained visually

K

krishnakeshav.pes

· 3 years ago

solution seems to be using 3 pointers but does it one pass(which is optimal) ie. O(n)

Another, O(n) would be to use 2 pointers but do 2 passes - place 0s in 1st pass and 1s in 2nd pass.

N

Nirbhay Lourembam

· 3 years ago

I found the below solution on youtube. In my opinion, this is the easiest one to understand and honestly much more elegant than what is given here.

public static void sortColors_3Pointers(int[] nums) {

    int start = 0;
    int mid = 0;
    int end = nums.length - 1;

    while (mid <= end) {

        switch (nums[mid]) {
            case 0:
                // Swap with start index
                swap(nums, start, mid);
                mid++;
                start++;
                break;

            case 1:
                mid++;// do nothing
                break;

            case 2:
                // Swap with end index
                swap(nums, mid, end);
                end--;
                break;
        }
    }

}
Show 1 reply
E

Eduardo Sánchez

· 4 years ago

Could I not push each element to a hashmap and then just concat it?

{ 0: [0,0], 1: [1,1], 2: [2] } then I just concat those 3 arrays (still treating each of the numbers as an object. This will also be O(n) for time and space O(n)

Show 2 replies
S

sw94070

· a year ago

When running your solution with example test cases, this is the error I see: com.google.gson.stream.MalformedJsonException: Unterminated array at line 1 column 5 path $[1] null

B

Bryan Pena

· 4 years ago

this solution doesn't work on leetcode. error is it cannot find the symbol for the swap() method form this tutorial.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def sort(self, arr):
    b, m, e = 0, 0, len(arr) - 1
    while m <= e:
        if arr[e] == 2:
            e -= 1
        elif arr[b] == 0:
            # here is the tricky part if the middle pointer at same position as the position as the beginning pointer 
            # and the beginning pointer = 0 it meas we are done with that part of the array so we can safely 
            # move the middle pointer too together with the beginning pointer
            if m == b: 
                m += 1
            b += 1
        elif arr[m] == 1:
            m += 1
        elif arr[e] < arr[m]:
            # swap 
            arr[e], arr[m] = arr[m], arr[e]
        elif arr[m] < arr[b]:
            # swap
            arr[m], arr[b] = arr[b], arr[m]
    return arr
Abdullah Khatib

Abdullah Khatib

· 3 months ago

A better explanation would be to think of low as being in charge of placing 1s and high being in charge of placing 2s . i is the variable that iterates through the loop and when it comes across a 0, both i and left increment because i increments no matter what, and left increments because it's not incharge of 0s. We must also swap i and left values, in case left was left behind at a 1 (and because the current number is a 0 and needs to be placed at the very back). Now we tackle 1s, if a one is found, we increment i because it's always incremented, but left is left behind to stay in charge of the 1, no swapping takes place. Lastly, when i comes across a 2, it understands that high is in charge of 2s, so it swaps with high and we decrement high to set up the next potential spot for a 2. Note