面试算法题总结

NeetCode.RoadMap

负载均衡算法

更多加分点： 加权等

package main
import (
	"math/rand"
    "time"
    "fmt"
)
type LoadBalancer struct {
    client []*Client
    size int32
}
func NewLB(size int32) *LoadBalalcer {
    lb := &LoadBalancer{client: make([]*Client, size), size: size}
    lb.client = append(lb.client, &Client{})
    return lb
}

func (l *LoadBalancer) getClient() *Client {
    rand.Seed(time.Now().Unix())
    x := rand.Int31n(100)
    return m.client[x & m.size]
}

type Client struct {
    Name string
}

func (m *Client) Do {
    fmt.Println("Do")
}

func main() {
    lb := NewLB(4)
    lb.getClient().Do()
}

利用反射调用函数

实例：

package main
import (
    "reflect"
    "fmt"
)
type Car struct {}

func (c *Car) Drive {
    fmt.Println("Driving")
}

func main() {
    car := Car{}
    val := reflect.ValueOf(&car)
    f := value.MethodByName("Drive")
    f.Call([]reflect.Value{})  // Drive
}

给定三个函数 cat dog fish ，每个函数启动一个 goroutine ，要求按照顺序打印100次

package main

import (
	"fmt"
	"sync"
)


func PrintCat(fishCH,catCH chan bool){
	defer waitgroup.Done()
	defer close(catCH)
	for i:= 0; i <100;i++{
		<-fishCH
		fmt.Println("cat ...")
		catCH <- true
	}
}

func PrintDog(catCH,dogCH chan bool){
	defer waitgroup.Done()
	defer close(dogCH)
	for i:= 0; i <100;i++{
		<-catCH
		fmt.Println("dog ...")
		dogCH<-true
	}
}

func PrintFish(dogCH,fishCH chan bool){
	defer waitgroup.Done()
	defer close(fishCH)
	for i:= 0; i <100;i++{
		<-dogCH
		fmt.Println("fish ...")
		fishCH<-true
	}
}


var waitgroup sync.WaitGroup

func main() {

	catCH := make(chan bool,1)
	dogCH := make(chan bool,1)
	fishCH := make(chan bool,1)
	fishCH <- true


	go PrintFish(dogCH,fishCH)
	go PrintDog(catCH,dogCH)
	go PrintCat(fishCH,catCH)

	waitgroup.Add(3)
	waitgroup.Wait()

}

抽奖问题

// 给定如下结构
// map中，key代表名称，value代表成交单数
var users map[string]int64 = map[string]int64{
  "a": 10,
  "b": 6,
  "c": 3,
  "d": 12,
  "f": 1,
}

1. 随机抽奖

从 map 中随机选取用户中奖
思路：将用户理解为一个个格子，从中选取一个格子中奖

package main
import (
  "fmt"
  "math/rand"
  "time"
)

func GetAwardUserName(users map[string]int64) (name string) {
  sizeOfUsers := len(users)
  award_index := rand.Intn(sizeOfUsers)

  var index int
  for u_name, _ := range users {
    if index == award_index {
      name = u_name
      return
    }
    index += 1
  }
  return
}

func main() {
  var users map[string]int64 = map[string]int64{
    "a": 10,
    "b": 6,
    "c": 3,
    "d": 12,
    "e": 20,
    "f": 1,
  }

  rand.Seed(time.Now().Unix())
  // 抽奖1次
  name := GetAwardUserName(users)
  fmt.Printf("user: %s jack point", name)
  // 抽奖1000次
  award_stat := make(map[string]int64)
  for i := 0; i < 1000; i += 1 {
    name := GetAwardUserName(users)
    if count, ok := award_stat[name]; ok {
      award_stat[name] = count + 1
    } else {
      award_stat[name] = 1
    }
  }

  for name, count := range award_stat {
    fmt.Printf("user: %s, award count: %d\n", name, count)
  }

  return
}

上方抽奖代码复杂度为 O(n) ，可以结合二分查找优化为 O(logN)

func GetAwardGenerator(users map[string]int64) (generator func() string) {
  var sum_num int64
  name_arr := make([]string, len(users))
  offset_arr := make([]int64, len(users))
  var index int
  for u_name, num := range users {
    name_arr[index] = u_name
    offset_arr[index] = sum_num
    sum_num += num
    index += 1
  }

  generator = func() string {
    award_num := rand.Int63n(sum_num)
    return name_arr[binary_search(offset_arr, award_num)]
  }
  return
}

func binary_search(nums []int64, target int64) int {
  start, end := 0, len(nums)-1
  for start <= end {
    mid := start + (end-start)/2
    if nums[mid] > target {
      end = mid - 1
    } else if nums[mid] < target {
      if mid+1 == len(nums) { // 最后一名中奖
        return mid
      }
      if nums[mid+1] > target {
        return mid
      }
      start = mid + 1
    } else {
      return mid
    }
  }

  return -1
}

2. 加权抽奖

// 这个也是我们常规概率抽奖的实现方案
// 前置逻辑需要做好并发相关的处理，包括异常状态处理
func GetAwardGenerator(users map[string]int64) string {
  var sum_num int64
  name_arr := make([]string, len(users))
  for u_name, num := range users {
    sum_num += num
    name_arr = append(name_arr, u_name)
  }

  var generator func() string
  generator = func() string {
    award_num := rand.Int63n(sum_num)

    var offset_num int64
    for _, u_name := range name_arr {
      offset_num += users[u_name]
      if award_num < offset_num {
        return u_name
      }
    }
    // 缺省返回，正常情况下，不会运行到此处
    return name_arr[0]
  }
  return
}

实现一个消息队列

核心：切片 + 锁

[字符串相加](https://leetcode-cn.com/problems/add-s

trings/)

func addStrings(num1 string, num2 string) string {
	add := 0
	ans := ""
	for i, j := len(num1) - 1, len(num2) - 1; i >= 0 || j >= 0 || add != 0; i, j = i - 1, j - 1 {
		var x, y int
		if i >= 0 {
			x = int(num1[i] - '0')
		}
		if j >= 0 {
			y = int(num2[j] - '0')
		}
		result := x + y + add
		ans = strconv.Itoa(result%10) + ans
		add = result / 10
	}
	return ans
}

求根号2的值

// 二分查找法求近似值
func mySqrt(x int) float64 {  
    l, r := float64(0), float64(x)  
    for r-l > 1e-7 {  
        mid := l + (r - l) / 2  
		if mid * mid <= float64(x) {  
            l = mid  
		} else {  
            r = mid  
		}  
    }  
    return r  
}

// 牛顿迭代
func mySqrt(x int) float64 {  
    if x == 0 {  
        return 0  
	}  
    C, x0 := float64(x), float64(x)  
    for {  
        xi := 0.5 * (x0 + C/x0)  
        if math.Abs(x0 - xi) < 1e-7 {  
            break  
		}  
        x0 = xi  
	}  
    return x0  
}