DEV Community: genichm

Prepare to Coding Interview > Know Data Structures > Hash Table

genichm — Sat, 03 Dec 2022 13:39:25 +0000

Hash table is a mapping between keys and values, each key can have several values, values can repeat, some implementations of the hash tables does not allow repeating values.

Adding value to the hash table

Compute the hash code
Map the hash code to the array index by hashCode % array.length
Put the value to the index

Get the value from Has Table

Compute the hash code
Map the hash code to the array index by hashCode % array.length
Go to the index and find the value if present

Base implementation with C# is below:

public class HashTableSimpleImplementation
{
    /*
        * Simple implementation of HashTable
    */
    private LinkedList<string>[] _hashTable;

    private int _hashTableSezie = 10;

    public HashTableSimpleImplementation()
    {
        _hashTable = new LinkedList<string>[_hashTableSezie];

        Init();
    }

    private void Init()
    {
        for(int i=0; i < _hashTable.Length; i++)
        {
            _hashTable[i] = new LinkedList<string>();
        }
    }

    /// <summary>
    /// Adding value to the hash table
    /// 1. Compute the hash code
    /// 2. Map the hash code to the array index by hashCode % array.length
    /// 3. Put the value to the index
    /// </summary>
    /// <param name="value"></param>
    public int Add(string value)
    {
        var index = GetIndex(value);

        _hashTable[index].AddLast(value);

        return index;
    }

    /// <summary>
    /// 1. Compute the hash code
    /// 2. Map the hash code to the array index by hashCode % array.length
    /// 3. Go to the index and find the value if present
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public string? Get(string value)
    {
        var index = GetIndex(value);

        var list = _hashTable[index];

        foreach(var item in list)
        {
            if (item.Equals(value))
            {
                return value;
            }
        }

        return null;
    }

    private int GetIndex(string value)
    {
        var hashCode = GetHashCode(value);

        var index = hashCode % _hashTableSezie;

        return index;
    }

    /// <summary>
    /// This implementation of hash code returns different code
    /// for the same string value on each run of the application
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    private int GetHashCode(string value)
    {
        var hashCode = value.GetHashCode();

        return hashCode > 0 ? hashCode : hashCode * -1;
    }
}

Layered Pattern

genichm — Wed, 30 Sep 2020 18:10:34 +0000

Layered pattern is the most well known and used, probably everyone uses or used this pattern in application development. This pattern splits the code into layers where each layer has responsibility, upper layers call to underlying layers to execute the operations. For example:

UI layer
Application layer
Data access layer

UI layer calls to the application layer it in turn executes functions from the data access layer which stores the data in some data storage.

CQRS (Command and Query Responsibility Segregation) Architectural Pattern

genichm — Mon, 28 Sep 2020 11:29:35 +0000

Following the comment of @klyse in my post. I decided to explain in a few words what is CQRS pattern and how we implemented it in our ETL system.
Command and Query Responsibility Segregation pattern separates reads and updates operations for data storage. I.e. the complete separation between insert/update and select operations.
If you want to understand the pattern better I can recommend the following article https://docs.microsoft.com/en-us/azure/architecture/patterns/cqrs

How we implemented it in our ETL system.

In the heart of our system located 2 microservices, 1. The processing service that is responsible for processing and calculations of the data consumed from the Kafka topic has only select queries for data that helps to accomplish the mission, at the end processed data produced to another Kafka topic and 2. Sync service responsible for synchronization of processed data to our time-series ETL database TimescaleDB and the multi-tenant data storage SQL Server. This service updates and inserts processed data into the databases.

Why we selected this pattern

The main reason is flexibility in scalability. Our reads and writes operations are not balanced, it means that when we scale-out the number of processing and synchronization services is not the same.
Second but very important reason is data consistency, all the updates and inserts operations done by the same service and the same code.
Ability to navigate the data to the different systems by developing new synchronization services.
Great flexibility in the development process.

Below you can see the container diagram of this part of the system.

Design Patterns With Examples in C#

genichm — Sun, 13 Sep 2020 19:41:16 +0000

A list of design patterns with examples in C#
[Observer, Adapter, Facade, Singleton, Factory Method, Bridge]

Behavioral patterns

Observer

Allows objects to notify other objects about changes in their state (publisher and subscribers). More information with the example available here https://docs.microsoft.com/en-us/dotnet/standard/events/observer-design-pattern


interface IObserver{
    void Update(object update);
}

interface ISubject{
    void Attach(IObserver observer);
    void Detach(IObserver observer);
    void Notify();
}

class Subject: ISubject{
    private List<IObserver> _subjectObservers;

    public Subject(){
        _subjectObservers = new List<IObserver>();
    }

    void Attach(IObserver observer){
        _subjectObservers.Add(observer);
    }

    void Detach(IObserver observer){
        _subjectObservers.Remove(observer);
    }

    void Notify(){
        foreach(var observer in _subjectObservers){
            observer.Update("Some state");
        }
    }

    /*
        Some logic that calls to Notify when needed
    */
}

class ObserverA: IObserver{
    void Update(object update){

    }
}

class ObserverB: IObserver{
    void Update(object update){

    }
}

class SomeClass{
    public void Init(){
        var observerA = new ObserverA();
        var observerB = new ObserverB();
        var subject = new Subject();
        subject.Attach(observerA);

    }
}

Structural patterns

Adapter

Allows incompatible interfaces to work together


class ToAdapt{
    public int Calculate(int a, int b){
        return a * b;
    }
}

class IAdaptInterface{
     public void CalculateWithLessParameters(int a);
}

class Adapter: ToAdapt, IAdaptInterface{
    public int CalculateWithLessParameters(int a){
        return Calculate(a, 10);
    }
}

Facade

Provides a simplified interface to complex classes, libraries

public class MemoryCacheFacade
{
    private MemoryCache _memoryCache;

    public MemoryCacheFacade(MemoryCacheOptions memoryCacheOptions)
    {
        _memoryCache = new MemoryCache(memoryCacheOptions);
    }

    public void Set<TItem>(object key, TItem value)
    {
        _memoryCache.Set(key, value);
    }

    public bool TryGetValue<TItem>(object key, out TItem result)
    {
        if (_memoryCache.TryGetValue(key, out result)) 
        {
            return true;
        }

        return false;
    }

    public ICacheEntry CreateEntry(object key)
    {
            return _memoryCache.CreateEntry(key);
    }
}

Bridge

Bridge design pattern decouples implementation from an abstraction. Useful in versioning when a new software replaces the old but both should run together for the existing codebase.


class Abstraction{
    Bridge _bridge;
    public Abstraction(Bridge bridge){
        _bridge = bridge;
    }

    public string Execute(){
        _bridge.ExecuteSomeFunction();
    }
}

interface IBridge{
    void ExecuteSomeFunction();
}

class Version1: IBridge{
    public void ExecuteSomeFunction(){

    }
}

class Version2: IBridge{
    public void ExecuteSomeFunction(){

    }
}

static void Main(){
    (new Abstraction(new Version1())).Execute();
    (new Abstraction(new Version2())).Execute();
}

Creational patterns

Singleton

Design pattern ensures that only one object of its type exists and there is an access point to that object.

Private constructor https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/private-constructors


class Singleton{

    private static Singleton singeltonInstance=null;

    /*
        Private constructor here is to prevent creation of
        multiple instances of this class
    */
    private Singleton()  
    {  
    } 

    public static Singleton SingletonInstance{
        if(singeltonInstance == null){
            singeltonInstance = new Singleton();
        }
        return singeltonInstance;
    }

}

Factory Method

Provides an interface for creating objects without specifying their concrete classes.

interface IShip{
    string Name();
}

class BigShip: IShip{
    public string Name(){
        return "Big ship";
    }
}

class SmallShip: IShip{
    public string Name(){
         return "Small ship";
    }
}

class Creator{
    private bool _bigShipAvailable = true;
    public IShip FactoryMethod(){
        if(_bigShipAvailable){
            _bigShipAvailable  = false;
            return new BigShip();
        }else{
            return new SmallShip();
        }
    }
}

Practical Tips on How to Design Code That Makes Unit Testing Easier and More Easily Maintainable

genichm — Sat, 29 Aug 2020 07:11:55 +0000

It’s surprisingly easy to write and maintain unit tests. All you have to do is the following:

Use a dependency injection
Separate functions executor from function holder classes
Functions in functions holder class should not have dependencies among them

1. Use a dependency injection

In a few words a dependency injection is a passing object to another object. For example:

class Receiver(IDependcyClass dependencyClass){
}

It makes unit tests much easier as using this design pattern makes it possible to inject mocked behavior into the class under the test. If you want to understand dependency injection better, I recommend that you read James Shore’s post http://www.jamesshore.com/v2/blog/2006/dependency-injection-demystified

2. Separate functions executor from function holder classes

Inject the functions into the class that executes the functions.

class A(){
        private readonly IB _b;
    public A(IB b){
        _b = b;
    }
    void ExecuteTheFlow(){
        _b.A();
        _b.B();
        _b.C();
    }
}

3. Functions in a functions holder class should not have dependencies among them.

void Func1(){
  var list = GetList();
}

Should be

void Func1(List<..> list){

}

The following examples explain how to design code for the unit to be more easily testable.

All the examples are created with the C# language and the XUnit testing framework.

Here is the class we want to test. Interface IDependency was injected as an example of a dependency injection.

public class ClassToTest
{
    private readonly IDependency _dependency;

    public ClassToTest(IDependency dependency)
    {
        _dependency = dependency;
    }

    public int? GetResult(int a)
    {
        var result = _dependency.ReturnValue(a);

        var subtracted = Subtract(result);

        if (subtracted < 2)
        {
            _dependency.SomeFunctionA();
        }
        else
        {
            _dependency.SomeFunctionB();
        }
        return subtracted;
    }

    public int? Subtract(int? value)
    {
        if (value < 4)
        {
            return value - 1;
        }
        return null;
    }
}

We want to ensure that if the function GetResult received a value lower than 4, then 1 subtracted from the value else returned a null. And if the value is lower than 2 after subtraction, call the function A. Otherwise call the function B.

Here are the tests that ensure it:

public class TestClassTests
{
    [Fact]
    public void Sutructed_1_IfTheValueIsLowerThan4()
    {
        var value = 1;

        var expected = 0;

        var dependencyA = new Mock<IDependency>();

        dependencyA.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(value);

        var target = new ClassToTest(dependencyA.Object);

        var result = target.GetResult(value);

        Assert.Equal(expected, result);
    }

    [Theory]
    [InlineData(4)]
    [InlineData(5)]
    public void Returned_Null_IfTheValueIsGreaterOrEqualTo4(int value)
    {

        int? expected = null;

        var dependencyA = new Mock<IDependency>();

        dependencyA.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(value);

        var target = new ClassToTest(dependencyA.Object);

        var result = target.GetResult(value);

        Assert.Equal(expected, result);
    }

    [Fact]
    public void EnsureTheFlow_SomeFunctionA_CalledIfReturnedValueLowerThan2()
    {
        var dependency = new Mock<IDependency>();

        dependency.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(2);

        var target = new ClassToTest(dependency.Object);

        var result = target.GetResult(It.IsAny<int>());

        dependency.Verify(x => x.SomeFunctionA(), Times.Once());
    }

    [Theory]
    [InlineData(3)]
    [InlineData(4)]
    public void EnsureTheFlow_SomeFunctionB_CalledIfSubtractedValueGreaterOrEqualTo2(int value)
    {
        var dependency = new Mock<IDependency>();

        dependency.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(value);

        var target = new ClassToTest(dependency.Object);

        var result = target.GetResult(It.IsAny<int>());

        dependency.Verify(x => x.SomeFunctionB(), Times.Once());
    }
}

The tests will work so what’s the problem with the tests in the example?

We want to achieve 2 goals — unit tests that are easier to 1. write and 2. maintain. The problem in the code design above is that if somebody refactors and by mistake replace if (value < 4) with if (value > 4) in the function Subtract some of the tests will fail without clear indication of where the problem is. At that moment the developer will start to debug the code in an attempt to find the reason for the unit tests failing. Remember the 60 / 60 rule: 60% of the life cycle costs of software systems come from maintenance (average). Here we start to mess with rules as we create code that is more difficult to maintain, so the cost of maintenance will increase proportionally to the nerves of the developer on finding the problem and why the tests fail.
Code is usually, much more complicated and functions call to functions that call to functions… One regression can fail tens of tests and not one of them will clearly point to the source of the problem.

Let’s improve this. Look at the example of the class to test below.

public class ClassToTest
{
    private readonly IDependency _dependency;

    public ClassToTest(IDependency dependency)
    {
        _dependency = dependency;
    }

    public int? GetResult(int a)
    {
        var result = _dependency.ReturnValue(a);

        var subtracted = _dependency.Subtract(result);

        if(subtracted < 2)
        {
            _dependency.SomeFunctionA();
        }
        else
        {
            _dependency.SomeFunctionB();
        }

        return subtracted;
    }
}

Here are the tests

public class TestClassTestsRight
{
    [Fact]
    public void Sutructed_1_IfTheValueIsLowerThan4()
    {
        var expected = 0;

        var value = 1;

        var target = new Dependency();

        var actual = target.Subtract(value);

        Assert.Equal(expected, actual);
    }

    [Theory]
    [InlineData(4)]
    [InlineData(5)]
    public void Returned_Null_IfTheValueIsGreaterOrEqualTo4(int value)
    {
        var target = new Dependency();

        var actual = target.Subtract(value);

        Assert.Null(actual);
    }

    [Fact]
    public void EnsureTheFlow_SomeFunctionA_CalledIfReturnedValueLowerThan2()
    {
        var dependency = new Mock<IDependency>();

        dependency.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(1);

        dependency.Setup(x => x.Subtract(It.IsAny<int>())).Returns(1);

        var target = new ClassToTest(dependency.Object);

        var result = target.GetResult(It.IsAny<int>());

        dependency.Verify(x => x.SomeFunctionA(), Times.Once());
    }

    [Theory]
    [InlineData(2)]
    [InlineData(3)]
    public void EnsureTheFlow_SomeFunctionB_CalledIfReturnedValueGreaterOrEqualTo2(int value)
    {
        var dependency = new Mock<IDependency>();

        dependency.Setup(x => x.ReturnValue(It.IsAny<int>())).Returns(value);

        dependency.Setup(x => x.Subtract(It.IsAny<int>())).Returns(value);

        var target = new ClassToTest(dependency.Object);

        var result = target.GetResult(It.IsAny<int>());

        dependency.Verify(x => x.SomeFunctionB(), Times.Once());
    }
}

The function Subtract moved to class Dependency and tested separately. The flow in the GetResult function tested separately too. It means that if somebody replaces if (value < 4) with if (value > 4) tests related to the particular function will fail, but the flow test will succeed as the flow has no regression. The developer can see where is the problem and why things fail. If something is changed in the GetResult function, only tests related to that function will fail and point to issues with the flow.

You can download the examples from https://github.com/genichm/unit-tests-example. They were created with .NET Core 3.1 and use the XUnit testing framework.

How you survive SCRUM?

genichm — Mon, 03 Dec 2018 21:11:31 +0000

Question to everyone who works in company that adopted SCRUM methodology. We adopted the methodology more than a year ago and I feel like worker in production line where the product is small and short tasks. For the first time from 2004 I'm not evolving in my coding skills and started pet project for not loose the ability to code complex solutions and make complex decisions. Thanks that it is only 50% job for me all other time it's architecture and technologies testing that helps to stay sharp too. So how you survive it?

Explain GPLv2 License like I am five

genichm — Fri, 06 Apr 2018 15:47:44 +0000

Explain in few words what is Continuous Integration, Delivery, and Deployment?

genichm — Tue, 17 Oct 2017 07:21:15 +0000

I need short explanation what is Continuous Integration, Delivery, and Deployment.

What is the pros and cons of TDD in our case and is it required at all?

genichm — Sun, 15 Oct 2017 20:37:22 +0000

Small intro, at this moment we are developing new system and have automation tests for web interface, unit tests for part of server side code, code reviews and sharing of knowledge in the team. Unit tests partial because of philosophy of writing valuable tests where you know what you want to validate and don't need to invent subject of validation.
We are not lunching rockets so nobody will die in case of bug. Also the aim is to get to continuous delivery and in case of bug the fix will published quickly (if it found). Applications has web client, api, many micro services and works with big databases of hundreds gigabytes of data, but we are not data creators we mostly consumers. Each service and part of application going to be continuously monitored by analytics system. Also we work with key value storages, queues and documents database. Most of logic is in database or API.
In few words nothing critical will happen in case of bug. But reputation is important too.

The questions are:

What's yours pros and cons for working with TDD methodology
Do TDD rises code quality? Is it true or only some legend to sell TDD?

And some personal question to everybody, don't you think that working with methodology like TDD that gives you way you have to develop your applications limits you in some frame? It looks little bit ridiculous that I can't use static variables and functions or singletons and it's only small part of the restrictions.

Thanks to all.