Coding Challenges for Beginners — Pattern Over Volume

# io.thecodeforge — Interview tutorial

# This is a pattern identification cheat-sheet in code form.
# Before writing a solution, run through this decision tree mentally.
# Real interviewers notice when you start by naming the pattern — it signals seniority.

def identify_pattern(problem_description: str) -> str:
    """
    A simplified mental model for pattern recognition.
    In a real interview, you walk through these questions out loud.
    That narration is what separates a 'good coder' from a 'good engineer' in the interviewer's mind.
    """

    # Signal words that point to specific patterns
    pattern_signals = {
        "two pointers": [
            "sorted array",        # Two pointers thrive on sorted data
            "pair that sums to",   # Classic two-sum variant
            "palindrome",          # Check from both ends simultaneously
            "remove duplicates",   # One pointer reads, one pointer writes
        ],
        "sliding window": [
            "subarray",            # Contiguous chunk of an array
            "substring",           # Contiguous chunk of a string
            "maximum sum of k",    # Fixed-size window
            "longest with condition", # Variable-size window
        ],
        "frequency map": [
            "most frequent",       # Count occurrences, find the max
            "anagram",             # Same characters, different order — check counts
            "appears more than",   # Threshold-based counting
            "first unique",        # Count then scan for count == 1
        ],
        "binary search": [
            "sorted",              # Binary search REQUIRES sorted input
            "find minimum",        # Often binary search on answer space
            "search in rotated",   # Classic binary search variant
        ],
        "fast and slow pointers": [
            "linked list cycle",   # Floyd's algorithm territory
            "middle of linked list", # Fast moves 2x, slow moves 1x
            "detect loop",         # Same as cycle detection
        ],
    }

    problem_lower = problem_description.lower()
    matches = []

    for pattern, signals in pattern_signals.items():
        for signal in signals:
            if signal in problem_lower:
                # Collect every matching pattern — some problems combine two
                matches.append(f"Pattern candidate: '{pattern}' (triggered by signal: '{signal}')")

    if not matches:
        return "No strong pattern signal detected — read constraints carefully and look for hidden sorting or counting structure."

    return "\n".join(matches)


# --- Test it on three real problem descriptions ---

problem_1 = "Given a sorted array, find two numbers that sum to a target value."
problem_2 = "Find the longest substring without repeating characters."
problem_3 = "Given an array, return the most frequent element."

print("Problem 1 Analysis:")
print(identify_pattern(problem_1))
print()

print("Problem 2 Analysis:")
print(identify_pattern(problem_2))
print()

print("Problem 3 Analysis:")
print(identify_pattern(problem_3))

# io.thecodeforge — Interview tutorial

# Five core patterns, each demonstrated on a real interview problem.
# Every solution includes the brute-force time complexity as a comparison
# so you understand exactly WHY the pattern exists.

from collections import defaultdict
from typing import List, Optional


# ─────────────────────────────────────────────
# PATTERN 1: TWO POINTERS
# Problem: Given a SORTED array, find indices of two numbers that sum to target.
# Brute force: O(n²) — nested loops checking every pair
# Two pointers: O(n) — one pass, no extra space
# ─────────────────────────────────────────────
def two_sum_sorted(numbers: List[int], target: int) -> List[int]:
    left = 0                          # Start pointer at the smallest element
    right = len(numbers) - 1         # End pointer at the largest element

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]   # Problem convention: 1-indexed output
        elif current_sum < target:
            left += 1    # Sum is too small — move left pointer right to increase it
        else:
            right -= 1   # Sum is too big — move right pointer left to decrease it

    return []  # No valid pair found — shouldn't happen if input is guaranteed valid


# ─────────────────────────────────────────────
# PATTERN 2: SLIDING WINDOW
# Problem: Find max sum of any contiguous subarray of size k.
# Brute force: O(n*k) — recalculate sum for every window from scratch
# Sliding window: O(n) — slide the frame, add new element, remove old element
# ─────────────────────────────────────────────
def max_subarray_sum_of_size_k(numbers: List[int], window_size: int) -> int:
    window_sum = sum(numbers[:window_size])   # Sum of the first window
    max_sum = window_sum

    for right_index in range(window_size, len(numbers)):
        # Slide the window: add the incoming element on the right,
        # remove the outgoing element on the left
        window_sum += numbers[right_index]
        window_sum -= numbers[right_index - window_size]  # Drop the element that fell off the left
        max_sum = max(max_sum, window_sum)

    return max_sum


# ─────────────────────────────────────────────
# PATTERN 3: FREQUENCY MAP
# Problem: Find the first non-repeating character in a string.
# Brute force: O(n²) — for each character, scan entire string to count occurrences
# Frequency map: O(n) — one pass to count, one pass to find first with count == 1
# ─────────────────────────────────────────────
def first_unique_character(text: str) -> int:
    char_count = defaultdict(int)

    for character in text:
        char_count[character] += 1   # Build frequency map in one pass

    for index, character in enumerate(text):
        if char_count[character] == 1:
            return index   # First character with count 1 is our answer

    return -1   # Every character appears more than once


# ─────────────────────────────────────────────
# PATTERN 4: BINARY SEARCH
# Problem: Search for a target in a sorted array. Return index or -1.
# Brute force: O(n) — linear scan
# Binary search: O(log n) — eliminate half the search space every step
# ─────────────────────────────────────────────
def binary_search(sorted_numbers: List[int], target: int) -> int:
    low = 0
    high = len(sorted_numbers) - 1

    while low <= high:
        mid = low + (high - low) // 2   # Avoid integer overflow — safer than (low + high) // 2

        if sorted_numbers[mid] == target:
            return mid
        elif sorted_numbers[mid] < target:
            low = mid + 1    # Target is in the right half — discard left
        else:
            high = mid - 1   # Target is in the left half — discard right

    return -1


# ─────────────────────────────────────────────
# PATTERN 5: FAST AND SLOW POINTERS
# Problem: Detect a cycle in a linked list.
# Brute force: O(n) time, O(n) space — store every visited node in a set
# Fast/slow: O(n) time, O(1) space — no extra storage needed
# ─────────────────────────────────────────────
class ListNode:
    def __init__(self, value: int):
        self.value = value
        self.next: Optional['ListNode'] = None

def has_cycle(head: Optional[ListNode]) -> bool:
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next          # Slow pointer moves one step
        fast = fast.next.next     # Fast pointer moves two steps

        if slow is fast:          # If they meet, a cycle exists
            return True

    return False   # Fast pointer hit the end — no cycle


# ─────────────────────────────────────────────
# RUN ALL FIVE PATTERNS
# ─────────────────────────────────────────────
if __name__ == "__main__":
    # Pattern 1: Two Pointers
    sorted_arr = [1, 3, 5, 7, 9, 11]
    print(f"Two Pointers — pair summing to 10: indices {two_sum_sorted(sorted_arr, 10)}")

    # Pattern 2: Sliding Window
    prices = [2, 1, 5, 1, 3, 2]
    print(f"Sliding Window — max sum of window size 3: {max_subarray_sum_of_size_k(prices, 3)}")

    # Pattern 3: Frequency Map
    word = "leetcode"
    print(f"Frequency Map — first unique char index in '{word}': {first_unique_character(word)}")

    # Pattern 4: Binary Search
    sorted_list = [1, 3, 5, 7, 9, 11, 13]
    print(f"Binary Search — index of 7 in list: {binary_search(sorted_list, 7)}")

    # Pattern 5: Fast and Slow Pointers — build a cycle manually
    node_a = ListNode(1)
    node_b = ListNode(2)
    node_c = ListNode(3)
    node_d = ListNode(4)
    node_a.next = node_b
    node_b.next = node_c
    node_c.next = node_d
    node_d.next = node_b   # Create cycle: D points back to B
    print(f"Fast/Slow Pointers — cycle detected: {has_cycle(node_a)}")

# io.thecodeforge — Interview tutorial

# This is the VARIABLE-SIZE sliding window — the harder variant beginners often skip.
# Fixed-size windows are intuitive (add one, remove one).
# Variable-size windows expand and CONTRACT based on a constraint.
# This is the pattern behind: longest substring without repeats, minimum window substring, etc.

# PROBLEM: Find the length of the longest substring with no repeating characters.
# Example: "abcabcbb" → 3 (the substring "abc")
# Example: "pwwkew"  → 3 (the substring "wke")

def longest_substring_no_repeats(text: str) -> int:
    """
    Variable-size sliding window with a set as the 'memory' of what's currently in the window.
    The window expands to the right greedily.
    The moment we see a duplicate, we shrink from the left until the duplicate is gone.
    """
    characters_in_window = set()  # Tracks which characters are currently in the window
    left_boundary = 0             # Left edge of the current window
    longest_length = 0

    for right_boundary in range(len(text)):
        current_char = text[right_boundary]

        # If the incoming character is already in our window, we have a violation.
        # Shrink the window from the left until the duplicate falls out.
        while current_char in characters_in_window:
            # Remove the character at the left boundary from our tracking set
            characters_in_window.remove(text[left_boundary])
            left_boundary += 1   # Shrink the window from the left

        # Now the window has no duplicates — safe to add the new character
        characters_in_window.add(current_char)

        # Window size = right_boundary - left_boundary + 1
        current_window_length = right_boundary - left_boundary + 1
        longest_length = max(longest_length, current_window_length)

    return longest_length


# ─────────────────────────────────────────────
# TRACE THROUGH ONE EXAMPLE MANUALLY
# Input: "abcabcbb"
# Step by step:
#   right=0, char='a' → window={'a'}, length=1
#   right=1, char='b' → window={'a','b'}, length=2
#   right=2, char='c' → window={'a','b','c'}, length=3  ← new max
#   right=3, char='a' → duplicate! shrink from left:
#       remove 'a' (left=0), left=1 → window={'b','c'}, add 'a' → {'b','c','a'}, length=3
#   right=4, char='b' → duplicate! shrink:
#       remove 'b' (left=1), left=2 → window={'c','a'}, add 'b' → {'c','a','b'}, length=3
# ... and so on. Max stays at 3.
# ─────────────────────────────────────────────

if __name__ == "__main__":
    test_cases = [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("abcdef", 6),   # All unique — entire string is the window
        ("", 0),          # Empty string edge case
    ]

    for input_string, expected_output in test_cases:
        result = longest_substring_no_repeats(input_string)
        status = "PASS" if result == expected_output else "FAIL"
        print(f"[{status}] Input: '{input_string}' → Got: {result}, Expected: {expected_output}")

# io.thecodeforge — Interview tutorial

# A lightweight practice tracker you can actually run.
# Track problem attempts, pattern tags, and whether you can re-solve from memory.
# The 'solved_from_memory' flag is the real metric — not whether you solved it at all.

from dataclasses import dataclass, field
from typing import List
from datetime import date


@dataclass
class PracticeEntry:
    problem_name: str
    platform: str                      # e.g. 'LeetCode', 'HackerRank', 'Codewars'
    pattern_tag: str                   # e.g. 'two_pointers', 'sliding_window'
    difficulty: str                    # 'easy', 'medium', 'hard'
    date_attempted: date
    solved_on_first_try: bool
    solved_from_memory_next_day: bool  # The REAL test — can you reconstruct without hints?
    time_to_solve_minutes: int
    notes: str = ""                    # Where you got stuck, what clicked


@dataclass
class PracticeLog:
    entries: List[PracticeEntry] = field(default_factory=list)

    def add_entry(self, entry: PracticeEntry) -> None:
        self.entries.append(entry)

    def pattern_mastery_report(self) -> dict:
        """
        For each pattern, calculate what % of problems you can re-solve from memory.
        Below 80%? That pattern needs more work before moving on.
        """
        pattern_stats = {}

        for entry in self.entries:
            tag = entry.pattern_tag
            if tag not in pattern_stats:
                pattern_stats[tag] = {"total": 0, "memory_solves": 0}

            pattern_stats[tag]["total"] += 1
            if entry.solved_from_memory_next_day:
                pattern_stats[tag]["memory_solves"] += 1

        report = {}
        for pattern, stats in pattern_stats.items():
            memory_rate = (stats["memory_solves"] / stats["total"]) * 100
            # Colour-coded readiness signal
            if memory_rate >= 80:
                readiness = "READY — move to next pattern"
            elif memory_rate >= 50:
                readiness = "IMPROVING — do 2 more problems in this pattern"
            else:
                readiness = "NEEDS WORK — re-read the pattern, re-solve old problems"

            report[pattern] = {
                "problems_attempted": stats["total"],
                "memory_solve_rate": f"{memory_rate:.0f}%",
                "readiness": readiness
            }

        return report

    def average_solve_time_by_pattern(self) -> dict:
        """Track whether your solve time is improving — it should drop week over week."""
        pattern_times = {}

        for entry in self.entries:
            tag = entry.pattern_tag
            if tag not in pattern_times:
                pattern_times[tag] = []
            pattern_times[tag].append(entry.time_to_solve_minutes)

        return {
            pattern: f"{sum(times) / len(times):.1f} min avg over {len(times)} problem(s)"
            for pattern, times in pattern_times.items()
        }


# ─────────────────────────────────────────────
# DEMO: Simulate one week of practice
# ─────────────────────────────────────────────
if __name__ == "__main__":
    log = PracticeLog()

    log.add_entry(PracticeEntry(
        problem_name="Valid Palindrome",
        platform="LeetCode",
        pattern_tag="two_pointers",
        difficulty="easy",
        date_attempted=date(2024, 1, 1),
        solved_on_first_try=True,
        solved_from_memory_next_day=True,
        time_to_solve_minutes=18,
        notes="Clicked immediately. Pointer logic straightforward on sorted-equivalent string."
    ))

    log.add_entry(PracticeEntry(
        problem_name="Two Sum II",
        platform="LeetCode",
        pattern_tag="two_pointers",
        difficulty="easy",
        date_attempted=date(2024, 1, 2),
        solved_on_first_try=True,
        solved_from_memory_next_day=True,
        time_to_solve_minutes=12,
        notes="Faster than yesterday. Pattern is sticking."
    ))

    log.add_entry(PracticeEntry(
        problem_name="Container With Most Water",
        platform="LeetCode",
        pattern_tag="two_pointers",
        difficulty="medium",
        date_attempted=date(2024, 1, 3),
        solved_on_first_try=False,
        solved_from_memory_next_day=True,
        time_to_solve_minutes=35,
        notes="Didn't see the greedy argument at first. Needed hint about always moving the shorter line."
    ))

    log.add_entry(PracticeEntry(
        problem_name="Max Average Subarray I",
        platform="LeetCode",
        pattern_tag="sliding_window",
        difficulty="easy",
        date_attempted=date(2024, 1, 8),
        solved_on_first_try=True,
        solved_from_memory_next_day=False,  # Forgot the exact window-slide arithmetic
        time_to_solve_minutes=22,
        notes="Fixed window is easy conceptually but I blanked on the index math next day."
    ))

    print("=== PATTERN MASTERY REPORT ===")
    for pattern, stats in log.pattern_mastery_report().items():
        print(f"\nPattern: {pattern.upper()}")
        for key, value in stats.items():
            print(f"  {key}: {value}")

    print("\n=== AVERAGE SOLVE TIME BY PATTERN ===")
    for pattern, avg in log.average_solve_time_by_pattern().items():
        print(f"  {pattern}: {avg}")

# io.thecodeforge — Interview tutorial

# Combining patterns: Frequency map + Sliding Window
# Problem: Find all start indices of anagrams of string p in string s.
# Use a frequency map to represent p's character counts.
# Use a sliding window of length len(p) to slide through s, maintain a running frequency map.
# Compare maps at each position — if equal, we found an anagram.

from collections import Counter
from typing import List

def find_anagrams(s: str, p: str) -> List[int]:
    """
    Returns the start indices of all anagrams of p in s.
    Pattern combination: frequency map (Counter) + fixed-size sliding window.
    """
    if len(p) > len(s):
        return []

    p_count = Counter(p)
    window_count = Counter()
    result = []
    window_size = len(p)

    # Build initial window
    for i in range(window_size):
        window_count[s[i]] += 1

    if window_count == p_count:
        result.append(0)

    # Slide the window
    for right in range(window_size, len(s)):
        # Add new character on the right
        window_count[s[right]] += 1
        # Remove character that fell off the left
        left_char = s[right - window_size]
        window_count[left_char] -= 1
        if window_count[left_char] == 0:
            del window_count[left_char]

        # Compare counts
        if window_count == p_count:
            result.append(right - window_size + 1)

    return result


# Test
print(find_anagrams("cbaebabacd", "abc"))  # Expected: [0, 6]
print(find_anagrams("abab", "ab"))         # Expected: [0, 1, 2]

// io.thecodeforge — interview tutorial

def rotate_left(arr, rotations):
    n = len(arr)
    if n == 0:
        return arr
    rotations = rotations % n  # production trap: forgot this, watched prod burn at 3am
    
    def reverse(start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    
    reverse(0, rotations - 1)
    reverse(rotations, n - 1)
    reverse(0, n - 1)
    return arr

prices = [10, 20, 30, 40, 50]
print(rotate_left(prices, 2))

// io.thecodeforge — interview tutorial

def is_anagram(a, b):
    if len(a) != len(b):
        return False
    # production warning: case sensitivity kills
    a_clean = a.lower()
    b_clean = b.lower()
    
    freq = {}
    for char in a_clean:
        freq[char] = freq.get(char, 0) + 1
    
    for char in b_clean:
        if char not in freq or freq[char] == 0:
            return False
        freq[char] -= 1
    return True

print(is_anagram("Listen", "Silent"))
print(is_anagram("Hello", "World"))