Facebook 电面

两道题
1） 给一个字符串和一个输入的字符，要求移走给定的字符， Leet

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

清了。是用hash table做的

试做一下第二题，应该是lintcode上subarray sum的变形：
public ArrayList<Integer> subarraySum(int[] nums, int target) {
    ArrayList<Integer> res = new ArrayList<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - target)) {
            res.add(map.get(sum - target) + 1);
            res.add(i);
            return res;
        } else {
            map.put(sum, i);
        }
    }    return res;
}

上面答案是求出符合答案的任意区间即返回的情况。如果要求写出所有符合的区间，那可能要建一个HashMap<Integer, ArrayList<Integer>>，用arraylist来储存所有sum相同的index，每当遇到map.containsKey(sum)的情况就往arraylist里加当前index，而当map.containsKey(sum - target)时就把那个arraylist里的index都for一遍来输出区间结果，如[index1 + 1, i]，[index2 + 1, i]等等。

partial_sum 就是 建一个数组sum[n], sum[i]代表从num[0]累加到num[i]的和， sum[j] - sum[i] 就代表从num[i]加到num[j]的和， 这样就转化为2sum这道题了

最近在复习面试，所以看到面经都想一下写写代码，顺便mark一下自己已经看过了。
和大家交流一下方法，如果有什么错误和改进的地方，希望能得到大家的指正。顺便预祝楼主顺利晋级：）

第一题是LC27 Remove Element https://leetcode.com/problems/remove-element/
用two point应该能解O(n)的解，我并没有remove因为觉得如果可以return的话，可以省去remove的那步

1.     def removeElement(self, nums, val):
   
2.         start, end = 0, len(nums)-1
   
3.         while start <= end:
   
4.             if nums[start] != val:
   
5.                 start += 1
   
6.             else:
   
7.                 nums[start],nums[end] = nums[end],nums[start]
   
8.                 end -= 1
   
9.         return nums[:start+1]

复制代码

第二题应该是 LC 325. Maximum Size Subarray Sum Equals k  的变种
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
题意没有很清楚是不是只有一个subarray可以满足sum = k，我就当只有一个答案来写了，如果有多个，应该是要建立一个dict，dict[sum] = [list of index] 然后用每个index来输出多种可能,如果不存在，return 0

1. def maxSubArrayLen(nums, k):
   
2.     sumNum = 0
   
3.     dict = {}
   
4.     for i in xrange(len(nums)):
   
5.         sumNum  = sumNum + nums[i]
   
6.         if sumNum == k:
   
7.             return nums[:i+1]
   
8. 
   
9.         elif dict.has_key(sumNum-k):
   
10.             return nums[dict[sumNum-k]+1:i+1]
    
11. 
    
12.         if not dict.has_key(sumNum):
    
13.             dict[sumNum] = i
    
14.     return 0

复制代码

第2）题用dp，用二维数组记录所有{i..j}的和？

第二题求partial_sum，然后看是否有两个sum差target或者-target，算是lc two sum的变种

glaciersilent 发表于 2016-7-19 05:14
第二题求partial_sum，然后看是否有两个sum差target或者-target，算是lc two sum的变种

什么是partial_sum

glaciersilent 发表于 2016-7-19 05:14
第二题求partial_sum，然后看是否有两个sum差target或者-target，算是lc two sum的变种

不理解，暴力不就是n^2嘛。。

问下楼主第二题要求是找出所有情况还是只要一种即可？谢谢

wszk1992 发表于 2016-7-19 18:05
partial_sum 就是 建一个数组sum[n], sum代表从num[0]累加到num的和， sum[j] - sum 就代表从num加到num[j] ...

所以和2sum的关系是.........

wszk1992 发表于 2016-7-19 18:05
partial_sum 就是 建一个数组sum[n], sum代表从num[0]累加到num的和， sum[j] - sum 就代表从num加到num[j] ...

而且是sum[j] - sum[i-1] 是[i,j]的和吧...

readman 发表于 2016-7-19 20:02
而且是sum[j] - sum 是的和吧...

这是我的解题思路，仅供参考。时间复杂度O(n)，空间复杂度O(n)

1. vector<int> rangeSum(vector<int>& nums, int target) {
   
2.     vector<int> sum(nums.size() + 1, 0);
   
3.     vector<int> res;
   
4.     unordered_map<int, int> map;
   
5.     sum[0] = 0;
   
6.     //得到sum数组， sum[i] 为 num[0]+...+num[i-1]的和， sum[0]为0
   
7.     //问题转化为求满足 sum[j] - sum[i] == target 的解 (j>i), 其中 <span style="line-height: 1.5;">sum[j] - sum[i] 即</span><span style="line-height: 1.5;">nums在[i,j-1]的和</span>

复制代码