脸书onsite

• 利扣91，做完dp解之后，又被问了不用dp怎么做（不限算法时间复杂度）
• 给n个d维的vector和一个first selected的vector, 选出k个vector,每次选择下一个时要求：选离所有selected vector最远的vector, 计算距离的函数已给出D(v1,v2)并假设调用此函数时间复杂度为O(1), 某vector与所有selected vectors的距离定义为这个vector与其nearest selected neighbor的距离。在面试官的提示下最终找到了复杂度为O(nk)的最优解，对每个unselected的vector存下其与selected vectosr的距离,每次遍历unselected vectors找出距离最远的vector为下一个selected vector, 用这个vector与每个unselected vector的距离去更新距离（若小于原距离，表示nearest selected neighbor更换了）
• 给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行时间为5（B_ _ _ B, _ 表示wait). 写一个函数输入task序列和interval, 输出总的运行时间。 follow up是给一个序列和interval，task的执行顺序可以打乱，输出optimal(总执行时间最短)的执行顺序
• 最近在做什么以及细问了简历。
  您好！
  本帖隐藏的内容需要积分高于 166 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

第四题的思路
res = sum(dp[i][k])
dp[i][j] = sum { dp[m][j - 1] | if canReach[i][m]}
canReach : boolean[10][10]
canReach[1][6], canReach[1][8], [2][7], [2][9], [3][4], [3][8], [4][3], [4][9], [4][0], [6][1], [6][7], [6][0], [7][2], [7][6], [8][1], [8][3], [9][2], [9][4] = true
init : dp[1][0] = 1;
一维dp就可以，时间应该是O(steps), 空间O(steps + 100)

试写了一下code，先统计了frequency of tasks然后用maxHeap做的，楼主能帮忙看看是这样么，感觉还有可以优化的地方，谢谢~
public static String taskSchedule(String str, int k) {
        StringBuilder rearranged = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : str.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }

        Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
                return entry2.getValue() - entry1.getValue();
            }
        });
        maxHeap.addAll(map.entrySet());

        while (!maxHeap.isEmpty()) {
            int i = 0;
            ArrayList<Map.Entry<Character, Integer>> temp = new ArrayList<>();
            while (i <= k && !maxHeap.isEmpty()) {
                Map.Entry<Character, Integer> curr = maxHeap.poll();
                rearranged.append(curr.getKey());
                curr.setValue(curr.getValue() - 1);
                temp.add(curr);
                i++;
            }
            for (Map.Entry<Character, Integer> e : temp) {
                if (e.getValue() > 0) {
                    maxHeap.offer(e);
                }
            }
        }
        return rearranged.toString();
    }

第三题类似leetcode 358 Rearrange String k Distance Apart?
写了一下

1. def optimalRunningTime(tasks, k):
   
2.     heap = [(-v, 0, c) for c, v in collections.Counter(tasks).items()]
   
3.     heapify(heap)
   
4.     t = 0
   
5.     lst = []
   
6.     while heap:
   
7.         cache = []
   
8.         offset = k
   
9.         tmp = None
   
10.         while heap and heap[0][1] > t:
    
11.             cache.append(heappop(heap))
    
12.             if not tmp or cache[-1][1] < tmp[1]:
    
13.                 tmp = cache[-1]
    
14.         v, i, c = 0, 0, ''
    
15.         if not heap:
    
16.             v, i, c = tmp
    
17.             t = i + 1
    
18.         else:
    
19.             v, i, c = heappop(heap)
    
20.             t += 1
    
21.         if v + 1 < 0:
    
22.             heappush(heap, (v + 1, t + k, c))
    
23.         lst.append(c)
    
24.         for ca in cache:
    
25.             if ca[2] != c:
    
26.                 heappush(heap, ca)
    
27.     print(lst)
    
28.     return t

复制代码

楼主啥时候面的啊??...比我的难好多- -

leixiang5 发表于 2016-10-21 22:54
楼主啥时候面的啊??...比我的难好多- -

群主这么晚还不就寝啊

第三轮task schedule第一问你的space complexity是多少? 我用的hashmap的方法做space compexity是O(n) interviewer说有更optimal的 但是我没想出来 时间也不多了

samuelling 发表于 2016-10-22 15:16
群主这么晚还不就寝啊

在加州 有时差的

非常感谢

楼主可以讲下第一题第四题怎么做的吗？

求问楼主第一题不用dp能咋做？？backtrack？

chestnut9919 发表于 2016-10-23 05:57
求问楼主第一题不用dp能咋做？？backtrack？

嗯对，字数字数

leixiang5 发表于 2016-10-22 14:54
楼主啥时候面的啊??...比我的难好多- -

本月初，字数字数