回复: 34
跳转到指定楼层
上一主题 下一主题
收起左侧

脸书onsite

全局:

2016(10-12月) 码农类General 硕士 全职@meta - 内推 - Onsite  | | Pass | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
  • 利扣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


评分

参与人数 2大米 +205 收起 理由
admin + 200
leixiang5 + 5 欢迎来一亩三分地论坛!

查看全部评分


上一篇:Interactive brokers Java OA 90min版
下一篇:LiveRamp Intern OA

本帖被以下淘专辑推荐:

推荐
mengmeng88717 2016-10-28 10:01:01 | 只看该作者
全局:
第四题的思路
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)
回复

使用道具 举报

推荐
Badger96 2016-10-25 13:18:55 | 只看该作者
全局:
试写了一下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();
    }
回复

使用道具 举报

推荐
jacky841102 2016-10-30 19:59:59 | 只看该作者
全局:
第三题类似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-22 14:54:01 | 只看该作者
全局:
楼主啥时候面的啊??...比我的难好多- -
回复

使用道具 举报

🔗
samuelling 2016-10-22 15:16:41 | 只看该作者
全局:
leixiang5 发表于 2016-10-21 22:54
楼主啥时候面的啊??...比我的难好多- -

群主这么晚还不就寝啊
回复

使用道具 举报

🔗
hrl1991 2016-10-22 15:51:01 | 只看该作者
全局:
第三轮task schedule第一问你的space complexity是多少? 我用的hashmap的方法做space compexity是O(n) interviewer说有更optimal的 但是我没想出来 时间也不多了
回复

使用道具 举报

🔗
leixiang5 2016-10-22 21:06:40 | 只看该作者
全局:
samuelling 发表于 2016-10-22 15:16
群主这么晚还不就寝啊

在加州 有时差的
回复

使用道具 举报

🔗
wwbin_l 2016-10-22 22:09:25 | 只看该作者
本楼:
全局:
非常感谢
回复

使用道具 举报

🔗
steveguang 2016-10-22 22:54:46 | 只看该作者
全局:
楼主可以讲下第一题第四题怎么做的吗?
回复

使用道具 举报

🔗
chestnut9919 2016-10-23 05:57:10 | 只看该作者
全局:
求问楼主第一题不用dp能咋做??backtrack?
回复

使用道具 举报

🔗
 楼主| yzlwjs 2016-10-24 01:24:03 | 只看该作者
全局:
chestnut9919 发表于 2016-10-23 05:57
求问楼主第一题不用dp能咋做??backtrack?

嗯对,字数字数
回复

使用道具 举报

🔗
 楼主| yzlwjs 2016-10-24 01:24:25 | 只看该作者
全局:
leixiang5 发表于 2016-10-22 14:54
楼主啥时候面的啊??...比我的难好多- -

本月初,字数字数
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表