楼主: Nicolle
460 26

【独家发布】Facebook实习面试题目解法 2016.8-2017.3 [推广有奖]

版主

巨擘

0%

还不是VIP/贵宾

-

TA的文库  其他...

Python Programming

SAS Programming

Must-Read Books

威望
16
论坛币
12397135 个
学术水平
2933 点
热心指数
2942 点
信用等级
2748 点
经验
445583 点
帖子
19866
精华
90
在线时间
7652 小时
注册时间
2005-4-23
最后登录
2019-4-20

楼主
Nicolle 学生认证  发表于 2019-4-2 02:14:27 |只看作者 |倒序

本帖隐藏的内容

Facebook实习面试题目解法.zip (96.99 KB)


关键词:面试题

本帖被以下文库推荐

stata SPSS
沙发
Nicolle 学生认证  发表于 2019-4-2 02:15:11 |只看作者
  1. Reader Writer Problem
  2. 给定:
  3.   Mutex:.
  4.     void lock();
  5.     bool unlock();

  6.   SharedMutex:
  7.     void readerLock();.
  8.     void readerUnlock();
  9.     void writerLock();
  10.     void writerUnlock();


  11. 实现下面4个api,自己定义mutex和variable,不管starvation。
  12.    
  13. public class ReadWriteLock{
  14.     private int readers       = 0;
  15.     private int writers       = 0;
  16.     private int writeRequests = 0;

  17.     public void lockRead() throws InterruptedException{
  18.         lock();
  19.         while(writers > 0 || writeRequests > 0)    await();
  20.         readers++;
  21.         unlock();   
  22.     }

  23.     public void unlockRead(){
  24.         lock();
  25.         readers--;
  26.         signal();
  27.         unlock();
  28.     }

  29.     public void lockWrite() throws InterruptedException{
  30.         lock();
  31.         writeRequests++;
  32.         while(readers > 0 || writers > 0)   await();
  33.         writeRequests--;
  34.         writers++;
  35.         unlock();
  36.     }

  37.     public void unlockWrite() throws InterruptedException{
  38.         lock();
  39.         writers--;
  40.         notifyAll();
  41.         unlock();
  42.     }
  43. }
复制代码
回复

使用道具 举报

藤椅
Nicolle 学生认证  发表于 2019-4-2 02:16:27 |只看作者
277
  1. 277. Find the Celebrity

  2. public int findCelebrity(int n) {
  3.     int candidate = 0;
  4.     for (int i = 1; i < n; i++)
  5.         if (knows(candidate, i))    candidate = i;
  6.     for (int i = 0; i < n; i++) {
  7.         if (i < candidate && (!knows(i, candidate) || knows(candidate, i)))  return -1;
  8.         if (i > candidate && !knows(i, candidate))  return -1;
  9.     }
  10.     return candidate;
  11. }

  12. // The first loop is to find the candidate as the author explains. In detail, suppose the candidate after the first for loop is person k,
  13. // it means 0 to k-1 cannot be the celebrity, because they know a previous or current candidate. Also,
  14. // since k knows no one between k+1 and n-1, k+1 to n-1 can not be the celebrity either. Therefore,
  15. // k is the only possible celebrity, if there exists one
复制代码
回复

使用道具 举报

板凳
Nicolle 学生认证  发表于 2019-4-2 02:17:53 |只看作者
139. Word Break
  1. 139. Word Break
  2. // https://leetcode.com/problems/word-break/

  3. public boolean wordBreak(String s, Set<String> wordDict) {
  4.     boolean[] dp = new boolean[s.length() + 1];
  5.     dp[0] = true;
  6.     for (int i = 1; i < dp.length; i++)
  7.         for (int j = 0; j < i; j++)
  8.             if (dp[j] && wordDict.contains(s.substring(j, i))) {
  9.                 dp[i] = true;
  10.                 break;
  11.             }
  12.     return dp[s.length()];
  13. }

  14. 给一个字符串 such as: "GoogleFacebookMicrosoft", 由字母构成,然后给一个字典,把给定的字符按照字典进行切割,然后输出分割后的一个解答,
  15. 例如:dict=['Google', 'Facebook', 'Microsoft', 'GoogleFace', 'bookMicsoft']
  16. 如果有多个解答,输出一个即可,对于这个例子显然有两个解答,"Google Facebook Microsoft", "GoogleFace bookMicrosoft"。随便输出一个就行
  17. 我回答,递归可以做,然后给出了答案,分析了复杂度O(n^m)。这里复杂度分析卡了一下,不过还好

  18. followup,有没有其他方法可以做?我说可以DP做,f[i] = True意味着0~i-1存在 matching,为了输出一个solution,用g[i+len(w)] = i记录结果,然后回溯方法可以输出一个答案。interviewer跑了个conner case比较满意。
  19. // http://www.1point3acres.com/bbs/forum.php?mod=redirect&goto=findpost&ptid=207049&pid=2597080&from^^uid=96813

  20. public String wordBreak(String s, Set<String> dict) {
  21.     if (s.length() == 0 || dict.size() == 0)    return true;
  22.     int maxLength = getMaxLength(dict);
  23.     boolean[] dp = new boolean[s.length() + 1];//dp[i]:whether 0 to i part of string can be segmented into words in dict
  24.     int[] words = new int[s.length() + 1];//words[i]:index of the end of a dict's word s.substr(i,words[i])
  25.     dp[0] = true;
  26.     words[0] = -1;
  27.     for (int i = 1; i <= s.length(); i++) //O(n) * O(maxLength)
  28.         for (int lastWordLength = 1; lastWordLength <= maxLength && lastWordLength <= i; lastWordLength++) //<= i !!!
  29.             if (dp[i - lastWordLength] && dict.contains(s.substring(i - lastWordLength, i))) {//need add s.substring !!!
  30.                 dp[i] = true;//if string from 0 to i-lastWordLength is segmentable, and i-lastWordLength to i is in dict
  31.                 words[i - lastWordLength] = i;//record the index of breaking position
  32.                 break;//eg. 0 L E E T C O D E -> L(F),i++ -> E(F),LE(F),i++ -> E(F),EE(F),LEE(F),i++ -> .....,LEET(T)
  33.             }         //    T F F F T F F F T
  34.     //remember to check dp[s.length()] first !!!
  35.     if (!dp[s.length()])     return "";
  36.     StringBuilder sb = new StringBuilder(s.substring(0, words[0]));
  37.     int start = words[0];
  38.     while (start != s.length()) {
  39.         sb.append(" " + s.substring(start, words[start]));
  40.         start = words[start];//remember to update start !!!
  41.     }
  42.     return sb.toString();
  43. }
  44. private int getMaxLength(Set<String> dict) {
  45.     int max = 0;
  46.     for (String s : dict)
  47.         max = Math.max(max, s.length());
  48.     return max;
  49. }
复制代码
回复

使用道具 举报

报纸
Nicolle 学生认证  发表于 2019-4-2 02:24:05 |只看作者
151. Reverse Words in a String
  1. 151. Reverse Words in a String

  2. Clarification:
  3. What constitutes a word?
  4.         A sequence of non-space characters constitutes a word.
  5. Could the input string contain leading or trailing spaces?
  6.         Yes. However, your reversed string should not contain leading or trailing spaces.
  7. How about multiple spaces between two words?
  8.         Reduce them to a single space in the reversed string.


  9. Solution:split + 倒序遍历append

  10. public String reverseWords(String s) {
  11.     String[] strs = s.split(" ");
  12.     StringBuilder sb = new StringBuilder();
  13.     for (int i = strs.length - 1; i >= 0; i--)
  14.         if (!strs[i].equals(""))
  15.             sb.append(strs[i]).append(" ");
  16.     return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
  17. }

  18. 此题不难,注意clarification里的细节,要去除头尾空格,单词中间多个空格reverse后只能有一个。
复制代码
回复

使用道具 举报

地板
Nicolle 学生认证  发表于 2019-4-2 02:24:32 |只看作者
186
  1. 186. Reverse Words in a String II

  2. public void reverseWords(char[] s) {
  3.     reverse(s, 0, s.length - 1); // reverse the whole sentense
  4.     int start = 0;
  5.     for (int i = 0; i < s.length; i++) // reverse each word
  6.         if (s[i] == ' ') {
  7.             reverse(s, start, i - 1);
  8.             start = i + 1;
  9.         }
  10.     reverse(s, start, s.length - 1); // reverse the last word
  11. }
  12. private void reverse(char[] s, int i, int j) {
  13.     while (i < j) {
  14.         char tmp = s[i];
  15.         s[i++] = s[j];
  16.         s[j--] = tmp;
  17.     }
  18. }
复制代码
回复

使用道具 举报

7
Nicolle 学生认证  发表于 2019-4-2 02:32:33 |只看作者
152. Maximum Product Subarray
  1. 152. Maximum Product Subarray
  2. // https://leetcode.com/problems/maximum-product-subarray/

  3. public int maxProduct(int A[], int n) {
  4.     if (n == 0) return 0;
  5.     int maxProduct = A[0], minProduct = A[0], maxRes = A[0];
  6.     for (int i = 1; i < n; i++) {
  7.         if (A[i] >= 0) {
  8.             maxProduct = max(maxProduct * A[i], A[i]);
  9.             minProduct = min(minProduct * A[i], A[i]);
  10.         } else {
  11.             int temp = maxProduct;
  12.             maxProduct = max(minProduct * A[i], A[i]);
  13.             minProduct = min(temp * A[i], A[i]);
  14.         }
  15.         maxRes = max(maxRes, maxProduct);
  16.     }
  17.     return maxRes;
  18. }
复制代码
回复

使用道具 举报

8
Nicolle 学生认证  发表于 2019-4-2 02:33:25 |只看作者

161. One Edit Distance

  1. 161. One Edit Distance
  2. // https://leetcode.com/problems/one-edit-distance/


  3. Tests: 1.replace one char, 2.delete one char in s, 3.delete one char in t
  4. corner cases: "" (len = 0)

  5. public boolean isOneEditDistance(String s, String t) {
  6.     int len = Math.min(s.length(), t.length());
  7.     for (int i = 0; i < len; i++) {
  8.         if (s.charAt(i) != t.charAt(i)) {
  9.             if (s.length() == t.length())   return s.substring(i + 1).equals(t.substring(i + 1)); // replace
  10.             else if (s.length() < t.length())   return s.substring(i).equals(t.substring(i + 1)); // delete t
  11.             else    return s.substring(i + 1).equals(t.substring(i)); // delete s
  12.         }
  13.     }
  14.     return Math.abs(s.length() - t.length()) == 1; // corner case: ""
  15. }

  16. 原题 但是不能用substring ====>>>   要一个字符一个字符比较
复制代码
回复

使用道具 举报

9
Nicolle 学生认证  发表于 2019-4-2 02:34:31 |只看作者

17. Letter Combinations of a Phone Number

本帖最后由 Nicolle 于 2019-4-2 02:36 编辑
  1. 17. Letter Combinations of a Phone Number

  2. Input:Digit string "23"
  3. Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

  4. 注意map取index时要 -‘0’

  5. Time: O(3 ^ n)

  6. public List<String> letterCombinations(String digits) {
  7.         String[] map = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  8.         List<String> res = new ArrayList<>();
  9.         if (digits.length() == 0)  return res; // important! "" -> [] Not [""]
  10.         dfs(res, "", map, digits, 0);
  11.         return res;
  12. }
  13. private void dfs(List<String> res, String tmp, String[] map, String digits, int start) {
  14.         if (start == digits.length()) {
  15.                 res.add(tmp);
  16.                 return;
  17.         }
  18.         for (int i = 0; i < map[digits.charAt(start) - '0'].length(); i++) { // -'0'
  19.                 dfs(res, tmp + map[digits.charAt(start) - '0'].charAt(i), map, digits, start + 1);
  20.         }
  21. }
复制代码
回复

使用道具 举报

10
Nicolle 学生认证  发表于 2019-4-2 02:36:22 |只看作者

200. Number of Islands

  1. 200. Number of Islands
  2. // https://leetcode.com/problems/number-of-islands/

  3. Solution 1: DFS
  4. Time: O(m * n)

  5. public int numIslands(char[][] grid) {
  6.     if (grid.length == 0 || grid[0].length == 0)   return 0;
  7.     int m = grid.length, n = grid[0].length, res = 0;
  8.     for (int i = 0; i < m; i++)
  9.         for (int j = 0; j < n; j++)
  10.             if (grid[i][j] == '1') {
  11.                 DFSMarking(grid, i, j);
  12.                 res++;
  13.             }
  14.     return res;
  15. }
  16. public void DFSMarking(char[][] grid, int i, int j) {
  17.     if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')
  18.         return;
  19.     grid[i][j] = '0';
  20.     DFSMarking(grid, i + 1, j);
  21.     DFSMarking(grid, i, j + 1);
  22.     DFSMarking(grid, i, j - 1);
  23.     DFSMarking(grid, i - 1, j);
  24. }
复制代码
回复

使用道具 举报

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

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2019-4-20 19:08
欧冠投注