Java岗开发3年，公司临时抽查算法，离职后这几题我记一辈子

前几天我们公司做了一件蠢事，非常非常愚蠢的事情。我原以为从学校出来之后，除了找工作有测试外，不会有任何与考试有关的事儿。

 

但是，天有不测风云，公司技术总监、人事总监两位大佬突然降临到我们事业线，叫上我老大，给我们组织了一场别开生面的“考试”。

那是一个风和日丽的下午，我翘着二郎腿，左手端着一杯卡布奇诺，右手抓着我的罗技鼠标，滚动着轮轴，穿梭在头条热点之间。

“淡黄的长裙~蓬松的头发~”

“WC，见证历史，今年高考推迟了一个月，当年我要是碰上这种事，我岂不分分钟985？”

同事：“这就是你考不上本科的原因？”

我：“呃~”

“WC，阿水水这是要去滔博吗？”

同事：“这跟你考不上本科有什么关系？”

我：“喂喂？”

这时，一位从没见过的中年地中海出现在我的视线里：“各位，注意一下，为了考察大家的编程能力，5分钟之后有一场测试，把自己的代码保存好后，到大会议室集合。”

...

同事甲：“这不是总部来的技术总监吗？”

同事乙：“WC，第一次看到大佬。”

我：“你们难道没有听到要测试吗？”

...

后来，我们就不明不白的进行了一场测试，当我一片空白的试卷交上去，把一片空白的脑子带出来，听着同事们谈论着测试答案。

同事告诉我，这份算法题来自百度，并给了我一份文件。

文件具体内容如下：

1、度度熊想去商场买一顶帽子，商场里有 N 顶帽子，有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子，问第三便宜的帽子价格是多少？

输入描述:

首先输入一个正整数 N（N <= 50），接下来输入 N 个数表示每顶帽子的价格（价格均是正整数，且小于等于 1000）

输出描述:

如果存在第三便宜的帽子，请输出这个价格是多少，否则输出-1

输入例子 1:

10

10 10 10 10 20 20 30 30 40 40

输出例子 1:

30

解答：

  

   

    

     

    
    

     

      /*简单，时间复杂度也低*/
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using 
      namespace 
      std;
      int main(){
     
    
   

    

     

    
    

     

      int n,t=
      0,syn=
      0;
     
    
   

    

     

    
    

     

      int price[
      1000]={
      0};
     
    
   

    

     

    
    

     

      cin>>n;
     
    
   

    

     

    
    

     

      while(n--){
     
    
   

    

     

    
    

     

      cin>>t;
     
    
   

    

     

    
    

     

      price[t]=
      1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      t=
      0;
     
    
   

    

     

    
    

     

      for(
      int i=
      0;i<
      1000;i++){
     
    
   

    

     

    
    

     

      if(price[t]&&syn<
      3)
     
    
   

    

     

    
    

     

      syn++;
     
    
   

    

     

    
    

     

      if(syn==
      3)
     
    
   

    

     

    
    

     

      break;
     
    
   

    

     

    
    

     

       t++;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      syn==
      3?
      cout<<t:
      cout<<
      -1;
     
    
   

    

     

    
    

     

      }
     
    
  

2、一个数轴上共有 N 个点，第一个点的坐标是度度熊现在位置，第 N-1 个点是度度熊的家。现在他需要依次的从 0 号坐标走到 N-1 号坐标。

但是除了 0 号坐标和 N-1 号坐标，他可以在其余的 N-2 个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

解答：

从 N-2 个坐标中选出一个点，并直接将这个点忽略掉。直接忽略一个点只会直接影响到，这个节点前后节点的距离。这个 影响的距离我们暂且命名为优化距离，将所有节点按顺序组成三个节点的集合，通过这种方式只需要通过一次循环便能得到结果。

优化距离越大说明如果去掉这个集合的中点元素将会使得总距离越短，下面上代码。

  

   

    

     

    
    

     

      import java.util.Scanner;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public 
      class 
      Main {
     
    
   

    

     

    
    

     
    
      public static void main(String[] args) {
     
    
   

    

     

    
    

     

              Scanner scanner = 
      new Scanner(System.
      in);
     
    
   

    

     

    
    

     
        
      int length = scanner.nextInt();
     
    
   

    

     

    
    

     
        
      int[] arrays = 
      new 
      int[length];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        
      for (
      int i = 
      0; i < length; i++) {
     
    
   

    

     

    
    

     

                  arrays[i] = scanner.nextInt();
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        
      /**
     
    
   

    

     

    
    

     

       * sum 总距离
     
    
   

    

     

    
    

     

       * repetition 三个节点 中被重复计算的总距离
     
    
   

    

     

    
    

     

       * select 优化距离最大的 三个节点两两相加的距离
     
    
   

    

     

    
    

     

       * add 三个结尾距离为 max 中 头尾节点的距离
     
    
   

    

     

    
    

     

       * last 最后三个节点中 尾距离没有被计算两次 需要加上
     
    
   

    

     

    
    

     

       * optimizeDistance 优化距离
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
        
      int sum = 
      0,
      int repetition = 
      0,
      int 
      select = 
      0,
      int 
      add = 
      0,
      int last = 
      0,
      int optimizeDistance = 
      0;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        
      for (
      int i = 
      0; i <= (arrays.length - 
      3); i++) {
     
    
   

    

     

    
    

     
            
      int begin = arrays[i];
     
    
   

    

     

    
    

     
            
      int mid = arrays[i + 
      1];
     
    
   

    

     

    
    

     
            
      int end = arrays[i + 
      2];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
            
      //三个点之间的距离
     
    
   

    

     

    
    

     
            
      int threePointDistance = Math.abs(mid - begin) +
     
    
   

    

     

    
    

     

                      Math.abs(end - mid);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
            
      //两个点之间的距离 即被多次计算待会需要减掉的距离
     
    
   

    

     

    
    

     
            
      int twoPointDistance = Math.abs(end - mid);
     
    
   

    

     

    
    

     
            
      int contrast = threePointDistance - Math.abs(begin - end);
     
    
   

    

     

    
    

     

                  repetition += twoPointDistance;
     
    
   

    

     

    
    

     

                  sum += threePointDistance;
     
    
   

    

     

    
    

     

                  last = twoPointDistance;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
            
      if (contrast > optimizeDistance) {
     
    
   

    

     

    
    

     

                      optimizeDistance = contrast;
     
    
   

    

     

    
    

     
                
      select = threePointDistance;
     
    
   

    

     

    
    

     
                
      add = Math.abs(end - begin);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              System.
      out.println((sum - 
      select + last) - repetition + 
      add);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  

3、度度熊最近对全排列特别感兴趣,对于 1 到 n 的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。

但是现在度度熊手中只有 k 个小于符号即('<'')和 n-k-1 个大于符号(即'>'),度度熊想知道对于 1 至n 任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

解答：

dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;

dp[i][j]表示有 i 个数字及 j 个小于号所能组成的数量(大于号数量当然是 i - j - 1 次，后面需要使用)

而加入第 i + 1 个数字时，分以下四种情况：

1. 如果将 i+1 插入当前序列的开头，即有了 1<2，加入后成为 3>1<2，会发现等于同时加入了一个大于号！(此时可以无视 1 与 2 之间的关系，因为 i+1>i)
2. 如果将 i+1 插入当前序列末尾,即 1<2 变成了 1<2<3，会发现等于同时加入了一个小于号！ (此时可以无视 1 与 2 之间的关系，因为 i+1>i)
3. 如果将i+1加入一个小于号之间，即已经有 1<2了，向中间加入3,会发现变成了1<3>2，等于同时加入了一个大于号！
4. 如果将 i+1 加入一个大于号中间，即有了 2>1，变成了 2<3>1，等于同时加入了一个小于号！

综上所述，dp[i][j]等于以上四种情况之和：

dp[i - 1][j] 将 i 加在开头等于加入一个大于号，即要求 i-1 个数时已经有了 j 个小于号；

dp[i - 1][j - 1] 将 i 加在末尾等于加入一个小于号，即要求 i-1 个数时已经有了 j-1 个小于号；

dp[i - 1][j] * j 将 i 加在任意一个小于号之间，等于加入了一个大于号，即要求 i-1 个数时已经有了 j 个小于号，每个小于号都可以进行这样的一次插入；

dp[i - 1][j - 1] * (i- j - 1) 将 i 加载任意一个大于号之间，等于加入了一个小于号，即要求i-1 个数时有了 j-1 个小于号；

而此时共有(i - 1) - (j - 1)- 1 个大于号，每个大于号都要进行一次这样的操作合并同类项即为dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1))。

最后要记得取模。

......

由于篇幅原因，我就不一一给大家展示了，需要文件的朋友可以来私信我。

由于在准备面试，以前收集的Java进阶宝典《Java核心知识点整理.pdf》，全文覆盖了JVM、锁、高并发、反射、mybatis、Spring原理、微服务、Zookeeper、数据库、数据结构等等内容，获取方式： 评论区获取！

于是，我被老大叫去办公室喝茶，然后，就离职了。

OS：你TM裁员就裁员，突击测试算怎么回事？

这段时间，我就是待就业状态，网上找了一些算法和安卓有关的课程（没错，我转安卓了，以后有问题可以一起探讨探讨）

帮忙宣传一下，这个课程的具体内容：

还有他们所录下的视频文件，报了名后有以前的所有录播视频，我先看着，更详细和更新的我等着看直播了，反正是终身可看的。

听说这些视频可以分享一些出来的，需要的可以私信我回复【资料】获取领取方式。

由于在准备面试，以前收集的Java进阶宝典《Java核心知识点整理.pdf》，全文覆盖了JVM、锁、高并发、反射、mybatis、Spring原理、微服务、Zookeeper、数据库、数据结构等等内容，获取方式：评论区获取！