DEV Community: Nam Nguyen

How To Solve Algorithm And Data Structure Problems [Tips]

Nam Nguyen — Thu, 10 Sep 2020 04:45:29 +0000

Are you struggling to solve coding problems? I’d like to share my own method to approach the solution. This is a reference on which I can build your own.

Table of Content

A. 5 Steps To Solve A Problem
B. Example
C. Summary

A. 5 Steps To Solve A Problem

1. Comprehend problem

Read the problem carefully (and underline keywords)
Extract rules from problem

2. Analyze Test Cases/Examples

Identify and evaluate Input/Output
Understand how the output is produced for each input

3. Define Data Structure

Choose the appropriate representations of data in problem to achieve output If you don’t know data structure yet, you learn data structure through my favourite video, Data Structures - Computer Science Course for Beginners

4. Design Algorithm

Write instructions to gain an output with a given corresponding input
Read books, articles, and other code to get some useful techniques.
Recommendations:
- Article: Complete Introduction to the 30 Most Essential Data Structures & Algorithms
- Book: Grokking Algorithms - Aditya Bhargava, Jed Limke
- More books: 10 Best Books to Learn Data Structure and Algorithms in Java, Python, C, and C++
- Github code examples:
  
  williamfiset / Algorithms
  
  A collection of algorithms and data structures

5. Implement Algorithm

Write algorithm in code

B. Example

Given an array A of integers of size n. Commute the maxim sum of s contiguous elements in the array. Return -1 if there is no valid output.

Input : A = [5,3,1,2], s = 2
Output: 8

Input : A = [1], s = 3
Output: -1

1. Comprehend Problem

Information extraction:

An array of integer
The maximum sum
Contiguous elements
Return -1 if no valid input

When you read the problem carefully, you can extract crucial information and make it explicit to solve the problem. If you don’t highlight out important terms, you will not be able to come to the correct output, which is time-consuming. For example, if you miss “contiguous” (consecutive), you will try to find a maximum combination from a set of combinations of the array, which is absolutely wrong.

However, sometimes you face strange terminology which the problem’s author uses to describe the problem, I recommend you check out the list of common terms, List of terms relating to algorithms and data structures

2. Analyze Test Cases/Examples

You utilize the above information extraction to apply on the input and return the correct output, so that you evaluate your understanding on the given problem. After that, you should try to think beyond on the given examples for edge cases. Edge cases are unexpected inputs which drive your algorithm to be incorrect.

Given A = [5,3,1,2], s = 2
Output: 5 + 3 = 8

3. Define Data Structure

In this problem, you can directly use the given array as a representation of data. In other problems, you should think of all possible data structures, list them out on paper, and choose the most efficient one. For example, if you want to map one item to another item (key-value relationship), a hash table is the best choice.

4. Design Algorithm

To make the game start easily, you can come up with a brute-force solution, which is the inefficient algorithm. Then you try to optimize it by thinking beyond it. You use and modify techniques or good algorithms to fit your certain problem. Therefore, reading articles, books and other codes is useful to improve your knowledge of algorithms.

In this example, I would solve it in the brute-force way, and then optimize it with a technique called “Window Sliding”.

# Brute-force solution

Initialize max_sum as INT_MIN
For every element `index` from 0 to (n-s+1)
    Set current_sum as 0
    For every `number` from 0 to s
        current_sum = current_sum + arr[index+number]
    max_sum = max(max_sum, current_sum)

The above solution, you need to use one loop and one inner loop to iterate through s elements to find the maximum sum. It takes O(ns) times to gain the correct output. But can we eliminate s to reduce only O(n). That’s where the “Window Sliding” technique comes to our playground.

Window Sliding is a technique of using a “window” with a specific length and run operation in this window. More specifically, consider a sub-array of length s, and move the sub-array by one element. Following the below figures to understand more:

Iteration 1

Iteration 2

# Optimal solution:
Initialize max_sum as INT_MIN
Initialize window_sum as 0

For every element `index` from 0 to s:
    window_sum += array[index]

max_sum = window_sum
For every element `index` from s to n:
    # Move to next window, and subtract the first
    # element in the previous window
    window_sum += arr[index] - arr[index - s]
    max_sum = max(max_sum, window_sum)

5. Implement Algorithm

Here’s is a C# implementation of the above algorithm:

public static int MaxContiguousSum(int[] arr, int n, int s) {
   if(n < s)
     return -1;

   int max_sum = Int32.MinValue;
   int window_sum = 0;
   for(int i = 0; i < s; i++)
     window_sum += arr[i];

   max_sum = window_sum;
   for(int i = s; i < n; i++) {
     window_sum += arr[i] - arr[i-s];
     max_sum = Math.Max(window_sum, max_sum);
   }

   return max_sum;
 }

C. Summary

I hope that my step-by-step instructions can help you to form your own method of solving future problems. Remember, here is only a tip of solving a problem, and it does not try to show this is the only technique you should use to cope with any problem. Therefore, the more important tip I want to give you is PRACTICE, PRACTICE, AND PRACTICE.

If you find any mistakes in my post, you can comment below to correct me. Thanks for reading.

Inheritance, Composition and Aggregation in C#

Nam Nguyen — Thu, 14 May 2020 13:14:05 +0000

In this post, I briefly introduce three main object-oriented programming terms for beginners in simple words. They are Inheritance, Composition and Aggregation. These programming techniques help developers write clean code, save many lines of code, refactor as well as maintain programs easily, where the developers have full control of the programs. After definition, I will list some main differences between composition and aggregation since they are quite similar.

1. Inheritance

In real life, inheritance is the action of passing property, debts or rights of parents to their children. Similarly, in programming, inheritance is the ability of a class to “copy” or acquire all properties and methods from another class. The class inheriting from another is a child class or derived class, and the class inherited by another class is the parent class. The inheritance helps derived classes extend their functionality as well as type, and create an “is-a” relationship between parent and child classes.

For example:

class Fighter
{
      private int _life;
      private int _attack; 
      public Fighter(int life, int attack)
      {
          _life = life;
          _attack = attack;
      }

      public int GetLife() 
      { 
         return _life;
      }
}

class Soldier : Fighter
{
      public Soldier(int life, int attack): base(life, attack){}
}

The above example illustrates that Fighter is a parent class and Soldier is a child class. In the child class, you do not need to repeat all attributes and methods defined in the parent class. Apparently, the Soldier “is-a” Fighter. Let me create instances of them and make a call to GetLife() method.


class Program
{
    static void Main(string[] args)
    {
        Soldier soldier = new Soldier(10, 1);
        int life soldier.GetLife();
        Console.WriteLine(life); // 10
    }
}

2. Composition and Aggregation

Composition and aggregation are programming techniques which allow a class to “contain” one or more objects of other classes to form a big object doing some specific functionalities. The container is the superclass and the classes contained by the superclass are subclasses. Therefore, the superclass and subclasses have a “has-a” relationship.

However, composition and aggregation must have some differences to distinguish between them. Let’s see the following examples:

Composition:

class ChairLeg
{
    public void Material() 
    {
       Console.WriteLine("Wood");
    }
}
class Chair
{
    private ChairLeg _leg;
    public Chair(ChairLeg leg)
    {
        _leg = leg;
    }
}

Aggregation


class Chair
{
    public void Material() 
    {
        Console.WriteLine("Wood");
    }
}
class DinnerTable
{
    private Chair _chair
    public Chair(Chair chair)
    {
        _chair = chair;
    }
}

The two examples above show “has-a” relationship, DinnerTable “has-a” Chair around and Chair “has-a” ChairLeg (obviously, a chair has 4 four legs, but here is just an example for you to understand the concept). Therefore, DinnerTable has a loose relationship with Chair because DinnerTable can not be useless or destroyed if it does not have a Chair object. In other words, DinnerTable exists independently from Chair. However, oppositely, Chair has a solid relationship with ChairLeg, which means that Chair cannot exist independently without ChairLeg.

As a result, the main difference is independence. In composition, subclasses' life cycle depends directly on superclass’s life cycle and vice versa. In aggregation, the subclasses and superclass have their own life cycle.

3. Conclusion

This post is a brief explanation of inheritance, composition and aggregation in object-oriented programming for beginners. If you find any mistakes in my post or give my feedback, please comment below. I am welcome to your responses.

Introduction To Method Overloading and Method Overriding in C#

Nam Nguyen — Sun, 10 May 2020 09:11:54 +0000

In this post, I would introduce definition of method overloading and method overriding in C# (be similar in most programming languages such as Java and C++). Also, I would discuss the differences between these methods for you to find out which one is the most suitable in a specific situation. Sometimes, while you are building your programs, you inadvertently use them to save many lines of code. Therefore, I am here to give you a quick definition and help you identify them clearly.

Before I jump into their definition and examples, I have one thing to let you know that method overloading and method overriding are two types of polymorphism. Polymorphism is a magical ability of objects to transform into multiple appearances, which allows the derived classes to have their own implementation (or their own playground in which you must conform to their rules). Let’s get started!

1. Method Overloading

Method Overloading is a special programming technique that gives you permission to define one or more one methods arming the same names with different types or numbers of arguments. At first place, beginners think that it is impossible to create two methods, for example, having the same name, and it would return a bunch of errors. Yes. Some errors occur if you do not follow rules of defining a method overloading. But no worries, I guarantee that it is easy and simple to use when it comes to see some below examples

There are two ways of overloading a method:

a. Define different numbers of parameters:

Oops. Just a quick definition here. You may see that sometimes I use “parameter” or “argument”, so what is the difference between them? “Parameter” is a hole defined in a method while “Argument” is an actual value passed to the method to make the method usable at runtime. Get back to examples to understand this way of overloading a method.

class Student
{
   void RetrieveStudentInfo(int studentID)
   {
      Console.WriteLine(“First Method”);
   }

   // Or
   void RetrieveStudentInfo(int studentID, int age)
   {
      Console.WriteLine(“Second Method”);
   } 
}

The two methods above are a valid case of method overloading (they are not perfect methods but a good example). As can be seen from the above lines of code, the “RetrieveStudentInfo” method has two definition, but they have different numbers of parameters. Therefore, when you pass the “RetrieveStudentInfo” method one argument (studentID), you are using the first method. And when you pass the method two arguments (studentID and age), you are taking the second method. It’s awesome, isn’t it?

class Student
{
   static void Main(string[] args)
   {
      Student student = new Student();
      student.RetrieveStudentInfo(98247); 
      // Print “First Method”

      student.RetrieveStudentInfo(98247, 21); 
      // Print “Second Method”
   } 
}

b. Define different types of parameters:

class Student
{
   void RetrieveStudentInfo(String name, int age)
   {
      Console.WriteLine(“First Method”);
   }

   // Or
   void RetrieveStudentInfo(int studentID, int age)
   {
      Console.WriteLine(“Second Method”);
   } 
}

The two methods above are also a typical usage of method overloading (again, they are not perfect methods but a good example). The first method takes String as the first argument type and int as the second one. But, the below method accepts two arguments as int.

class Student
{
   static void Main(string[] args)
   {
      Student student = new Student();
      student.RetrieveStudentInfo(“Nam Nguyen”, 21); 
      // Print “First Method”

      student.RetrieveStudentInfo(98247, 21); 
      // Print “Second Method”

   } 
}

2. Method Overriding

Method overriding is a special technique in object-oriented programming that allows you to override child-class methods defined in the parent class earlier. Before overriding, the child classes have to inherit the parent class. A quick definition, inheritance is a “copying” ability of children classes that they can “steal” all public properties and methods of the parent class. Please look at the below example to get understanding.

// Parent class
class Fighter
{
    // Overridden method
   void virtual AttackDamage()
   {
      Console.WriteLine(“The enemy loses 5 points”);
   }
}

// Child class
class Soldier : Fighter
{
    // Overriding method
   void override AttackDamage()
   {
      Console.WriteLine(“The enemy loses 10 points”);
   }
}

The “AttackDamage” method in “Soldier” class rewriting the one in “Fighter” is called overriding method, and the one in the parent class is the overridden method. Therefore, when you instantiate a “Soldier” object and call “AttackDamage” method, the console prints out “The enemy loses 10 points”

class Program
{
   static void Main(string[] args)
   {
      Fighter soldier = new Soldier();
      soldier.AttackDamage(); // The enemy loses 10 points
   } 
}

3. Differences Between Method Overloading And Method Overriding

Here is a list of main differences for beginners:

Method overriding requires forcefully to rewrite the method with the same parameters in terms of size and type. In meanwhile, method overloading is more flexible by allowing multiple types and different sizes which are its speciality and outstanding ability.
Method overloading cannot perform outside the class that the first method is defined in, which means all overloading should be defined within the same class. Method overriding has a totally different story. Because method overriding is a representation of relationship between classes, specifically parent and child classes, overriding methods must be re-defined in other classes.
Method overloading executes at compile-time where all overloaded methods are formed their argument types, size and definition early before executing the program. Method overriding is as stubborn as a mule, and it prefers to define itself in runtime, which means during execution, it shows “information” as well as actual “characteristics”.

4. Conclusion

This post is a quick introduction to Method Overloading and Method Overriding in C# as well as object-oriented programming. Also, this is my first time I’ve written a tech post. I want to force myself to review my own knowledge about programming concepts and to see how solid I know about OOp as well as how well I could explain it to my reader by my own words.

Therefore, if you find any mistake in my post or give me feedback, please comment below. I am welcome to your responses.