contains test scaffold – John Canessa

Rabin-Karp Algorithm – Revisited

In this post we will revisit the implementation of a string-search algorithm developed by Richard Karp and Michael Rabin.

We visited this algorithm in this blog a few years ago. My motivation is a book that I am currently reading. As soon as I am done reading and experimenting with some more advanced algorithms, I will generate several posts associated with the book.

In the meantime, let’s refresh what the Rabin-Karp algorithm is used for and go over an implementation using the Java programming language. Continue reading “Rabin-Karp Algorithm – Revisited”

LeetCode 111. Minimum Depth of Binary Tree in Java

In this post we will solve LeetCode 111. Minimum Depth of Binary Tree problem using Java and the VSCode IDE on a Windows computer. Not that it matters, but I am using Windows 11.

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path 
from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Constraints:

o The number of nodes in the tree is in the range [0, 10^5].
o -1000 <= Node.val <= 1000

Related Topics:

o Tree
* Depth-First Search
* Breadth-First Search
o Binary Tree

We are given the root of a binary tree and are asked to find the minimum depth of the tree. A couple years ago we solved in this post Maximum Depth of a Binary Tree.

The definition of minimum depth is provided in the requirements for the problem at hand. Continue reading “LeetCode 111. Minimum Depth of Binary Tree in Java”

LeetCode 295. Find Median from Data Stream in Java

In this post we will try to solve the LeetCode 295. Find Median from Data Stream problem using the Java programming language and the VSCode IDE on a Windows computer.

The median is the middle value in an ordered integer list. 
If the size of the list is even, 
there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

o MedianFinder()
	initializes the MedianFinder object.
o void addNum(int num)
	adds the integer num from the data stream to the data structure.
o double findMedian()
	returns the median of all elements so far. 
	Answers within 10-5 of the actual answer will be accepted.
	
Constraints:

o -10^5 &lt;= num &lt;= 10^5
o There will be at least one element in the data structure before calling findMedian.
o At most 5 * 10^4 calls will be made to addNum and findMedian.

Related Topics:

o Two Pointers
o Design
o Sorting
* Heap (Priority Queue)
o Data Stream

In a nutshell the class needs to process integers in the specified range and at different points we can be asked to return the current Median. As a brute force approach, I tried sorting. I did not submit such an approach because it is quite expensive (slow) and the problem is rated Hard by LeetCode. Continue reading “LeetCode 295. Find Median from Data Stream in Java”

HackerRank Largest Permutation in Java

In this post we will be solving the HackerRank Largest Permutation problem using the Java programming language, the VSCode IDE and a Windows computer.

You are given an unordered array of `unique integers` incrementing from 1.
You can swap any two elements a limited number of times.

Determine the largest lexicographical value array that can be created 
by executing `no more` than the limited number of swaps.

Constraints

o 1 <= n <= 10^5
o 1 <= k <= 10^9

We are given a list of unique integers incrementing from 1. We can swap two values at a time up to a number `k`. We need to return the largest possible permutation in the list. Continue reading “HackerRank Largest Permutation 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 1518. Water Bottles in Java

In this post we will solve LeetCode 1518. Water Bottles problem using the Java programming language.

There are numBottles water bottles that are initially full of water. 
You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, 
return the maximum number of water bottles you can drink.

Constraints:

o 1 <= numBottles <= 100
o 2 <= numExchange <= 100

Related Topics:

o Math
o Simulation

Before you start solving a problem associated with a website make sure you read the current description directly from the site in order to get the current description of the problem. On occasions descriptions may be updated providing additional information that may help you come up with a better solution faster. Continue reading “LeetCode 1518. Water Bottles in Java”

LeetCode 328 Odd Even Linked List in Java

In this post I will try three implementations of the function of interest for LeetCode 328 Odd Even Linked List problem using the Java programming language.

Given a singly linked list, 
group all odd nodes together followed by the even nodes.

Please note here we are talking about the node number and not the value in the nodes!!!

You should try to do it in place. 
The program should run in O(1) space complexity and O(nodes) time complexity.

Constraints:

o The relative order inside both the even and odd groups should remain as it was in the input.
o The first node is considered odd, the second node even and so on ...
o The length of the linked list is between [0, 10^4].

We are given a singly linked list. We need to group all `odd` nodes together followed by the `even` nodes. Please note the definition of what makes a node `odd` and `even`. It is not the value in the node but the position of the node in the linked list. Continue reading “LeetCode 328 Odd Even Linked List in Java”

LeetCode 169 Majority Element in Java

In this post we will attempt to solve LeetCode 169. Majority Element problem using Java.

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than floor(n / 2) times. 
You may assume that the majority element always exists in the array.

Constraints:

o n == nums.length
o 1 <= n <= 5 * 10^4
o -2^31 <= nums[i] <= 2^31 - 1

Related Topics:

o Array
o Hash Table
o Divide and Conquer
o Sorting
o Counting

We are given an int[] array and we must return the majority element. There are several variations of this problem. I believe we have solved a couple in this post. Continue reading “LeetCode 169 Majority Element in Java”

LeetCode 237. Delete Node in a Linked List in Java

I noticed that a second implementation of the function of interest was missing from this post. I have updated the GitHub repo and the post. Sorry about that!

In this post we will solve the LeetCode 237 Delete Node in a Linked List problem using the Java programming language and the VSCode IDE on a Windows platform. Java is quite portable so it should run on most (never generalize) platforms.

Write a function to delete a node in a singly-linked list. 
You will not be given access to the head of the list, 
instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Constraints:

o The number of the nodes in the given list is in the range [2, 1000].
o -1000 &amp;lt;= Node.val &amp;lt;= 1000
o The value of each node in the list is unique.
o The node to be deleted is in the list and is not a tail node

The problem at first glance seems to be simple. We have to delete a node from a singly linked list. The complication arises when we are only given the node to delete. In general, to delete a node from a linked list we are given the head of the linked list. Continue reading “LeetCode 237. Delete Node in a Linked List in Java”

Sum of Nodes Between Two Nodes in Binary Tree

Good day!!! Hope all is going well for you. It is Friday and has been a very stressful week for me. Glad that the weekend is just around the corner.

Today we are going to cover a problem which a software engineer and I discussed earlier this week, but for some reason or the other, we did not generate code at the time. We just talked about it.

We are given a binary tree with integer values and two different nodes in the binary tree,
we must return the sum of the values of the nodes that connect p and q inclusive.

Constraints:

o -1000 &lt;= val &lt;= 1000
o 2 &lt;= n &lt;= 200

As you can see, we are given a binary tree populated with integers. Do not recall if all integers were included. We will assume, since I am writing the requirements as we speak, that the values for the nodes are in the specified range and the number of nodes in the binary tree should not exceed the specified value. Continue reading “Sum of Nodes Between Two Nodes in Binary Tree”