Category: Python Coding Test

1. Introduction

Today, we will discuss one of the effective sorting algorithms using Python, known as Quick Sort. Quick Sort has an average time complexity of O(n log n) and is, in practice, a very fast and efficient sorting algorithm. In this process, we will examine the working principle of Quick Sort and learn how to implement it in Python.

2. What is Quick Sort?

Quick Sort is a type of divide-and-conquer algorithm that divides an array into two sub-arrays and recursively sorts each sub-array to sort the entire array. The key to this process is to choose a reference value called ‘pivot’ and partition the array based on that value.

2.1 Steps of Quick Sort

1. Select the pivot value from the array.
2. Partition the array into two sub-arrays based on the pivot. The first sub-array consists of values less than the pivot, while the second sub-array consists of values greater than the pivot.
3. Recursively repeat the above steps to sort the sub-arrays.
4. Once all sub-arrays are sorted, the entire array will be sorted.

2.2 Pivot Selection

There are several methods for selecting the pivot, and generally, one of the first element, last element, or middle element is chosen. Additionally, there is a method to select the pivot randomly, which helps maintain an O(n log n) performance even in the worst-case scenario.

3. Problem Solving

3.1 Problem Description

Write a function that takes an input integer array and returns a sorted array. You must use the Quick Sort algorithm.

3.2 Input and Output Format

• Input: Integer array arr = [3, 6, 8, 10, 1, 2, 1]
• Output: Sorted array [1, 1, 2, 3, 6, 8, 10]

3.3 Solution Process

Let’s examine the process of implementing the Quick Sort algorithm in Python step by step.

3.3.1 Pivot Selection and Array Partitioning

First, we will write a function to select the pivot and partition the array based on the pivot. Below is the code that performs this task.

    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1
        
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    

3.3.2 Implementing the Quick Sort Function

Now we will implement a function that recursively sorts the partitioned array.

    def quick_sort(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            quick_sort(arr, low, pi - 1)
            quick_sort(arr, pi + 1, high)
    

3.3.3 Complete Code

Using the functions we have written above, the complete Quick Sort code is as follows.

    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1
        
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    def quick_sort(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            quick_sort(arr, low, pi - 1)
            quick_sort(arr, pi + 1, high)

    arr = [3, 6, 8, 10, 1, 2, 1]
    quick_sort(arr, 0, len(arr) - 1)
    print("Sorted array:", arr)
    

4. Advantages and Disadvantages of Quick Sort

4.1 Advantages

• Generally has a time complexity of O(n log n), making it fast.
• The recursive nature allows for concise code.
• Supports in-place sorting, leading to minimal additional memory usage.

4.2 Disadvantages

• In the worst case (e.g., already sorted array), it can have a time complexity of O(n^2).
• Excessive recursive calls may lead to stack overflow.

5. Conclusion

In this lecture, we explored the implementation process of the Quick Sort algorithm using Python. While Quick Sort is an effective sorting method in many situations, there are points of caution to be aware of when using it. Understanding the properties of the algorithm and applying it correctly in appropriate situations is important.

I hope this has been helpful in understanding Quick Sort. In the next lecture, we will delve into other sorting algorithms. Thank you!

Hello! Today we will learn about one of the frequently asked algorithm problems in coding tests called the “Kevin Bacon’s Six Degrees of Separation.” This problem can be solved by utilizing various concepts from graph theory and offers a great opportunity to practice basic search algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS).

1. Problem Description

Kevin Bacon’s Six Degrees of Separation is a famous social network theory stating that there is a connection through relationships between any two people within six steps. This is a problem to implement this theory in code.

The problem is as follows:

Given N users and the relationships between them,
calculate the Kevin Bacon score for each user,
and output the user with the lowest score.
The score is the sum of the shortest distances to that user.

2. Input Format

The first line contains the number of users N (1 ≤ N ≤ 100) and the number of relationships M (0 ≤ M ≤ 4,900).

The next M lines contain two integers a and b, indicating that users a and b are friends with each other.

3. Output Format

Print the number of the user with the lowest Kevin Bacon score. In case of a tie, print the user with the smallest number.

4. Problem Solving Process

To solve this problem, follow these steps:

4.1. Graph Creation

First, create a graph representing each user’s friendships in the form of an adjacency list. This graph can be represented using a dictionary or list.

graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

4.2. Implement BFS or DFS

For each user, calculate the shortest distance to other users using BFS or DFS. Since BFS guarantees the shortest path, it is more suitable for this problem.

def bfs(start, graph):
    queue = [start]
    visited = {start: 0}
    
    while queue:
        current = queue.pop(0)
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)
    return sum(visited.values())

4.3. Score Calculation

Calculate the Kevin Bacon score for all users. Use the BFS results to store the scores and find the lowest score.

min_score = float('inf')
user_with_min_score = -1
for user in range(1, N + 1):
    score = bfs(user, graph)
    if score < min_score:
        min_score = score
        user_with_min_score = user
    elif score == min_score:
        user_with_min_score = min(user_with_min_score, user)

5. Full Code

Now, let's write the full code that integrates the above processes.

from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = {start: 0}
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)
    return sum(visited.values())

def find_kevin_bacon(graph, n):
    min_score = float('inf')
    user_with_min_score = -1
    
    for user in range(1, n + 1):
        score = bfs(user, graph)
        if score < min_score:
            min_score = score
            user_with_min_score = user
        elif score == min_score:
            user_with_min_score = min(user_with_min_score, user)
    
    return user_with_min_score

# Input
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# Output result
result = find_kevin_bacon(graph, N)
print(result)

6. Code Explanation

The code takes input values for N and M, constructs a graph based on friendships, and then calculates the Kevin Bacon score for each user using BFS. Finally, it outputs the number of the user with the lowest score. This problem provides a great practice for understanding graph theory and the BFS algorithm.

7. Performance Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices (users) and E is the number of edges (relationships). Assuming N is 100, the worst-case scenario could have 4900 relationships, resulting in approximately 495,000 searches during 100 BFS calls. This is within a range that can be sufficiently handled within the given time.

8. Conclusion

This problem utilizing Kevin Bacon's Six Degrees of Separation provides a good opportunity to solidify the fundamentals of graph theory and learn how to apply BFS. Practicing various variations of this problem can further enhance your algorithmic thinking. We wish you continued success in preparing for coding tests through diverse problem-solving!

Thank you!

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!