腾讯后端实习生凉面经止步二面

编程入门行业动态更新时间:2024-10-15 16:24:27

腾讯后端实习生凉面经止步二面

前两天腾讯面试官电话联系我约定了面试时间，没说面试方式，也没发在线面试或者视频会议链接，我以为会是电话面试，那就没法笔试，应该主要考察计算机网络，操作系统，数据库之类的知识，结果面试官打个电话过来给我一个腾讯视频房间号，让我上号。

然后上来就是四道算法，我人傻了。

腾讯的面试非常有特点，题目给你个需求，不做很多限制，面试官希望你尽可能周密地把你能想到的情形都写出来，上限很高。
比如一面第二题字符串转数字，如果你默认输入是自然数，那么你在第一层，作为一个老千层饼，你应该考虑以下几层：

浮点数
科学计数法
非法输入
正负号
数字越界

我在第5层，你呢？
如果你在6+层，欢迎在评论区留言。

答案我慢慢整理，先写个题目大纲，慢慢填坑。
写面经不易，点个赞吧，当是祝我三面好运！

二面面试感受不错，以为过了，实则没有。

一面

大数相乘

所谓大数就是可能超出数值类型范围的数字，一般来说这种数字要用字符串来存储。

字符串转数字

这道题我是用正则表达式做的。

	//无符号整数regUInt,_:=regexp.Compile("^[1-9][0-9]*|0$")//无符号浮点数regUFloat,_:=regexp.Compile("^(([1-9][0-9]*|0)?\\.)?[1-9][0-9]*|0$")//有符号浮点数regFloat,_:=regexp.Compile("^[+\\-]?(([1-9][0-9]*|0)?\\.)?[1-9][0-9]*|0$")//科学计数法regSciNum,_:=regexp.Compile("^(([+\\-]?(([1-9][0-9]*|0)?\\.)?[1-9][0-9]*|0)?[eE])?[+\\-]?(([1-9][0-9]*|0)?\\.)?[1-9][0-9]*|0$")

从上往下是递进的关系，基本数字组成无符号整数，两个无符号整数夹点组成浮点数，符号加浮点数得有符号浮点数，两个有符号浮点数夹e就是科学计数法。

第K大的数字

恰好今天的leetcode每日一题也是这个。
当你只关系最大的值而不关心其他元素的顺序就可以用大顶堆，C++的宝库STL里有现成的，不要为难自己。

#include <iostream>
#include <vector>
#include <queue>using namespace std;class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq;for (auto n:nums){pq.push(n);}for (int i=0;i<k-1;i++){pq.pop();};return pq.top();}
};

但是面试官还问了我底层实现，那就没办法了。我一两个月前其实是看过的，不过这会儿已经忘记了，非常遗憾。事后重新学习了之后，写了一份Golang的大顶堆。
推荐一个讲堆排序的视频，讲得逻辑清晰，简单易懂。
bilibili: 堆排序(heapsort)

package mainimport "fmt"//对于节点	idx=i
//父节点		idx=(i-1)/2
func fatherIndex(idx int) int {return (idx-1)/2
}//左子		idx=2*i+1
func leftSonIndex(idx int) int {return 2*idx+1
}//右子		idx=2*i+2
func rightSonIndex(idx int) int {return 2*idx+2
}//交换元素
func swap(nums *[]int,i,j int)  {(*nums)[i],(*nums)[j]=(*nums)[j],(*nums)[i]
}//堆处理
func heapify(nums *[]int,idx int)  {if idx>=len((*nums)){return}maxIndex:= idxleftSonIdx:=leftSonIndex(idx)rightSonIdx:=rightSonIndex(idx)if leftSonIdx< len((*nums)) && (*nums)[leftSonIdx]>(*nums)[maxIndex]{maxIndex=leftSonIdx}if rightSonIdx< len((*nums)) && (*nums)[rightSonIdx]>(*nums)[maxIndex]{maxIndex=rightSonIdx}if idx!=maxIndex{swap(nums,idx,maxIndex)heapify(nums,maxIndex)}
}//构造堆
//为了省空间原地改的
//但是为了安全性不提倡这样做
func buildHeap(nums *[]int)  {start:= fatherIndex(len(*nums)-1)for i:=start;i>=0;i--{heapify(nums,i)}
}//移除堆顶元素并调整
func popFromHeap(nums *[]int)  {swap(nums,0, len((*nums))-1)*nums=(*nums)[:len((*nums))-1]heapify(nums,0)
}//寻找第K大的值
func findKthLargest(nums []int, k int) int {buildHeap(&nums)for i:=0;i<k-1;i++{popFromHeap(&nums)}return nums[0]
}//测试
func main() {nums:=[]int{1,6,2,8,4,9,5}fmt.Println(findKthLargest(nums,3))
}

两个有序数组里第K大的数字

这道题我在leetcode上是做过的，但是一时找不到了，如果你知道的话可以在评论区留言。

边界在程序里写，这里考虑一般情况，讲一下思想。

对于两个降序数组，要找第K大的值，两数组里第K/2个值，假如较大值所在的组是arr1，那么两个有序数组里第K大的数字不可能在arr1的前K/2个值里。
不断递归，每次排除一半。

具体的细节也非常多，可以参考以下代码。

package mainimport ("errors""fmt"
)//求最小值
func min(i,j int) int {if i<j{return i}else{return j}
}//交换切片里的元素
func swap(nums *[]int,i,j int)  {(*nums)[i],(*nums)[j]=(*nums)[j],(*nums)[i]
}//倒转切片
func reverseSlice(nums *[]int)  {for i:=0;i< len((*nums))/2;i++{swap(nums,i, len((*nums))-1-i)}
}//在两个有序数组中找第K个值
//题目只说有序，没说是增序或者降序
//统一整理为降序再处理
func findKthLargestInTwoSortedArray(arr1,arr2 []int, k int) (int,error) {if len(arr1)+ len(arr2)<k{return 0,errors.New("Kth largest do not exist.")}if k<0{return 0,errors.New("Invalid k.")}if len(arr1)>1{if arr1[0]<arr1[len(arr1)-1]{reverseSlice(&arr1)}}if len(arr2)>1{if arr2[0]<arr2[len(arr2)-1]{reverseSlice(&arr2)}}return findKthLargestInTwoDecendingArray(arr1,arr2,k),nil
}//在两个降序数组中找第K个值
//已保证输入合法
func findKthLargestInTwoDecendingArray(arr1,arr2 []int, k int) int {if len(arr1)< len(arr2){arr1,arr2=arr2,arr1}if len(arr2)==0{return arr1[k-1]}if k==1{if arr1[0]>arr2[0]{return arr1[0]}else{return arr2[0]}}end:=min(k/2-1, len(arr2)-1)if arr1[end]<=arr2[end]{arr1,arr2=arr2,arr1}return findKthLargestInTwoDecendingArray(arr1[end+1:],arr2, k-end-1)
}//测试
func main() {nums1:=[]int{1,2,7,8}nums2:=[]int{}fmt.Println(findKthLargestInTwoSortedArray(nums1,nums2,3))
}