分享

大数据技术之高频面试题(一):面试说明与排序代码

本帖最后由 levycui 于 2020-9-23 21:25 编辑
问题导读:
1、面试过程最关键的是什么?
2、面试时该怎么说?
3、有哪些面试技巧?
4、如何手写排序代码?




第1章 面试说明

1.1 面试过程最关键的是什么?

1)不是你说了什么,而是你怎么说
2)大大方方的聊,放松

1.2 面试时该怎么说?
1)语言表达清楚
        (1)思维逻辑清晰,表达流畅
        (2)一二三层次表达

2)所述内容不犯错
        (1)不说前东家或者自己的坏话
        (2)往自己擅长的方面说
        (3)实质,对考官来说,内容听过,就是自我肯定;没听过,那就是个学习的过程。

1.3 面试技巧
1.3.1 六个常见问题

1)你的优点是什么?
        大胆的说出自己各个方面的优势和特长
2)你的缺点是什么?
        不要谈自己真实问题;用“缺点”衬托自己的优点

3)你的离职原因是什么?
  • 不说前东家坏话,哪怕被伤过
  • 合情合理合法
  • 不要说超过1个以上的原因

4)您对薪资的期望是多少?
  • 非终面不深谈薪资
  • 只说区间,不说具体数字
  • 底线是不低于当前薪资
  • 非要具体数字,区间取中间值,或者当前薪资的+20%

5)您还有什么想问的问题?
  • 这是体现个人眼界和层次的问题
  • 问题本身不在于面试官想得到什么样的答案,而在于你跟别的应聘者的对比
  • 标准答案:
公司希望我入职后的3-6个月内,给公司解决什么样的问题
公司(或者对这个部门)未来的战略规划是什么样子的?
以你现在对我的了解,您觉得我需要多长时间融入公司?

6)您最快多长时间能入职?
        一周左右,如果公司需要,可以适当提前

1.3.2 两个注意事项
1)职业化的语言
2)职业化的形象


1.3.3 自我介绍(控制在4分半以内,不超过5分钟)
1)个人基本信息
2)工作履历
        时间、公司名称、任职岗位、主要工作内容、工作业绩、离职原因

3)深度沟通(也叫压力面试)
        刨根问底下沉式追问(注意是下沉式,而不是发散式的)
        基本技巧:往自己熟悉的方向说


第2章 手写代码
2.1 冒泡排序

/**
* 冒泡排序 时间复杂度 O(n^2) 空间复杂度O(1)
*/
public class BubbleSort {
   public static void bubbleSort(int[] data) {
      System.out.println("开始排序");
      int arrayLength = data.length;
      for (int i = 0; i < arrayLength - 1; i++) {
         boolean flag = false;
         for (int j = 0; j < arrayLength - 1 - i; j++) {
            if(data[j] > data[j + 1]){
               int temp = data[j + 1];
               data[j + 1] = data[j];
               data[j] = temp;
               flag = true;
            }
         }
         System.out.println(java.util.Arrays.toString(data));
         if (!flag)
            break;
      }
   }
   public static void main(String[] args) {
      int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
      System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
      bubbleSort(data);
      System.out.println("排序之后:\n" + java.util.Arrays.toString(data));
   }
}

2.2 二分查找
2020-09-22_200948.jpg
图4-二分查找核心思路

  1. 实现代码:
  2. /**
  3. * 二分查找 时间复杂度O(log2n);空间复杂度O(1)
  4. */
  5. def binarySearch(arr:Array[Int],left:Int,right:Int,findVal:Int): Int={
  6.   if(left>right){//递归退出条件,找不到,返回-1
  7.     -1
  8.   }
  9.   val midIndex = (left+right)/2
  10.   if (findVal < arr(midIndex)){//向左递归查找
  11.     binarySearch(arr,left,midIndex,findVal)
  12.   }else if(findVal > arr(midIndex)){//向右递归查找
  13.     binarySearch(arr,midIndex,right,findVal)
  14.   }else{//查找到,返回下标
  15.     midIndex
  16.   }
  17. }
复制代码
拓展需求:当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到。
代码实现如下:
  1. /*
  2.   {1,8, 10, 89, 1000, 1000,1234} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000.
  3.   //分析
  4.   1. 返回的结果是一个可变数组 ArrayBuffer
  5.   2. 在找到结果时,向左边扫描,向右边扫描 [条件]
  6.   3. 找到结果后,就加入到ArrayBuffer
  7.    */
  8.   def binarySearch2(arr: Array[Int], l: Int, r: Int,
  9.                     findVal: Int): ArrayBuffer[Int] = {
  10.     //找不到条件?
  11.     if (l > r) {
  12.       return ArrayBuffer()
  13.     }
  14.     val midIndex = (l + r) / 2
  15.     val midVal = arr(midIndex)
  16.     if (midVal > findVal) {
  17.       //向左进行递归查找
  18.       binarySearch2(arr, l, midIndex - 1, findVal)
  19.     } else if (midVal < findVal) { //向右进行递归查找
  20.       binarySearch2(arr, midIndex + 1, r, findVal)
  21.     } else {
  22.       println("midIndex=" + midIndex)
  23.       //定义一个可变数组
  24.       val resArr = ArrayBuffer[Int]()
  25.       //向左边扫描
  26.       var temp = midIndex - 1
  27.       breakable {
  28.         while (true) {
  29.           if (temp < 0 || arr(temp) != findVal) {
  30.             break()
  31.           }
  32.           if (arr(temp) == findVal) {
  33.             resArr.append(temp)
  34.           }
  35.           temp -= 1
  36.         }
  37.       }
  38.       //将中间这个索引加入
  39.       resArr.append(midIndex)
  40.       //向右边扫描
  41.       temp = midIndex + 1
  42.       breakable {
  43.         while (true) {
  44.           if (temp > arr.length - 1 || arr(temp) != findVal) {
  45.             break()
  46.           }
  47.           if (arr(temp) == findVal) {
  48.             resArr.append(temp)
  49.           }
  50.           temp += 1
  51.         }
  52.       }
  53.       return resArr
  54.     }
复制代码

2.3 快排
2020-09-22_201402.jpg

图1-快速排序核心思想
  1. 代码实现:
  2. /**
  3. * 快排
  4. * 时间复杂度:平均时间复杂度为O(nlogn)
  5. * 空间复杂度:O(logn),因为递归栈空间的使用问题
  6. */
  7. def quickSort(list: List[Int]): List[Int] = list match {
  8.     case Nil => Nil
  9.     case List() => List()
  10.     case head :: tail =>
  11.       val (left, right) = tail.partition(_ < head)
  12.       quickSort(left) ::: head :: quickSort(right)
  13.   }
复制代码
2.4 归并
2020-09-22_201522.jpg

图2-归并排序核心思想
核心思想:不断的将大的数组分成两个小数组,直到不能拆分为止,即形成了单个值。此时使用合并的排序思想对已经有序的数组进行合并,合并为一个大的数据,不断重复此过程,直到最终所有数据合并到一个数组为止。


2020-09-22_201556.jpg

  1. 代码实现:
  2. /**
  3. * 快排
  4. * 时间复杂度:O(nlogn)
  5. * 空间复杂度:O(n)
  6. */
  7. def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
  8.     case (Nil, _) => right
  9.     case (_, Nil) => left
  10.     case (x :: xTail, y :: yTail) =>
  11.       if (x <= y) x :: merge(xTail, right)
  12.       else y :: merge(left, yTail)
  13.   }
复制代码
2.5  二叉树之Scala实现
2.5.1 二叉树概念
2020-09-22_201712.jpg

2.5.2 二叉树的特点
1)树执行查找、删除、插入的时间复杂度都是O(logN)
2)遍历二叉树的方法包括前序、中序、后序
3)非平衡树指的是根的左右两边的子节点的数量不一致
4) 在非空二叉树中,第i层的结点总数不超过 , i>=1;
5)深度为h的二叉树最多有个结点(h>=1),最少有h个结点;
6)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

2.5.3 二叉树的Scala代码实现
定义节点以及前序、中序、后序遍历
  1. class TreeNode(treeNo:Int){
  2.   val no = treeNo
  3.   var left:TreeNode = null
  4.   var right:TreeNode = null
  5.   //后序遍历
  6.   def postOrder():Unit={
  7.     //向左递归输出左子树
  8.     if(this.left != null){
  9.       this.left.postOrder
  10.     }
  11.     //向右递归输出右子树
  12.     if (this.right != null) {
  13.       this.right.postOrder
  14.     }
  15.     //输出当前节点值
  16.     printf("节点信息 no=%d \n",no)
  17.   }
  18.   //中序遍历
  19.   def infixOrder():Unit={
  20.     //向左递归输出左子树
  21.     if(this.left != null){
  22.       this.left.infixOrder()
  23.     }
  24.     //输出当前节点值
  25.     printf("节点信息 no=%d \n",no)
  26.     //向右递归输出右子树
  27.     if (this.right != null) {
  28.       this.right.infixOrder()
  29.     }
  30.   }
  31.   //前序遍历
  32.   def preOrder():Unit={
  33.     //输出当前节点值
  34.     printf("节点信息 no=%d \n",no)
  35.     //向左递归输出左子树
  36.     if(this.left != null){
  37.       this.left.postOrder()
  38.     }
  39.     //向右递归输出右子树
  40.     if (this.right != null) {
  41.       this.right.preOrder()
  42.     }
  43.   }
  44.   //后序遍历查找
  45.   def postOrderSearch(no:Int): TreeNode = {
  46.     //向左递归输出左子树
  47.     var resNode:TreeNode = null
  48.     if (this.left != null) {
  49.       resNode = this.left.postOrderSearch(no)
  50.     }
  51.     if (resNode != null) {
  52.       return resNode
  53.     }
  54.     if (this.right != null) {
  55.       resNode = this.right.postOrderSearch(no)
  56.     }
  57.     if (resNode != null) {
  58.       return resNode
  59.     }
  60.     println("ttt~~")
  61.     if (this.no == no) {
  62.       return this
  63.     }
  64.     resNode
  65.   }
  66.   //中序遍历查找
  67.   def infixOrderSearch(no:Int): TreeNode = {
  68.     var resNode : TreeNode = null
  69.     //先向左递归查找
  70.     if (this.left != null) {
  71.       resNode = this.left.infixOrderSearch(no)
  72.     }
  73.     if (resNode != null) {
  74.       return resNode
  75.     }
  76.     println("yyy~~")
  77.     if (no == this.no) {
  78.       return this
  79.     }
  80.     //向右递归查找
  81.     if (this.right != null) {
  82.       resNode = this.right.infixOrderSearch(no)
  83.     }
  84.     return resNode
  85.   }
  86.   //前序查找
  87.   def preOrderSearch(no:Int): TreeNode = {
  88.     if (no == this.no) {
  89.       return this
  90.     }
  91.     //向左递归查找
  92.     var resNode : TreeNode = null
  93.     if (this.left != null) {
  94.       resNode = this.left.preOrderSearch(no)
  95.     }
  96.     if (resNode != null){
  97.       return  resNode
  98.     }
  99.     //向右边递归查找
  100.     if (this.right != null) {
  101.       resNode = this.right.preOrderSearch(no)
  102.     }
  103.     return resNode
  104.   }
  105.   //删除节点
  106.   //删除节点规则
  107.   //1如果删除的节点是叶子节点,则删除该节点
  108.   //2如果删除的节点是非叶子节点,则删除该子树
  109.   def delNode(no:Int): Unit = {
  110.     //首先比较当前节点的左子节点是否为要删除的节点
  111.     if (this.left != null && this.left.no == no) {
  112.       this.left = null
  113.       return
  114.     }
  115.     //比较当前节点的右子节点是否为要删除的节点
  116.     if (this.right != null && this.right.no == no) {
  117.       this.right = null
  118.       return
  119.     }
  120.     //向左递归删除
  121.     if (this.left != null) {
  122.       this.left.delNode(no)
  123.     }
  124.     //向右递归删除
  125.     if (this.right != null) {
  126.       this.right.delNode(no)
  127.     }
  128.   }
  129. }
复制代码

定义二叉树,前序、中序、后序遍历,前序、中序、后序查找,删除节点
  1. class BinaryTree{
  2.   var root:TreeNode = null
  3.   //后序遍历
  4.   def postOrder(): Unit = {
  5.     if (root != null){
  6.       root.postOrder()
  7.     }else {
  8.       println("当前二叉树为空,不能遍历")
  9. }
  10. }
  11.     //中序遍历
  12.     def infixOrder(): Unit = {
  13.       if (root != null){
  14.         root.infixOrder()
  15.       }else {
  16.         println("当前二叉树为空,不能遍历")
  17.       }
  18.     }
  19.     //前序遍历
  20.     def preOrder(): Unit = {
  21.       if (root != null){
  22.         root.preOrder()
  23.       }else {
  24.         println("当前二叉树为空,不能遍历")
  25.       }
  26.     }
  27.     //后序遍历查找
  28.     def postOrderSearch(no:Int): TreeNode = {
  29.       if (root != null) {
  30.         root.postOrderSearch(no)
  31.       }else{
  32.         null
  33.       }
  34.     }
  35.     //中序遍历查找
  36.     def infixOrderSeacher(no:Int): TreeNode = {
  37.       if (root != null) {
  38.         return root.infixOrderSearch(no)
  39.       }else {
  40.         return null
  41.       }
  42.     }
  43.     //前序查找
  44.     def preOrderSearch(no:Int): TreeNode = {
  45.       if (root != null) {
  46.         return root.preOrderSearch(no)
  47.       }else{
  48.         //println("当前二叉树为空,不能查找")
  49.         return null
  50.       }
  51.     }
  52. //删除节点
  53.     def delNode(no:Int): Unit = {
  54.       if (root != null) {
  55.         //先处理一下root是不是要删除的
  56.         if (root.no == no){
  57.           root = null
  58.         }else {
  59.           root.delNode(no)
  60.         }
  61.       }
  62.    
  63.   }
复制代码
2.6 手写Spark-WordCount
  1. val conf: SparkConf =
  2. new SparkConf().setMaster("local[*]").setAppName("WordCount")
  3. val sc = new SparkContext(conf)
  4. sc.textFile("/input")
  5.   .flatMap(_.split(" "))
  6.   .map((_, 1))
  7.   .reduceByKey(_ + _)
  8.   .saveAsTextFile("/output")
  9. sc.stop()
复制代码
2.7 手写Spark程序
要求:(a,1) (a,3) (b,3) (b,5) (c,4),求每个key对应value的平均值
  1. rdd.combineByKey(v=>(v,1),(acc:(Int,Int),newV)=>(acc._1+newV,acc._2+1),(acc1:(Int,Int),acc2:(Int,Int))=>(acc1._1+acc2._1,acc1._2+acc2._2))
复制代码

最新经典文章,欢迎关注公众号


没找到任何评论,期待你打破沉寂

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

推荐上一条 /5 下一条