Tag: includes test scaffold

First ChatGPT Post – Populate Binary Tree

Hope your weekend is going well. I will start with an unrelated event to the main subject of this post.

When I was working at my first job in Minneapolis, Minnesota the Red Cross would stop by at work for blood drives. They made it simple, so I started to give blood once a year.

Time went by and I decided to do it twice a year (one for my wife and one for me). I had my first appointment for 2023 last Friday afternoon. All went well as usual up to the point in which after the gauze was taped to my arm to protect the area from which the needle was removed. The technician offered a bandage to put pressure over the gauze to protect it for a couple hours. I have always declined and this time was no different. Continue reading “First ChatGPT Post – Populate Binary Tree”

Largest Triple Product Third Post in Java

In this post we will revisit a practice question Largest Triple Products. Not sure if today this question would be of interest to Facebook and /or to Meta Platforms technical job seekers.

My original post Largest Triple Products was superseded by Largest Triple Products – Revisited and by this latest post.

The motivation for this post came from a question left by Brent Boyer which suggested an implementation for the function of interest. I have included it in this post as `findMaxProduct3`. Continue reading “Largest Triple Product Third Post in Java”

LeetCode 307. Range Sum Query – Mutable in Java

In this post we will tackle the LeetCode 307. Range Sum Query – Mutable problem using the Java programming language and the VSCode IDE on a Windows computer. Unless you have a good reason (i.e., keep test code and solution on the same source code) my suggestion is to solve the problem using the online IDE provided by LeetCode.

Given an integer array nums, handle multiple queries of the following types:

o Update the value of an element in nums.
o Calculate the sum of the elements of nums between indices left and right inclusive 
  where left <= right.

Implement the NumArray class:

o NumArray(int[] nums)
	Initializes the object with the integer array nums.
	
o void update(int index, int val)
	Updates the value of nums[index] to be val.
	
o int sumRange(int left, int right) 
	Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
	
Constraints:

o 1 <= nums.length <= 3 * 10^4
o -100 <= nums[i] <= 100
o 0 <= index < nums.length
o -100 <= val <= 100
o 0 <= left <= right < nums.length
o At most 3 * 10^4 calls will be made to update and sumRange.

Related Topics:

* Array
o Design
o Binary Indexed Tree
* Segment Tree

We are given an int[] and asked to perform two operations as part of a class. Continue reading “LeetCode 307. Range Sum Query – Mutable in Java”

LeetCode 1504. Count Submatrices With All Ones in Java

In this post we will solve LeetCode 1504. Count Submatrices With All Ones problem using the Java programming language, the VSCode IDE on a Windows computer. My suggestion to you is that unless you have some special set of requirements, use the online IDE provided by LeetCode.

Given an m x n binary matrix mat, 
eturn the number of submatrices that have all ones.

Constraints:

o 1 <= m, n <= 150
o mat[i][j] is either 0 or 1.

Related Topics:

o Array
* Dynamic Programming
o Stack
o Matrix
o Monotonic Stack

In this problem we are provided a two dimensional matrix that only contains 1s and 0s. The dimensions are specified by `n` and `m`. Our mission if we wish to accept it, is to return the number of submatrices of 1s. Continue reading “LeetCode 1504. Count Submatrices With All Ones in Java”

LeetCode 42. Trapping Rain Water in Java

In this post we will solve the LeetCode 42. Trapping Rain Water problem using the Java programming language and the VSCode IDE on a Windows computer. The simplest approach is to develop the code on the online IDE provided by LeetCode.

Given n non-negative integers representing an 
elevation map where the width of each bar is 1, 
compute how much water it can trap after raining.

Constraints:

o n == height.length
o 1 <= n <= 2 * 10^4
o 0 <= height[i] <= 10^5

Related Topics:

* Array
* Two Pointers
o Dynamic Programming
o Stack
o Monotonic Stack

The diagram on the LeetCode page is very useful to get the general idea of what the problem is. It also helps to draw the diagram on a piece of paper and figure out an approach. We need to calculate the amount of water on each cell and add them together to get our result. The trick is in how we implement the task. Continue reading “LeetCode 42. Trapping Rain Water in Java”

LeetCode 949. Largest Time for Given Digits 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.

Related Topics:

o String
o Enumeration

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”

LeetCode 1804. Implement Trie II (Prefix Tree) 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”

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 904. Fruit Into Baskets 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.

Constraints:

o 1 <= fruits.length <= 10^5
o 0 <= fruits[i] < fruits.length

Related Topics:

o Array
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”

LeetCode 141 Linked List Cycle in Java

In this post we will solve the LeetCode 141 Linked List Cycle problem.

Given head, the head of a linked list, 
determine if the linked list has a cycle in it.

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. 
Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. 
Otherwise, return false.

Constraints:

o The number of the nodes in the list is in the range [0, 10^4].
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

We are given a singly linked list and are asked to determine if there is a cycle in it. If interested in the problem please take a look at the current description of it in the LeetCode website. Continue reading “LeetCode 141 Linked List Cycle in Java”