LRU 算法实现

题目要求

golang 实现lru算法，要求在 O(1) 时间内完成get和put请求

最长连续序列实现

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

js示例
输入：
nums = [100,4,200,1,3,2]
输出：
4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：
nums = [0,3,7,2,5,8,4,6,0,1]
输出：
9
示例 3：
输入：
nums = [1,0,1,2]
输出：
3

组件

• ChatModel‌：与大模型交互的核心组件，支持生成式对话（Generate）和流式输出（Stream），部分实现还支持工具调用（ToolCallingChatModel）
• Tool‌：扩展大模型能力的工具，可调用外部 API、数据库、文件系统等，支持同步（Invoke）和流式（Stream）两种范式
• Retriever‌：从向量库或文档库中检索与查询相关的文档片段，常用于 RAG 场景。
• Embedding‌：将文本转换为向量表示，用于语义搜索和向量索引。
• Indexer‌：负责存储和索引文档向量，支持 Redis、Milvus 等向量数据库。 ‌- Document Loader‌：加载并解析多种格式的原始文档（如 PDF、Markdown、TXT 等），统一为schema.Document 结构。
• Document Transformer‌：对文档进行切分、过滤或格式转换，如按标题、递归或语义切分。
• ChatTemplate‌：管理提示词模板，支持 FString、GoTemplate、Jinja2 等语法，便于动态构建系统提示

从头开始，每K个一组，翻转链表

js
func main() {
    head := buildList([]int{1, 2, 3, 4, 5, 6})

    k := 3

    fmt.Println("原链表：")
    printList(head)

    newHead := reverseKGroup(head, k)

    fmt.Println("每K个翻转后：")
    printList(newHead)
}

golang 实现链表反转的升级版

背景

js
func main() {
    // 示例：
    // 1→2→3→4→5→6→7→8
    head := buildList([]int{1, 2, 3, 4, 5, 6, 7, 8})

    k := 3

    fmt.Println("原链表：")
    printList(head)

    newHead := reverseKFromTail(head, k)

    fmt.Println("处理后：")
    printList(newHead)
}

python 回收机制

• 引用计数
  • 每个对象维护一个 ob_refcnt 字段。每当对象被引用时计数加 1，引用失效时减 1。
• 标记清楚
  • 寻找根对象：从全局变量、调用栈等根集合出发。
  • 标记：遍历所有可达对象并打上标记。
  • 清除：遍历内存中所有对象，将没有标记（不可达）的对象销毁。
• 分代回收
  • 将内存对象分为三代（0代、1代、2代）。
  • 0代：新创建的对象。
  • 1代：在一次 GC 中幸存的对象。
  • 2代：多次 GC 后依然存活的常驻对象。
  • 策略：存活时间越久的对象越不可能是垃圾。因此，0代回收最频繁，2代回收频率最低。当某一代的对象数量达到预设阈值（Threshold）时，触发该代及更年轻代的回收。

golang实现快速排序

• 什么是快速排序
  • 从数组中选中一个基准值，递归遍历数组的值和基准值作对比，分为比基准值大的，比基准值小的数组后合并

面试实现版本

js
package main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        // 获取分区后的基准索引
        pivotIndex := partition(arr, left, right)

        // 递归排序左半部分
        quickSort(arr, left, pivotIndex-1)
        // 递归排序右半部分
        quickSort(arr, pivotIndex+1, right)
    }
}

func partition(arr []int, left, right int) int {
    // 选择最右侧元素作为基准
    pivot := arr[right]
    i := left - 1 // i 指向小于基准的区域边界

    for j := left; j < right; j++ {
        // 如果当前元素小于或等于基准
        if arr[j] <= pivot {
            i++
            // 交换元素
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // 将基准值交换到中间正确的位置
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1
}

func main() {
    data := []int{34, 7, 23, 32, 5, 62}
    fmt.Println("排序前:", data)

    quickSort(data, 0, len(data)-1)

    fmt.Println("排序后:", data)
}

原地排序版本

js
package main

import "fmt"

func quickSort(nums []int, left, right int) {
    if left >= right {
            return
    }

    pivot := nums[left] // 选最左作为基准
    i, j := left, right

    for i < j {
        // 从右往左找小于 pivot 的
        for i < j && nums[j] >= pivot {
                j--
        }
        // 从左往右找大于 pivot 的
        for i < j && nums[i] <= pivot {
                i++
        }
        nums[i], nums[j] = nums[j], nums[i]
    }

    // 把 pivot 放到正确位置
    nums[left], nums[i] = nums[i], nums[left]

    quickSort(nums, left, i-1)
    quickSort(nums, i+1, right)
}

func main() {
    arr := []int{5, 2, 3, 1, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

最大连续数组和

题目描述

• 一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和及最大子数组，case： nums = [-2,1,-3,4,-1,2,1,-5,4]

解题思路

• 默认当前最大值、以及当前的总和，为数组的第一个元素
• 遍历数组
  • 如果当前和小于0, 则用当前值进行覆盖，否则 += 当前值
  • 当前和大于当前最大和，则更新最大和

golang实现

js
package main

import (
    "fmt"
)

// maxSubArray 求最大连续子数组和
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
            return 0
    }

    currentSum := nums[0]
    maxSum := nums[0]

    for i := 1; i < len(nums); i++ {
        // 当前和要么接着加，要么从当前元素重新开始
        if currentSum < 0 {
                currentSum = nums[i]
        } else {
                currentSum += nums[i]
        }

        // 更新最大值
        if currentSum > maxSum {
                maxSum = currentSum
        }
    }

    return maxSum
}

func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    result := maxSubArray(nums)
    fmt.Println("最大连续子数组和为:", result)
}