Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although some of them were already taught in the University, it’s still good to summarise here

1. Selection Sort

  • In iteration i, find index min of smallest remaining entry.
  • Swap a[i] and a[min]

Selection Sort Gif

class Selection {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min]))
                    min = j;
            swap(a, i, min); // swap the 2 items
        }
    }
}
Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, it’s still good to summarise here

1. Stacks

Stack

Last In First Out

Linked-list Implementation

Maintain a pointer to the first item of the linked-list. Add or remove are simply to update that pointer.

public class LinkedStackOfStrings {
    private Node first = null;

    private class Node {
        String item;
        Node next;
    }

    public void push(String item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public String pop() {
        String item = first.item;
        first = first.next;
        return item;
    }
}
Read more

So, my friend gave me this exercise and asked me to solve it. Sometimes it’s fun to solve algorithm problem… sometimes…

Given an array A of n integer numbers, find all the (i,j) pairs such that A[i] + A[i+1] + A[i+2] + … + A[j] = 6. For example, A = [1, 5, 4, -2, 4, 8, 7, 9, 0], these pairs are valid i,j (0,1) and (2,4) because sum(A[0->1])=6 and sum(A[2->4])=6

Of course, the worst solution is to perform n2 operations. For each number in A, do another loop inside that to find the sub-sequence having the sum = 6.

Surely there should be a better solution. And here is the O(n) solution.

Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course.

Question

Suppose that you have an nnn-story building (with floors 1 through nnn) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of T given the following limitations on the number of eggs and tosses

Solution 1

1 egg, ≤T tosses

This is an O(n) solution. Just do a simple loop from the first floor until the egg break.

Solution 2

∼1lgN eggs, ∼1lgN tosses

Use Binary search strategy.

  • Start from the middle floor, drop the egg
  • If it breaks, repeat with the lower half
  • Otherwise, repeat with the upper half

Solution 3

∼lgT eggs, ∼2lgT tosses

Read more

An interviewer once asked me this question. At first, I was a bit nervous and thought that this is a very tricky question. It took me a while to figure out the solution and turned out this can be converted to a simpler algorithm we already learned in University.

Question

Given a computer with only 1MB of RAM and unlimited hard disk space, sort a file which contain 1 million 8-bit integers, each on one line.

Solution

The problem with this is our computer is limited in memory. We cannot read all 1 million integers at once into the memory. That means we can only read some small parts of the file, which leads me to a divide and conquer solution like this. The basic idea is to divide the large problem into smaller one, process each of them and then try to merge the result.

  • First, read a number of integers that can fit into the memory. Actually, you should read the number of integers that can fit in the RAM/2 space (which is 512KB in this case). The reason is in the next part
  • Perform any sort algorithm that you can think of on that array. Because you need another array for storing the result, you can only read only the number of integers that can fit in half of your RAM.
    • In this case, each 8-bit integer is 2 bytes, so each time you can only retrieve maximum 512KB * 1024 / 2B = 262,144 integers.
  • After the array is sorted, write them back to a file.
  • Repeat the above steps until you finally process all the integers in the source file.
    • You will need to read 4 times in this case
  • Now you have a collection of sorted integers files. The next step is to apply merge sort on those file to produce the final output file. The merge sort algorithm is like this
    • Read the 2 sorted files, line by line
    • Compare the 2 values
    • Compare which one is smaller, write to the output file
    • Repeat the above steps until we reach the end one 1 of the 2 files
    • Write back all the remaining values of the other files to the output file

Pseudo code

Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course.

1. The 3-sum problem

3-sum not 3-some For fun picture: 3-sum not 3-some 🤣

But I wish there were an algorithm like that in reality 😂

The 3-sum problem is described as below

Given N distinct integers, how many triples sum to exactly zero?

Read more

Overview

Long time ago, I worked one a project which allowed users to select images on a 2D canvas and then draw that image on a cylinder surface (the mug in this case).

I had to Google for the suitable libraries but I couldn’t find any. I also asked a question on stackoverflow but the answer did not satisfy me. The reason is that it demonstrates how to stretch the image, not how to bend the image (which is what shown in the picture above). Because of that, I decided to implement it by myself and turned out that it was not as hard as I thought before. Everything is just a loop of basic mathematic formula that I had been taught in (Vietnamese) high school.

Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Here are some Quick Union related interview questions and my answers

1. Social network connectivity

Question

Given a social network containing n members and a log file containing m timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be mlogn or better and use extra space proportional to n.

Answer

The earliest time at which all members are connected is when we union all into 1 connected component (1 tree). That means all the nodes in the tree have the same root.
This is an improvement of weighted quick union algorithm. Every time we call the union, we will check the weight of the tree to see whether it is equal to the size of n.

Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course.

Weighted Quick Union

  • Use Quick Union but avoid tall tree, to avoid traversing through very long path
  • Use an extra array to track the size of each tree (stored in the root node)
  • Link the smaller tree to the root of the larger tree
  • The size of the new tree is the total size of both tree

Read more

Nothing special here. It’s just a blog post for summarising my algorithm learning course.

Approach

The underlying data structure for Quick Union is similar to Quick Find. We need an array for all the items. The values are still the id, but it’s the id of the parent item. The connected component is organised using a tree structure like this

  • isConnected(p, q) check whether the 2 items have the same root
  • union(p, q) set the id of p’s root to the id of q’s root
Read more