コーディング問題

FizzBuzz実装問題

1. 1から100までの数字をループで処理する。

2. 3の倍数のときは「Fizz」と表示する。

3. 5の倍数のときは「Buzz」と表示する。

4. 両方の倍数のときは「FizzBuzz」と表示する。

5. それ以外の数字はそのまま表示する。

def fizz_buzz():
    for i in range(1, 101):
        if i % 15 == 0:
            print("FizzBuzz")
        elif i % 3 == 0:
            print("Fizz")
        elif i % 5 == 0:
            print("Buzz")
        else:
            print(i)

fizz_buzz()

フィボナッチ数列実装問題

1. 関数は引数として整数nを受け取る。

2. フィボナッチ数列のn番目の項を返す。

3. フィボナッチ数列は以下のように定義される:
• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n >= 2)

def fibonacci(n):
    if n < 0:
        raise ValueError("n must be a non-negative integer")
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

# テスト
print(fibonacci(10))  # 出力例: 55

メモ化による最適化

1. メモ化を用いることで、同じ計算を繰り返さずに済むようにする。

2. 計算済みのフィボナッチ数列の値を保存して、再利用する。

def fibonacci_memo(n, memo={}):
    if n < 0:
        raise ValueError("n must be a non-negative integer")
    elif n in memo:
        return memo[n]
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
        return memo[n]

# テスト
print(fibonacci_memo(10))  # 出力例: 55

ビッグオー記法について

• 計算量: O(2^n)

• フィボナッチ数列を再帰的に計算する場合、各関数呼び出しが2つの新しい呼び出しを生成するため、指数関数的な時間がかかります。

• 計算量: O(n)

• メモ化を使用することで、各フィボナッチ数を一度だけ計算し、その結果を再利用するため、線形時間で計算できます。

回文判別実装問題

1. 関数は引数として文字列を受け取る。

2. 文字列が回文である場合は True を返し、そうでない場合は False を返す。

3. 回文とは、前から読んでも後ろから読んでも同じ文字列のことを指します。

4. 大文字と小文字は区別しない。

5. 空白や句読点は無視する。

def is_palindrome(s):
    # アルファベットと数字のみを抽出し、小文字に変換
    cleaned_str = ''.join(char.lower() for char in s if char.isalnum())
    # 逆順と比較して回文かどうかを判定
    return cleaned_str == cleaned_str[::-1]

# テスト
print(is_palindrome("A man, a plan, a canal, Panama"))  # 出力例: True
print(is_palindrome("Hello, World!"))  # 出力例: False

ビッグオー記法について

• 計算量: O(n)

• 文字列を一度スキャンし、逆順と比較するため、線形時間がかかります。

行列回転実装問題

1. 関数は引数としてN×Nの2次元リスト（行列）を受け取る。

2. 行列を時計回りに90度回転させた新しい行列を返す。

def rotate_matrix(matrix):
    n = len(matrix)
    # 新しい行列を作成
    rotated_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            rotated_matrix[j][n - 1 - i] = matrix[i][j]
    return rotated_matrix

# テスト
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotated = rotate_matrix(matrix)
for row in rotated:
    print(row)
# 出力例:
# [7, 4, 1]
# [8, 5, 2]
# [9, 6, 3]

ビッグオー記法について

• 計算量: O(n^2)

• 行列の各要素に一度アクセスして新しい位置に移動するため、二重ループを使用し、時間計算量はO(n^2)です。

Linked List 実装問題 1: 単方向連結リストの逆転

1. 関数は引数として連結リストのヘッドノードを受け取る。

2. 連結リストを逆転させ、新しいヘッドノードを返す。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

# テスト
def print_list(node):
    while node:
        print(node.val, end=" -> ")
        node = node.next
    print("None")

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Original list:")
print_list(head)
reversed_head = reverse_linked_list(head)
print("Reversed list:")
print_list(reversed_head)

• 時間計算量: O(n)

• 空間計算量: O(1)

Linked List 実装問題 2: 連結リストの中間ノードの削除

1. 関数は削除するノードそのものを受け取る。

2. ノードは連結リストの最初でも最後でもないことが保証されている。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def delete_middle_node(node):
    if node is None or node.next is None:
        return
    next_node = node.next
    node.val = next_node.val
    node.next = next_node.next

# テスト
def print_list(node):
    while node:
        print(node.val, end=" -> ")
        node = node.next
    print("None")

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Original list:")
print_list(head)
delete_middle_node(head.next.next)  # 3を削除
print("List after deleting the middle node (3):")
print_list(head)

• 時間計算量: O(1)

• 空間計算量: O(1)

Linked List 実装問題 3: 連結リストのサイクル検出

1. 関数は引数として連結リストのヘッドノードを受け取る。

2. リストにサイクルが存在する場合は True を返し、そうでない場合は False を返す。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# テスト
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = head.next.next  # サイクルを作成

print("Does the list have a cycle?")
print(has_cycle(head))  # 出力例: True

• 時間計算量: O(n)

• 空間計算量: O(1)

Coding Challenge: School Library Book Distribution

• 2Y ≤ X ≤ 1000, where X is an integer

• 10 ≤ Y ≤ 100, where Y is an integer

• 2 ≤ Z < Y, where Z is an integer

• The number of books each latecomer receives should be less than or equal to the final number of books each of the initially present students retains (after one book has been collected from each)."

Test Cases for the Challenge

• Input: X = 100, Y = 20, Z = 5

• Expected Output: 4

• Input: X = 500, Y = 25, Z = 10

• Expected Output: 19

• Input: X = 300, Y = 30, Z = 5

• Expected Output: 9

• Input: X = 800, Y = 40, Z = 20

• Expected Output: 19

• Input: X = 400, Y = 50, Z = 10

• Expected Output: 7

• Input: X = 200, Y = 10, Z = 9

• Expected Output: 11

Programming Challenge: Sugoroku Practice

• 2 ≤ A ≤ 100000

• A is an integer

Test Cases for the Challenge

• Input: A = 10

• Expected Output: 2

• Input: A = 7

• Expected Output: 2

• Input: A = 15

• Expected Output: 3

• Input: A = 20

• Expected Output: 4

• Input: A = 2

• Expected Output: 1

• Input: A = 100000

• Expected Output: 16667