Jinwon Park

This is question 13 from LeetCode.

It is a question where given the roman numeral character, find the integer value.

Some are just straight forward. Ex. III = 1 + 1 + 1 = 3.

Others require more calculation. Ex. IV != 1 + 5 = 6. IV = 4.

Each digits from left to right should flow from largest to smallest, except for cases like IV, where it is 5–1 instead of 5+1, when the order is reversed.

Below is my implementation of solution in Java. It took 13ms, which is a little below average for the success submission in LeetCode. I will comeback to optimize the solution.

--

--

Quick sort use divide-and-conquer strategy to sort. It is one of the most used sorting algorithms, as its time complexity is fast(O(nlog(n))).

How does it work?

  1. Select the pivot. It can be anything, but the I picked the last item in the list.
  2. Re-arrange the elements so that left side of pivot is smaller than pivot, and the right side of pivot is greater than pivot.(Partitioning)
  3. Repeat this process until the whole array is sorted.

Below is implementation of quick sort in Javascript.

--

--

Merge sort splits the list into two, again and again until each list has only one item. Then each items are sorted and merged, until it is merged to total list. It has time complexity of O(nlog(n)), which is efficient.

Below is implementation of merge sort in Javascript.

--

--

Insertion sort goes through the list and inserts items to the new list, one by one. It has time complexity of O(n) on average, and O(n²) on the worst case. Compared to merge sort or quick sort, its time complexity is not great. It is good for

  • List that is already almost sorted.
  • List of small number of elements.

Below is the implementation of insertion sort in Javascript.

--

--

Graphs are data structure that contains vertices(nodes) and edges. It looks like the image below.

Directed vs Undirected

In directed graph, vertex points to other vertex in one way, whereas undirected graph vertex points both ways.

Unweighted vs Weighted

In weighted graph, edges have values, whereas unweighted graph edges does not have values.

Cyclic vs Acyclic

In cyclic graph, vertices are connected circularly, whereas acyclic graphs does not contain vertices that are connected circularly.

So, the image above is undirected, unweighted, and cyclic graph.

Here is the implementation of graph in Javascript.

--

--