DEV Community: Sunbeom Kweon (Ben)

[Algorithms] 13 - Network Delay Time

Sunbeom Kweon (Ben) — Tue, 27 Sep 2022 18:25:29 +0000

1. Overview

The problem needs understanding of Djikstra's shortest path algorithm.
The problem needs understanding of min-heap.
The problem needs understanding of adjacency matrix.
The problem needs understanding of Breadth-First-Search (BFS)

2. Solution

The solution is not very complicated, since the algorithm(Djisktra's shortest path) is a greedy algorithm.

The first big hint we can consider to approach this problem would be that each node can have connected nodes as many as it wants. Therefore, we need an adjacency matrix to keep track of how many nodes are connected to each node. Notice that each node will be stored in 2D array as a pair since each node has different weight(time) to reach.

C++ example

// time will be given as => vector<vector<int>>& times;
vector<vector<pair<int, int>>> adj(n+1);
for(auto t : times)
{
     int source = t[0];
     int dest = t[1];
     int time = t[2];

     // From 'source', we can reach 'dest' consuming 'time'
     adj[source].push_back({time, dest});
}

Moreover, note that we need to since we have the starting node K, and we need to scan the nodes in level order. We need the level order scan because we are interested in finding the shortest amount of time elapsed to reach each node from K. And that can be done by scanning all nodes attached to the current node (level order). And level order search can be done by implementing BFS.

BFS will be implemented using a queue. But for this specific problem, we need a priority queue (min-heap). Why would we use priority queue? Since the algorithm is greedy, we want to test the node with the shortest elapsed time FIRST. So any node that has smallest accumulated time will have the first priority.

We also need an array that can keep track of the previous smallest accumulated time it took to get to the ith node. This will be used to return the result.

C++ Example

// There are going to be n number of nodes
// recvTimes[i] : Minimum time it takes to reach i from K
vector<int> recvTimes(n + 1, INT_MAX);

// K from K will take 0
recvTimes[k] = 0;

3. Full Implementation

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {

        // 0: weight
        // 1: destination
        vector<vector<pair<int, int>>> adj(n+1);

        for(auto t : times)
        {
            int source = t[0];
            int dest = t[1];
            int time = t[2];
            adj[source].push_back({time, dest});
        }

        // Keep track of minimum time of receiving signal from node k
        vector<int> recvTimes(n + 1, INT_MAX);
        recvTimes[k] = 0;

        // Minheap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0,k});

        while(!pq.empty())
        {
            // Getting the current node (pair).
            int currNode = pq.top().second;
            int currTime = pq.top().first;
            pq.pop();

            // Skip if the pair cannot be an optimal solution
            if (currTime > recvTimes[currNode]) 
                continue;

            // Scan all attached nodes and push to pq if the item can be an optimal solution.
            // Don't forget to update the elapsed time.
            for(auto item : adj[currNode]){
                if(recvTimes[item.second] > currTime+item.first){
                    recvTimes[item.second] = currTime+item.first;
                    pq.push({currTime+item.first, item.second});
                }
            }

        }

        int result = INT_MIN;

        // Getting results
        for (int i = 1; i <= n; i++){
            result = max(recvTimes[i], result);
        }

        return (result==INT_MAX) ? -1 : result;
    }
};

[Advanced Node JS] 1 - Event Loop

Sunbeom Kweon (Ben) — Tue, 13 Sep 2022 03:59:46 +0000

Event Loop is one of the most important concepts in JavaScript(Browser) & Node JS.

Event Loop is also the biggest difference between other classic programming languages like C/C++ or Java.

Node JS vs Browser

Browser and Node JS both have their own Event Loop. Node JS Event Loop is a little bit complex and has more phases, but both shares the same concept. I am going to introduce the Browser's Event Loop.

Difference Between The Event Loop in Browser and Node JS

Synchronous Call vs Asynchronous Call

Synchronous calls goes to Stack, just like other programming languages. They get executed until the stack is empty.

But asynchronous calls goes to Queue (Event Loop). This is how Event Loop looks like in a simple code:

while (queue.waitForMessage()) {
  queue.processNextMessage();
}

The message polling occurs when the stack is empty. So all the synchronous calls will be processed first. Since synchronous functions are pushed to the stack first, all queued functions(messages) need to wait to be processed.


// Synchronous Call
console.log("1: Pushed to stack");

// Asynchronous Call
setTimeout(()=>{
    console.log("1: Pushed to queue");
}, 1000);

// Synchronous Call
console.log("2: Pushed to stack");

// > Output: 
// 1: Pushed to stack
// 2: Pushed to stack
// 1: Pushed to queue

The processing of functions continues until the stack is once again empty. Then, the event loop will process the next message in the queue (if there is one). Each message in the queue contains a function. Therefore, polling a new message from queue will push a function on the top of the Stack.

We would like to use the queue(Event Loop) when the function's workload is heavy. Normally on web browsers, when we call any Web APIs such as setTimeout, eventListener those function calls will be queued.

[Algorithms] 12 - Let's Master Heap

Sunbeom Kweon (Ben) — Mon, 05 Sep 2022 19:44:49 +0000

1. Introduction of Heap

Definition
- Heap is a complete binary tree that satisfies the heap properties (min or max heap).
- Max Heap: Every node has greater or equal key(value) to their children.
- Min Heap: Every node has smaller or equal key(value) to their children.
Properties
- Basically heap is an array.
- Height of any heap will be log(n) only.
- Left child is at 2*i
- Right child is at 2*i+1
- Parent is at i/2

2. Insertion (max heap)

1) Insert the element to the end of the array.
2) Then swap the element with its parent until the parent is greater or equal to the element

void Insert(int arr[], int i){
  while(i > 0 && arr[i/2] < arr[i]){

    // Swapping parent and current  
    swap(arr[i/2], arr[i]);

    // Move on to the next element
    i = i/2;
  }
}

3. Deletion (max heap)

In heap, deletion means deleting the root node.
1) Swap the element with the given index with the last element in the heap.
2) Delete the current last element.
3) Compare swapped element's children. Swap the element with the greater child (only when any of the children are greater or equal to the element).
4) Repeat the process until we find the place where both children are smaller than the element.

void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];

    // Replace root with last element
    arr[0] = lastElement;

    // Decrease size of heap by 1 (element deleted)
    n = n - 1;

    // Start from the bottom
    int i = n;

    // Construct the heap again after the deletion
    while(true){

      // After we proceed the root node, break out of the loop.
      if(i < 0)break;

      // Compare two children and swap
      if(i*2 <= n && arr[i] < arr[i*2]){
        swap(arr[i], arr[i*2]);
      } else if(arr[i] < arr[i*2+1]){
        swap(arr[i], arr[i*2+1]);
      }

      i--;
   }
}

4. Heap Sort

Use one of properties of deletion.
Every time we delete an element from the heap, we get an additional empty space at the end of the array.
We also get the maximum element among the heap.
Therefore, if we keep inserting those deleted elements to the end of the array, the array will be eventually sorted.

5. Heapify

Heapify allows you to create a heap within O(N) time complexity. Using insertion method would take O(N*log(N)).
Heapify starts from the bottom. It repeatedly compares every children of nodes and swap with the parent until it reaches to the root node.
- Max heap example: swap(arr[i], max(arr[2*i], arr[2*i+1]))
- Min heap example: swap(arr[i], min(arr[2*i], arr[2*i+1]))

6. How to use Heap in C++

priority_queue<T> can be used as Max Heap in C++. Max Heap is the default behavior of the library.
- ex) priority_queue<T> pq;
priority_queue<T> can be used as Min Heap in C++. You just need to pass some additional arguments to the constructor.
- ex) priority_queue <T, vector<T>, greater<T> > pq;

[Algorithms] 11 - Dynamic Programming

Sunbeom Kweon (Ben) — Sun, 07 Aug 2022 00:44:33 +0000

Dynamic Programming is hard. But there are some ways that let us approach the problem more smoothly.

1. Identify if the problem needs Dynamic Programming

It is very important to find out whether the problem needs Dynamic Programming or not. Following cases normally requires Dynamic Programming.

When you need to try every single case to find the result.
When you need to find the possible smallest, biggest, longest, or shortest ... etc case (optimization problems).

Following list is from Neetcode's 5 Dynamic Programming Patterns Link:

1. Fibonacci

When you need previous results to calculate the current result.
Normally can be solved by updating two values recursively.

2. Zero/one knapsack

Visualizing the problem as a n-ary tree can be helpful.
Two possible cases: whether we take it or not. = Therefore, we do not need to consider some other cases.

3. Unbounded knapsack

Visualizing the problem as a grid(like a chessboard) can help be helpful.
Hash map is used.
Need to consider every case to come up with the last answer.

4. Longest Common Subsequence

5. Palindromes

2. Figure out the subproblems

This is the most important step of the Dynamic Programming. Finding the subproblems and proving recursively solving those subproblems will lead to the answer are very hard. To shape the subproblems, we need to read the problem very thoroughly.

It is good to start from finding how many possible choices that each recursive step has. (e.g. The robot can go either left or bottom. There are only two options for each step.)Also, visualizing the solution as tree graph can help this step.

If there are too many options for each step, (e.g. Queen can move to any grid that is diagonal or adjacent. There are so many possibilities) we need to consider memoization.

3. Practice memoization

Most of the Dynamic Programming questions require to use memoization since the computation tend to have exponential time complexity. It is good to learn how to use 2D arrays, maps or sets.

[Algorithms] 10 - 3Sum

Sunbeom Kweon (Ben) — Thu, 28 Jul 2022 23:55:00 +0000

Link to the problem

Three sum problem uses some ideas from two sum problem. But this problem is way harder to come up with the valid solution than two sum, thus, very different question. In this post I am going to go over what makes this problem so hard to solve and the solution as well.

Why this is harder than two sum?

Using hash map or set would not be efficient enough to catch duplicates. In two sum problem, all we needed to do was to push visited elements to the set and if the element was visited, ignore it.

But for three sum, we need to store an array for each number to make sure the combination of numbers are unique or not. This is very hard to implement and inefficient when it comes to time complexity as well.

Solution

So what would be the valid approach to the solution? The first key is using sorting technique to remove all duplicates so that we don't make same combination.

For example, if the array looks like

[1,-3,5,4,-3,2,2,-3,4,-3]

and if we sort it, we get

[-3,-3,-3,-3,1,2,2,4,4,5]

Therefore, we can skip the duplicated numbers after we find the valid combination that makes the sum 0 by sorting the array.

The second key is using two pointers method to search for the right number. We can increase the low pointer when the sum is less than zero, and decrease the high pointer when the sum is bigger than zero unless the two pointers pointing to the same element.

The problem is a little bit tricky to implement in the code.


class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>res;

        // Sort the array first. This is for removing duplicates & two pointer search.
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++)
        {

            if(i > 0 && nums[i] == nums[i-1])continue;

            int low = i +1;
            int high = nums.size() - 1;

            while(low < high)
            {
                int sum = nums[low] + nums[high] + nums[i];
                if(sum < 0) low++;
                else if(sum > 0) high--;
                else{
                    vector<int> tmp = {nums[low], nums[high], nums[i]};
                    res.push_back(tmp);
                    low++;
                    while(nums[low] == nums[low-1] && low < high)low++;
                }
            }
        }

        return res;
    }
};

As you can see, we are skipping elements if they have the same values.

if(i > 0 && nums[i] == nums[i-1])continue;

while(nums[low] == nums[low-1] && low < high)low++;

Time complexity analysis

The time complexity of the solution is O(n^2) because we are using two pointers method. I was confused about it at first, because I thought I was using binary search for the problem. But since we are moving low and high one by one for each loop, the solution will have O(n^2) instead of O(nlogn)

[Algorithms] 9 - Product of Array Except Self

Sunbeom Kweon (Ben) — Thu, 28 Jul 2022 21:53:00 +0000

Link for the problem

Link for the solution

Overview

To solve the problem is pretty easy. But the given conditions are what make this problem very tricky. I would like to introduce the problem because the solution is pretty unique.

Problem in detail

The constraints for this problem are:

Time complexity: O(n)
Space complexity: O(1)
Cannot use division

Notice that the problem will not count the returning array as an extra space.

It seems almost impossible to solve the problem with those constraints. Especially achieving O(1) space complexity without using division drove me crazy to think about the solution. So I gave it up and looked at the solution.

Solution

The solution was something that I have never seen, but easy to understand. First, we need to think how to get the products without itself. It is actually the product of left side of an element and the right side of an element.

[ 1, 2, 3, 4 ]

ex) product without 1

- left side: 1 (does not exist)
- right side: 2*3*4 (without 1)
- left side * right side = 1 * 24 = 24


ex) product without 3

- left side: 1*2 (does not exist)
- right side: 4 (without 3)
- left side * right side = 1 * 2 * 4 = 8

Next, we need to find the way to get prefixes and postfixes in a linear time, and using only constant space. Actually this part is very hard to come up with by ourselves.

The way to create prefixes is:

Set up a variable prefix, initialized with 1.
Push the prefix to the returning array.
Keep multiplying prefix as loop goes through.

Notice that the first prefix is always going to be 1 since there is no element on the left side of the first element.

After the step, we will get an array that filled with prefixes for each element. Now all we need to do is get postfixes for each element and simply update the returning array by multiplying those postfixes.

Code implementation


    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res;
        int prefix = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            res.push_back(prefix);
            prefix *= nums[i];
        }
        int postfix = 1;
        for (int i = nums.size()-1; i >= 0; i--)
        {
            res[i] *= postfix;
            postfix *= nums[i];
        }
        return res;
    }

[Algorithms] 8 - Valid Binary Search Tree

Sunbeom Kweon (Ben) — Thu, 28 Jul 2022 17:51:00 +0000

Link for the problem

Link for the solution

This may not be the hardest BST problem, but really good to understand the concept of BST structure.

Wrong Approach

When I first saw the problem, I simply tried to compare the parent node and its left & right nodes with the recursion. I thought it will eventually give me the answer by using recursion, because I am recursively checking all parents are strictly greater than its left and smaller than it right.

Mistake that I made

The mistake I made here (and probably 99% of people who tried to solve this problem would have faced the same issue) was that, I was merely checking if each subtree is valid. It is weird, because it sounds true that if all subtrees in the BST are valid BSTs, than the whole tree is a valid BST. But
look at the following example.

Invalid BST - 3 and 4 cannot be in the right tree of 5 ![BST Image](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)

In the example, all subtrees are valid. But the whole BST is not valid. Therefore, we need to do something more to make sure the tree is a valid BST. But what should we do?

Solution

Let's start from why checking all subtrees are valid does not lead to the answer. The reason is that, for each check we do not consider the previous results. Then what previous results that we need to keep track of? The minimum and the maximum boundaries.

For example,

      (10)
     /    \
   (7)    (17)
   /\      /\
 (4)(9)  (11)(18)
    /\
  (1)(?)

Let's think of the value that we can fill in (?).
=> [10,11,12,13... ]
Because we can tell the value should be strictly bigger than 9

But if we consider that fact that all (?) has to be smaller than 10, because (?) in the left side of the root node with the value of 10, then we can find out that there is no number we can fill in the blank.

Okay now it seems clearer, but we need to figure one more thing. When do we get the maximum boundary?

Let's start from the root node. We can see that every node inside of the root node's left tree has to be smaller than 10. So everything under 10's left node will be having the maximum boundary of 10. On the other hand, every node inside of the root node's right tree has to be greater than 10.

left tree nodes => [...8,9]
right tree nodes => [11, 12, ...]

Therefore, we can see that every time we move to left child, the maximum boundary will be set and every time we move to the right child, the minimum boundary will be set.

My solution

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // The idea for the solution:
        //      Need to set the minimum and maximum boundary
        //      1. Left node cannot be greater than the current node
        //      2. Right node cannot be smaller than the current node
        //      3. If the node is left, maximum boundary will be set up.
        //      4. If the node is right, minimum boundary will be set up.
        return helper(root, LONG_MIN, LONG_MAX);
    }

    bool helper(TreeNode* root, long long int minVal, long long int maxVal){

        // Base case
        if(!root)return true;

        // within the range of minval and maxval
        if(root->val <= minVal || root->val >= maxVal)return false;

        // root->left => should be less than root->val
        if(root->left && root->left->val >= root->val) return false;

        // root->right => should be greater than root->val
        if(root->right && root->right->val <= root->val) return false;

        // Should update the left node restriction
        return (helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal));
    }
};

[AWS Experiment] 8 - AWS ECS Deep Dive (Part.2)

Sunbeom Kweon (Ben) — Tue, 26 Jul 2022 02:04:00 +0000

1. Useful Resources & Links

2. Experiment Implementation

Docker Image Explanation

I created a custom Docker image for this tutorial. I briefly mentioned its specs below.

Base Image: python-alpine
Image Name: exit21sb/ecs-demo:taskrole-test
Python Scripts
- script_session.py: Start the job. Download all necessary images.
- script_session_process_images.py: Process the images.
- script_session_move_images.py: Move the images to /old directory.
Libraries:
- boto3 (AWS SDK)

Uploading sample images to the S3 Bucket

Create a bucket and create two folders which are /old and /new
The application will download all files in the /new, then process the images, and will move the images to the /old folder.
Upload some images to the /new folder.

Uploading images - 1

Uploading images - 2

Make sure the bucket is not public. It won't affect following the tutorial, but just for your sake.
We don't need to worry about the Bucket Policy since we are going to use S3FullAccess permission.

Task Role

Go to IAM console and create DemoRoleForECSandS3
Add Elastic Container Service (ECS) as Trusted Entity of the role.

Task Role

Add AmazonS3FullAccess permission (AWS managed policy).

Perfect! We are going to attach the role to the ECS Task later. Attaching the role to tasks is very convenient since we now don't need to worry about how the application inside of ECS container authenticates to AWS services.

Not we can move on to the Task Definition part.

Task Definition

Task Definition - 1

Task Definition - 2

Name: Any
Image URI: exit21sb/ecs-demo:taskrole-test
Port Mappings: None
Environment Variables (required):
- BUCKET_NAME
- REGION
App Environment: Fargate
Operating system/Architecture: Linux/ARM64 (important)
CPU: 1 vCPU (does not matter)
Memory: 3GB (does not matter)
Task Role: DemoRoleForECSandS3 (the one we created beforehand)
... and leave all optional settings as default

Great! Now we are ready to run the ECS container.

Run the Task

Go to ECS console and create a cluster.
Go to Tasks tab and click the "Run new task" button. Service and Tasks are a little bit different. For this tutorial, our ECS container will not last for too long time, we are sticking to Task option.
Specify the Launch type. Choose FARGATE option.
Application type is Task.
Leave desired tasks option as 1.
Choose the Family and Revision for the Task Definition we created beforehand.
Launch the Task

Task Running Process

The application will sleep for 5 mins because of the script script_session_process_images.py. I put sleep function just to demo the behavior. Feel free to update the script and deploy new Docker image if you want to use the application for the real-world project.

After 5 minutes, all the images in /new folder will be moved to /old folder. This can take a little bit of time.

Launched Screen

Task Launched - 1

Task Launched - 2

Task Launched - 3

S3 Screen

No images in /new folder anymore

/old folder

Cloud Watch Logs

Notice: The "Image processing is done!" log printed out earlier than the time when actual job gets done. I think this is because of the way how Fargate works. It seems like Fargate runs another threads to process the rest of the jobs while the current thread is sleeping (not really sure if my explanation is right).

3. Conclusion

Using ECS can be very easy with Fargate and Task role. Try use ECS for you batch jobs that take lots of time to process!

[Algorithms] 7 - My Solution for Palindrome Linked List with O(N) Time Complexity & O(1) Space Complexity

Sunbeom Kweon (Ben) — Mon, 25 Jul 2022 17:11:00 +0000

Link for the problem

My understanding for the problem

Idea: Reverse the nodes as slow pointer moves forward. Once the fast pointer reaches to the end of the list, then we compare the nodes from where the slow pointer is at and the nodes that are reversed.
Edge cases:
- What if the list has odd number of nodes? ex) [1,2,3,4,5]
- The method that I used to figure out if the number of nodes is odd or even:
  - If fast pointer's next exists => even
  - If fast pointer's next does not exists => odd
- When the list has only one node => true (2 does not matter)


class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* slowPrev = dummy, *slow = head, *slowNext = slow, *fast = head;
        dummy->next = head;
        bool isOdd = false;

        while(fast){

            // Move fast forward
            if(fast->next){
                fast = fast->next->next;
            }else{
                fast = fast->next;
                isOdd = true;
            }

            // Reverse slow
            slowNext = slow->next;
            slow->next = slowPrev;
            slowPrev = slow;
            slow = slowNext;
        }

        // Detach dummy node (otherwise will get memory access error)
        head->next = nullptr;
        delete dummy;

        if(isOdd){
            slowPrev = slowPrev->next;
        }

        while(slowPrev && slow){
            if (slow->val != slowPrev->val) return false;
            slowPrev = slowPrev->next;
            slow = slow->next;
        }

        return true;
    }
};

[Algorithms] 6 - My Solution for PrintTree Problem (DFS)

Sunbeom Kweon (Ben) — Sat, 23 Jul 2022 20:23:00 +0000

Link for the problem description video


#include <iostream>
#include <vector>
#include <string>
#include <utility>      // std::pair, std::make_pair
#include <unordered_map>

using namespace std;

void DFS(int depth, string key, unordered_map<string, vector<string>> mp){
    if(!mp.count(key))// if key does not exist
        return;
    vector<string> values = mp[key];

    for (int i = 0; i < values.size(); i++){
        for (int j = 0; j < depth; j++)
            cout << "\t";
        cout << values[i] << endl;
        DFS(depth+1, values[i], mp);
    }
}

int main()
{
    vector<pair<string, string>> input;
    input.push_back(make_pair("animal", "mammal"));
    input.push_back(make_pair("animal", "bird"));
    input.push_back(make_pair("lifeform", "animal"));
    input.push_back(make_pair("cat", "lion"));
    input.push_back(make_pair("mammal", "cat"));
    input.push_back(make_pair("animal", "fish"));
    unordered_map<string, vector<string>> mp;
    unordered_map<string, bool> seen;

    for (auto p : input){

        string key = p.first;
        string val = p.second;
        seen[val] = true;


        if(mp.count(key)){
            mp[key].push_back(val);
        } else {
            vector<string> arr = {val};
            mp[key] = arr;
        }
    }

    // Finding the start point (root node)
    // 1. Brute force: Use DFS and count the height
    // 2. If the string ever appeared in the p.second (as a val) then remove from the candidate
    string root = "";
    for (auto m : mp){
        if(!seen.count(m.first)){
            root = m.first;
        }
    }
    cout << root << endl;
    DFS(1, root, mp);

    // Use DFS to print out every child
    // Need to add depth for every vector array

    return 0;
}

[AWS Experiment] 8 - AWS ECS Deep Dive (Part.1)

Sunbeom Kweon (Ben) — Wed, 20 Jul 2022 18:41:00 +0000

1. Definitions

ECS

ECS stands for Elastic Container Service
ECS allows you to launch Docker containers(Tasks) on AWS

Launch Types

It is very important to understand how ECS works depends on its launch type.

ECS needs physical machines that can run Docker daemon. There are two ways to launch ECS

1. EC2 Launch Type

EC2 launch type runs Docker containers on EC2 instances. And each EC2 instances can run several Tasks.
Depends on the Auto Scaling Group set up, more EC2 instances will be automatically launched to run more Tasks.
The launched EC2 instances MUST have ECS Agent to run Tasks. AWS will automatically launch AMI that ECS Agent is already installed.

2. Fargate Launch Type

There is no EC2 instances to manage. AWS will manage.
To run more tasks, simply need to add more tasks. There is no need to know which exact machine will be running the tasks.

So which one we should use? It really depends on the situation, but normally EC2 launch type is more cost efficient compared to Fargate launch type. Typically, a service will end up charging more when the service is more easy to handle and user friendly.

Check out this blog post if you want to know more about comparison between those two services. Link

Tasks

A single Task simply means a single Docker container.
More precisely, a single Docker container will be running on top of a Task. And the Task will only contain one Docker container.
Each Task can have different IAM Role.

Clusters

A Cluster can manage several EC2 machines or Fargate Tasks.
Notice that each EC2 machine can run several Tasks.

2. Usage

Process batch jobs or data to convert and store them to database (e.g.DynamoDB).
Want to deploy multiple containers for better performance for your applications.

ECS vs Lambda?

When it comes to processing batch jobs, ECS and Lambda does pretty much the same thing. Here is a good blog post explains the difference between two and when to use them Link
To summarize the blog post
- ECS provides environment flexibility & task scheduling.
- Lambda is good for processing batch jobs that take less than 15 minutes. Also, can be more time & cost efficiency depends on what you want to do

3. Experiment Overview

Image processing with ECS

User interaction

Upload image files to S3. This will be done manually.
Launch the prepared ECS Task using Fargate.

Inside of the Fargate Task Link for the GitHub Repo

The container will run Python scripts as it is configured.
Download all the images in /new folder in the S3 bucket with the specified region and name.
Process the images. For this tutorial, I did not do anything for the image processing job.
Move all image files in /new to /old

3. Conclusion

The rest of implementation will be continued in `[AWS Experiment] 8 - AWS ECS Deep Dive (Part.2)`

[Algorithms] 5 - Unique Paths I

Sunbeom Kweon (Ben) — Sun, 10 Jul 2022 03:16:00 +0000

Link to the solution

Link to the problem

1. Introduction

I was able to figure out the brute force solution using dynamic programming, which was pretty intuitive. But I could not figure out how to implement the memoization to my solution. I found out one of the solutions & explanation from the problem's discussion page and I would like to share it with you guys.

2. Problem Explanation

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

My understanding

Since there were only two direction to check for each grid, I used recursion until the passed row and column indices are either out of the range or on the destination grid. And return 1 if the function reached to the destination and return 0 else.

At the end of the function, I am returning the sum of two recursive calls which are checking right side block and down side block respectively.

My brute force solution⬇️ (the solution will eventually get time limit exceeded error on Leetcode)

class Solution {
public:
    int uniquePaths(int m, int n) { 
        return findPaths(m,n,0,0);
    }

    int findPaths(int m, int n, int row, int col){

        // Checking out bound error
        if(row < 0 || col < 0 || row >= m || col >= n) return 0;

        // Checking if the function reached to the destination
        if(row == m-1 && col == n-1) return 1;

        // return the sum of paths
        return findPaths(m,n,row+1,col) + findPaths(m,n,row,col+1);
    }

};

3. Efficient Solution using memoization

Key concept

First, it is good to remind ourself about the purpose of implementing memoization. Why would we want to do this?

The definition of memoization from Wikipedia:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

So our goal is to store the result from the previous result to prevent redundant function calls. But there is one thing important to know before you implement the memoization: Will this leverage up our time complexity by sacrificing our space complexity?

For this specific problem, the answer is "yes." We are calling too many redundant function calls while we are scanning bottom and right points and we want to avoid it so that the program passes for the heavier test cases. I made a diagram that explains how memoization can make our code more efficient. Link to PDF

Memoization diagram (2022/07/09 by Sunbeom Kweon)

Code implementation

Link to the solution

DEV Community: Sunbeom Kweon (Ben)

[Algorithms] 13 - Network Delay Time

1. Overview

2. Solution

3. Full Implementation

[Advanced Node JS] 1 - Event Loop

Node JS vs Browser

Synchronous Call vs Asynchronous Call

[Algorithms] 12 - Let's Master Heap

1. Introduction of Heap

2. Insertion (max heap)

3. Deletion (max heap)

4. Heap Sort

5. Heapify

6. How to use Heap in C++

[Algorithms] 11 - Dynamic Programming

1. Identify if the problem needs Dynamic Programming

1. Fibonacci

2. Zero/one knapsack

3. Unbounded knapsack

4. Longest Common Subsequence

5. Palindromes

2. Figure out the subproblems

3. Practice memoization

[Algorithms] 10 - 3Sum

Why this is harder than two sum?

Solution

Time complexity analysis

[Algorithms] 9 - Product of Array Except Self

Overview

Problem in detail

Solution

Code implementation

[Algorithms] 8 - Valid Binary Search Tree

Wrong Approach

Mistake that I made

Solution

My solution

[AWS Experiment] 8 - AWS ECS Deep Dive (Part.2)

1. Useful Resources & Links

2. Experiment Implementation

Docker Image Explanation

Uploading sample images to the S3 Bucket

Task Role

Task Definition

Run the Task

Task Running Process

Launched Screen

S3 Screen

Cloud Watch Logs

3. Conclusion

[Algorithms] 7 - My Solution for Palindrome Linked List with O(N) Time Complexity & O(1) Space Complexity

My understanding for the problem

[Algorithms] 6 - My Solution for PrintTree Problem (DFS)

[AWS Experiment] 8 - AWS ECS Deep Dive (Part.1)

1. Definitions

ECS

Launch Types

Tasks

Clusters

2. Usage

ECS vs Lambda?

3. Experiment Overview

Image processing with ECS

User interaction

Inside of the Fargate Task Link for the GitHub Repo

3. Conclusion

The rest of implementation will be continued in [AWS Experiment] 8 - AWS ECS Deep Dive (Part.2)

[Algorithms] 5 - Unique Paths I

1. Introduction

2. Problem Explanation

My understanding

My brute force solution⬇️ (the solution will eventually get time limit exceeded error on Leetcode)

3. Efficient Solution using memoization

Key concept

Code implementation

The rest of implementation will be continued in `[AWS Experiment] 8 - AWS ECS Deep Dive (Part.2)`