Facebook高頻題 | Shortest Word Distance的多個變種和解法

NO IMAGE

Shortest Word Distance是Facebook、LinkedIn等公司的高頻面試題。

這個題目本身不是很難,但卻有很多follow up問題。今天我們就針對這個題目進行講解和延伸,幫助大家梳理拓寬思路,更好接招面試官的層層追問。

先一起來看看題目:

題目描述

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Note:

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Example:

Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Input:word1 = “coding”, word2 = “practice”Output:3

Input:word1 = “makes”, word2 = “coding”Output:1

考點解析

shortest word distance是Facebook非常高頻的一道面試題目。

這道題目有很多變種。不同於以往我們把一個題目講的比較細緻,今天這個題目,我們希望將多個變種串起來講,並且再多延伸一些。

希望通過這道習題,幫助大家開闊思路,瞭解這個看似不那麼困難的題目,在面試中會怎樣被面試官步步延伸和追問。這也正是facebook特別喜歡考這道題的原因。

主講人:Emma老師

FLGU一線公司資深工程師

​掃描下方二維碼

進入來Offer官網觀看

解題思路

在這道題目中,Emma老師講解了多個不同的解法,以及follow up問題的回答思路。

Solution 1: Naive Solution

拿到題目,一個比較自然的想法就是把array從左到右遍歷一遍,記錄word1和word2所出現的位置,得到兩個sorted index list。

以下面的這個例子來說:

 0  1  2  3  4  5  6  7

[a, c, d,b, b, b, c,a]

Input:

word1 = “a”

word2 = “b”

則遍歷後的list分別為:

la: 0, 7       

lb: 3, 4, 5   

經過這一步的處理,這個題目就變成了從la取一個數字,從lb取一個數字,差值最小的組合是什麼。

最brute force的做法,就是計算出所有可能的組合的差,再從中選擇最小的一對。但顯然,這是一個複雜度比較高的做法,我們可以在這個基礎上進行優化。

Optimize 1: Binary Search

已知這兩個list都是排好序的,那我們就可以利用binary search:

對於a裡面的每一個元素,在b裡面進行binary search,找到離a中元素最近的那個元素。之後再在所有結果中取一個最近的結果。

思考題

對a中的元素在b中進行binary search,和對b中的元素在a中進行binary search時間複雜度有區別嗎?

Optimize 2: Two Pointer

再進一步,兩個list都是sorted,要找到最小距離的情況,我們應該可以想到,這是一個典型的two pointer誰小移誰的問題。

我們可以分別在a、b兩個list放置兩個pointer,每次移動兩個pointer中,對應的元素中相對較小的一個,同時計算一下兩個pointer對應元素相差的距離,在需要更新的時候更新。

也就是說:

if la(i) is smaller, lb(j) is the smallest larger element in lb comparing to la(i)

if lb(j) is smaller, la(i) is the smallest larger element in la comparing to lb(j)

Solution 2

我們是否可以不建這兩個list呢?能否只是從左到右遍歷一遍原array,忽略無關的元素,只去看a和b呢?也是可以的。

我們換一種分解問題的方法,把這個問題考慮為:

For each a, we need to get the most recent position of b.

For each b, we need to get the most recent position of a.

這樣他們中差值最小的那個,就是我們需要的答案。

那麼在實現的時候,我們就需要從左到右掃一遍array,並記錄:

IndexA:最近一次出現a的位置

IndexB:最近一次出現b的位置

Result:當前的最短距離

每當我們找到一個a或者b時,我們就要檢查IndexB和IndexA之間的差是否比result的值小,如果是,則更新result的值,直到遍歷完整個array。

在講解Follow Up問題前,我們先看一下這個解法的程式碼實現:

程式碼實現

Follow Up 1: 

Multiple query with unlimited times

原問題只是query一次,而且是確定的兩個單詞。那麼,如果是要query很多次,而且單詞是不固定的,那麼應該怎樣更好的解決這個問題呢?

在這種情況下,如果使用之前的方法,我們就需要在每次query的時候都把array掃一遍,cost非常大。

我們應該想到這個題目的需要precomputation

比較直接的一個方法,就是使用一個hashmap,記錄所有distinct word出現的位置。那麼,在query某兩個word的時候,只需要看那兩個word的list就可以了。省去了反覆遍歷原array的時間。

進一步,還可以和面試官探討,如果某個組合被query了很多次,那我們是否需要cache這個結果。

另外一個要與面試官討論的就是,假設我需要非常快的返回這個結果,而且重複query的情況非常多。那我可能需要直接將每兩個word的最短距離直接記下來,這樣之後的每次query都只需要O(1)的時間了。

思考題:

如果這樣的話,precomputation的效率如何,有沒有什麼tradeoff?是否是所有情況下都合適的方法?

Follow Up 2: 

Find the Shortest Word Distance 

Among k Words

這個題目的另一種變形方式就是,我不只求2個word的最短距離,而是多個word的最短距離。

這裡距離的定義是在原input array中最小的subarray的長度,這個subarray需要包含所有k個指定的words。

那這時又要如何求解呢?

與上面思路相承接,一個可能的解法是,針對k個字母,都建立一個list。問題轉化為:從這k個list中,各抽一個元素,使得其最大值和最小值的差最小。

這時,我們利用k pointer的方法,使用priority queue,tree set或者tree map等資料結構都可以解決。

另一個思路,是將這道題目與minimum substring window聯絡起來,可以用sliding window的方法來解決。

更多科技求職資訊,請關注”來Offer”