大厂面试系列(七):数据结构与算法等

镇屌 2020-11-10 11:55:29
面试 大厂 数据结构 数据 系列


数据结构和算法

链表

  • 链表,常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分,这个一般必须得完全无误的情况下写出来;
  • 给出两个链表的头结点,找出这两个链表的交点。
  • java 中数组和链表的区别,各自优势 如何设计拥有高效的随机读取能力的的链表(跳表) 设计跳表,跳表插入开销,跳表随机读取过程
  • 给你一个单向链表,给这个链表做K反转,例如 k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 反转后为: 3 -> 2 -> 1 -> 6 -> 5 -> 4 链表长度保证为K的倍数
  • 给定一个链表,返回链表开始入环的第一个节点
  • n个降序的链表返回前K个大的节点构成的链表
  • 链表合并:给出n个有序的链表,将他们合并为一个有序链表。
  • 有k个有序单链表,怎么合并成一个有序单链表?
  • 链表逆序,不能用修改指针的方法,用递归如何实现。
  • 反转单链表
  • 知道双向链表怎么翻转吗
  • 有两个数字非常大已经超出了long型的范围,现在以链表的方式存储其中链表头表示最高位,例如1->2->3->4表示1234,请设计一个算法求出两数之和;
  • 反转数字,不能把数字变成字符串
  • 链表找环的入口
  • 单链表的逆序
  • 两个链表合并,最长公共子串问题
  • 单链表逆序,快排,数组中找两个数和等于目标值

数组

  • 在M个大小的数组中找到第K大的数(最大堆)
  • 我现在有一个数组[1,2,3,4],请实现算法,得到这个数组的全排列的数组,如[2,1,3,4],•[2,1,4,3]。。。。你这个算法的时间复杂度是多少
  • 数组A,2*n个元素,n个奇数、n个偶数,设计一个算法,使得数组奇数下标位置放置的都是奇数,偶数下标位置放置的都是偶数 •先说下你的思路 •下一个奇数?怎么找? •有思路么? •你这样时间复杂度有点高,如果要求O(N)要怎么做
  • 手写算法,两个有序数组的合并。
  • 十万行二维数组,每行长度为10,每个数组降序,找出最大的15个数。先跟面试官说了思路,然后又在白纸上写了出来
  • 对一个数组进行绝对值排序的算法;
  • 非降序数组,打印某个值最后出现的位置
  • 找出数组中超过半数的那个数字(摩尔投票)
  • 一个数组反转,o(logn)复杂度用什么排序算法;
  • 一个 100长度数组, 里面是 固定的随机数, 要求列出重复的数字的最优算法.;
  • 给定两个数组,每个数组中都有重复的数字。不用类库函数,对这两个数组排序。
  • 给定一个数组,求该数组所有的自子数组 去掉一个字符串中的所有空格
  • 给定一个数组,元素的大小0~25,有重复元素。按出现频次的高低输出所有的数字
  • 给定一个乱序数组,求数组内最大连续的数;
  • 无序数组找第k大的数
  • 给一个数组,和k,求数组中的哪两个数之和为k,除了双层for循环和字典的方式还能用什么方式实现;

查找

  • 写二分查找算法
  • 有主字符串A,子字符串B,在A中查找B
  • 手撕一个有序数组的二分查找算法
  • 请说出二分查找的实现思路及时空复杂度。
  • 用二分法查找一个长度为18的,排好的线性表,当查找不成功时,最多需要比较多少次

排序

  • 快排怎么实现的,快速排序(包括算法步骤、平均算法复杂度、最好和最坏的情形)
  • 5亿整数的大文件,怎么排?
  • 两个1G排好序的文件,按序合并
  • 手写归并排序。 两个有序数组合并。
  • 常见的排序算法有哪些?各种排序算法的平均时间复杂度和最坏情况下的时间复杂度?
  • 写出你熟悉的排序算法,并说明其优缺点
  • 给了长度为N的有重复元素的数组,要求输出第10大的数。
  • 手写一下快速排序吧,我看你参加过ACM,所以用非递归实现一下。
  • 快排听过吗?他是怎么实现的?
  • 如果是单链表的快速排序,你怎么做?
  • 快排时间空间复杂度,最好最坏的情况,优化方案?
  • 手写了冒泡排序
  • 手写递归排序等
  • 两个排序好的数组,构思算法把一个按序插入另一个数组
  • 手工实现一个快速排序算法
  • 列举数据的几个排序算法
  • 快速排序?快速排序是稳定的么? 如何实现一个快速排序的稳定性?
  • 给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
  • 快排会吗?知道原理吗?
  • 排序算法,介绍一下快速排序,快速排序时间复杂度,是不是稳定排序,介绍几种你所知道的稳定排序算法
  • 10亿个数选最大的K个,用什么方法,复杂度多少
  • 说一下冒泡排序的原理
  • 请对3个有序数组进行归并排序

  • AVL树和B树的概念、细节,比如会问mysql数据库的索引的实现原理,基本上就等于问你B树了。
  • 红黑树,这个基本上必问的一个数据结构,包括红黑树的概念、平均算法复杂度、最好最坏情况下的算法复杂度、左右旋转、颜色变换。
  • 找出二叉树中任意两个节点的最低公共根节点, 如果树是BST呢. 深度优先搜索+二分查找树性质
  • B+树如何分裂?
  • 二叉树前中后遍历 二叉树层次遍历 二叉树深度优先遍历(递归、非递归) 二叉树广度优先遍历(递归、非递归) 和为n的二叉树路径 二叉树深度 二叉树是否对称 链表反转
  • 红黑树有啥特性?
  • 二叉树层序遍历输出,每一层输出数组(手写算法)。
  • JDK1.8采用的红黑树特性,以及采用红黑树的理由而不采用AVL和B树的原因?
  • 一个二叉搜索树,找出某两个节点的公共祖先。
  • 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 例如,输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
  • 平衡二叉树的基本概念 简单介绍一下b+树
  • 多叉树的生成 给定一个数组【[a,b]、[c,b]、[e,a]、[h,a]、[k,h]】,数组前一个代表子节点、后一个代表父节点,生成一颗多叉树,返回根节点
  • 按照Z字形分层遍历二叉树,要求bug free,并且构造二叉树进行测试
  • 二叉树的右视图。
  • 写一个二叉树的深度遍历
  • 二叉树翻转
  • 二叉树的s型遍历,层序遍历的变种,简单,不过要写测试用例,等于还要写一个数组转二叉树的函数
  • 一颗非平衡二叉树,如何最快的方式找到距离最远的两个叶子节点。
  • 给一个二叉树和一个目标值,找到和等于这个值的所有路径
  • B和B+树,B+树的搜索次数、为什么不用二叉树。
  • 红黑树最差旋转几次
  • 给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。 最近公共祖先是两个节点的公共的祖先节点且具有最大深度。 假设给出的两个节点都在树中存在。
  • 层次遍历二叉树,返回一个二维数组,每行表示一层
  • 不用迭代方法计算树的高度;
  • 假设一棵二叉树的后序遍历序列为DFGGEBHICA,中序遍历序列为:DBFEGAHCI,则前序遍历序列为?
  • 多叉树的第n层 层次遍历 2.递归太深会怎样?答栈溢出。为什么会栈溢出?python函数中的临时变量存在哪?那很深的时候,用循环会怎样呢?为什么不会栈溢出?
  • 给定一个二叉树,依次打印出每一行
  • 前序遍历 中序遍历 后序遍历 知道那些可以恢复二叉树,只知道前序和后序可以吗?
  • 有N个节点的满二叉树的高度

其他

  • 哈希表,对哈希表的细节要求很高,比如哈希表的冲突检测、哈希函数常用实现、算法复杂度;比如百度二面就让我写一个哈希表插入元素算法,元素类型是任意类型。
  • 找出两个有序数组中的重复项,分析时间和空间复杂度,然后就是不断优化优化优化。。 要是数组长度非常大会出现什么情况?
  • 俩线程分别持续打印奇数和偶数,实现俩线程的交替打印(从小到大)
  • 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。 示例: s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
  • leetcode213 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。 示例 1: 输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。 示例 2: 输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
  • 有15个瓶子,其中最多有一瓶有毒,现在有四只老鼠,喝了有毒的水之后,第二天就会死。如何在第二天就可以判断出哪个瓶子有毒
  • 看你简历提到了raft算法,讲下raft算法的基本流程?raft算法里面如果出现脑裂怎么处理?有没有了解过paxos和zookeeper的zab算法,他们之前有啥区别?
  • 根据身高重建队列 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。 注意: 总人数少于1100人。 示例 输入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
  • 一个二维数组,每一列的数字从左往右增大,每一行从上往下增大,求一个指定的数字在这个数组中的位置
  • 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
  • 股票买卖的一道题 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
  • 给你一个 n * m 的二维整数数组,数字都是大于等于0,现在要你对数组做一种操作,对于所有0,将0所在的行和列全部变为0。要求使用尽量少的空间和时间。
  • 给你一个整数数组,数组中的元素定义一种距离 d[i] 为将数组排序后,该元素移动的距离,现在给你一个K数组,即数组中所有元素的距离d <= k,对这个K数组排序,希望尽量小的时间复杂度。
  • 输入一个不含相同整数的整数集合,输出所有子集 输入:[1,2,3] 输出:[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 有三十瓶水,十个桶,每个桶能放0-10瓶水,有多少种方案
  • 给定一个字符串和一个整数 k,你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符,则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符,则反转前 k 个字符,并将剩余的字符保持原样。 示例: 输入: s = "abcdefg", k = 2 输出: "bacdfeg" 要求: (1)该字符串只包含小写的英文字母。 ( 2)给定字符串的长度和 k 在 [1, 10000]范围内。
  • 翻转字符串,反转句子等。
  • 判断一串字符串里括号的最大有效长度。用动态规划实现
  • 给一个字符串,找出连续相同的字符,如果有两个以上相同的,取ASCII码小的。
  • 给一个字符串,删除最大连续相同的字符串并返回
  • 有一组未排序的整形数组,你设计一个算法,对数组的元素两两配对,然后输出最大的绝对值差和最小的绝对值差的"对数"
  • m*n二维数组整体有序,查找value
  • 返回一个数字数组的排序值,比如数据[6,2,5,0]的返回是[4,2,3,1];
  • 一个正数数组,长度为N,且数组元素<N,统计每个正数出现的次数,要求时间复杂度O(n),空间复杂度O(1);
  • 实现一个fibonacci函数,输入数字n,输出fibonacci数列的第n项数字,并给该函数加入缓存功能。
  • 100G文本找某个单词出现的频率
  • 是否连接红黑树 •
  • 是否了解数据结构的“堆”
  • 斐波拉契数列非递归实现
  • 算法n的阶乘末尾0的个数
  • 我一个文件,有45亿个阿拉伯数字,如何进行去重啊?如何找出最大的那个数啊?
  • 写一个fibnaccio的相关例子
  • 输入两个字符串str1 str2和整数n,要求两个数以n进制相加,然后输出字符串str3
  • 就是二位数组如何进行螺旋输出 然后第二道的算法题是如何从25匹马中通过赛马的形式找到最快的3匹,每次最多只能5匹马参赛,问最少需要赛几次?答案是7次,我思路对了,不过我把次数给弄错了,多了2次没必要的比赛。
  • 6个元素1.2.3.4.5.6的顺序进栈,请问下列哪个不是合法的出栈序列? a:345261 b:436521 c:245316 d:124653 e:543612
  • 图的最短路径问题
  • 算法题(爬楼梯,问一个人爬楼梯,每次只能爬一个台阶或两个台阶,问有N个台阶,总共能有多少种爬法);
  • 实现一个random(m,n)方法,返回m到n的随机数
  • 64只球队找到最强的,找前二强的,前k强的
  • 就是m*n的矩形从左上面到右下面的路径有多少条
  • 求N内的所有素数
  • 判断字符串是否是一个数字
  • 当一个文本文件中有200万行数据,如何在在每一行的尾部追加一个字符;
  • 求一个字符串中最长不重复子串的长度
  • 三个有符号的整型(long)数a, b, c,怎么判断a+b > c?实现并且设计测试用例(在main函数中调用,打印结果) (考虑同号越界问题)
  • 给一个字符串和一个k,要求找到不超过k个不同字符的最长子串的长度
  • 10进制转16进制(紧张了,有点费时间,啧啧啧)
  • f(0)=0;f(1)=1; f(n)=f(n-1)+f(n-2) 求f(n)
  • 有主字符串A,子字符串B,在A中查找B

欢迎搜索关注本人与朋友共同开发的微信面经小程序【大厂面试助手】和公众号【微瞰技术】

file
file

版权声明
本文为[镇屌]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/zhendiao/p/13952925.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云