Design Unique ID Generator in Distributed Systems

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”

LeetCode 208. Implement Trie (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:

* Trie()
  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.
 
Constraints:

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.
 
Related Topics:

o Hash Table
o String
o Design
o Trie

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”

LeetCode 760. Find Anagram Mappings in Java

In this post we will solve LeetCode 760. Find Anagram Mappings problem using the Java programming language.

You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. 
Both arrays may contain duplicates.

Return an index mapping array mapping from nums1 to nums2 where 
mapping[i] = j means the ith element in nums1 appears in nums2 at index j. 
If there are multiple answers, return any of them.

An array a is an anagram of an array b means b is made by randomizing the order of the elements in a.

Constraints:

o 1 <= nums1.length <= 100
o nums2.length == nums1.length
o 0 <= nums1[i], nums2[i] <= 10^5
o nums2 is an anagram of nums1.

Related Topics:

o Array
o Hash Table

We are provided with two int[] holding two anagrams. We need to write a function that returns an index mapping array mapping from nums1 to nums2 where mapping[i] = j means the ith element in nums1 appears in nums2 at index j. Continue reading “LeetCode 760. Find Anagram Mappings in Java”

LeetCode 223 Rectangle Area in Java

In this post we will solve LeetCode 223 Rectangle Area in Java.

Given the coordinates of two rectilinear rectangles in a 2D plane, 
return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).

Constraints:

o -10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4

Related Topics:

o Math
o Geometry

We are given the coordinates of two rectilinear rectangles in a 2D plane and are asked to return the total area covered by the two rectangles. Continue reading “LeetCode 223 Rectangle Area in Java”

LeetCode 142 Linked List Cycle II in Java

In this post I will be solving LeetCode 142 Linked List Cycle II using the Java programming language.

This problem seems to be the continuation of a problem we solved earlier LeetCode 141 Linked List Cycle in Java in this blog. Perhaps you would like to read it before attempting to solve the problem in this post.

Given the head of a linked list, 
return the node where the cycle begins.
If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that 
can be reached again by continuously following the next pointer. 

Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed).
It is -1 if there is no cycle.
Note that pos is not passed as a parameter.

Do not modify the linked list.

Constraints:

o The number of the nodes in the list is in the range [0, 104].
o -10^5 <= Node.val <= 10^5
o pos is -1 or a valid index in the linked-list.

Related Topics:

o Hash Table
o Linked List
o Two Pointers

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

We are given a singly linked list which may or may not have a cycle. We need to return `null` if it does not contain a cycle, or the node where the cycle begins. The LeetCode web site contains some diagrams to better illustrate the linked lists with a cycle. Continue reading “LeetCode 142 Linked List Cycle II in Java”

LeetCode 242 Valid Anagram in Java

In this post we will be solving the LeetCode 242 Valid Anagram problem using the Java programming language.

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Constraints:

o 1 <= s.length, t.length <= 5 * 10^4
o s and t consist of lowercase English letters.

Related Topics:

o Hash Table
o String
o Sorting

We are given two strings. We need to determine if one string is the anagram of the other. Continue reading “LeetCode 242 Valid Anagram in Java”

LeetCode 872. Leaf-Similar Trees in Java

In this post we will be solving LeetCode 872. Leaf-Similar Trees. As usual, if interested, please visit the LeetCode site and read the current version of the problem to make sure all is well before you start developing code.

Consider all the leaves of a binary tree, 
from left to right order, 
the values of those leaves form a leaf value sequence.

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Constraints:

o The number of nodes in each tree will be in the range [1, 200].
o Both of the given trees will have values in the range [0, 200].

Related Topics:

o Tree
o Depth-First Search
o Binary Tree

We are given two binary trees. We need to determine if the sequence of leaf nodes match or not. Seems like an in-order tree traversal problem. We could populate a list with the leaf nodes of the first tree and repeat with the nodes of the second tree. Our answer will be based on the contents of both lists. Continue reading “LeetCode 872. Leaf-Similar Trees in Java”

LeetCode 669. Trim a Binary Search Tree in Java

In this post we will solve the LeetCode 669 Trim a Binary Search Tree problem. This problem is ranked a Medium by LeetCode. It took me some extra time to figure out what I had to do.

Given the root of a binary search tree and the lowest and highest boundaries as low and high, 
trim the tree so that all its elements lies in [low, high]. 
Trimming the tree should not change the relative structure of the elements that will remain in the tree 
(i.e., any node's descendant should remain a descendant).
It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. 
Note that the root may change depending on the given bounds.

Constraints:

o The number of nodes in the tree in the range [1, 10^4].
o 0 <= Node.val <= 10^4
o The value of each node in the tree is unique.
o root is guaranteed to be a valid binary search tree.
o 0 <= low <= high <= 10^4

Related Topics:

o Tree
o Depth-First Search
o Binary Search Tree
o Binary Tree

The problem clearly states that we are presented with a binary search tree which specifies the relationship between node values. Continue reading “LeetCode 669. Trim a Binary Search Tree in Java”

LeetCode 1185 Day of the Week in Java

In this post we will attempt to solve the LeetCode 1185 Day of the Week problem.

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

In a nutshell we are given a date in day, month, and year and we need to return a string that contains the name of the day. The problem is very easy to understand. Continue reading “LeetCode 1185 Day of the Week in Java”

LeetCode 232. Implement Queue using Stacks in Java

In this post we will attempt to solve LeetCode 232 Implement Queue using Stacks. I believe this problem is similar to another I solved in this blog several years ago. If interested take a look at the post Queue implemented with Stacks.

Continue reading “LeetCode 232. Implement Queue using Stacks in Java”