Hash Table

Why would one implement a hash table? When needed, software developers use existing classes which exhibit the properties of a hash table. For example, one might use a List or Dictionary class. That said; the user should fully understand the need and concept of a raw hash table.

A hash table is typically considered when the application requires random access speeds, the domain of values is large and an array would be sparse (most entices unused). The concept is to use some type of function that would allow quickly computing an index in a smaller array to store and looking up the element. Ideally the function would be uniform. That reduces collisions (multiple objects go into the same entry). A way to deal with that is to implement an overflow mechanism allowing multiple buckets Continue reading “Hash Table”

Johnny Cake

Last evening watched the Super Bowl LI game, halftime show and commercials. I am not a sports fan. That said; the game was amazing. The halftime show was very good. Not sure about the commercials. An effective commercial is one that you remember and takes you to the advertised product. Do not seem to recall any ad that fitted such description.

For some reason last night I was thinking about the FizzBuzz post. The code seems to work but I believe I fell short from describing what was going on and perhaps why was it of value. Would like it to revisit the same example but with a different name and similar code. Continue reading “Johnny Cake”

Circular Buffer – Part II

Last week I was chatting with software engineer about Circular Buffers. As far as I understand a circular buffer is a data structure typically implemented with an array of fixed length. There are two indices which are used to determine where to put / add / insert the next element and the other were to pull / remove the last element. The data structure implements a LIFO buffer.

I have used “Circular Buffers” on many occasions. The oldest implementations, besides college assignments, have been in device drivers on different real time operating systems to manage keyboard input, serial input and Internet input. A year or so ago I recalled a situation in which I used a Circular Buffer to implement copying files between two networked computers; one was the client and the other a server. Continue reading “Circular Buffer – Part II”

Iterator – Java

If you have a collection in some object oriented language (e.g., Java) you might be interested in traversing it. By traversing I mean visiting each and every one of the members in the collection in some specific order (e.g., front to back, back to front). Many collections already come with an Iterator. Some do not. In particular you may develop an object and wish to traverse it from first to last. In that case you could develop an Iterator.

If you wish to learn more about collections and iterators, I would recommend using a reference book (e.g., Algorithms fourth edition by Robert Sedgewick and Kevin Wayne) or perform a search on the Internet. Continue reading “Iterator – Java”

Circular Buffer – Part I

A circular buffer is an object used to ‘buffer’ data between Producer and Consumer. If the consumer is faster than the consumer, perhaps an intermediate object like a circular buffer would not be needed. If such condition cannot be guaranteed, then a circular buffer might be what the doctor ordered.

When I decided to write about this subject, I quickly went and designed and implemented a complete solution in C. Last night I decided that was not a good idea. Instead let’s start very simple with the basics and gradually increase the complexity of the solution as requirements evolve. I believe that is one of the main ideas for Agile. If you are an experienced software developer then you would immediately see the need for additional functionality in the initial implementation. In addition, depending on what the requirements are, several additional features might be required. I am not planning on spending a few days on this topic so I will try to get multiple implementations to some degree of functionality. Continue reading “Circular Buffer – Part I”

Pyramid Max Path

Was talking with a software developer regarding how to determining the max path of a pyramid. We discussed a solution but it is nice to see it come to live.

The following figure illustrates the structure of the pyramid:

 

The requirements are that the height be in the range 1 <= height <= 25. The tree is complete. There are no missing nodes. That implies that the base contains leaf nodes (no children). The values for the nodes should arbitrarily be in the range 1 <= val <= 100. Continue reading “Pyramid Max Path”

FizzBuzz

I ran into the FizzBuzz challenge at HackerRank (https://www.hackerrank.com/challenges/fizzbuzz?h_r=internal-search).

If you are interested take a look at the specified URL.

It was interesting the following statement:  Write a solution (or reduce an existing one) so it has as few characters as possible.

It seems to me that the practice of writing cryptic code should not be encouraged. That code needs to be maintained and in most cases modified. That said, given specific requirements, if needed very compact but efficient and well documented code is required in some cases. Continue reading “FizzBuzz”

Construct the Rectangle

I chose the following challenge from LeetCode: https://leetcode.com/problems/construct-the-rectangle/ and gave it a try.

f interested please follow the link to get the requirements.

The following is a screen capture of the console using the sample data:

area:        4 = [L:        2 W:        2]

Please note that the challenge only requires the method constructRectangle(). The test cases were generated by me.

Additional output from the console for additional tests follows: Continue reading “Construct the Rectangle”

Symmetric Difference

Received via email a message regarding the following HackerRank challenge: https://www.hackerrank.com/challenges/symmetric-difference?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

I liked that a refresher / tutorial preceded the actual challenge.

If interested use the above mentioned link and read the requirements.

Following is a screen capture from the Python console from the Spider 3 IDE: Continue reading “Symmetric Difference”

Bitwise AND of Numbers Range

What a humbling experience. Picked up at random a challenge at LeetCode (https://leetcode.com/problems/bitwise-and-of-numbers-range/)

The requirements are quite brief and one can easily determine what is required:

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4”.

I got a piece of paper and jotted down the following: Continue reading “Bitwise AND of Numbers Range”