🎁 黑五活动已开始: VIP通行证1年立减$55 蓝莓最高减$25 🎁
查看: 4505|回复: 17
收起左侧

数据砖店面

|只看干货
匿名用户-5C9  2022-2-8 11:12:36 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2022(1-3月) 码农类General 硕士 全职@databricks - 猎头 - 技术电面  | 😐 Neutral 😐 AverageFail | 在职跳槽

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

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

x
在地里没见过,po 出来帮助后面的同学。其实题不难。但是自己脑子浆糊了

Assume we have some static, globally available reference string
// ref_string = ['a', 'b', 'c', '1', '2', '3', '4', 'a', 'b', 'c', 'd', '!'] == "abc1234abcd!"
//    (index) =   0    1    2    3    4    5    6    7    8    9    10   11

// Using the reference string, we want to compress a source string
// src_string = ['a', 'b', 'c', 'd', '1', '2', '3'] == "abcd123"
//    (index) =   0    1    2    3    4    5    6


// A cover represents a compression of src_string relative to ref_string and is
// comprised of (inclusive, exlcusive) indicies-pairs called "blocks". For example,
// block1 = (7, 11) => "abcd"

// For example, one valid cover for src_string:
// cov1 = [(7, 11), (3, 6)] => ["abcd", "123"]

// Another valid cover for src_string:
// cov2 = [(7, 10), (10, 11), (3, 6)] => ["abc", "d", "123"]


// Implement delete(cover, index)
// Given a valid cover and index of S, return a valid cover for S[
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
d", "123"]

// cov2 is NOT maximal since ("abc" + "d") or "abcd" is in ref_string
// cov2 = [(7, 10), (10, 11), (3, 6)] => ["abc", "d", "123"]

// delete(cov1, 3) = [(7,10), (3,6)}] = "abc""123" = (0,6)

评分

参与人数 6大米 +17 收起 理由
rfnepku + 1 给你点个赞!
bluejay + 1 给你点个赞!
luofeidream + 1 很有用的信息!
清道神君 + 12
wb1231 + 1 很有用的信息!

查看全部评分


上一篇:bill.com oa
下一篇:黑车面经-战略金融分析
地里匿名用户
匿名用户-D7B  2022-4-13 09:33:50
本楼: 👍   100% (4)
 
 
0% (0)   👎
  1. private List<Pair> stringToMaxCover(String refString, String str) {
  2.         Map<Character, List<Integer>> charIndices = new HashMap<>();
  3.         char[] refArray = refString.toCharArray();
  4.         for (int i = 0; i < refArray.length; i++) {
  5.             charIndices.computeIfAbsent(refArray[i], e -> new ArrayList<>()).add(i);
  6.         }
  7.         Queue<List<Pair>> queue = new LinkedList<>();
  8.         char[] strArray = str.toCharArray();
  9.         for (Integer i : charIndices.get(strArray[0])) {
  10.             List<Pair> l = new ArrayList<>();
  11.             l.add(new Pair(i, i+1));
  12.             queue.offer(l);
  13.         }
  14.         int cur = 1;
  15.         while (!queue.isEmpty() && cur < strArray.length) {
  16.             int size = queue.size();
  17.             for (int i = 0; i < size; i++) {
  18.                 List<Pair> cover = queue.poll();
  19.                 for (int curIndex : charIndices.get(strArray[cur])) {
  20.                     // copy list
  21.                     List<Pair> copy = new ArrayList<>(cover);
  22.                     Pair last = copy.get(copy.size() - 1);
  23.                     if (last.e == curIndex) {
  24.                         last.e = curIndex + 1;
  25.                     } else {
  26.                         copy.add(new Pair(curIndex, curIndex+1));
  27.                     }
  28.                     queue.offer(copy);
  29.                 }
  30.             }
  31.             ++cur;
  32.         }
  33.         // poll all solutions in queue and return the shortest
  34.         List<Pair> res = null;
  35.         int shortest = Integer.MAX_VALUE;
  36.         while (!queue.isEmpty()) {
  37.             List<Pair> cover = queue.poll();
  38.             if (cover.size() < shortest) {
  39.                 res = cover;
  40.                 shortest = cover.size();
  41.             }
  42.         }
  43.         return res;
  44.     }
复制代码
返回最优解的方法来了啊,觉得有用加点米啦

评分

参与人数 3大米 +3 收起 理由
chipmunks123 + 1 很有用的信息!
gmame + 1 给你点个赞!
落落落 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

地里匿名用户
匿名用户-671  2022-2-21 13:59:33
本楼: 👍   100% (2)
 
 
0% (0)   👎
匿名者 发表于 2022-2-8 09:07
So the first question is to implement delete(cover, index), right?

I do not understand the follow ...

天竺人⚠️
回复

使用道具 举报

小亩_418b455 2022-2-8 14:04:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (125)
 
 
33% (62)    👎
LZ面的哪个level?
回复

使用道具 举报

xiangcong 2022-2-8 16:34:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (52)
 
 
0% (0)    👎
好奇LZ是怎么记下完整的题的
回复

使用道具 举报

地里匿名用户
匿名用户-5C9  2022-2-9 00:59:34
本楼: 👍   0% (0)
 
 
0% (0)   👎
ctrl c + ctrl v

Senior level
回复

使用道具 举报

地里匿名用户
匿名用户-46A  2022-2-9 01:07:43
本楼: 👍   0% (0)
 
 
0% (0)   👎
So the first question is to implement delete(cover, index), right?

I do not understand the follow-up though:
- Can you elaborate on the definition of maximal cover? Why isn't "abcd!abc1234" is a maximal cover, for instance?
- What does delete(cover, index) have to do with a maximal cover? Finding a maximal cover should independent of delete(cover, index). no?

(Rice added)
回复

使用道具 举报

地里匿名用户
匿名用户-BF2  2022-2-9 14:37:57
本楼: 👍   0% (0)
 
 
0% (0)   👎
匿名者 发表于 2022-2-8 09:07
So the first question is to implement delete(cover, index), right?

I do not understand the follow ...

每次看到这个rice added,就知道是硬度人来偷面筋了
回复

使用道具 举报

地里匿名用户
匿名用户-2DD  2022-2-13 13:12:53
本楼: 👍   0% (0)
 
 
0% (0)   👎
感谢,加米了,这题主要是题目长,面试的时候看的头大。。
回复

使用道具 举报

威猛的小老虎 2022-2-27 16:26:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (118)
 
 
2% (3)    👎
我感觉好像我没有理解题目的意思- -,第一问delete里面,其实他已经给定了cover和index,所以其实你不用自己选到底是哪个cover对吗,就其实第一问和原来的string没有关系,只是在给定的cover里面删掉一个数对吧;第二问同样的也是给定了cover是吗, 那删掉一个index其实答案也是唯一的?是不是我们只能判断他是不是max cover而不是一定能Return max cover?还是我们自己需要选一个cover的分配方式使得他删掉一个数是max cover呀
回复

使用道具 举报

babaffalo 2022-3-5 08:56:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
威猛的小老虎 发表于 2022-2-27 00:26
我感觉好像我没有理解题目的意思- -,第一问delete里面,其实他已经给定了cover和index,所以其实你不用自 ...

follow up 我的理解是先delete delete完之后有可能有几个区间是可以merge的,所以再merge一下interval就可以了。不知道make sense不。

评分

参与人数 1大米 +1 收起 理由
威猛的小老虎 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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