芒果zzZ

Java Go

面试智力题

发表于 更新于 分类于
本文字数： 7.3k 阅读时长 ≈ 7 分钟

智力题面试

面试智力题

一面

题目

请用尽可能少的代码实现一个函数，用于计算用户一个月共计交费多少港元。（代码请写的尽量清晰简洁，我们希望能够看到你的编码风格和习惯） 用户在的平台上进行交易，需要交平台使用费。平台使用费的梯度收费方案如下： 每月累计订单数 每笔订单（港元） 梯度1：1-5笔 => 30.00 梯度2：6-20笔 => 15.00 梯度3：21-50笔 => 10.00 梯度4：51笔及以上 => 1.00 假设一个用户，一个月交易了6笔订单，则在梯度1交费共计： 30港元*5=150港元，在梯度二交费：15港元，一共交费165港元。

func calcAmount(orderCount int) (amount int) {
	type level struct {
		min int
		max int
		fee int // 单价
	}
	levels := []level{
		{min: 1, max: 5, fee: 30},
		{min: 6, max: 20, fee: 15},
		{min: 21, max: 50, fee: 10},
		{min: 51, max: 0, fee: 1},
	}
	for _, l := range levels {
		if orderCount >= l.min && (orderCount <= l.max || l.max == 0) {
			amount += l.fee * (orderCount - l.min + 1)
			break
		} else {
			amount += l.fee * (l.max - l.min + 1)
		}
	}
	return amount
}

给25匹马，5个赛道，最少几次赛跑能够找到前3

分成5组：A B C D E
先跑5次得到排名
把 A1 B2 C3 D4 E1跑一次得到第一名.假设排名为A1 B2 C3 D4 E1，那么得到第一名A1
在把上面的第二、第三名, 得到第一名的A组的第二名再拉出来跑即可
A2 B2 C3 

所以是7次

给定两个排序数组，判断数组A是否是数组B的子集，只需要给思路，不需要写代码

1. 快慢指针
2. 二分
3. 归并

八股

数据库索引

分布式锁

简单谈谈项目

二面

题目

删除字符串的空格，要求去除首位空格，中间的空格合并成一个

func main() {
	println(trimSpaces("  hello  world!  "))
	println(trimSpaces("  hello world!  "))
}

func trimSpaces(str string) string {
	var slow, fast = 0, len(str) - 1
	for slow < fast && str[slow] == ' ' {
		slow++
	}
	for slow < fast && str[fast] == ' ' {
		fast--
	}
	str = str[slow : fast+1]

	slow, fast = 0, 0
	arr := []byte(str)
	for fast < len(arr) {
		if arr[fast] != ' ' || (fast-1 > 0 && arr[fast-1] != ' ') {
			arr[slow] = arr[fast]
			slow++
			fast++
		} else {
			fast++
		}
	}

	return string(arr[:slow])
}

leetcode 151

func reverseWords(s string) string {
	// 先去除首空格
	var i int
	arr := []byte(s)
	for ; arr[i] == ' '; i++ {
	}
	arr = arr[i:]
	i = len(arr) - 1
	for ; arr[i] == ' '; i-- {
	}

	arr = arr[:i+1]
	// 去除中间的空格
	slow, fast := 0, 0
	for fast < len(arr) {
		if arr[fast] != ' ' || (fast-1 > 0 && arr[fast-1] != ' ') {
			arr[slow] = arr[fast]
			slow++
			fast++
		} else {
			fast++
		}
	}
	arr = arr[:slow]
	// 全部反转
	reverse(arr, 0, len(arr)-1)

	// 再对每一个单词进行反转
	slow, fast = 0, 0

	for fast < len(arr) {
		for fast < len(arr) && arr[fast] != ' ' {
			fast++
		}
		reverse(arr, slow, fast-1)
		slow = fast + 1
		fast = fast + 1
	}

	return string(arr)
}

func reverse(str []byte, left, right int) {
	for left < right {
		str[left], str[right] = str[right], str[left]
		left++
		right--
	}
}

八股&设计题

设计B站弹幕系统

与前端交互部分：用户定位在视频中的某一秒中的时候，拉取视频ID后续N秒的所有弹幕给前端
后端实现部分：
只讨论一个视频ID的情况，设置一个弹幕量级系统，
如果未达到某个量级直接全量下发即可
达到某量级则进入到离线任务调度，进行弹幕优先级判断，在任务未结束的时候可以按照弹幕发布时间给前端，任务结束之后则按照优先级给前端，这样可以保证用户体验以及后端性能

超时时间控制？问的是如何判定一个rpc的超时时间

如果和外部的话会约定一个超时时间，一般在建议时间中+2S

一般分为三个等级
1. 调用基础服务 1S
2. 调用统计等 5S
3. 调用外部服务 10S

三面

题目

并发扣款问题，纯内存操作，解决方案

锁。可以扩展到CAS，读写锁之类的。操作系统原理是信号量
channel队列。排队

数组取最小、大值，要求最小比较次数，和求出期望比较次数，要求最少比较次数

https://blog.csdn.net/shuiziliu1025/article/details/50958190

期望比较次数比较重要： (3N)/2 次

DDD判断ipV4，不能使用库函数

func main() {
	println(strconv2Number("123"), 123)
	println(strconv2Number("0"), 0)
	println(isIpV4(""), false)
	println(isIpV4("aaa"), false)
	println(isIpV4("123.123.123.123.1"), false)
	println(isIpV4("123.123.123"), false)
	println(isIpV4("128.0.0.1"), false)
	println(isIpV4("128.0.0.01"), false)
	println(isIpV4("127.0.0.1"), true)
}

// 思路如下.
// 首先判空，判定格式
// 再判断每一个数字是否为0-255
func isIpV4(ip string) bool {
	if ip == "" {
		return false
	}

	// 判定是否刚刚好有三个.
	// 判定是否为数字和.
	var count int
	for i := 0; i < len(ip); i++ {
		if ip[i] != '.' && (ip[i] < '0' || ip[i] > '9') {
			return false
		}
		if ip[i] == '.' {
			count++
		}
	}
	if count != 3 {
		return false
	}

	// 获取三个数字
	var strArr = make([]string, 0, 3)
	var slow, fast int
	for i := 0; i < len(ip); i++ {
		if ip[i] == '.' {
			strArr = append(strArr, ip[slow:fast])
			slow = fast + 1
		}
		fast++
	}
	strArr = append(strArr, ip[slow:])

	// 判定数字是否合法
	for _, v := range strArr {
		if len(v) > 1 && v[0] == '0' { // 数字0开头不合法
			return false
		}
		number := strconv2Number(v)
		if number < 0 || number > 255 {
			return false
		}
	}

	return true
}

func strconv2Number(str string) int {
	arr := []byte(str)
	var num int
	for i := 0; i < len(arr); i++ {
		num = num*10 + int(arr[i]-'0')
	}
	return num
}

tracing原理(我简历上写了)

其余收集到的

leetcode 116


func fractionToDecimal(numerator int, denominator int) string {
	// 能够整除
	if numerator%denominator == 0 {
		return strconv.Itoa(numerator / denominator)
	}

	// 一定是存在小数位的
	var s []byte
	if numerator < 0 != (denominator < 0) {
		s = append(s, '-')
	}

	// 求整数部分
	numerator = abs(numerator)
	denominator = abs(denominator)
	s = append(s, strconv.Itoa(numerator/denominator)...)
	s = append(s, '.')

	// 求小数部分
	indexMap := map[int]int{}
	remainder := numerator % denominator
	for remainder != 0 && indexMap[remainder] == 0 {
		indexMap[remainder] = len(s)
		remainder *= 10
		s = append(s, '0'+byte(remainder/denominator))
		remainder %= denominator
	}

	// 有循环节
	if remainder > 0 {
		insertIndex := indexMap[remainder]
		s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)
		s = append(s, ')')
	}

	return string(s)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

查找元素比放在它左边的所有元素都大, 比它右边的元素都小

func findElements(arr []int) []int {
	// 定义一个辅助rightMinArr数组，rightMinArr[i]表示在[i,len(arr)-1]的元素中的最小值
	rightMinArr := make([]int, len(arr))
	var min = math.MaxInt
	for i := len(arr) - 1; i >= 0; i-- {
		rightMinArr[i] = min
		if arr[i] < min {
			min = arr[i]
		}
	}

	// 在从左往右走
	var res = make([]int, 0, len(arr))
	var max int = -math.MaxInt
	for i := 0; i < len(arr); i++ {
		min = rightMinArr[i]
		val := arr[i]
		if val > max && val < min {
			res = append(res, val)
		}

		if val > max {
			max = val
		}
	}
	return res
}

两个人先收抛硬币，先抛到正面的赢，问先手抛赢的概率

两种解决方案
1. 举例
总共有四种情况
正反 赢
反反 平
正正 赢
反正 输

2/3

2. 公式计算
假设先手抛赢的概率为 p
则甲赢的概率为 p
乙赢的概率为 0.5p. 0.5为甲先手抛到反面

p+0.5p=1
2/3

100个人回答五道题，有81人答对第一题，91人答对第二题，85人答对第三题，79人答对第四题，74人答对第五题。答对三道题或三道题以上的人算及格，那么在这100人中至少有多少人及格呢？

计算不及格的即可
总共有500道题，总共答错：500-81-91-85-79-74=90
最多有90/3=30人不及格
所以最少有70人及格

持续抛1枚硬币，直到连续出现3次正面为止，求期望的抛硬币的次数是多少

算递推公式即可

假设 e 为抛出正面的期望
则e2可由e1得出

e2 = 
e1-> 0.5 正面 1
e1-> 0.5 反面 1+e2

所以e2 = e1 + (0.5 + 0.5(1+e2))
e2 = 2(e1+1)
同理
e3 = 
e2-> 0.5 正面 1
e2-> 0.5 反面 1+e3

所以e3 = e2 + (0.5 + 0.5(1+e3))
e3 = 2(e2+1)

最后得到e2 = 6
e3 = 14

恰有两个小孩的家庭，若已知一家有一个男孩，则这家小孩都是男孩的概率为？

所有概率为
男男
女女
男女
女男
其中女女不可能。所以为 1/3

一副扑克54张牌,现在分成3份,每份18张,问大小王出现在同一份中的概率是多少?

首先分为 A B C 三堆
其中必有一堆有大王，那么只需要考虑小王是否和大王同一堆即可
17/ (17+18+18) = 17/53
分子为小王和大王在一起的情况，分母为所有分法

有A、B两桶颜料，两桶容量都一样，A桶颜色为红。B桶颜色为蓝色，用一勺子从A桶舀一勺颜料到B桶(过程假设没有损耗，颜料能均匀混合)，然后再从B桶舀一勺颜料到A桶，求问A桶的蓝红颜料比例和B桶的红蓝颜料比例相比，是大于、等于还是小于的关系。

假设桶容量为K，勺为1
第一次从A->B
A 此时的容量为 K-1
B 此时的容量为 k+1

B桶的蓝色比例为
1/K+1

从B桶舀一勺的红色比例为
K/K+1


倒回A桶的红比例为
K/K+1/K = 1/K+1
其中k/k+1是红色的数量。K为总容量

所以比例一样

河两岸各有60w人和40w人，一天内会产生100w通电话，每通电话都是随机打的，问跨河打的有多少?

其中
AA = 0.6*0.6=0.36
AB = 0.6*0.4=0.24
BA = 0.4*0.6=0.24
BB = 0.4*0.4=0.16

故而跨地的有 48W

A、B两人分别在两座岛上。B生病了，A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西，但东西只能放在箱子里。只要箱子没被上锁，C都会偷走箱子里的东西，不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙，A应该如何把东西安全递交给B？

额，A直接把药放在箱子里，再加锁即可，送到B去。
B再把自己的锁加在箱子里。送给A
A解自己的锁后给B就行

现在你手里有两柱形状不均匀的香（这两柱香每分钟燃烧的长度是不确定的），已知他们正常燃尽都需要花费一个小时的时间，求如何确定一段15分钟的时间？

A点一段，B点两端，这样是30min
然后B烧完的时候A点另外一端，这样是15min

1000瓶药水里面只有1瓶是有毒的，毒发时间为24个小时，问需要多少只老鼠才能在24小时后试出那瓶有毒

其实问题是，如何给1000瓶毒药编码，我们可以尝试二进制编码

那么1000瓶毒药的编码总共需要log1000=10位

晚上有四个人需要过桥，但是只有一个手电筒，并且桥一次最多两个人，每个人通过桥所需的时间也不同，A、B、C、D过桥所需的时间分别为1、2、5、10分钟。请问如何过桥所需时间最短？

最佳的解决方案是将两个耗时最多的人一起过桥

第一次过桥：A和B一起过桥，需要2分钟，A再回来，所需1分钟，一共所需3分钟
第二次过桥：C和D一起过桥，需要10分钟，B再回来，所需2分钟，一共需12分钟
第三次过桥：A和B一起过桥，所需2分钟

一共所需17分钟。
请用钱砸死我！！！