LeetCode 30 Day Challenge | Day 7 | Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

C++ Solution:

class Solution {
public:
    int countElements(vector<int>& arr) {
        unordered_map<int, int> _map;
        
        for(int a : arr){
            if(_map.find(a) != _map.end())
                _map[a]++;
            else
                _map[a] = 1;
        }
        
        int result = 0;
        for(auto n : _map){
            if(_map.find(n.first + 1) != _map.end())
                result += n.second;
        }
        
        return result;
    }
};

Detailed Explanation on Youtube:

LeedCcode 30 day Challenge #2 - Happy Numbers

LeetCode 202 - Happy Numbers

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Detailed Explanation with 2 different methods in following video:

Source: https://crack-coding-interviews.blogspot.com/2020/04/leedccode-30-day-challenge-2-happy.html

System Design : Load Balancing | How Load Balancers work

Features of Load Balancer:

• Distribute load/requests across multiple resources/servers.
• Keep track of status of all resources while distributing requests. If a server is down, it stops sending traffic to that server. [depending on activeness of the server]
• Ease of use in adding/removing servers in network based on demand.

Algorithms used for Load Balancing:

1. Round Robin
2. Least Connections
3. Least Response Time
4. IP Hash
5. URL Hash


Where can we use Load Balancers?

• User Requests -- [Load Balancer] -- Web Server
• Web Server --  [Load Balancer] -- Backend Server
• Internal Server -- [Load Balancer] -- Databases

Detailed explanation can be viewed on Knowledge Center's Youtube channel:

Subscribe to KnowledgeCenter 

4 Tips to crack System Design Interview

• Leverage your Existing Knowledge:
• Database Technologies
• Load Balancers
• Message Handlers
• Caching Techniques
• Scaling Techniques

• Understand the Problem very well: (Ask Questions)
• Constraints ?
• Users - Who, How large ?

• High Level Architecture Design (Abstract Design):
• Break problem into Components/Modules
• How the components are connected
• Don't go Deep

• Go Deep into Component of Interest:
• UI
• Database Side
• Caching
• Scalability
• Server

Detailed Explanation can be found on Youtube:

Subscribe toKnowledgeCenter 

Swap Nodes of Linked List without Copying

C++ Code:

void swap_nodes(Node **headPtr, int a, int b){

    if(a == b || !headPtr || !(*headPtr))

        return;

    

    Node *curr = *headPtr;

    Node *prev = nullptr;

    Node *nodeA = nullptr;

    Node *nodeB = nullptr;

    Node *prevA = nullptr;

    Node *prevB = nullptr;

    

    while (curr) {

        if(curr->data == a){

            nodeA = curr;

            prevA = prev;

        } else if(curr->data == b){

            nodeB = curr;

            prevB = prev;

        }

        prev = curr;

        curr = curr->next;

    }

    

    if(!nodeA || !nodeB)

        return;

    

    if(prevA){

        prevA->next = nodeB;

    } else { // nodeA is head

        *headPtr = nodeB;

    }

    

    if(prevB){

        prevB->next = nodeA;

    } else { // nodeB is head

        *headPtr = nodeA;

    }

    

    Node *tmp = nodeA->next;

    nodeA->next = nodeB->next;

    nodeB->next = tmp;

}

Detailed explanation is available on youtube:  

Subscribe toKnowledgeCenter 

Check if a Linked List is palindrome

Detailed explanation is available on youtube: 

Subscribe to KnowledgeCenter

Remove Loop From Linked List using Floyd's Algorithm

C++ Code:

void remove_loop(Node *head){

    Node *slow = head;

    Node *fast = head;

    if (!head || !(head->next))

        return;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast)

            break;

    }

    

    // No Loop exixts

    if (slow != fast){

        std::cout << "No Loop" << std::endl;

        return;

    }

    

    // When Loop exists

    slow = head;

    while(slow->next != fast->next){

        slow = slow->next;

        fast = fast->next;

    }

    fast->next = nullptr;

}

Detailed explanation is available on Youtube:

Subscribe to KnowledgeCenter

Why Floyd's Loop Detection Algorithm works ?

For detailed Explanation watch the youtube video:

Subscribe to KnowledgeCenter

Find First Element of Loop in Linked List

C++ Code:

void find_loop_beginning(Node *head){

    Node *slow = head;

    Node *fast = head;

    if (!head || !(head->next))

        return;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast)

            break;

    }

    

    // No Loop exixts

    if (slow != fast){

        std::cout << "No Loop" << std::endl;

        return;

    }

    

    // When Loop exists

    slow = head;

    while(slow != fast){

        slow = slow->next;

        fast = fast->next;

    }

    std::cout << "First loop element = " << slow->data << std::endl;

}

Detailed explanation can be found on Youtube:

Subscribe to KnowledgeCenter

Find k-th node from end in Linked List

void print_kth_from_end(Node *head, int k){

    Node *lead = head;

    Node *lag = head;

    while(k > 0){

        if(lead){

            k--;

            lead = lead->next;

        }

        else{

            std::cout << "K is larger than length of Linked List" << std::endl;

            return;

        }

    }

    while(lead){

        lead = lead->next;

        lag = lag->next;

    }

    std::cout << "kth node from end = " << lag->data << std::endl;

}

Detailed explanation can be found on Youtube:

Subscribe to KnowledgeCenter

Find the middle element of a Linked List

void print_middle(Node *head){

    Node *fast = head;

    Node *slow = head;

    while(fast && fast->next){

        fast = fast->next->next;

        slow = slow->next;

    }

    std::cout << slow->data << std::endl;

}

Watch the detailed explanation of the concepts on Youtube:

Subscribe to KnowledgeCenter

Reinforcement Learning : Introduction

Characteristics:

1. No Supervisor, Reward signal
2. Delayed Feedback
3. Data depends on Agent's actions

Examples:

1. Learning to play chess
2. Making a robot walk
3. Fly stunt manoeuvres in Helicopter

Reward (Rt):

• A scalar feedback signal
• Indicates how well agent is doing at time t
• Agent tries to maximize cumulative Reward over time

E.g.,

• Chess : +ve reward for winning the game, -ve for losing
• Robot walk : +ve for forward movement, -ve for falling
• Helicopter manoeuvres : +ve for following trajectory, -ve for crashing

Sequential Decision Making:

• Select actions to maximize total future rewards
• Long-term consequences
• May need to sacrifice immediate rewards for better Long-term rewards

E.g.,

Some moves in chess, financial investments

Agent and Environment:

At each step t, the Agent:

• Executes action At
• Receives observation Ot
• Receives scalar reward Rt

Environment:

• Receives action At
• Emits observation Ot+1
• Emits reward Rt+1

t increments at environment step

Detailed explanation and illustrative examples can be found on Youtube:

Subscribe to KnowledgeCenter

History & State:

History:

• A sequence of Observations, Actions and Rewards that the Agent has seen so far.

            Ht = A1, O1, R1, ….., At, Ot, Rt

• All observable variables up to time t

• What happens next depends on the history:
• Agent(our Algorithm) selects Actions
• Environment selects Observations/Rewards

State:

• History is not very useful as it's a very long stream of data.

• State is the information used to determine what happens next.

• Function of History

St = f(Ht)

E.g, take only last 3 observations

Environment/World State:

• State of environment used to determine how to generate next Observation and Reward.

• Usually not accessible to Agent.

• Even if visible, may not have any information useful for Agent

Agent State:

• Agent's internal representation

• Information used by Agent(our algorithm) to pick next Action

• Can be any function of History

Markov Assumption:

• Information State: State used by Agent is a sufficient statistic of History. In order to predict the future you only only need the current state of the environment.

• State St is Makov if and only if:

P(St+1|St, At) = P(St+1|S1,S2,..,St, At)

• Future is independent of Past given Present

• E.g., State defined by a Trading Algorithm used by HFT traders.
• 
  

Detailed explanation and illustrative examples can be found on Youtube:

Subscribe to KnowledgeCenter

Environment :

Fully Observable Environment:

• Agent directly observes environment state

           O(t) = Sa(t) = Se(t)

• Agent State = Environment State

• Markov Decision Process(MDP)

Partially Observable Environment:

• Agent indirectly observes Environment:
• A HFT trader observes only current prices
• A robot with camera vision doesn't observe its absolute location
• Poker playing agent observes only public cards

• Agent State != Environment State

• Partially Observable Markov Decision Process (POMDP)

• Agent has to construct its own representation of State

E.g.,

• Sa(t) = H(t)
• Sa(t) = (P[Se(t) = s1],....., P[Se(t) = sn])
• Sa(t) = f(Sa(t-1), O(t))

Detailed description can be found on youtube:

Subscribe to KnowledgeCenter

Find the Length of Loop in Linked List

We modify the Floyd's Loop/Cycle Detection Algorithm that we saw in the previous Post to find the count of Nodes which are part of the Linked List.

int count_loop_lenth(Node *node){

    int count = 1;

    Node *curr = node;

    while(curr->next != node){

        curr = curr->next;

        ++count;

    }

    return count;

}

int detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast){

            return count_loop_lenth(slow);

        }

    }

    return 0;

}

Watch detailed Explanation on Youtube.

Subscribe to KnowledgeCenter

Detect Loop in a Linked List

Method 1: (Hashing)

bool detect_loop_map(Node *head){

    std::unordered_map<Node*, bool> visited;

    Node *curr = head;

    while(curr){

        if (visited[curr] == true)

            return true;

        visited[curr] = true;

        curr = curr->next;

    }

    return false;

}

Method 2:(Floyd's Cycle Detection)

bool detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast){

            return true;

        }

    }

    return false;

}

Watch detailed explanation on Youtube:

Visit our Youtube playlist for Linked List: https://www.youtube.com/playlist?list=PL1w8k37X_6L-bwZCPpELH6Cwo3WzUxDp7

Subscribe to KnowledgeCenter

Detecting Faces in image using Convolutional Neural Networks

Detecting Faces in image using Convolutional Neural Networks