Facebook OA 3月面经题

题目描述：Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

Example 1 :

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Example 2 :

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]

题解：

这题比较简单，采用分治的思想，归并排序，具体看代码

参考代码

 public void merge(int[] nums1, int m, int[] nums2, int n) { 
       int temp[] = new int[m + n]; 
       int index = 0; 
       int i = 0; 
       int j = 0; 
       while (i < m && j < n) { 
           if (nums1[i] <= nums2[j]) 
               temp[index++] = nums1[i++]; 
           else 
               temp[index++] = nums2[j++]; 
       } 
       for (; i < m; ) { 
           temp[index++] = nums1[i++]; 
       } 
       for (; j < n; ) { 
           temp[index++] = nums2[j++]; 
       } 
       //再把数组temp中的值赋给nums1 
       for (int k = 0; k < m + n; k++) { 
           nums1[k] = temp[k]; 
       } 
   } 

Uber OA 3月面经题

题目描述：Reverse Words in a String

Given an input string s, reverse the order of the words.A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.Return a string of the words in reverse order concatenated by a single space.Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1 :

Input: s = "the sky is blue"

Output: "blue is sky the"

Example 2 :

Input: s = " hello world "

Output: "world hello"

Explanation: Your reversed string should not contain leading or trailing spaces.

题解： 从字符串末尾往前开始遍历，每读到一个单词就添加到结果字符串中，再插入一个空格字符，最后得到的字符串就是翻转单词的字符串

参考代码

class Solution { 
   public static String reverseWords(String s) { 
       if(s == null || s.length() < 2){ 
           return s; 
       } 
       StringBuilder builder = new StringBuilder(); 
       char[] charArr = s.toCharArray(); 
       //从末尾开始遍历 
       for(int i = charArr.length - 1; i >= 0; i--){ 
           if(charArr[i] != ' '){ 
               int left = i - 1; 
               //读取一个单词，直到读取到空格位置 
               while(left >= 0 && charArr[left] != ' '){ 
                   left--; 
               } 
               //将单词正序存取输出结果中 
               for(int j = left + 1; j <= i; j++){ 
                   builder.append(charArr[j]); 
               } 
               builder.append(' '); 
               i = left; 
           } 
       } 
       return builder.toString().trim(); 
   } 
}

Google OA 3月面经题

题目描述：Random Pick with Weight

You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed).We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).More formally, the probability of picking index i is w[i] / sum(w).

Example 1:

Input

["Solution","pickIndex"]

[[[1]],[]]

Output

[null,0]

Explanation

Solution solution = new Solution([1]);

solution.pickIndex(); // return 0. Since there is only one single element on the array the only option is to return the first element.

题解：

这题采用前缀和和二分查找来解决。

参考代码

class Solution { 
   int[] sum; 

   public Solution(int[] w) { 
       sum = new int[w.length + 1]; 
       for (int i = 1;i <= w.length; i++){ 
           sum[i] = sum[i - 1] + w[i - 1]; 
       } 
   } 

   public int pickIndex() { 
       int n = sum.length; 
       int x = new Random().nextInt(sum[n - 1]) + 1; 
       int l = 0, r = n; 
       while (l < r){ 
           int mid = l + r >> 1; 
           if (sum[mid] >= x) r = mid; 
           else l = mid + 1; 
       } 
       return l - 1; 
   } 
}

题目描述：Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.If there is more than one answer, return any of them.

Input: root = [1,null,2,null,3,null,4,null,null]

Output: [2,1,3,null,null,null,4]

Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

题解：

首先，二叉搜索树中序遍历的结果是升序序列，所以通过中序遍历获得二叉搜索树的升序序列，然后利用二分法重新构建二叉搜索树，这里要注意以下几点：

设置递归结束的条件：start > end;

每次递归都以中间值为根节点，中间值的左边数为左子树，中间值的右边数为右子树。

参考代码

class Solution { 
       //用于存放原始二叉搜索树的所有节点 
   List<TreeNode> list = new ArrayList<>(); 
   public TreeNode balanceBST(TreeNode root) { 
       //中序遍历，获取原始二叉搜索树的升序节点序列 
       dfs(root); 
       if(list.isEmpty()){ 
           return null; 
       } 
       //重构二叉搜索树，使之变平衡 
       return build(0, list.size()-1); 
   } 

   private TreeNode build(int start, int end) { 
       //递归终止条件 
       if(start > end){ 
           return null; 
       } 
       //获取中间节点，构建根节点 
       int mid = (start + end)/2; 
       TreeNode node = list.get(mid); 
       //构建左子树 
       node.left = build(start, mid - 1); 
       //构建右子树 
       node.right = build(mid +1, end); 
       return node; 
   } 

   private void dfs(TreeNode root) { 
       if(root == null){ 
           return; 
       } 
       dfs(root.left); 
       list.add(root); 
       dfs(root.right); 
   } 
}

上岸Data方向明星老师们四月公开课：

04/03 上岸学员心得分享（SDE方向） 04/05 小K老师： 简历项目深挖+BQ模拟面试 04/07 米线儿老师：大数据在企业的应用以及工具 04/17 莎莎老师： 出道即巅峰：转专业上岸亚麻Applied Scientist史 04/19 小春老师 ：推荐系统讲座 04/26 小雨老师： SQL 带刷 04/28 Ginger老师： 疫情下我是如何拿到Facebook DS Offer的

4/5 前有效