数据挖掘2022年2023届秋招kanaries雾角科技算法岗笔试题(代码片段)

BetterBench BetterBench     2022-12-04     253

关键词:

Kanaries雾角科技算法岗位笔试

笔试时间:2022年10月13号

时长:120分钟

几乎是刷过的算法题,最后一题是难度题,其他都是中等题目。

1、 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色

(1)题目

总共有 n 个颜色片段排成一列,每个颜色片段要么是 ‘A’ 要么是 ‘B’ 。给你一个长度为 n 的字符串 colors ,其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏,他们 轮流 从这个字符串中删除颜色。Alice 先手 。

如果一个颜色片段为 ‘A’ 且 相邻两个颜色 都是颜色 ‘A’ ,那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 ‘B’ 片段。
如果一个颜色片段为 ‘B’ 且 相邻两个颜色 都是颜色 ‘B’ ,那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 ‘A’ 片段。
Alice 和 Bob 不能 从字符串两端删除颜色片段。
如果其中一人无法继续操作,则该玩家 输 掉游戏且另一玩家 获胜 。
假设 Alice 和 Bob 都采用最优策略,如果 Alice 获胜,请返回 true,否则 Bob 获胜,返回 false。

示例 1:

输入:colors = “AAABABB”
输出:true
解释:
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 ‘A’ ,这也是唯一一个相邻颜色片段都是 ‘A’ 的 ‘A’ 。

现在轮到 Bob 操作。
Bob 无法执行任何操作,因为没有相邻位置都是 ‘B’ 的颜色片段 ‘B’ 。
因此,Alice 获胜,返回 true 。
示例 2:

输入:colors = “AA”
输出:false
解释:
Alice 先操作。
只有 2 个 ‘A’ 且它们都在字符串的两端,所以她无法执行任何操作。
因此,Bob 获胜,返回 false 。
示例 3:

输入:colors = “ABBBBBBBAAA”
输出:false
解释:
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 ‘A’ 。

ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择,他可以选择任何一个 ‘B’ 删除。

然后轮到 Alice 操作,她无法删除任何片段。
所以 Bob 获胜,返回 false 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

计算满足删除条件的字符,每次删除都计数。当Alice 的操作数大于Bob 的操作数时,Alice 获胜;否则,Bob 获胜。

(3)Python实现

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        count = 0
        for i in range(1,len(colors)-1):
            if colors[i] ==colors[i-1] and colors[i]==colors[i+1]:
                if colors[i]=='A':
                    count+=1
                else:
                    count-=1
        return count>0

2、LeetCode 478. 在圆内随机生成点

(1)题目

给定圆的半径和圆心的位置,实现函数 randPoint ,在圆中产生均匀随机点。

实现 Solution 类:

Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

示例 1:

输入:
[“Solution”,“randPoint”,“randPoint”,“randPoint”]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493,-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]

提示:

0 < radius <= 108
-107 <= x_center, y_center <= 107
randPoint 最多被调用 3 * 104 次

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/generate-random-point-in-a-circle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

极坐标变换的方法,随机一个半径长度ρ,[0,2π]内再随机一个角度θ,就可以得到一个圆内的点:x=ρ×cos(θ),y=ρ×sin(θ)。需要注意的是这个半径ρ需要从[0,r×r]内随机抽样然后再开方,不能直接从[0,r]上随机采样得到。因为圆的面积是π×r×r,正比于r的平方,必须从[0,r×r]内随机才能保证是整个圆面中的均匀分布。

(3)Python实现

import random
import math
class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius  = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> List[float]:
        
        theta = random.random()*2*math.pi
        r = math.sqrt(random.random() * self.radius**2)
        x = self.x_center + r*math.cos(theta)
        y = self.y_center + r*math.sin(theta)
        return x,y

3、LeetCode 73. 矩阵置零

(1)题目

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1:

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]
示例 2:

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

先确定元素0 的位置,再根据位置,将每行和每列设置为0。

(3)Python实现

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        temp = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==0:
                    temp.append((i,j))
        for row,col in temp:
            matrix[row]=[0]*len(matrix[0])
            for i in range(len(matrix)):
                matrix[i][col] =0

4、 牛客. 数组中未出现的最小正整数

(1)题目

给定一个无序数组arr,找到数组中未出现的最小正整数

例如arr = [-1, 2, 3, 4]。返回1

​ arr = [1, 2, 3, 4]。返回5

[要求]

时间复杂度为O(n),空间复杂度为O(1)

链接:https://www.nowcoder.com/questionTerminal/030cabe03d94484c819e87c2e38c41bd?f=discussion
来源:牛客网

输入描述:

第一行为一个整数N。表示数组长度。

接下来一行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

4

-1 2 3 4

输出

1

示例2

输入

4

1 2 3 4

输出

5

(2)解析

合法的元素序列是,索引和nums元素对应,即索引0对应1,索引1对应2,依次递增。

边排序,边判断不合法元素的位置。

不合法的情况有三种:

  • 当前值小于索引
  • 当前值大于索引
  • 当前值与前面的元素重复

(3)Python实现

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        while (i<n):
            # 合法的情况:nums中元素与索引对应。索引0对应1,索引1对应2,依次递增
            if nums[i]==i+1:
                i+=1
            '''
            出现不合法情况
            1.nums的当前值小于索引
            2.nums的当前值大于索引
            3.nums当前值出现了重复
            '''
            elif (nums[i]<=i or nums[i]>n or nums[nums[i]-1]==nums[i]):
                n -=1
                nums[i] = nums[n]
            # 表示当前值是一个合法的值,但是没有在理想的位置上,需要进行交换处理
            else:
                temp = nums[i]
                nums[i] = nums[nums[i]-1]
                nums[temp-1] = temp
        return i+1

5、LeetCode 剑指 Offer 32 - III. 从上到下打印二叉树 III

(1)题目

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/
9 20
/
15 7

返回其层次遍历结果:

[ [3], [20,9], [15,7]]

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

思路和【剑指 Offer 32 - II. 从上到下打印二叉树 II】一样,区别在此基础上,只改进一点,奇数层列表是正序,偶数层列表是反序。

(3)Python实现

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res,queue = [],[root,]  
        count = 1 
        while queue:
            level_list = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level_list.append(node.val)
                if node.left:queue.append(node.left)
                if node.right:queue.append(node.right)
            if count%2==0:
                res.append(level_list[::-1])
            else:
                res.append(level_list)
            count+=1
        return res

6、LeetCode50. Pow(x, n)

(1)题目

实现 Pow(x, n), 即计算 x 的整数 n 次幂函数(即, x n x^n xn )。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:

输入:x = 2.10000, n = 3
输出:9.26100
示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

递归分治法,如果n是1,则返回1,如果是负数,就是求正的分之一,如果是正数,分为两种情况,是奇数,拆出一个x出来,剩余的n-1次幂是偶数继续递归。是偶数,分为两部分乘积,对n对半去递归求解。例如求 x 4 x^4 x4拆分为 x 2 × x 2 x^2 × x^2 x2×x2

(3)Python实现

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n==0:
            return 1
        if n<0:
            return 1 / self.myPow(x,-n)
        if n%2:
            return x*self.myPow(x,n-1)
        return self.myPow(x*x,n/2)

7、leetcode1467. 两个盒子中球的颜色数相同的概率

(1)题目

桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k的整数数组 balls`,其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。

注意:这两个盒子是不同的。例如,两个球颜色分别为 a 和 b盒子分别为 [] 和 (),那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的(请认真阅读示例 1 的解释部分)。

请计算「两个盒子中球的颜色数相同」的情况的概率。

示例 1:

输入:balls = [1,1]
输出:1.00000
解释:球平均分配的方式只有两种:
- 颜色为 1 的球放入第一个盒子,颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子,颜色为 1 的球放入第二个盒子
这两种分配,两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。

示例 2:

输入:balls = [2,1,1]
输出:0.66667
解释:球的列表为 [1, 1, 2, 3]
随机打乱,得到 12 种等概率的不同打乱方案,每种方案概率为 1/12 :
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后,我们将前两个球放入第一个盒子,后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667

示例 3:

输入:balls = [1,2,1,2]
输出:0.60000
解释:球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的,但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。

示例 4:

输入:balls = [3,2,1]
输出:0.30000
解释:球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的,但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。
概率 = 18 / 60 = 0.3 。

示例 5:

输入:balls = [6,6,6,6,6,6]
输出:0.90327

提示:

  • 1 <= balls.length <= 8
  • 1 <= balls[i] <= 6
  • sum(balls) 是偶数
  • 答案与真实值误差在 10^-5 以内,则被视为正确答案

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(2)解析

参考知乎文章讲解:https://zhuanlan.zhihu.com/p/145606485

(3)Python实现

def get_num(self,balls):
        summ = math.factorial(sum(balls))
        temp = 1
        for ball in balls:
            temp *= math.factorial(ball) 
        return summ/temp
    def dfs(self,c,balls,left_arr,right_arr,left_sum,right_sum,n):
        if left_sum > n or right_sum > n:
            return 0
        if c == len(balls):
            left_color = 0
            right_color = 0
            for x in left_arr:
                if x:
                    left_color += 1
            for x in right_arr:
                if x:
                    right_color += 1
            if left_color == right_color:
                return self.get_num(left_arr) * self.get_num(right_arr)
            else:
                return 0

        res = 0
        for i in range(balls[c]+1):
            left_arr[c] = i
            right_arr[c] = balls[c] - i
            res += self.dfs(c+1,balls,left_arr,right_arr,left_sum+left_arr[c],right_sum+right_arr[c],n)
        return res

    def getProbability(self, balls: List[int]) -> float:
        total = self.get_num(balls) 
        print(total)
        n = sum(balls) 
        left_arr = [0 for _ in range(len(balls))]
        right_arr = [0 for _ in range(len(balls))]
        return self.dfs(0,balls,left_arr,right_arr,0,0,n)/total

es = 0
for i in range(balls[c]+1):
left_arr[c] = i
right_arr[c] = balls[c] - i
res += self.dfs(c+1,balls,left_arr,right_arr,left_sum+left_arr[c],right_sum+right_arr[c],n)
return res

def getProbability(self, balls: List[int]) -> float:
    total = self.get_num(balls) 
    print(total)
    n = sum(balls) 
    left_arr = [0 for _ in range(len(balls))]
    right_arr = [0 for _ in range(len(balls))]
    return self.dfs(0,balls,left_arr,right_arr,0,0,n)/total

数据挖掘2022年2023届秋招知能科技公司机器学习算法工程师笔试题(代码片段)

岗位:高级机器学习算法工程师笔试时间:2022-9-281简答题1、神经网络中防止过拟合的方法(1)降低模型复杂度(2)正则化,正则化正是通过在损失函数上添加额外的参数稀疏性惩罚项(正则项... 查看详情

数据挖掘2022年2023届秋招爱玩特智能量化研究员岗笔试题(代码片段)

公司:爱玩特智能岗位:量化研究员时间:2022年10月17号,线下开卷笔试1题目笔试说明1、编程要求语言:Python结果汇总至Excel,表一至表五代码分块汇总至一个python文件、要求注释完整2、数据说明数据库... 查看详情

数据挖掘2022年2023届秋招宏瓴科技公司机器学习算法工程师笔试题

1简介公司:宏瓴科技有限公司岗位:机器学习算法工程师笔试时间:2022-9-28以下答案全是自己总结,这些点对于我来说太难了,我对自己总结的答案也没有信心,题目中说要用公式去表示,我都不知道... 查看详情

我的cv算法岗上岸之路(2023届秋招)

 Datawhale干货 作者:记忆的迷谷@知乎,整理:极市平台来源丨https://zhuanlan.zhihu.com/p/576729164导读 在卷成麻花的2022年,一个没有上述背景、没有名校撑腰的普通科班小硕能入坑中大厂的CV算法岗吗?作者亲... 查看详情

2023届秋招提前批信息汇总(持续更新ing)

 实时更新的文档:2023届秋招提前批信息汇总(持续更新ing)(qq.com)公司投递链接面试网站工作地点截止时间互联网及私企(软件)网易游戏网易游戏(互娱)校园招聘官网https://www.mianshi.online/广州深圳、杭州、... 查看详情

2023届秋招回顾,寒气逼人。。。

作者:OliQ来源:https://www.cnblogs.com/yuanchuziwen/p/16770895.html一、自我介绍就叫我OliQ吧(《白鲸》式的开局)!我来自杭州的一所双非一本学校,是一名普通的本科生,专业【软件工程】。1.1初学编程事实上,我... 查看详情

米哈游2023届秋招开启校招唯一专属内推码eytuc

爆个猛料很猛的米哈游7月又有新岗位啦!!!!不打卡弹性工作。抓紧金7银8面试机会,年中岗位多、急、需求量大,offer流程快。现招:技术(算法、前端、后台、大数据、安卓ios测试,C++,游戏开发,客户端开发,Unity开发,引... 查看详情

偷偷盘点一下23届秋招薪资(代码片段)

...者丨库森来源丨程序员库森(ID:Coolsen88)2023届秋招形式比起前几年严峻了很多,大厂缩招、小厂停招,寒气逼人。我根据牛客网、offershow小程序、脉脉、qq微信群等渠道收集汇总了一波2023届秋招技术岗薪资... 查看详情

一个高考失利人的2022届秋招复盘,目前收到腾讯字节百度阿里京东的offer

文章目录一个高考失利人的2022届秋招复盘,目前收到腾讯字节百度阿里京东的offer前言本人情况和秋招结果战绩大学时间线安排大一大二举一些面试例子数据结构和算法如何考?如何学习这部分知识网络原理如何考?如何学习这部分... 查看详情

数据挖掘恒生金融有限公司2023届秋招数据etl工程师笔试题解析(代码片段)

公司:恒生科技笔试时间:2022年9月24号岗位:数据ETL工程师时间:120分钟1不定项选择题1、SQL修改表结构的关键词是A.alterB.createC.descD.rename答案:A2、正确的是A.一个表中,主键可以唯标识一行记录B.一个事... 查看详情

2023届秋招技术岗内推专场来啦~内推名额等待优秀的你

2023届秋季校园招聘开始啦!作为一个过来人,深知找工作的无奈和奔走的劳累。我是本次校招推星官,小伙伴们赶快准备简历,然后找我内推吧。23届毕业找工作的同学可以注意一下,和博主一起共事的内推... 查看详情

2023届秋招技术岗内推专场来啦~内推名额等待优秀的你

2023届秋季校园招聘开始啦!作为一个过来人,深知找工作的无奈和奔走的劳累。我是本次校招推星官,小伙伴们赶快准备简历,然后找我内推吧。23届毕业找工作的同学可以注意一下,和博主一起共事的内推... 查看详情

2023秋招——快手数据研发一二面面经(代码片段)

🌼今天来总结一下快手数据研发的一、二面,在面试中进步,在总结中成长!对往期内容感兴趣的小伙伴可以参考下面👇:链接:2022暑期实习字节跳动数据研发面试经历-基础数仓.链接:2022百度大数据开发... 查看详情

2023秋招——快手数据研发一二面面经(代码片段)

🌼今天来总结一下快手数据研发的一、二面,在面试中进步,在总结中成长!对往期内容感兴趣的小伙伴可以参考下面👇:链接:2022暑期实习字节跳动数据研发面试经历-基础数仓.链接:2022百度大数据开发... 查看详情

如何看待2022届秋招嵌入式开发岗位薪资大涨?

大家好,我是无际。最近在网上看到了关于2022届嵌入式开发岗位薪资大涨的帖子,比如说像海康、大华、汇顶、联发科等公司的招聘。普遍年薪达到25W,甚至有40W的,直逼互联网。虽然不知道是不是网友吹牛逼的... 查看详情

2023届秋招,我重新认清了自己

仅记录个人经历,充满主观感受,甚至纯属虚构,仅供参考,杠就是你对本想毕业再写,但是考虑到等毕业了,24秋招的提前批就快开始了,大概就来不及了,正好现在有点时间,陆陆续续的写... 查看详情

新出炉|2022秋招洞察&2023春招趋势解读

...据支持。(完整报告可在公众号"Hollis"后台回复"秋招"即可获得)本文档中包含了行业洞察、职位洞察、城市、薪资、学历以及2023春招趋势。PS:因为每个读者的具体情况不同,所 查看详情

2023秋招——大数据研发工程师提前批一面(代码片段)

🌻最近在准备秋招,又到了面试的环节,我将会对秋招面试的问题进行一系列的复盘,在面试中一点一点成长。对往期内容感兴趣的小伙伴可以参考下面👇:链接:2022暑期实习字节跳动数据研发面试经历-... 查看详情