秋招blog--pdd

更新:9月11日。挂

时间:8.25
岗位是后端开发,一共就 4 道算法题,无选择题,120 分钟

1. 题目没读懂。。

2. 给 n 个数,对数进行操作:1. 值减半;2. 将两个值用他们的和替换。问最少多少次操作才能使数组全部元素变为奇数。解题思路:奇 + 偶 = 奇,利用这个性质,只要有一个奇数,我们就可以利用操作 2 在 n 次操作将 n 个偶数变为奇数,答案就是偶数的个数。而果没有奇数,可以通过操作 1 将一个偶数变为奇数,答案为通过操作 1 获得一个奇数所需要的最少步骤 + 偶数个数 - 1。

3. 给定一个数组,和一个数 k。可以将 k 与数组中任意一个小于 k 的元素进行交换。问至少交换多少次,才能够使得数组单调不减。
解题思路:根据题目要求,只有当前持有的 k 大于数组元素时,可以进行交换,也就是说,数组的每个元素之能增加或不变,不可能减少,并且每次交换之后,所持有的 k 的值一定会减小。那么什么时候不可能得到单调不减的数组呢?对于下标 i 位置处的元素和目前所持有的 k,都小于下标 i 之前最大的那个数,说明不管交换与否,下标 i 之前那个最大的数永远比下标 i 处的元素大,也就不可能得到单调不减数组。因此,我们可以倒序遍历数组,对于每个下标 i 的元素 ai 去看是否需要交换。第一种情况是 max(ai, k)  < i 之前最大数,单调递减数组不可能得到,输出 -1。第二种情况是 ai < i 之前最大的数 < k,那么必须进行交换才有可能得到单调递减数组;第三种情况是 i 之前最大的数 < ai < k。那么对于这种情况换不换都可以,如果不换的话,这就意味着 k 不能再与 i 之前的数进行交换,否则就会出现 k > ai,而 k 在 ai 前面,也就无法构成单调不减的数组,也就是说,只有前面的数已经满足题意了,才可以不换,否则就必须交换,只有交换了,才能够在接下来的遍历中拥有交换的权利,使得依然有可能构成单调不减的数组。
为了优化复杂度,可以预处理两个数组,order[i] 和 mx[i]。order[i] 表示下标 i 之前的数组是否单调不减;mx[i] 表示下标 i 之前的最大的数。

4. 给定一个 01 字符串,每次操作可以将字符串分成前后两个部分,然后将前后两个部分翻转再拼接,问最长能够得到的 01 交替字符串长度。
解题思路:观察这样的变化:++--|--++  ->  --++|++--。所谓的切分翻转拼接其实就是将前缀和后缀拼接,答案要么为原始字符串中最长交替字符串长度,要么最左边和最右边翻转过来的拼接得到的 01,条件是首尾字符不同。翻转一次就够了,题目说任意次操作有点误导人。

第一次分享思路,没表达清楚意思的话还请原谅。代码我发在评论区。
全部评论
感觉比暑期实习的pdd简单啊😂
点赞 回复 分享
发布于 08-25 18:40 上海
算法岗也是同款题目
点赞 回复 分享
发布于 08-25 20:49 福建
有大佬发解答,让我学习一下吗
点赞 回复 分享
发布于 08-25 21:16 湖北
点赞 回复 分享
发布于 08-26 01:11 北京

相关推荐

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;一直面试只能让你把会的背的更熟,但想进步还是得回头看看不会的问题。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;今天回顾一下我遇到的一些有价值的问题,结合我自己的一些理解对这些问题尝试解答一下,相信对大家一些知识的理解也会有些帮助(有问题的话欢迎指出)。有用的话感谢大家点赞收藏送花~1.(滴滴提前批二面)Vue开启了keep&nbsp;alive之后会经历哪些生命周期?缓存了什么东西?&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这个点我自己是没有仔细思考过的,当时面试官提问vue的生命周期,我提到了Vue开启keep&nbsp;alive前后生命周期的不同,面试官拓展的问了这个问题。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;背八股的时候都背过,使用&lt;keep-alive&gt;&lt;/keep-alive&gt;组件包裹后可以在切换路由的时候不必销毁组件。并且会多出两个生命周期:activated和deactivated。其中activated在组件渲染的时候执行,deactivated在组件隐藏时执行,因此将这两个生命周期对比mounted和beforeDestory来学习。组件在初次渲染的时候会经历从beforeCreate到mounted这整个阶段,在后续切换的过程中则只会经历activated,随后的beforeUpdate和updated都会经历,隐藏时经历deactivated,最后销毁的时候才会经历beforeDestory和destoryed。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;那么缓存了什么?我们知道在mounted阶段,虚拟DOM转为真实DOM,此时data,method,虚拟DOM都有了;而activated阶段可以不经历前面的钩子,直接挂载DOM,说明keep-alive缓存了虚拟DOM,并且还有所有的数据/方法,也就是缓存了组件实例。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果面试阶段没有见过这个题,可以从每个生命周期干了什么开始联想,其中走到mounted阶段拥有了什么,那么actived阶段就也会有这些。2.(4399一面)http1.1的情况下,一个网页的图片是一张一张加载还是一批一批加载的?&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;首先回顾一下http1.1的特性:&nbsp;&nbsp;&nbsp;&nbsp;●&nbsp;默认长连接,新增响应头Connection:keep-alive字段,保持TCP连接不断开&nbsp;&nbsp;&nbsp;&nbsp;●&nbsp;管道化:基于上面长连接的基础,管道化可以不等第一个请求响应继续发送后面的请求,但响应的顺序还是按照请求的顺序返回&nbsp;&nbsp;&nbsp;&nbsp;●&nbsp;缓存处理:新增catch-control字段&nbsp;&nbsp;&nbsp;&nbsp;●&nbsp;断点传输机制。文件传输时如果遇到网络故障,可以从已经上传/下载好的地方继续请求,不用从头开始&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;其中第二点提到的管道化基本可以解答整个问题,虽然可以发送多个请求,但是返回的顺序还是有序的。因此虽然TCP最大连接数有6~8个,但是返回时还是顺序返回的。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;但是需要注意,如果严谨一点的话还是要考虑一下预加载的情况。例如,当浏览器解析到&nbsp;HTML&nbsp;中的&lt;link&nbsp;rel=&amp;quot;prefetch&amp;quot;&gt;标签时,它可能会提前发起对指定资源(包括图片)的请求,这样在真正需要显示该图片时,可能已经加载完成或者部分加载,从而在一定程度上出现看似一批加载的情况。3.(Minimax一面)eval和new&nbsp;Function的this指向问题:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eval的this指向可以看这篇,很详细:https://ayk.moe/articles/javascript-change-this-in-eval-function/index.html&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;简单的说:eval函数只要是在全局直接运行或者是通过一个函数调用执行、作为对象属性被调用执行这种间接的执行方式,他的指向都是全局作用域。他不能直接被call/bind/apply改变this指向,改变的思路是在eval外面包一层函数,改变外面这个函数的this指向。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new&nbsp;Function:使用&nbsp;new&nbsp;Function&nbsp;创建的函数,它的&nbsp;[[Environment]]&nbsp;指向全局词法环境,而不是函数所在的外部词法环境。因此,我们不能在&nbsp;new&nbsp;Function&nbsp;中直接使用外部变量。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果你对这块不熟悉,来看看这个:https://zh.javascript.info/new-function4.(Minimax二面)React:在if&nbsp;else里书写hooks,为什么不可以?&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;我用我自己比较容易理解的话术来简述一下关键原因,这里面的具体细节还是比较复杂的,有兴趣的牛u可以找找资料了解一下。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;react的fiber树有两颗:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current&nbsp;fiber树:&nbsp;当完成一次渲染之后,会产生一个current树,current会在commit阶段替换成真实的Dom树(可以看成虚拟dom转真实dom)。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;workInProgress&nbsp;fiber树:&nbsp;即将调和渲染的&nbsp;fiber&nbsp;树。再一次新的组件更新过程中,会从current复制一份作为workInProgress,更新完毕后,将当前的workInProgress树赋值给current树。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;workInProgress&nbsp;tree上有一个memoizedState属性,在函数组件中,memoizedState在一次调和渲染过程中,以链表的形式存放hooks信息。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;每一个hook函数执行,都会产生一个hook对象,里面存放了hook的当前信息,然后会以链表的形式串联每个hook对象,并赋值给workInProgress的memoizedState。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;每次组件更新的时候,会先复制一份current&nbsp;tree到workInProgress&nbsp;tree,此时在workInProgress上进行更新。一旦在条件语句中声明hooks,在下一次函数组件更新,hooks链表结构,将会被破坏(某个节点可能被跳过),current树的memoizedState缓存hooks信息,和当前workInProgress不一致,如果涉及到读取state等操作,就会发生异常。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;以上很多是自己的理解,可能讲述不准确但有助于自己理解,欢迎评论区留言指出错误~#面经##前端##滴滴##4399##minimax##24届软开秋招面试经验大赏#
点赞 评论 收藏
分享
4 2 评论
分享
牛客网
牛客企业服务