Dmitrii's Blog

Our online Coding Dojo sessions became the most powerful learning experience for me, and recently we came across Conway’s Game of Life.

I remember playing this game on paper when I was a child. Yesterday I had the pleasure to code the rules and see them working.

To make it more fun, we in our Coding Dojo club decided to separate concerns between “cells” and “grid” where the cells exist. After an exciting discussion for which I am grateful to Dennis, Saeed and Byron, I had started an all-nighter.

Here is what I got with a sunrise:

Conclusion:

I can not deny that SOLID code has its price. It takes much more time (2x or maybe 3x to compare to writing a monolithic code).
Nevertheless, we get benefits such as extensibility and reusability.

Let’s say we want to run the same game in 3D space. We can easily make this modification with SOLID code.

The LeetCode page for this task can be found here

Link to the description of the task: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Link to the description of the task: https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

Straightforward Solution:

Time Complexity Analysis:

List.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

List.AddRange(anotherList) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherList.Count

List.Contains(member) -> O(k) where k is Count

Loop:

1. Take a record from the log
2. Get groups ids for each member {List.Contains(member)} -> 2 * O(n)
3. If the ids are the same then do nothing
4. If one of the ids is null then add the member {List.Add(newFriend) -> O(1) or O(k)
5. If both are null then create new Group {new List{a, b}} -> O(2)
6. If not null and different then merge groups {List.AddRange} -> O(l)
7. If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(n). Also, m must be equal or larger then log(n) to make all members connected. This way the solution complexity is at least O(log(n) * n)

Two problems with this method:

1. Getting a group id for a member is too slow (O(n))
2. Merging groups is slow (O(n)) in the worst-case scenario

Straightforward Solution with HashSet:

Time Complexity Analysis:

HashSet.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

HashSet.UnionWith(anotherHashSet) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherHashSet.Count

HashSet.Contains(member) -> O(1)

Loop:

1. Take a record from the log
2. Get groups ids for each member {HashSet.Contains(member)} -> 2 * O(1)
3. If the ids are the same then do nothing
4. If one of the ids is null then add the member {HashSet.Add(newFriend) -> O(1) or O(k)
5. If both are null then create new Group {new HashSet{a, b}} -> O(2)
6. If not null and different then merge groups {HashSet.UnionWith} -> O(l)
7. If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(l). It is possible to minimize l by comparing HashSet.Count and anotherHashSet.Count, and then adding smallest to the biggest.

This way the total complexity is about O(m * log(n)) which makes the answer acceptable.

Link to the description of the task: https://leetcode.com/problems/add-two-numbers/

Conclusion:

It looks pretty nice!

When you set a reference type to ‘null’ like this:

string str = null;

it means that it’s undefined. It’s not a zero or empty. It’s nothing. I wonder what nothing looks like inside of computer memory.

Continue reading “C#: What ‘null’ looks like in computer memory?”