一、

一開始因為沒收到含有共享文檔鏈接的郵件，所以簡單自我介紹，聊了幾句項目。問了：

1. 玩嗨如果數據庫結構變化要怎么辦

2. 哈佛項目是否為官方渠道

一直沒收到郵件，面試官讀網址給我，進到共享文檔界面。

?

共享文檔編程：

1. 單鏈表的快速排序

我先求了長度，他說不用求長度。

第一個元素為樞軸，然后把當前鏈表分成兩個鏈表，一個全部是小于等于樞軸的元素，另一個全部是大于等于樞軸的元素，然后遞歸快排這兩個新鏈表，最后把它們連起來。

2. 給一個無序數組，元素不重復，連續數字的最大長度。例：[4,5,1,3,8,9]的最長連續數字為[3,4,5]，所以最大長度為3。

我先說的排序，然后遍歷。時間復雜度O(nlogn)。

面試官說時間復雜度低一些的呢。

提示可以用額外的存儲空間來換時間。

最后說出來用哈希表存儲每個元素是否出現，然后從每個元素開始找它加1的元素是否存在，若存在則長度加1，若不存在則重新計數。

具體實現：首先遍歷鏈表用map記錄元素是否存在（map.find(element) != map.end()即元素存在），然后再遍歷鏈表，對每一個元素，找比它大和比它小的連續元素，從map中刪除所有找過的元素，記錄最大長度。

時間復雜度O(n)。

3. 給一個n，求從0到n所有數字的二進制表示中1的個數。

n為偶數時，n的二進制表示中1的個數 = (n/2)的二進制表示中1的個數。

n為奇數時，n的二進制表示中1的個數 = (n-1)的二進制表示中1的個數 + 1。

設f(n)為 0到n所有數字的二進制表示中1的個數。

n為奇數時，0到n的所有偶數的二進制表示中1的個數為 f(n/2)，0到n的所有奇數的二進制表示中1的個數為 f(n/2)+(n+1)/2。

n為偶數時，0到n的所有偶數的二進制表示中1的個數為 f(n/2)，0到n的所有奇數的二進制表示中1的個數為 f((n-1)/2)+((n-1)+1)/2。

綜上，

f(n) = f(n/2) * 2 + (n+1) / 2, n為奇數

? ? ? ? ? f(n/2) + f((n-1) / 2) + n/2, n為偶數

?

二、

五道算法題：

1. 矩形覆蓋層數：給n個矩形的長和寬，長寬都大于等于的可以覆蓋，問最多能覆蓋的層數。

按矩形的寬和長從小到大排序，然后動態規劃。

從第一個開始，記錄到它為止最大覆蓋層數。

對每個矩形，遍歷它前面的所有矩形，若能覆蓋，則更新該矩形的覆蓋數的最大值。

?

2. 求排列的下一個

從最右開始找到n[i]<n[i+1]的第一對相鄰數字。若沒有則說明沒有下一個排列。

將n[i]與最右數字（即i到最右的最小數字）交換，再將i+1到最右排序。

3. n個人比賽 0 VS 1, 2 VS 3, ..., (n-2) VS (n-1), 問i和j什么時候相遇（假設i和j每次都能勝出）。

假設都是編號較小者勝。

第一局：0 VS 1, 2 VS 3, ..., (n-2) VS (n-1)

第二局：0 VS 2, 4 VS 6, ..., (n-2) VS (n-1)

當 i / 2^k == j / 2^k 時，i和j相遇。

4. 求n位字符串有多少種形式

5. 求完全二叉樹的最后一個節點

遞歸后序遍歷，每次返回該子樹的深度和其中最右節點指針。

對某個節點，若其左子樹深度大于右子樹，則該子樹深度為左子樹深度加一，返回其左子樹最右節點指針；否則，該子樹深度為右子樹深度加一，返回其右子樹最右節點指針。

?

轉載于:https://www.cnblogs.com/argenbarbie/p/5349248.html

總結

以上是生活随笔為你收集整理的hulu的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。