Author: root

Algorithm problem-solving skills are an important factor in technical interviews. In this post, we will deal with the algorithm problem called ‘Card Sorting’ and examine the problem-solving process step by step. This problem is one of the types frequently appearing in actual coding tests and involves sorting the given cards in a specific way. Through this article, let’s enhance our understanding of the problem and learn methods that can be applied in practice.

Problem Definition

There are N given cards. These cards are marked with numbers, which are integers. Our goal is to sort these cards. However, we must follow specific rules during this process.

Function Signature:
def card_sorting(cards: List[int]) -> List[int]:
    pass

Here, cards is a list of integers and we need to return the sorted cards. However, each card must be sorted in a predetermined manner. It is important to note that there may be specific conditions related to performing the card sorting, and these conditions must be handled effectively.

Approach to the Problem

Now, let’s look at the approach to solve the problem. Let’s assume there are the following detailed rules for the card sorting problem:

• The cards are arranged in the given order, and each card is sorted by comparing it with adjacent cards.
• During the sorting process, cards with smaller numbers are moved to the left.
• The numbers on each card are unique and not duplicated.

Now, we can use various algorithms to sort the cards. The commonly used algorithms are as follows:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort

A theoretical explanation is also needed for each algorithm, so I will provide a brief description for each of them.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. This algorithm sorts by comparing two adjacent elements. It repeats the process for the size of the list, comparing adjacent elements and swapping them as needed. In the worst case, it has a time complexity of O(N²).

Selection Sort

Selection Sort finds the smallest value from the given list and continues sorting from there. It repeats the process for the size of the list, finding the smallest value from the remaining elements and placing it in the current position. This also has a time complexity of O(N²).

Insertion Sort

Insertion Sort inserts new elements into already sorted data. Initially, the first element is considered sorted, and from the next element, it is inserted in the sorted position. Generally, it has a time complexity of O(N²), but it performs better when the data is nearly sorted.

Quick Sort

Quick Sort is based on a divide-and-conquer algorithm and selects a pivot element to partition the list into values smaller and larger than the pivot. After that, it recursively applies Quick Sort to each sublist. On average, it has a time complexity of O(N log N).

Merge Sort

Merge Sort also uses the divide-and-conquer technique. It splits the list in half, recursively sorts each list, and then merges the two sorted lists. It also has a time complexity of O(N log N).

Solution – Implementing Card Sorting

Now, let’s implement the Python code to solve the card sorting problem. We will use Quick Sort to tackle this problem.

from typing import List

def quick_sort(cards: List[int]) -> List[int]:
    if len(cards) <= 1:
        return cards
    pivot = cards[len(cards) // 2]
    left = [x for x in cards if x < pivot]
    middle = [x for x in cards if x == pivot]
    right = [x for x in cards if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def card_sorting(cards: List[int]) -> List[int]:
    return quick_sort(cards)

Test Cases

Now that the code is implemented, let’s check if it works correctly with various test cases.

if __name__ == "__main__":
    test_cases = [
        [3, 6, 8, 10, 1, 2, 1],
        [5, 2, 9, 1, 5, 6],
        [2, 7, 1, 8, 2, 3, 5]
    ]
    
    for cards in test_cases:
        sorted_cards = card_sorting(cards)
        print(f"Original: {cards} -> Sorted: {sorted_cards}")

When you run this code, you can get results like the following:

Original: [3, 6, 8, 10, 1, 2, 1] -> Sorted: [1, 1, 2, 3, 6, 8, 10]
Original: [5, 2, 9, 1, 5, 6] -> Sorted: [1, 2, 5, 5, 6, 9]
Original: [2, 7, 1, 8, 2, 3, 5] -> Sorted: [1, 2, 2, 3, 5, 7, 8]

Conclusion

In this article, we explored various sorting algorithms to solve the ‘Card Sorting’ problem, using the Quick Sort algorithm to arrive at a solution. The implementation method using Python, along with appropriate test cases, verified the accuracy of the code. Through problems like this, I hope to cultivate algorithmic thinking and achieve good results in coding tests. Keep practicing with various problems and enhance your skills!

We often encounter game problems with specific rules in coding tests. In this lecture, we will cover a problem related to card games. Card game problems are a good example that can be effectively solved using algorithms and data structures.

Problem Description

Two players are playing a card game. Each player has unique cards labeled with numbers from 1 to N. Players take turns picking one card at a time. Each player earns points equal to the number on the card they pick.

Problem: Implement a function to maximize the scores that both players can achieve while playing the game and calculate the final score. The following conditions apply:

• Each player can select cards from 1 to N.
• Each player can select one card at a time, and a card cannot be selected again.
• The final score is the sum of the cards chosen by each player.

Input

• An integer N (1 ≤ N ≤ 100) – the number of cards

Output

• The total score of both players

Algorithmic Approach

This problem requires simple score calculations and optimizations based on card selection. We will solve the problem with the following approach:

1. Create a list of card numbers for the players to choose from.
2. Define how each player can calculate their card scores.
3. Simulate the card selections of both players to calculate the final scores.

Code Implementation

Now, let’s implement the code to solve the problem. Below is the Python code for solving the problem:

def card_game(n):
    # Generate card numbers.
    cards = list(range(1, n + 1))
    
    # Initialize player scores
    player1_score = 0
    player2_score = 0
    
    # Players take turns selecting cards
    turn = 0
    while cards:
        # Current player's selection
        if turn % 2 == 0:  # Player 1's turn
            chosen_card = max(cards)  # Select the highest value
            player1_score += chosen_card
        else:  # Player 2's turn
            chosen_card = min(cards)  # Select the lowest value
            player2_score += chosen_card

        # Remove the chosen card
        cards.remove(chosen_card)
        turn += 1

    return player1_score + player2_score

# Example
n = 5
print("Final score:", card_game(n))

Code Explanation

Let me briefly explain the code we wrote:

1. def card_game(n): – Defines the card game function. It takes N as input.
2. cards = list(range(1, n + 1)) – Creates a list of cards from 1 to N.
3. player1_score and player2_score – Initializes the scores for both players.
4. while cards: – Continues to loop while there are cards left.
5. if turn % 2 == 0: – Checks the player’s turn and selects cards alternately.
6. Depending on the player’s selection, either the maximum card or the minimum card is chosen and added to the score.
7. cards.remove(chosen_card) – Removes the chosen card from the card list.
8. Finally, it returns the sum of the scores of both players.

Test Cases

Let’s test the function that calculates the final score. We’ll create various test cases to observe different results:

print("N=3:", card_game(3))  # Output: 6
print("N=4:", card_game(4))  # Output: 10
print("N=5:", card_game(5))  # Output: 15
print("N=10:", card_game(10))  # Output: 55

Conclusion

In this lecture, we learned the basic uses of algorithms and data structures through a simple card game problem. We saw how one must strategically think about score accumulation with each card selection.

Such card game problems help develop algorithmic thinking and can be practiced through various variations. You can apply the problem discussed in this lecture to explore more complex card games or different types of problems. I hope you continue to enhance your skills through a variety of algorithm problem-solving!

Problem Description

You need to develop a program that understands user relationships in a social network.
The program must provide answers to the following two requests based on the friendships of the given users.

• Print the friend list of the given user A.
• Check whether the given users A and B are friends.

Input Format

The first line contains the number of users N and the number of friendships M. (1 ≤ N ≤ 100,000, 0 ≤ M ≤ 1,000,000)

The next M lines each contain two integers A and B, meaning A is a friend of B.

Output Format

Print the friend list of user A in ascending order on the first line.
On the second line, print ‘YES’ or ‘NO’ regarding whether A and B are friends.

Example

        Input Example:
        5 4
        1 2
        1 3
        2 4
        3 5
        
        1
        2

        Output Example:
        2 3
        NO
    

Approach

To solve this problem, you need to efficiently store and query friendship relationships.
You can utilize graph theory by using an adjacency list or set data structure.

First, initialize an empty list to store information about users and friendship relationships.
Then, receive each friendship relationship as input and store the information.
Sort the friend list for output and also provide a response to the friendship verification request.

Source Code

        def manage_friendship(n, m, friendships, a, b):
            friends = {i: set() for i in range(1, n + 1)}
            
            for x, y in friendships:
                friends[x].add(y)
                friends[y].add(x)
            
            friend_list = sorted(friends[a])
            is_friend = "YES" if b in friends[a] else "NO"
            
            return friend_list, is_friend
        
        # Input processing
        n, m = map(int, input().split())
        friendships = [tuple(map(int, input().split())) for _ in range(m)]
        a = int(input())
        b = int(input())

        # Manage friendships
        friend_list, is_friend = manage_friendship(n, m, friendships, a, b)

        # Output results
        print(" ".join(map(str, friend_list)))
        print(is_friend)
    

Conclusion

This algorithm problem requires a basic understanding of data structures and algorithms to efficiently manage and
query friendship relationships.
In real software development, handling such data relationships often appears in platforms such as custom applications or social networks,
so learning how to solve these problems is very useful.

Appendix

Many graph problems, such as friendship relationships, can evolve into more advanced problems through searching algorithms like DFS (Depth First Search) or BFS (Breadth First Search).
Based on this problem, I hope you challenge those advanced problems as well.

Problem Description

Given two strings, this is a problem of finding the Longest Common Subsequence (LCS) between them. A common subsequence refers to characters that appear in both strings while maintaining their order. The goal is to find the maximum length of such a subsequence.

Example

Input

String A: ABCBDAB
String B: BDCAB

Output

Longest Common Subsequence: BDAB

Approach to the Problem

To solve the LCS problem, we can use Dynamic Programming. Dynamic Programming is a technique that solves problems by storing already computed results and reusing them. To find the LCS, we store the length of the subsequence based on the comparison results of each character in the two strings.

Finding LCS using Dynamic Programming

Step 1: Initialize the DP Table

Let the lengths of the two strings be m and n, we create and initialize a 2D DP array of size (m + 1) x (n + 1). Each element of the DP array stores the length of the common subsequence found in the two strings.

Step 2: Fill the DP Table

We fill in the DP table while comparing each character of the two strings. If the characters match, the LCS length including that character is DP[i-1][j-1] + 1. If they do not match, we use DP[i][j] = max(DP[i-1][j], DP[i][j-1]) to record the length of the LCS found so far.

Step 3: Extract LCS Length and String

After filling the DP table, check DP[m][n] to get the length of the longest common subsequence, and extract the actual common subsequence using this length. The extraction process is carried out by tracing back through the table to find common characters.

Algorithm Code

    
def lcs(A, B):
    # Step 1: Initialize the DP array
    m = len(A)
    n = len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Step 2: Fill the DP array
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Step 3: Get LCS length
    lcs_length = dp[m][n]

    # Extract LCS string
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if A[i - 1] == B[j - 1]:
            lcs_str.append(A[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs_str.reverse()  # Reverse the extracted string to restore original order
    return lcs_length, ''.join(lcs_str)

# Test code
A = "ABCBDAB"
B = "BDCAB"
length, lcs_string = lcs(A, B)
print("LCS length:", length)
print("LCS string:", lcs_string)
    
    

Complexity Analysis

The time complexity of this algorithm is O(m * n). Since each character needs to be compared, the result is a product of the lengths of the two strings. The space complexity is also O(m * n), determined by the size of the created DP table. However, there are ways to reduce the size of the DP table. For example, since only the previous row’s data is needed, it can be implemented using two 1D arrays.

Optimized Code Example

    
def optimized_lcs(A, B):
    m = len(A)
    n = len(B)
    dp = [0] * (n + 1)

    for i in range(1, m + 1):
        current = 0  # Value at the current position
        for j in range(1, n + 1):
            temp = dp[j]
            if A[i - 1] == B[j - 1]:
                dp[j] = current + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            current = temp  # Store the value from the previous row

    return dp[n]

# Optimized test
length = optimized_lcs(A, B)
print("LCS length:", length)
    
    

Conclusion

In this lecture, we dealt with the problem of finding the Longest Common Subsequence (LCS). This problem is a great example of how to easily utilize string processing and dynamic programming concepts. The LCS problem is widely used in various fields, especially in gene analysis and finding identical sequences, so understanding and implementing the algorithm is very useful for coding tests and practical applications.

References

• Longest Common Subsequence – Wikipedia
• GeeksforGeeks: Longest Common Subsequence