1 回顧

透露一下,本人是雙非二本,自從高考失利以后還以為自己要一直這么平凡下去,沒想到過了三年終于又給我一個機會讓我重新證明了自己,能給我去阿里茎杂、頭條跟美團的面試機會错览，最后選擇去到美團這樣的大廠工作,真的倍感榮幸,如果喜歡我的文章別忘了給我點個贊轉(zhuǎn)發(fā)跟評論,拜托了這對我來說真的很重要。

2 把自己訓(xùn)練成HashMap和復(fù)讀機

這幾次面試給我最大的感觸就是,當(dāng)你覺得自己像復(fù)讀機能把面試題給復(fù)讀出來并且對面試官所提的問題能像HashMap一樣在常數(shù)時間內(nèi)找到答案的時候,你就離成功很近了.

下面是我在準(zhǔn)備面試的時候收集的一些知識點:

2.1 Java

2.1.1 volatile理解煌往，JMM中主存和工作內(nèi)存到底是啥倾哺？和JVM各個部分怎么個對應(yīng)關(guān)系轧邪？

參考link

2.1.2 序列化

Serializable在序列化時使用了反射,從而導(dǎo)致GC的頻繁調(diào)用,參考link

2.1.3 可見性荚守，原子性奔誓，有序性(必考)

• 可見性volatile,一個線程的修改對另外一個線程是馬上可見的,
• 原子性CAS操作,要么都做要么都不做
• 有序性synchronized通過進入和退出Monitor(觀察器)實現(xiàn),CPU可能會亂序執(zhí)行指令,如果在本線程內(nèi)觀察,所有操作都是有序的,如果在一個線程中觀察另一個線程,所有操作都是無序的.參考link

2.1.4 Java鎖機制

java鎖機制其實是鎖總線,同步關(guān)鍵字和Lock接口的優(yōu)劣.

2.1.5 Java的常量池略吨？不同String賦值方法咽瓷，引用是否相等获列？

字面值是常量,在字節(jié)碼中使用id索引,equals相等引用不一定相等,Android上String的構(gòu)造函數(shù)會被虛擬機攔截,重定向到StringFactory

2.1.6 HashMap的實現(xiàn)?樹化閾值?負載因子?

數(shù)組加鏈表加紅黑樹,默認(rèn)負載因子0.75,樹化閾值8,這部分比較惩倥矗考,建議專門準(zhǔn)備.(打個小廣告OWO,你也可以關(guān)注我的專欄,里面有一篇文章分析了HashMap和ArrayMap)

2.1.7 Java實現(xiàn)無鎖同步

CAS的實現(xiàn)如AtomicInteger等等

2.1.8 單例模式

• 雙重檢查

public class Singleton {

    private static volatile Singleton singleton;

    private Singleton() {}

    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null) {
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }
}

• 反序列化安全,反射安全 枚舉級單例,類加載時由JVM保證單例,反序列化不會生成新對象,另外一種反射安全是在構(gòu)造函數(shù)中對單例進行檢查如果存在則拋出異常.

2.1.9 鎖的條件變量

信號量要與一個鎖結(jié)合使用,當(dāng)前線程要先獲得這個鎖,然后等待與這個鎖相關(guān)聯(lián)的信號量,此時該鎖會被解鎖,其他線程可以搶到這個鎖,如果其他線程搶到了這個鎖,那他可以通知這個信號量,然后釋放該鎖,如果此時第一個線程搶到了該鎖,那么它將從等待處繼續(xù)執(zhí)行(應(yīng)用場景,將異步回調(diào)操作封裝為變?yōu)橥讲僮?避免回調(diào)地獄)

信號量與鎖相比的應(yīng)用場景不同,鎖是服務(wù)于共享資源的,而信號量是服務(wù)于多個線程間的執(zhí)行的邏輯順序的,鎖的效率更高一些.

2.1.10 ThreadLocal原理

線程上保存著ThreadLocalMap,每個ThreadLocal使用弱引用包裝作為Key存入這個Map里,當(dāng)線程被回收或者沒有其他地方引用ThreadLocal時,ThreadLocal也會被回收進而回收其保存的值

2.1.11 軟引用,弱引用,虛引用

• 軟引用內(nèi)存不夠的時候會釋放
• 弱引用GC時釋放
• 虛引用,需要和一個引用隊列聯(lián)系在一起使用,引用了跟沒引用一樣,主要是用來跟GC做一些交互.

2.1.12 ClassLoader雙親委派機制

簡單來說就是先把加載請求轉(zhuǎn)發(fā)到父加載器,父加載器失敗了,再自己試著加載

2.1.13 GC Roots有這些

通過System Class Loader或者Boot Class Loader加載的class對象爽撒，通過自定義類加載器加載的class不一定是GC Root:

• 處于激活狀態(tài)的線程
• 棧中的對象
• JNI棧中的對象
• JNI中的全局對象
• 正在被用于同步的各種鎖對象
• JVM自身持有的對象蕊唐，比如系統(tǒng)類加載器等腊徙。

2.1.14 GC算法

2.2 ACM

對于ACM,比較骋啵考鏈表的題,不常刷算法的同學(xué)一定不要對其有抵觸心理.

你可能會問為什么要ACM?網(wǎng)上答案說的什么提高代碼質(zhì)量,能夠更好地閱讀別人的代碼這些理由有一定道理,但對于我們?nèi)ッ嬖嚨娜硕宰钪匾氖茿CM是面試官考察你編碼能力的最直接的手段,所以不用說這么多廢話刷題就夠了.

刷題的話,建議去刷leetcode,題號在200以內(nèi)的,簡單和中等難度,不建議刷困難,因為面試的時候基本就不會出,沒人愿意在那里等你想一個半個小時的.

在面試官面前現(xiàn)場白板編程時,可以先把思路告訴面試官,寫不寫得出來是另外一回事,時間復(fù)雜度和空間復(fù)雜度是怎么來的一定要搞清楚.在編碼時也不一定要寫出最佳的時間和空間的算法,但推薦你寫出代碼量最少,思路最清晰的,這樣面試官看得舒服,你講得也舒服.

下面是我在網(wǎng)上收集或者是在實際中遇到過的ACM題,基本上在leetcode上也都有類似的.

2.2.1 數(shù)組、鏈表

• 鏈表逆序(頭條幾乎是必考的)

    public ListNode reverseList(ListNode head)
    {
        if (head == null)
        {
            return null;
        }
        if (head.next == null)
        {
            return head;
        }
        ListNode prev = null;
        ListNode current = head;
        while (current != null)
        {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

• 刪除排序數(shù)組中的重復(fù)項

    public int removeDuplicates(int[] nums)
    {
        int length = nums.length;
        if (length == 0 || length == 1)
        {
            return length;
        }
        int size = 1;
        int pre = nums[0];
        for (int i = 1; i < length; )
        {
            if (nums[i] == pre)
            {
                i++;
            } else
            {
                pre = nums[size++] = nums[i++];
            }
        }
        return size;
    }

• 數(shù)組中找到重復(fù)元素
• n個長為n的有序數(shù)組篇梭，求最大的n個數(shù)
• 用O(1)的時間復(fù)雜度刪除單鏈表中的某個節(jié)點 把后一個元素賦值給待刪除節(jié)點氢橙，這樣也就相當(dāng)于是刪除了當(dāng)前元素,只有刪除最后一個元素的時間為o(N)平均時間復(fù)雜度仍然為O(1)

      public void deleteNode(ListNode node) {
          ListNode next = node.next;
          node.val = next.val;
          node.next = next.next;
      }

• 刪除單鏈表的倒數(shù)第N個元素 兩個指針,第一個先走N步第二個再走,時間復(fù)雜度為O(N),參考link

      public ListNode removeNthFromEnd(ListNode head, int n) {
          if (head == null)
          {
              return null;
          }
          if (head.next == null)
          {
              return n == 1 ? null : head;
          }
          int size = 0;
          ListNode point = head;
          ListNode node = head;
          do
          {
              if (size >= n + 1)
              {
                  point = point.next;
              }
              node = node.next;
              size++;
          } while (node != null);
          if (size == n)
          {
              return head.next;
          }
          node = point.next;
          point.next = node == null ? null : node.next;
          return head;
      }

• 從長序列中找出前K大的數(shù)字
• 用數(shù)組實現(xiàn)雙頭棧

  public static class Stack<T>
      {
          public Stack(int cap)
          {
              if (cap <= 0)
              {
                  throw new IllegalArgumentException();
              }
              array = new Object[cap];
              left = 0;
              right = cap - 1;
          }
          private Object[] array;
          private int left;
          private int right;
          public void push1(T val)
          {
              int index = left + 1;
              if (index < right)
              {
                  array[index] = val;
              }
              left = index;
          }
          @SuppressWarnings("unchecked")
          public T pop1()
          {
              if (left > 0)
              {
                  return (T)array[left--];
              }
              return null;
          }
          public void push2(T val)
          {
              int index = right - 1;
              if (index > left)
              {
                  array[index] = val;
              }
              right = index;
          }
          @SuppressWarnings("unchecked")
          public T pop2()
          {
              if (right < array.length)
              {
                 return (T)array[right++];
              }
              return null;
          }
      }

• 兩個鏈表求和，返回結(jié)果也用鏈表表示 1 -> 2 -> 3 + 2 -> 3 -> 4 = 3 -> 5 -> 7

      public ListNode addTwoNumbers(ListNode node1, ListNode node2)
      {
          ListNode head = null;
          ListNode tail = null;
          boolean upAdd = false;
          while (!(node1 == null && node2 == null))
          {
              ListNode midResult = null;
              if (node1 != null)
              {
                  midResult = node1;
                  node1 = node1.next;
              }
              if (node2 != null)
              {
                  if (midResult == null)
                  {
                      midResult = node2;
                  } else
                  {
                      midResult.val += node2.val;
                  }
                  node2 = node2.next;
              }
              if (upAdd)
              {
                  midResult.val += 1;
              }
              if (midResult.val >= 10)
              {
                  upAdd = true;
                  midResult.val %= 10;
              }
              else
              {
                  upAdd = false;
              }
              if (head == null)
              {
                  head = midResult;
                  tail = midResult;
              } else
              {
                  tail.next = midResult;
                  tail = midResult;
              }
          }
          if (upAdd)
          {
              tail.next = new ListNode(1);
          }
          return head;
      }

• 交換鏈表兩兩節(jié)點

      public ListNode swapPairs(ListNode head)
      {
          if (head == null)
          {
              return null;
          }
          if (head.next == null)
          {
              return head;
          }
          ListNode current = head;
          ListNode after = current.next;
          ListNode nextCurrent;
          head = after;
          do
          {
              nextCurrent = after.next;
              after.next = current;
              if (nextCurrent == null)
              {
                  current.next = null;
                  break;
              }
              current.next = nextCurrent.next;
              after = nextCurrent.next;
              if (after == null)
              {
                  current.next = nextCurrent;
                  break;
              }
              current = nextCurrent;
          } while (true);
          return head;
      }

• 找出數(shù)組中和為給定值的兩個元素恬偷，如：[1, 2, 3, 4, 5]中找出和為6的兩個元素。

      public int[] twoSum(int[]mun,int target)
      {
          Map<Integer, Integer> table = new HashMap<>();
          for (int i = 0; i < mun.length; ++i)
          {
              Integer value = table.get(target - mun[i]);
              if (value != null)
              {
                  return new int[]{i, value};
              }
              table.put(mun[i], i);
          }
          return null;
      }

2.2.2 樹

• 二叉樹某一層有多少個節(jié)點

2.2.3 排序

• 雙向鏈表排序(這個就比較過分了,遇到了就自求多福吧)

  public static void quickSort(Node head, Node tail) {
        if (head == null || tail == null || head == tail || head.next == tail) {
            return;
        }
        if (head != tail) {
            Node mid = getMid(head, tail);
            quickSort(head, mid);
            quickSort(mid.next, tail);
        }
    }
    public static Node getMid(Node start, Node end) {
        int base = start.value;
        while (start != end) {
            while(start != end && base <= end.value) {
                end = end.pre;
            }
            start.value = end.value;
            while(start != end && base >= start.value) {
                start = start.next;
            }
            end.value = start.value;
        }
        start.value = base;
        return start;
    }   // 使用如內(nèi)部實現(xiàn)使用雙向鏈表的LinkedList容器實現(xiàn)的快排   
    public static void quickSort(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return;
        }
        quickSort(list, 0, list.size() - 1);
    }
    private static void quickSort(List<Integer> list, int i, int j) {
        if (i < j) {
            int mid = partition(list, i, j);
            partition(list, i, mid);
            partition(list,mid + 1, j);
        }
    }
    private static int partition(List<Integer> list, int i, int j) {
        int baseVal = list.get(i);
        while (i < j) {
            while (i < j && baseVal <= list.get(j)) {
                j--;
            }
            list.set(i, list.get(j));
            while (i < j && baseVal >= list.get(i)) {
                i++;
            }
            list.set(j, list.get(i));
        }
        list.set(i, baseVal);
        return i;
    }

• 常見排序,如堆排序,快速,歸并,冒泡等,還得記住他們的時間復(fù)雜度.

2.3項目

2.3.1 視頻聊天使用什么協(xié)議帘睦？

不要答TCP,答RTMP實時傳輸協(xié)議,RTMP在Github也有很多開源實現(xiàn),建議面這方面的同學(xué)可以去了解一下.

2.3.2 你在項目中遇到的一些問題,如何解決,思路是什么?

這一塊比較抽象,根據(jù)你自己的項目來,著重講你比較熟悉,有把握的模塊,一般面試官都會從中抽取一些問題來向你提問.

3 最后說一些個人認(rèn)為比較重要的事

3.1 積極準(zhǔn)備袍患、不斷試錯

• 機會都是留給有準(zhǔn)備的人的,千萬不要想著不準(zhǔn)備上戰(zhàn)場就能成功.

• 多看面經(jīng),面經(jīng)就是面試官們的招聘導(dǎo)向,透過閱讀大量的面經(jīng),你能夠感受得到面試官想要找到什么樣的人,并且你可以有針對性地去準(zhǔn)備.

• 不斷地去面試,如果你這次面試失敗了,那一定要好好總結(jié)其中的原因,一定要想方設(shè)法地從面試官口中套出自己的不足,這樣你下次面試成功的概率就會增加.

作者：曦瞳
鏈接：https://juejin.im/post/5ce50acdf265da1bb0039583