DEV Community: Lydia Yuan

Android Interview Prep Details: Part 1

Lydia Yuan — Sat, 24 Feb 2024 22:27:00 +0000

Q: When creating an immutable class in Java, how do you handle mutable fields like objects?

A: It's advisable to return a deep copy or an immutable copy of the mutable field. This approach helps prevent users from modifying the original data, ensuring the immutability of the class.

Q: How can exceptions be handled in Java aside from using the try-catch block?

A: For unchecked exceptions, such as ArrayIndexOutOfBoundsException, where using a try-catch block might consume significant resources, an alternative approach is to employ an if-else check to preemptively prevent the exception. Additionally, for NullPointerException, consider utilizing the Optional class as a more structured way to handle potentially null values.

Q: When creating a thread in Java, which method do you prefer?

A: It depends on the scenario. If you are solely utilizing the run method without the need for additional customization of the thread's behavior, it's advisable to implement the Runnable interface. This approach adheres to the principle of favoring composition over inheritance in object-oriented programming (OOP). When a class extends the Thread class, it breaks the is-a relationship, as the new class is not truly a type of thread but rather a thread itself. By implementing Runnable, you can achieve the desired behavior while maintaining a cleaner and more flexible design, promoting code reuse through composition. If, however, you need to customize the thread behavior extensively, extending the Thread class might be a suitable choice.

Q: In industry-level code, how do we handle threads?

A: In the context of industry-level code, a widely adopted practice is to use the ExecutorService in Java for handling threads. ExecutorService provides a higher-level replacement for managing threads compared to manually creating and managing threads. It abstracts away the complexity of thread creation, pooling, and lifecycle management.

Moreover, ExecutorService offers several benefits such as thread pooling, efficient task scheduling, and easier resource management. By utilizing executor services, you can improve the scalability and performance of your application, ensuring better resource utilization.

Q: What are some common issues in multi-threaded programs?

A: One common issue in multi-threaded programs is data racing. Data racing occurs when two or more threads concurrently access shared data, and at least one of them modifies the data. This can lead to unpredictable behavior, as the order of execution becomes non-deterministic.

To mitigate data racing, synchronization mechanisms are often employed. Locks, such as the synchronized keyword in Java, are used to ensure that only one thread can access the shared data at a time. However, introducing locks raises another potential issue: deadlock.

Deadlock occurs when two or more threads are blocked forever, each waiting for the other to release a lock. This can halt the progress of the entire program. To prevent deadlocks, it's essential to follow best practices in lock acquisition order. If multiple locks are needed, ensure that all threads acquire the locks in the same order to avoid circular dependencies.

Additionally, using timeouts when acquiring locks is a recommended strategy. This involves specifying the maximum time a thread is willing to wait for a lock. If the lock is not acquired within the specified time, the thread can take appropriate action, such as releasing resources and retrying or notifying the user of the issue.

( data racing => lock => deadlock => how to avoid deadlock )

Q: For a sealed class in Kotlin, can you extend it in the same file? How about in the same package?

A: In Kotlin, a sealed class is a class that restricts the inheritance of its subclasses to a predefined set within the same file. Therefore, you can extend a sealed class within the same file but not outside of it.

When it comes to extending a sealed class in the same package but different files, Kotlin allows this as well. As long as the file is within the same package as the sealed class, you can create new subclasses of the sealed class in different files within that package.

This encapsulation of sealed classes to the same file provides a level of control over the hierarchy of subclasses, making it easier to manage and understand the complete set of subclasses that are meant to inherit from the sealed class.

Q: How can you overload the primary constructor in Kotlin?

A: You can achieve overloading in the primary constructor of a Kotlin class by providing default values to parameters. This allows you to create multiple constructor variations with different sets of parameters, making the class more flexible and accommodating various use cases.

Understanding Parameter Order in Kotlin's Primary Constructors

Lydia Yuan ・ Feb 23

#kotlin

Q: What's the advantage of coroutine in Kotlin?

A: Coroutines in Kotlin offer several advantages:

Scope Management:
Coroutines provide a built-in way to manage the scope of asynchronous operations. This ensures that coroutines launched within a specific scope are cancelled when that scope is cancelled. This is particularly valuable for structured concurrency, making it easier to handle the lifecycle of concurrent operations.
Lightweight:
Coroutines are more lightweight compared to traditional threads. They are well-suited for resource-intensive environments like Android, where creating and managing numerous threads can be costly. Coroutines use fewer system resources and are more scalable, making them a preferable choice for asynchronous programming.
Non-blocking:
Coroutines allow non-blocking execution, meaning they don't block the main thread. This is crucial for maintaining a responsive user interface in applications, especially on platforms like Android. With coroutines, you can perform asynchronous tasks without freezing the UI, leading to a smoother and more responsive user experience.
Suspend Functions:
Coroutines introduce the concept of suspend functions, which can be used within a coroutine to perform asynchronous tasks without blocking the thread. This simplifies asynchronous code, making it more readable and maintainable compared to traditional callback-based approaches.

Q: List three common permissions in the Android manifest.

A: Three common permissions in the Android manifest are:

android.permission.ACCESS_FINE_LOCATION: This permission is used to access precise location information, such as GPS coordinates.
android.permission.INTERNET: This permission allows the application to open network sockets and use the internet.
android.permission.POST_NOTIFICATIONS: This permission is related to notifications and allows the application to post notifications on the device.

Q: How do you securely store a token in Android?

A: To securely store a token in Android, it's recommended to utilize the Android Keystore system. The Android Keystore provides a secure and hardware-backed environment for key and token storage, offering protection against unauthorized access and extraction.

Q: How do you handle navigation in Android?

A: Navigation in Android can be accomplished in various ways, depending on the context:

To a New Activity:
- Start a new activity by using an intent. You can use the Intent class to navigate from one activity to another. This is a common approach for transitioning between different screens or functionalities within an Android application.
To a New Fragment (Jetpack Compose):
- In Jetpack Compose, you can use a NavHost for navigation. The NavHost is a container for hosting navigation within Compose applications. It works in conjunction with the Navigation component to handle navigation between different composables. This allows for a declarative and efficient way to manage UI navigation in a Compose-based Android app.
To a New Fragment (XML):
- In XML-based layouts, you can use a Navigation Graph (navgraph) to define the navigation flow between fragments. The Navigation component in Android provides a visual way to represent and manage the navigation paths within an application. This is particularly useful when dealing with complex navigation patterns.

Q: How do you avoid adding a new activity to the back stack in Android?

A: To prevent adding a new activity to the back stack in Android, you can use the finish() method. When you call finish() on an activity, it signals that the current activity should be closed, and it won't be added to the back stack.

Q: How do you override the back button in Android?

A: To override the back button in Android, you can use the OnBackPressedDispatcher provided by ComponentActivity, the base class for FragmentActivity and AppCompatActivity. The OnBackPressedDispatcher allows you to control the behavior of the back button by managing OnBackPressedCallback objects.

class MyFragment : Fragment() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)

        // This callback is only called when MyFragment is at least started
        val callback = requireActivity().onBackPressedDispatcher.addCallback(this) {
            // Handle the back button event
        }

        // The callback can be enabled or disabled here or in the lambda
    }
    ...
}

Q: What are some view groups in Android XML?

A: In Android XML, view groups are containers that hold and organize other UI elements. Some commonly used view groups include:

LinearLayout:
- Arranges child views in a single row or column. You can specify the orientation as either horizontal or vertical.
RelativeLayout:
- Positions child views relative to each other or the parent. It allows you to define the layout rules based on the position of sibling views.
FrameLayout:
- Places child views on top of each other, with the last child added appearing at the top of the stack. It's often used for simple overlays.
ConstraintLayout:
- A flexible layout that allows you to create complex UIs by setting constraints between views. It's particularly useful for responsive and dynamic designs.
ScrollView:
- A special type of view group that allows its content to be scrolled vertically or horizontally. It's often used when the content is too large to fit on the screen.

...

Understanding Parameter Order in Kotlin's Primary Constructors

Lydia Yuan — Fri, 23 Feb 2024 22:29:17 +0000

Kotlin follows positional parameter passing by default. So the first example does not work, the first parameter will be taken as a.

About thread join and run method in Java

Lydia Yuan — Thu, 15 Feb 2024 20:47:10 +0000

When you invoke run(), if the thread was initially created using a distinct Runnable run object, then the run method of that Runnable object is executed. Otherwise, if the thread was constructed without a separate Runnable object, the method does nothing and returns.

Surprisingly, even if the thread has already completed or terminated, as indicated by the first thread.join(), calling thread.run() will still execute and print output. Cuz this line of code calls the run() method directly, not starting a new thread.

Additionally, calling multiple join() statements will not result in any exceptions being thrown.

class JoinExample {

    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread(() -> System.out.println("Thread is running with runnable..."));

        thread.start();
        thread.join(); // Waits for the thread to complete
        thread.run();  // Calls the run() method directly, not starting a new thread
        thread.join(); // Waits again, no exception here

        // Second start will cause an IllegalThreadStateException
        // thread.start();
    }
}

//Output:
//Thread is running with runnable...
//Thread is running with runnable...

class JoinExample {

    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread();

        thread.start();
        thread.join(); // Waits for the thread to complete
        thread.run();  // Calls the run() method directly, not starting a new thread
        thread.join(); // Waits again, no exception here

        // Second start will cause an IllegalThreadStateException
        // thread.start();
    }
}

//Output:
// nothing

Utilizing Git Submodules for Including a Separate Repository

Lydia Yuan — Wed, 05 Jul 2023 03:16:03 +0000

As developers, we often find ourselves in situations where we want to include a separate repository within another repository. Git submodules provide a helpful feature to achieve this goal. In this blog post, we'll explore how to set up Git submodules to include a separate repository within another repository.

Setting Up Git Submodules

To get started, follow these steps:

Step 1: Create the Separate Repository

Begin by creating the separate repository that you want to include within another repository.

Step 2: Navigate to the Target Repository

Next, navigate to the repository where you want to include the separate repository.

Step 3: Add the Separate Repository as a Submodule

In the target repository's folder, run the following command to add the separate repository as a submodule:

git submodule add <separate-repo-url> <submodule-folder-name>

Make sure to replace <separate-repo-url> with the URL of the separate repository and <submodule-folder-name> with the desired name for the submodule folder.

Step 4: Commit the Changes

Step 5: Push Changes to the Remote Repository

Benefits of Git Submodules

By following these steps, whenever someone clones the target repository, the separate repository will be included as a submodule. This setup allows you to update, commit, and push changes to the separate repository independently from the target repository. It enables you to maintain separate commit histories and manage the two repositories effectively.

Cloning the Repository on Another Machine

It's important to note that when cloning the target repository on another machine, additional steps are required to fetch and initialize the submodule. After cloning the repository, run the following commands:

git submodule init
git submodule update --remote

These commands will fetch the separate repository and initialize it within the target repository on the new machine.

I hope you find this guide helpful for incorporating Git submodules into your projects ✍(◔◡◔)

Find the Smallest N Prime Numbers in Ascending Order

Lydia Yuan — Sat, 08 Apr 2023 14:02:11 +0000

The Question

Please implement a function that, given an integer parameter N, can print the smallest N prime numbers in ascending order, for example, when N = 10, print 2 3 5 7 11 13 17 19 23 29.

The Most Basic Trail Division

public static boolean isPrime(int n) {
        if (n <= 1 || n % 2 == 0) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void printFirstNPrimeNumbers(int N) {
        if (N == 0) {
            return;
        }
        System.out.println(2);
        int printedCount = 1;
        int current = 3;
        while (printedCount < N) {
            if (isPrime(current)) {
                printedCount++;
                System.out.println(current);
            }
            current++;
        }
    }

Less Checks & Cache Time Space Tradeoff

A better way to judge if a number is a prime number is to check if it can be divided by a prime number. Rather than checking all odd numbers until the square root of the given number, we can check only prime numbers until the square root of the given number. This is because if a number is not divisible by 2, it is also not divisible by any other even number. Similarly, if a number is not divisible by 3, it is also not divisible by any multiple of 3, such as 9. Therefore, we can improve the performance of our prime number check by caching all the encountered prime numbers and only checking division by these prime numbers up to the square root of the given number. This reduces the number of division checks required, which can be a significant optimization for large numbers.

public static boolean isPrime(int n, Set<Integer> encounteredPrimeNumbers) {
        if (encounteredPrimeNumbers.contains(n)) {
            return true;
        }
        if (n <= 1 || n % 2 == 0) {
            return false;
        }
        for (int primeNumber : encounteredPrimeNumbers) {
            if (n % primeNumber == 0) {
                return false;
            }
        }
        encounteredPrimeNumbers.add(n);
        return true;
    }

    public static void printFirstNPrimeNumbers(int N) {
        if (N == 0) {
            return;
        }
        Set<Integer> encounteredPrimeNumbers = new LinkedHashSet<>();
        encounteredPrimeNumbers.add(2);
        System.out.println(2);
        int printedCount = 1;
        int current = 3;
        while (printedCount < N) {
            if (isPrime(current, encounteredPrimeNumbers)) {
                printedCount++;
                System.out.println(current);
            }
            current++;
        }
    }

Sieve of Eratosthenes

For a visual demonstration of the Sieve of Eratosthenes algorithm, be sure to check out the animated gif on the Wikipedia page. It can help give you a better intuition for how the sieve method works and how it is used to find prime numbers.

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

View on Wikipedia

Implementing the Sieve of Eratosthenes method requires a boolean array to mark whether a number is prime or not. Additionally, we need to estimate the number of candidate numbers we need to examine to find the first N prime numbers. To do so, we can use prime counting functions. However, the distribution of primes is not uniform, and there may be potential gaps in our range. A good rule of thumb is to expand the range by about 10-20% of the target value of N. I would be conservative and choose the 20% expansion here to go with the most simple prime counting function x / ln(x).

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by $π$ (x) (unrelated to the number $π$ ).

View on Wikipedia

public static int getEstimatedUpperBound(int N) {
        // binary search
        // Prime-counting function with 20% expansion : x / ln(x) > N * 1.2
        int lo = 1;
        int hi = Integer.MAX_VALUE;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            double val = mid / Math.log(mid);
            if (val > N * 1.2) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }


    public static void printFirstNPrimeNumbers(int N) {
        if (N == 0) {
            return;
        }
        int estimatedUpperBound = getEstimatedUpperBound(N);
        Boolean[] isComposite = new Boolean[estimatedUpperBound + 1];
        Arrays.fill(isComposite, false);
        int primeNumberCount = 0;
        for (int i = 2; i <= isComposite.length && primeNumberCount < N; i++) {
            if (!isComposite[i]) {
                System.out.println(i);
                primeNumberCount++;
                for (int j = i * i; j < isComposite.length; j += i) {
                    isComposite[j] = true;
                }
            }
        }
    }

Use Bit Masking to Save More Space

Bitmasking is a space-efficient technique that can be used to represent boolean values. In the given code, a boolean array is used to mark composite numbers while finding the first N prime numbers. However, the size of the boolean array grows linearly with the size of the range of numbers being searched.

On the other hand, if we use a bitset, we can store each boolean value using just one bit, rather than a whole byte as with a boolean array. This means that we can store 8 boolean values in the space of a single byte, effectively reducing the memory consumption by a factor of 8. Thus, the bit masking method saves 8 times more space than the regular boolean array in this code.

public static void printFirstNPrimeNumbers(int N) {
        if (N == 0) {
            return;
        }
        int estimatedUpperBound = getEstimatedUpperBound(N);
        int numInts = (estimatedUpperBound + 1 + 31) / 32;
        // number of integers needed, rounded up to 32*n
        int[] isComposite = new int[numInts];
        int primeNumberCount = 0;
        for (int i = 2; i <= estimatedUpperBound && primeNumberCount < N; i++) {
            if ((isComposite[i / 32] & (1 << (i % 32))) == 0) {
                System.out.println(i);
                primeNumberCount++;
                for (int j = i * i; j <= estimatedUpperBound; j += i) {
                    // mark all multiples of i as composite
                    isComposite[j / 32] |= (1 << (j % 32));
                }
            }
        }
    }

Writing a curried add in JavaScript

Lydia Yuan — Thu, 16 Mar 2023 18:25:39 +0000

I wanted to create a curried add function that allows for unlimited chaining, like add(1)(2)...(n). I started with a curry function that returns a curried version of the input function:

const curry = (fn) => {
  const curried = (...args) => {
    if (args.length >= fn.length) {
      return fn(...args);
    }
    return (...moreArgs) => curried(...args, ...moreArgs);
  };
  return curried;
}

Next, I tried to use curry to create a curriedAdd function with fixed parameters:

const add = (a , b) => a + b

const curriedAdd = curry(add)

console.log(curriedAdd(2, 3))
// 5

console.log(curriedAdd(2)(3))
// 5

console.log(curriedAdd(2)(3)(4))
// Oops an error!
// Uncaught TypeError: curriedAdd(...)(...) is not a function at <anonymous>:5:29

However, I encountered a problem while trying to achieve unlimited chaining using the currying technique. JavaScript functions have a fixed number of parameters, which makes it impossible to create a function that can accept an unlimited number of arguments without using some sort of workaround.

When we call curriedAdd(2), it returns a function that takes another parameter and adds it to 2. Therefore, curriedAdd(2)(3) results in a number 5.

But attempting to call 5(4) leads to a runtime error since 5 is a number and not a function that can accept another argument.

Instead, I came up with a solution that involves returning a function that can be called with an empty argument to indicate the end of the chain. With this approach, the user needs to manually call the function with an empty argument () to signal the end of the chain.

Although this requires a bit more effort from the user to call the execution, it allows for an unlimited number of arguments to be passed in a curried manner, as demonstrated by add(1)(2)...(n)().


const add = (x) => {
  let sum = x;

  const innerAdd = (y) => {
    if (y !== undefined) {
      sum += y;
      return innerAdd;
    } else {
      return sum;
    }
  };

  return innerAdd;
};



add(1)(2)(3)(); // returns 6
add(1)(2)(3)(4)(5)(); // returns 15

Alternatively, if we know the expected number of parameters ahead of time, we can use curry with a fixed number of arguments:


const curryN = (fn, fnArgsLen = fn.length) =>
  (...args) =>
    args.length >= fnArgsLen
      ? fn(...args)
      : (...moreArgs) => curryN(fn, fnArgsLen)(...args, ...moreArgs);


const add = (x, y, z) => x + y + z
const curriedAdd = curryN(add, 3);

console.log(curriedAdd(1)(2)(3)); // prints 6
console.log(curriedAdd(1, 2)(3)); // prints 6
console.log(curriedAdd(1, 2, 3)); // prints 6

While this approach isn't truly unlimited chaining, it can handle a large number of arguments and provides a flexible way to compose functions.

In-place Merge Sort in Java

Lydia Yuan — Sat, 26 Nov 2022 22:32:19 +0000

Plain In-place Merge Sort

Time complexity: $O(N^2)$


class PlainInPlaceMergeSort {
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    private void inPlaceMerge(int[] nums, int start, int mid, int end) {
        int leftPointer = start;
        int rightPointer = mid + 1;
        while (leftPointer <= mid && rightPointer <= end) {
            if (nums[leftPointer] <= nums[rightPointer]) {
                leftPointer++;
            } else {
                int currentRightElement = nums[rightPointer];
                int currentRightPointer = rightPointer;
                while (currentRightPointer > leftPointer) {
                    nums[currentRightPointer] = nums[currentRightPointer - 1];
                    currentRightPointer--;
                }
                nums[leftPointer] = currentRightElement;
                leftPointer++;
                rightPointer++;
                mid++;
            }
        }
    }

    private int getMid(int start, int end) {
        return start + (end - start) / 2;
    }

    private void inPlaceMergeSortHelper(int[] nums, int start, int end) {
        if(end - start < 2) {
            return;
        }
        int mid = getMid(start, end);
        inPlaceMergeSortHelper(nums, start, mid);
        inPlaceMergeSortHelper(nums, mid + 1, end);
        inPlaceMerge(nums, start, mid, end);
    }

    public void inPlaceMergeSort(int[] nums) {
        inPlaceMergeSortHelper(nums, 0, nums.length - 1);
    }
}

Shell Sort Mixed In-place Merge Sort

Time Complexity: $O(N*(logN)^2)$


class ShellSortMixedInplaceMergeSort {
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    private void inPlaceMerge(int[] nums, int start, int end) {
        int length = end - start + 1;
        int comparisonRange = getComparisonRange(length);
        while (comparisonRange >= 1) {
            int pointer = start;
            while (pointer + comparisonRange <= end) {
                if (nums[pointer] > nums[pointer + comparisonRange]) {
                    swap(nums, pointer, pointer + comparisonRange);
                }
                pointer++;
            }
            if(comparisonRange == 1) {
                break;
            }
            comparisonRange = getComparisonRange(comparisonRange);
        }
    }

    private int getComparisonRange(int previousLength) {
        return (int) Math.ceil((double) previousLength / 2);
    }

    private int getMid(int start, int end) {
        return start + (end - start) / 2;
    }

    private void inPlaceMergeSortHelper(int[] nums, int start, int end) {
        if (end - start < 1) {
            return;
        }
        int mid = getMid(start, end);
        inPlaceMergeSortHelper(nums, start, mid);
        inPlaceMergeSortHelper(nums, mid + 1, end);
        inPlaceMerge(nums, start, end);
    }

    public void inPlaceMergeSort(int[] nums) {
        inPlaceMergeSortHelper(nums, 0, nums.length - 1);
    }
}

Top Down / Bottom Up Merge Sort in Java

Lydia Yuan — Sat, 19 Nov 2022 05:55:00 +0000

Maybe check out the description of the two methods first?

Timing Experiment Results Prediction

Bottom up method should perform better:

Top down method calls mergeSortHelper recursively, which will take O(logN) extra function call stack space
Top down method takes O(logN) extra time to break down the array into one / zero elements

But both of their space complexities are O(N) ( the temporary array to store sorted data )

Timing Experiment Results

Bottom up method sometimes performs slightly better than the top down one

The trend suggests that there is not that much a difference between the performance of the two methods

Some personal guess on why the gap between two methods is not that obvious:

The data points I choose are not the best presentations
My implementation is not the best practice
The merge part takes so much time that it overshadows the breakdown process / extra call stack space
The compiler did some optimization black magic under the hood

About the tests:

Testing data set: randomly permuted Integer array list
Testing data type: Integer
Test data size: [0, 10k], step: 500
Trails per data point: 10000

Top Down / Recursive Merge Sort

    /**
     * @return integer overflow prevention mid index getter
     */
    private static int getMiddleIndex(int start, int end) {
        return start + (end - start) / 2;
    }

    /**
     * merge two sorted array into a new sorted array
     */
    private static <T> void merge(ArrayList<T> data, int startLeft, int endLeft, int startRight, int endRight, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int leftPointer = startLeft, rightPointer = startRight;
        int index = startLeft;
        while (leftPointer <= endLeft && rightPointer <= endRight) {
            T data1 = data.get(leftPointer);
            T data2 = data.get(rightPointer);
            if (comparator.compare(data1, data2) < 0) {
                sortedResults.set(index, data1);
                leftPointer++;
            } else {
                sortedResults.set(index, data2);
                rightPointer++;
            }
            index++;
        }
        while (leftPointer <= endLeft) {
            sortedResults.set(index, data.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer <= endRight) {
            sortedResults.set(index, data.get(rightPointer));
            rightPointer++;
            index++;
        }
        for (int i = startLeft; i <= endRight; i++) {
            data.set(i, sortedResults.get(i));
        }
    }

    /**
     * merge sort, time complexity: O(N*logN), space complexity: O(N)
     */
    private static <T> void mergeSortHelper(ArrayList<T> data, int start, int end, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
        int dataSize = end - start + 1;

        if (dataSize < 2) {
            return;
        }

        int mid = getMiddleIndex(start, end);
        mergeSortHelper(data, start, mid, comparator, sortedResults);
        mergeSortHelper(data, mid + 1, end, comparator, sortedResults);
        merge(data, start, mid, mid + 1, end, comparator, sortedResults);
    }

    /**
     * call mergeSortHelper to do top down merge sort
     */
    public static <T> void topDownMergeSort(ArrayList<T> data, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(data.size(), null));
        mergeSortHelper(data, 0, data.size() - 1, comparator, sortedResults);
    }

Bottom Up / Iterative Merge Sort


    public static <T> void bottomUpMergeSort(ArrayList<T> originalData, Comparator<? super T> comparator) {
        ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(originalData.size(), null));
        for (int sortingRange = 1; sortingRange < originalData.size(); sortingRange *= 2) {
            for (int left = 0; left < originalData.size(); left += 2 * sortingRange) {
                bottomUpMerge(originalData, sortedResults, left, sortingRange, comparator);
            }
            copyArray(sortedResults, originalData);
        }
    }

    private static <T> void bottomUpMerge(ArrayList<T> originalData, ArrayList<T> sortedResults, int start, int sortingRange, Comparator<? super T> comparator) {
        int right = Math.min(start + sortingRange, originalData.size());
        int end = Math.min(start + 2 * sortingRange, originalData.size());
        int leftPointer = start;
        int rightPointer = leftPointer + sortingRange;
        int index = start;
        while (leftPointer < right && rightPointer < end) {
            if (comparator.compare(originalData.get(leftPointer), originalData.get(rightPointer)) <= 0) {
                sortedResults.set(index, originalData.get(leftPointer));
                leftPointer++;
            } else {
                sortedResults.set(index, originalData.get(rightPointer));
                rightPointer++;
            }
            index++;
        }
        while (leftPointer < right) {
            sortedResults.set(index, originalData.get(leftPointer));
            leftPointer++;
            index++;
        }
        while (rightPointer < end) {
            sortedResults.set(index, originalData.get(rightPointer));
            rightPointer++;
            index++;
        }
    }

    /**
     * copy everything in the "from" array into "to" array
     */
    private static <T> void copyArray(ArrayList<T> from, ArrayList<T> to) {
        if (from.size() != to.size()) {
            throw new UnsupportedOperationException("From & to arrays have different sizes!");
        }
        for (int i = 0; i < from.size(); i++) {
            to.set(i, from.get(i));
        }
    }

concurrent mode 对 useRef 使用可能造成的影响

Lydia Yuan — Thu, 25 Nov 2021 06:41:58 +0000

需要的前置知识：

Concurrent mode 在 concurrent mode，最后一次 render 不代表「最新的 committed 状态」有最新 state / props 的优先级较低的 render 可能会重写当前 event handler 使用的 reference
useRef
React strict mode
React render phase & commit phase
useEffect : timing of effect

我在这个 issue 的讨论里面看到了关于未来 concurrent mode 对 useRef 使用可能造成的影响

Q: What issues has "mutation of ref during rendering"? Can you explain me in brief?
A: In concurrent mode (not yet released), it would "remember" the last rendered version, which isn't great if we render different work-in-progress priorities. So it's not "async safe".

这个回答还是有点简略，不太好懂，我再扩展一下

useRef 的功能相当于是一个全局变量，所以改变它其实是会造成副作用的

比如这个 demo：https://codesandbox.io/s/useref-strict-mode-3xpf3?file=/src/App.tsx

可以对比一下例子里面的两个组件

BadCounter.tsx

const BadCounter = () => {
  const count = useRef(0);
  count.current += 1;
  return (
    <div className="counter">
      BAD COUNTER <br /> count:{count.current}
    </div>
  );
};

显然这在现在非 concurrent mode 的情景下可以正常工作，因为现在 render 阶段（计算组件哪里需要更新，即调用 render 函数比较本次和之前的计算结果）和 commit 阶段（把计算出来的变化CRUD到 DOM 里）是一比一的
但是我通过把它包在 <StrictMode/> 里面利用 strict mode 触发了两次 Function component bodies 中的内容
进行了两次 render 但是只 commit 了一次，所以点按钮重渲染之后会增加 2

GoodCounter.tsx

import React, { useEffect, useRef } from "react";
const GoodCounter = () => {
  const count = useRef(0);
  let currentCount = count.current;
  useEffect(() => {
    count.current = currentCount;
  });
  currentCount += 1;
  return (
    <div className="counter">
      GOOD COUNTER <br /> count:{currentCount}
    </div>
  );
};
export default GoodCounter;

改进后的组件把对 ref 的修改放进了 useEffect 中
useEffect 里面的函数只会在 commit phase 去调用
所以就算 render phase : commit phase 不再是 1:1 也可以「展示想要的状态」

PS 这里官方对于 useCallback 里面如何读取总是改变的值的 workaround 的例子就是放在 useEffect 里面处理的：https://reactjs.org/docs/hooks-faq.html#how-to-read-an-often-changing-value-from-usecallback

别人写的使用 concurrent mode 的相同 demo : https://codesandbox.io/s/x2p46v02z4
也是一样的道理

所以未来如果要升级到 concurrent mode 的版本
对于 useRef 的使用需要非常小心

我能想到的对于升级到 concurrent mode 的 best practice

可以通过 strict mode 先对会产生副作用的函数（包括但不仅限于改变 ref.current ）进行一波检查
~~因为考虑到会出现的危险，尽量少用~~ ~~useRef~~ 考虑能否用其他 async safe 的 hook 替代（比如上面的例子就可以用 useState 或者 useCallback 替代）

参考资料

useLockFn 中 useCallback 的用途

Lydia Yuan — Thu, 25 Nov 2021 06:38:57 +0000

ahooks 库里面有一个 useLockFn

    import { useRef, useCallback } from 'react';
    function useLockFn<P extends any[] = any[], V extends any = any>(fn: (...args: P) => Promise<V>) {
      const lockRef = useRef(false);
      return useCallback(
        async (...args: P) => {
          if (lockRef.current) return;
          lockRef.current = true;
          try {
            const ret = await fn(...args);
            lockRef.current = false;
            return ret;
          } catch (e) {
            lockRef.current = false;
            throw e;
          }
        },
        [fn],
      );
    }
    export default useLockFn;

它的作用是拦截重复的异步请求（ demo: https://ahooks.js.org/hooks/advanced/use-lock-fn ）
我删掉了其中的 useCallback 发现还是能正常拦截的（ demo: https://codepen.io/yuanruqian/pen/eYWgVpM )
所以我很疑惑这里的 useCallback 的作用是什么
于是我提了一个 issue 问了下 ahooks 的人
他们的回复是：是考虑到 performance 的问题才加的
根据回复我写了两个 demo 比较加和不加的情况

加 useCallback 避免用到返回的 memoized 函数的子组件进行不必要的渲染： https://codepen.io/yuanruqian/pen/yLbgqEm
不加 useCallback ，每次返回的是新生成的一个函数，子组件就算 memo 了也会跟着父组件一起渲染：https://codepen.io/yuanruqian/pen/rNmjreX

同时根据他们的回复，我也发现了这里的一个坑：只有满足特定条件的情况下才能阻止组件重新渲染

比如忘记给传入 useLockFn 的函数加上 useRef 或者 useCallback ，每次父组件刷新都会生成一个新函数传给 useLockFn ，加的 useCallback 就没有发挥出「防止不必要的重渲染」的作用 demo：https://codepen.io/yuanruqian/pen/yLbgqEm

综上，这个 hook 能发挥「防止不必要的重渲染」的 条件如下

传入的 useLockFn 的函数不变（需要用 useRef 或者 useCallback 进行处理）
用到这个函数的组件需要用 memo 进行缓存（这也可以说是 useCallback 的一个坑，因为它往往需要和 memo 一起组合使用才能防止重新渲染）
组件里没有其他改变 state 的 hook，如果里面有一个 useState 就前功尽弃了

如果不能做到这些条件，那么 useCallback 只是白占了空间和时间资源而已（ useCallback 内部实现会记录 prevState 占内存，每次都会比较 deps 数组的变化占时间）

而且就算能做到这些条件，对于大部分的开发项目来说，真的有必要这样做吗？React 渲染 UI 的速度是很快的，除了一些非常复杂的交互图等之外，或许因为上面说的时空耗费比本来 re-rendering 更慢一些也说不定（当然简单组件慢也慢不了多少，这里只是质疑一下有些时候一些「性能优化」不一定是必要的）

推荐阅读

useMemo / useCallback 将来可能的隐患以及可行的对策

Lydia Yuan — Thu, 25 Nov 2021 06:15:37 +0000

起因

这两个 API 可能不够 stable，未来可能导致代码库里用到的地方需要进行相关改动
具体可以看官方文档中有这么一段话

You may rely on useMemo as a performance optimization, not as a semantic guarantee. In the future, React may choose to “forget” some previously memoized values and recalculate them on next render, e.g. to free memory for offscreen components. Write your code so that it still works without useMemo — and then add it to optimize performance.

总结一下 React core team 成员对这个问题的回复

如果未来真的上这个 feature

会提供额外的 API 来 mark 当前组件是否允许进行内存回收
只会在「能够合理破坏 memoization」的地方进行回收，比如「一个 tab 隐藏了几分钟，可以释放掉仅仅被 memoization 占用的额外内存」

社区已经有的替代方案

useMemoOne
基本是用 useRef 重新实现了一遍 useMemo 和 useCallback

useCreation
ahooks 的一个 useMemo 的替代品或者说是根据 deps 变化的 useRef

目前 `useRef` 和 `useMemo` `useCallback` 具体实现原理

useRef

    function useRef<T>(initialValue: T): {|current: T|} {
      currentlyRenderingComponent = resolveCurrentlyRenderingComponent();
      workInProgressHook = createWorkInProgressHook();
      const previousRef = workInProgressHook.memoizedState;
      if (previousRef === null) {
        const ref = {current: initialValue};
        if (__DEV__) {
          Object.seal(ref);
        }
        workInProgressHook.memoizedState = ref;
        return ref;
      } else {
        return previousRef;
      }
    }

useMemo

    function useMemo<T>(nextCreate: () => T, deps: Array<mixed> | void | null): T {
      currentlyRenderingComponent = resolveCurrentlyRenderingComponent();
      workInProgressHook = createWorkInProgressHook();

      const nextDeps = deps === undefined ? null : deps;

      if (workInProgressHook !== null) {
        const prevState = workInProgressHook.memoizedState;
        if (prevState !== null) {
          if (nextDeps !== null) {
            const prevDeps = prevState[1];
            if (areHookInputsEqual(nextDeps, prevDeps)) {
              return prevState[0];
            }
          }
        }
      }

      if (__DEV__) {
        isInHookUserCodeInDev = true;
      }
      const nextValue = nextCreate();
      if (__DEV__) {
        isInHookUserCodeInDev = false;
      }
      workInProgressHook.memoizedState = [nextValue, nextDeps];
      return nextValue;
    }

useCallback

    export function useCallback<T>(
      callback: T,
      deps: Array<mixed> | void | null,
    ): T {
      return useMemo(() => callback, deps);
    }

可见 useCallback 基本可以认为是为了传入函数更方便（少写一层 () => fn）的 useMemo，因此也会被这个问题牵扯

DEV Community: Lydia Yuan

Android Interview Prep Details: Part 1

Understanding Parameter Order in Kotlin's Primary Constructors

Lydia Yuan ・ Feb 23

Understanding Parameter Order in Kotlin's Primary Constructors

About thread join and run method in Java

Utilizing Git Submodules for Including a Separate Repository

Setting Up Git Submodules

Step 1: Create the Separate Repository

Step 2: Navigate to the Target Repository

Step 3: Add the Separate Repository as a Submodule

Step 4: Commit the Changes

Step 5: Push Changes to the Remote Repository

Benefits of Git Submodules

Cloning the Repository on Another Machine

Find the Smallest N Prime Numbers in Ascending Order

The Question

The Most Basic Trail Division

Less Checks & Cache Time Space Tradeoff

Sieve of Eratosthenes

Use Bit Masking to Save More Space

Writing a curried add in JavaScript

In-place Merge Sort in Java

Plain In-place Merge Sort

Shell Sort Mixed In-place Merge Sort

Top Down / Bottom Up Merge Sort in Java

Timing Experiment Results Prediction

Timing Experiment Results

Top Down / Recursive Merge Sort

Bottom Up / Iterative Merge Sort

concurrent mode 对 useRef 使用可能造成的影响

useLockFn 中 useCallback 的用途

useMemo / useCallback 将来可能的隐患以及可行的对策

起因

总结一下 React core team 成员对这个问题的回复

社区已经有的替代方案

目前 useRef 和 useMemo useCallback 具体实现原理

相关资料

目前 `useRef` 和 `useMemo` `useCallback` 具体实现原理