// Truy cập phần tử qua index hoặc key
const getItemFromHashMap = (map: Map<string, number>, key: string): number | undefined => {
    return map.get(key); // Luôn 1 bước!
}

// Lấy phần tử theo index - LUÔN nhanh!
function getFirstStudent(students: string[]): string {
    return students[0]; // Boom! Xong ngay!
}

// Binary Search - Chia đôi mỗi bước
function binarySearch(sortedArray: number[], target: number): number {
    let left = 0;
    let right = sortedArray.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (sortedArray[mid] === target) return mid;
        
        // Loại bỏ một nửa mảng
        if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
// 1,000 phần tử = ~10 bước
// 1,000,000 phần tử = ~20 bước (Quá ngon! 🎉)

// Duyệt qua danh sách một lần
function findMax(numbers: number[]): number {
    let max = numbers[0];
    for (const num of numbers) { // Duyệt n phần tử
        if (num > max) max = num;
    }
    return max;
}
// 30 học sinh = 30 lần kiểm tra
// 300 học sinh = 300 lần kiểm tra

// Merge Sort - Chia để trị
function mergeSort(array: number[]): number[] {
    if (array.length <= 1) return array;
    
    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));
    
    return merge(left, right); // Chia log n lần, merge n phần tử
}

function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Bubble Sort hoặc vòng lặp lồng nhau
function bubbleSort(array: number[]): number[] {
    const arr = [...array];
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
// 10 học sinh = ~45 so sánh
// 100 học sinh = ~4,950 so sánh (Ôi không! 😱)

// Nhân ma trận - 3 vòng lặp lồng nhau
function multiplyMatrices(a: number[][], b: number[][]): number[][] {
    const n = a.length;
    const result: number[][] = Array(n).fill(0).map(() => Array(n).fill(0));
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}

// Fibonacci đệ quy naive (không cache)
function fibonacci(n: number): number {
    if (n <= 1) return n;
    
    // Mỗi call tạo ra 2 call khác!
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// n=20: ~20,000 calls
// n=40: ~2 tỷ calls 😱

// Tìm tất cả hoán vị (permutations)
function getPermutations(array: string[]): string[][] {
    if (array.length <= 1) return [array];
    
    const result: string[][] = [];
    for (let i = 0; i < array.length; i++) {
        const current = array[i];
        const remaining = array.filter((_, index) => index !== i);
        const perms = getPermutations(remaining);
        
        for (const perm of perms) {
            result.push([current, ...perm]);
        }
    }
    return result;
}
// 10 items = 3,628,800 permutations!

interface Student {
    id: string;
    name: string;
    homework: boolean;
    score: number;
}

class ClassroomManager {
    private students: Student[] = [];
    private studentMap: Map<string, Student> = new Map();
    
    // O(1) - Kiểm tra sĩ số (chỉ đọc thuộc tính)
    getClassSize(): number {
        return this.students.length; // Instant!
    }
    
    // O(1) với Map - Tìm học sinh theo ID (thông minh!)
    findStudentById(id: string): Student | undefined {
        return this.studentMap.get(id); // Tra cứu trực tiếp!
    }
    
    // O(n) - Điểm danh cả lớp
    checkAttendance(): string[] {
        const presentStudents: string[] = [];
        
        // Phải gọi tên TỪNG bạn
        for (const student of this.students) {
            presentStudents.push([student.name](http://student.name));
        }
        
        return presentStudents;
    }
    
    // O(n) với Array - Tìm học sinh theo ID (cách cũ)
    findStudentByIdSlow(id: string): Student | undefined {
        // Phải lục tung cả danh sách
        return this.students.find(student => [student.id](http://student.id) === id);
    }
    
    // O(n log n) - Sắp xếp học sinh theo điểm
    sortByScore(): Student[] {
        return [...this.students].sort((a, b) => b.score - a.score);
    }
    
    // O(n²) - So sánh từng cặp học sinh
    findStudyPairs(): Array<[Student, Student]> {
        const pairs: Array<[Student, Student]> = [];
        
        for (let i = 0; i < this.students.length; i++) {
            for (let j = i + 1; j < this.students.length; j++) {
                // Logic ghép cặp học tập
                if (Math.abs(this.students[i].score - this.students[j].score) < 10) {
                    pairs.push([this.students[i], this.students[j]]);
                }
            }
        }
        
        return pairs;
    }
}