コーディング問題

FizzBuzz実装問題

課題: 1から100までの数字を表示し、3の倍数のときは「Fizz」、5の倍数のときは「Buzz」、両方の倍数のときは「FizzBuzz」と表示する関数を作成してください。

要件:

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

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

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

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

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

Python:


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から100までの数が出力され、3の倍数のときは「Fizz」、5の倍数のときは「Buzz」、両方の倍数のときは「FizzBuzz」として表示されます。

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

課題: フィボナッチ数列のn番目の項を計算する関数を作成してください。

要件:

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

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

フィボナッチ数列は以下のように定義される:

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2) (n >= 2)

Python:


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

この関数を実行すると、指定されたn番目のフィボナッチ数が出力されます。たとえば、fibonacci(10)を呼び出すと、出力は55になります。

メモ化による最適化

課題: メモ化を用いてフィボナッチ数列のn番目の項を効率的に計算する関数を作成してください。

要件:

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

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

Python:


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

この関数を実行すると、指定されたn番目のフィボナッチ数が出力されます。たとえば、fibonacci_memo(10)を呼び出すと、出力は55になります。

ビッグオー記法について

通常のフィボナッチ計算:

計算量: O(2^n)

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

メモ化を使用したフィボナッチ計算:

計算量: O(n)

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

回文判別実装問題

課題: 与えられた文字列が回文かどうかを判別する関数を作成してください。

要件:

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

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

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

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

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

Python:


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

この関数を実行すると、与えられた文字列が回文かどうかを判定します。たとえば、is_palindrome("A man, a plan, a canal, Panama")を呼び出すと、出力は True になります。

ビッグオー記法について

計算量: O(n)

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

行列回転実装問題

課題: 与えられたN×Nの行列を90度回転する関数を作成してください。

要件:

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

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

Python:


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]

この関数を実行すると、与えられたN×Nの行列が時計回りに90度回転した新しい行列が出力されます。

ビッグオー記法について

通常の行列回転:

計算量: O(n^2)

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

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

課題: 単方向連結リストを逆転する関数を作成してください。

要件:

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

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

Python:


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: 連結リストの中間ノードの削除

課題: 単方向連結リストの中間にあるノードを削除する関数を作成してください。

要件:

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

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

Python:


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: 連結リストのサイクル検出

課題: 単方向連結リストにサイクルが存在するかどうかを検出する関数を作成してください。

要件:

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

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

Python:


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

"In a school library, there were 'X' books to be distributed equally among 'Y' students. After the distribution, each student received an equal number of books. However, later 'Z' additional students joined. To ensure fairness, the librarian decided to collect one book from each of the 'Y' students who had already received books, and redistribute these collected books along with any remaining undistributed books to the 'Z' new students.

Your task is to write a program that calculates how many books each of the 'Z' latecomers will receive. The program should take 'X', 'Y', and 'Z' as inputs and output the number of books received by each latecomer student.

Constraints:

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

Test Case 1:

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

Expected Output: 4

Test Case 2:

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

Expected Output: 19

Test Case 3:

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

Expected Output: 9

Test Case 4:

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

Expected Output: 19

Test Case 5:

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

Expected Output: 7

Test Case 6 (Edge Case):

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

Expected Output: 11

Programming Challenge: Sugoroku Practice

"Satomi is practicing Sugoroku on a linear board with A squares, starting from the leftmost square (start) and aiming to reach the rightmost square (goal). In each turn, she rolls a six-sided die and moves the piece forward by the number indicated on the die. Your task is to create a program that calculates the minimum number of times Satomi needs to roll the die to potentially reach the goal.

Constraints:

2 ≤ A ≤ 100000

A is an integer

The program should take an integer A as input and output the minimum number of die rolls required."

Test Cases for the Challenge

Test Case 1:

Input: A = 10

Expected Output: 2

Test Case 2:

Input: A = 7

Expected Output: 2

Test Case 3:

Input: A = 15

Expected Output: 3

Test Case 4:

Input: A = 20

Expected Output: 4

Test Case 5:

Input: A = 2

Expected Output: 1

Test Case 6 (Edge Case):

Input: A = 100000

Expected Output: 16667

FizzBuzz実装問題

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

メモ化による最適化

ビッグオー記法について

回文判別実装問題

ビッグオー記法について

行列回転実装問題

ビッグオー記法について

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

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

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

Coding Challenge: School Library Book Distribution

Test Cases for the Challenge

Programming Challenge: Sugoroku Practice

Test Cases for the Challenge

テック企業求人一覽

テック企業求人一覽