Forem: Balamurugan

Conway's Game Of Life - Coding Challenge - React & SpringBoot

Balamurugan — Sun, 21 Mar 2021 09:32:41 +0000

The Game of Life is not a game in the conventional sense. There are no players, and no winning or losing but its a good coding challenge to solve :)

The universe of the Game of Life is an infinite twodimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent.

Rules:

At each step in time, the following transitions occur:

Any live cell with fewer than two live neighbours dies as if caused by underpopulation.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. The Game of Life can be simulated using multiple patterns, I have set the default pattern as Glider Pattern (more info can be found here https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)) but it can be modified to any pattern before starting the game.

I have tried to solve this challenge with the backend using Spring Boot and the front end using React

As seen in the above diagram, the user needs to input data to start the game

User can modify the dimension of the matrix ( by default 20*20 )
User can modify the initial generation of live cells (by default glider pattern will be created at the top of the matrix)
Click START

Solution:

Based on the input data selected, the front end makes a request to the backend to retrieve the next generation of live cells which is populated in the UI.

If the validations are successful (matrix dimension is valid), in order to generate the next set of generations below steps are performed.

Consider eg an 8 * 5 dimension with initial live cells as [10, 19, 25, 26, 27]

For each of the initial generation, identify its nearest unique neighbours considering border conditions. In the above diagram example, [1, 3, 6, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]

It's best to use a HashSet in this case as this data further will be used for searching and searching in a HashSet will result in O(1)

For each of the identified cells, check whether they are going to be alive in the next generation by applying rules by identifying the neighbour for each cell and count the number of cells which are ALIVE in the current generation (by comparing against input).

For eg, Cell 1 (current dead cell) -> neighbours are 2(L), 9, 10 and only one cell is currently live and hence as per rules, it won't survive the next generation.

Also for cell 10(current dead cell), -> neighbours are 1, 2(L), 3, 9, 11(L), 17, 18, 19(L) and exactly 3 cells are currently live which will make 10 to be alive in next generation
Also for cell 19( current live cell), -> neighbours are 10, 11(L), 12, 18, 20, 26(L), 27(L), 28. We will have 3 cells that are currently live and as per rules, this can survive in the next generation.

Similarly for each cell, their next-generation status is identified.

Collect the cells which are alive in the next generation and return the result set

This solution is available in Game of Life UI

Regardless of the size of the matrix, this solution would take constant time(considering a finite number of alive cells) because the size of the matrix is not used in any calculation apart from identifying the neighbour cells which will be constant. If you have solved this problem in a more efficient approach, Please share it here I would like to know.

Repository :

UI
API
Swagger for API

Understanding equals and hashCode in Java

Balamurugan — Sun, 31 Jan 2021 23:39:39 +0000

This post was originally published here at https://balasr.com/blog/2n857rotH9da7mBF5ZWO2V

This is going to be one of the series of posts related to Interview topics that I would be writing. In this post, we are going to explore the importance of equals and hashCode methods in Java.

equals() and hashCode() are two methods that are part of every class in Java. Object class is the superclass for all other classes in Java. equals and hashCode are the methods that are part of the Object class

As a general rule,

If two objects are equal according to the implementation, their hashCode should match!

Let us approach understanding this with a scenario, Have you ever noticed what happens when an identical order is placed in Dominos app within a stipulated time by mistake?

Any duplicate orders will be rejected as they suspect it could be due to a mistake.

It's recommended that both equals and hashCode methods need to be overridden to achieve better business decisions. So why its best to override these implementations? Before that, we need to understand what does the base implementation does.

**equals() base method**

As Java is an Object-oriented programming language, except for primitives everything else is an object in Java.

public boolean equals(Object obj) {
        return (this == obj);
}

The base implementation compares and identifies whether the current object and the passed object are one and the same i.e., they share the same memory location as in the below diagram. Both the objects have the same reference in the heap memory

**hashCode() base method**

This method returns the hash value of the given object as an integer value. Within the application lifetime, it's expected that the hashCode value of an object remains the same regardless of the however number of times it got invoked.

Hence if 2 objects are considered equal according to the default equals method then their hashCode value will always be the same.

**Overridding equals() method**

Coming back to our scenario, according to our requirement, any 2 orders are equals if their attributes (ordering user, order items, quantity, and delivery address) are the same. So let's override the equals method to reflect the same
equals method alone overridden as below

Result when the equal method is overridden

**Impact if hashCode() method is not overriden**

The impact would be visible if the orders are stored in hash-based collections. For instance, consider the below example where orders are maintained in HashSet and we try to perform whether the newly received order is already present with us. This would be a problem as we have not overridden the hashCode method yet

As you can see in the above image, 2 orders even as per our requirements are equal, it's being considered as not equal.

**Overriding hashCode() method and equal()**

Let's override the hashCode method to include a combination of our attributes (this is one of the ways) for comparison

Now let us compare orders with both equal and hashCode overridden as per our requirement

As we can see, overriding equals and hashCode method results in exactly what we are looking for in case of any type of collections the orders are being stored

So always respect the contract, it's binary either both methods (equals and hashcode) should be overridden or none of both methods.

This will be one among the series of posts that I would be writing which are essential for interviews. So if you are interested in this thread and found it useful, please follow me at my website or dev

Understanding Hashmap

Balamurugan — Sun, 03 Jan 2021 22:29:03 +0000

This is going to be one of the series of posts related to Interview topics that I would be writing. In this post, we are going to explore hashmap. I couldn't remember any interview without Hashmap being involved.

So what is Hashmap?

In Simple terms, Hashmap stores data in key-value format.

Let's take an example of key-value pairs

myCloset={
"RoundNeckTShirts":5,
"VNeckTShirts":3,
"NightPyjamas":5,
"Trousers"5
}

Each and every value inside the object will be stored as a key-value in the form of an array, but how to identify which pairs are stored in which array index?

That is where Hash functions come into the picture

Hash Functions uses the key to calculates the index in which the key-value pair needs to be stored. Various programming language uses a different hash function to calculate the array index. Let's take the below example for instance

Imagine you have a chest of drawers and you want to arrange your kid's clothes in it category wise(as shown in cover pic), For eg, if its a Nightdress, it should go into the Pajamas drawer, if its a V Neck Top, it should go into T-Shirts drawer, etc

Similarly, the hash function helps identify the array index (drawer in this example) where the key-value pair(clothes in this instance) needs to be stored.

Hence regardless of the number of inputs to be stored, big O notation for insert will always be o(1) because the amount of work and the time required to perform the operation(Identify hash -> Identify index position -> Store the value ) doesn't change based on the volume of data

Hash Collision

Obviously, you will have more than one set of clothes under one category(in this example) like below which is quite possible but it should be avoided. This is termed as Hash Collision

During data insertion, If more than one data returns the same value from a hash function then hash collision happens and the data is stored in the same bucket with reference to one another

During data retrieval, if there are multiple nodes present in each bucket, then each of them is compared against the target value to retrieve the data from the bucket. Hence the best case(if there are no collisions) Big O would be o(1) and worst-case ( if there are multiple collisions and more data are stored in the same bucket) then each item will be compared against the target from the top to bottom until an element is found which might lead to o(n) - depending on the number of elements

Load Factor

The Initial capacity of buckets in this example is 5(number of chest drawers), Load factor is the measurement of how much the buckets can be filled before additional capacity is increased. This factor differs for different programming languages. In Java, it is 0.75f with an initial capacity of 16 buckets hence 0.75*16= 12. After storing 12 keys, an additional 16 buckets will be added to the capacity.

So overall HashMap/Table is one of the most efficient data structures, it becomes worse if there are more collisions. Below Big O cheatsheet can be found here

Here is a link where you can visualize the manipulation in the hashmap

This will be one among the series of posts that I would be writing which are essential for interviews. So if you find are interested in this thread and found it useful, please follow me at my website or dev