Insertion Sort implements an algorithm similar to ordering a hand of cards in ascending order. The algorithm is O(n^2) execution and typically is useful when sorting a rather small number of elements.
Several years ago (November 03, 2016) I generated the post Insertion Sort in this blog. The code snippets do not look nice. It seems that the tool I was using to format source code is no longer working as expected. Continue reading “Insertion Sort – Revisited”
It has been a few weeks since my last post. I apologize for this. Will let you know after my current quest is completed. Hopefully everything will turn out as I desire.
In the meantime I have been taking a few on-line courses.
I am almost done with the course C++20 Fundamentals by Paul J. Deitel. The course was released July, 2021 and published by Pearson3. The ISBN: 013687518. This online course is made available through O’Reilly. I am a member of the Association of Computing Machinery and have access to several O’Reilly titles. Continue reading “Bubble Sort in Java”
In this post I will not be solving a problem, instead I will be talking about something I learned by reading chapter 7 Design a Unique ID Generator in Distributed Systems in the book System Design Interview by Alex Wu.
The idea of a unique ID is a requirement in most distributed systems. In my case, some years ago I was developing a storage server and needed to name the objects of different types and sizes a client might wish to store and of course, at some later point in time, retrieve. The idea of a file system path did not make sense because it would be nearly impossible to keep the same immutable configuration among many distributed systems with a huge capacity. Continue reading “Design Unique ID Generator in Distributed Systems”
In this post we will solve LeetCode 681. Next Closest Time problem using the Java programming language, the VSCode IDE on a Windows computer. Please note that the computer platform and the IDE should make no difference. One of the simplest ways to solve the problem is to use the online IDE provided by LeetCode.
Given a time represented in the format "HH:MM",
form the next closest time by reusing the current digits.
There is no limit on how many times a digit can be reused.
You may assume the given input string is always valid.
For example, "01:34", "12:09" are all valid.
"1:34", "12:9" are all invalid.
* time.length == 5
* time is a valid time in the form "HH:MM".
o 0 <= HH < 24
o 0 <= MM < 60
We are given a string with a time expressed in 24-hour format. By reusing the digits as many times as needed, we need to form the next closest time. Continue reading “LeetCode 681. Next Closest Time in Java”
In this post we will solve the LeetCode 949. Largest Time for Given Digits problem using the Java programming language and the VSCode IDE on a Windows computer.
Given an array arr of 4 digits,
find the latest 24-hour time that can be made using each digit exactly once.
24-hour times are formatted as "HH:MM",
where HH is between 00 and 23,
and MM is between 00 and 59.
The earliest 24-hour time is 00:00, and the latest is 23:59.
Return the `latest`di 24-hour time in "HH:MM" format.
If no valid time can be made, return an empty string.
We are given an int array with four digits. We need to find the latest 24-hour time using exactly each digit once and return the results using the HH:MM format. Continue reading “LeetCode 949. Largest Time for Given Digits in Java”
In this post we will solve LeetCode 84. Largest Rectangle in Histogram problem using the Java programming language and the VSCode IDE on a Windows computer.
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1,
return the area of the largest rectangle in the histogram.
o 1 <= heights.length <= 10^5
o 0 <= heights[i] <= 10^4
* Monotonic Stack
We are given an array representing a histogram. The width of each bar holding a value is 1 unit. We are asked to return the area of the largest rectangle in the histogram. Continue reading “LeetCode 84. Largest Rectangle in Histogram in Java”
In this post I will solve LeetCode 1804. Implement Trie II (Prefix Tree) problem using Java and the VSCode IDE on a Windows computer.
In a previous post we discussed and implemented a solution for LeetCode 208. Implement Trie (Prefix Tree) in Java which is similar yet different to this one.
Please note that I carried away experimenting with the current problem as I did with the previous one. Due to this I implemented two solutions. After the first one was accepted I tried improving performance and readability. That created a second solution. Due to my approach I ended up with a large amount of code which I will post and comment on. For the first implementation I will go light on comments. Continue reading “LeetCode 1804. Implement Trie II (Prefix Tree) in Java”
In this post I will solve the LeetCode 208 Implement Trie (Prefix Tree) problem using the Java programming language and the VSCode IDE on a Windows computer. After the code was accepted by LeetCode I decided to add a couple features. The first one is to provide a method to access one of the main uses for a Trie (https://en.wikipedia.org/wiki/Trie). The second, which is based on the first one, is used to display, in order, the words inserted into the Trie.
A trie (pronounced as "try") or prefix tree is a tree data structure
used to efficiently store and retrieve keys in a dataset of strings.
There are various applications of this data structure,
such as autocomplete and spellchecker.
Implement the Trie class:
Initializes the trie object.
* void insert(String word)
Inserts the string word into the trie.
* boolean search(String word)
Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
* boolean startsWith(String prefix)
Returns true if there is a previously inserted string word that has the prefix prefix,
and false otherwise.
o 1 <= word.length, prefix.length <= 2000
o word and prefix consist only of lowercase English letters.
o At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
o Hash Table
The requirements are very well described. We need to implement the class Trie which must include a specific set of methods. In addition we need to specify the class members. Continue reading “LeetCode 208. Implement Trie (Prefix Tree) in Java”
In this post we will solve the LeetCode 904. Fruit Into Baskets problem using the Java programming language.
You are visiting a farm that has a single row of fruit trees arranged from left to right.
The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible.
However, the owner has some strict rules that you must follow:
o You only have two baskets, and each basket can only hold a single type of fruit.
There is no limit on the amount of fruit each basket can hold.
o Starting from any tree of your choice,
you must pick exactly one fruit from every tree (including the start tree) while moving to the right.
The picked fruits must fit in one of your baskets.
o Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
o 1 <= fruits.length <= 10^5
o 0 <= fruits[i] < fruits.length
o Hash Table
o Sliding Window
The two approaches that came to mind are using a hashmap, which should not have the best performance but should be acceptable, and the second using a sliding window, which should be faster than the one using a hashmap. Continue reading “LeetCode 904. Fruit Into Baskets in Java”
In this post we will solve the LeetCode 1302. Deepest Leaves Sum problem using the Java programming language with the VSCode IDE on a Windows computer.
Given the root of a binary tree,
return the sum of values of its deepest leaves.
o The number of nodes in the tree is in the range [1, 10^4].
o 1 <= Node.val <= 100
o Depth-First Search
o Breadth-First Search
o Binary Tree
We are given a binary tree and we need to return the sum of the values of all deepest leaves. Continue reading “LeetCode 1302. Deepest Leaves Sum in Java”