📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

打它砖 店面

全局:

2023(10-12月) 码农类General 硕士 全职@databricks - 猎头 - 技术电面  | 🙁 Negative 😣 Hard | Fail | 在职跳槽

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

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

x
打它砖 挂经

上周面试打他转。题目是 snapshotSet

interface SnapShotSet<T> {
  void add( T value);
  void remove(T value);
  boolean contains();
  Iterator<T> iterator();
}

call 了 intera
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
rator 的问题。但是 空间复杂度更高啊。因为interviewer 说我的空间复杂度高,我就没提这个solution。不会是要这样解吧?问他能不能多个iterator。他说一个。但是应该问他第二步是不是多个iterator。

总之很怪,不知道他要考啥。

评分

参与人数 1大米 +10 收起 理由
匿名用户-PLUFA + 10 欢迎分享你知道的情况,会给更多大米奖励!

查看全部评分


上一篇:思科码农NG OA
下一篇:数据狗电面
🔗
brucewill1 2023-10-10 04:33:38 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +1 收起 理由
新用户-4587 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

地里匿名用户
🔗
匿名用户-T3WQX  2023-10-26 08:40:23
请教一下LZ 面的是staff 么? 是architecture 面试么?
回复

使用道具 举报

🔗
taucross 2023-10-28 07:42:42 | 只看该作者
全局:
本帖最后由 taucross 于 2023-10-27 16:44 编辑

跟 brucewill1 一样的思路,用C++实现了一遍。简单起见,每个add和remove都会increment snapshot version。
  1. struct Node {
  2.   int value;
  3.   vector<int> snapshots;
  4. };

  5. class Iterator {
  6. public:
  7.   Iterator(list<Node>::iterator begin, list<Node>::iterator end, int version)
  8.     : it(begin), end(end), version(version) {}

  9.   // is_end() == false
  10.   int ref() { return it->value; }

  11.   // is_end() == false
  12.   void advance() { it++; }

  13.   bool is_end() {
  14.     next_valid();
  15.     return it == end;
  16.   }

  17. private:
  18.   void next_valid() {
  19.     while (it != end) {
  20.       vector<int>::iterator vi = ranges::upper_bound(it->snapshots, version);
  21.       if ((vi - it->snapshots.begin()) % 2 == 1) {
  22.         break;
  23.       }
  24.       it++;
  25.     }
  26.     return;
  27.   }

  28.   list<Node>::iterator it;
  29.   list<Node>::iterator end;
  30.   int version;
  31. };

  32. class SnapshotSet {
  33. public:
  34.   SnapshotSet() : version(0) {}

  35.   void add(int value) {
  36.     if (!m.contains(value)) {
  37.       Node node = {value, {}};
  38.       nodes.push_back(node);
  39.       m[value] = prev(nodes.end());
  40.     }
  41.     // already added.
  42.     if (m[value]->snapshots.size() % 2 == 1) return;
  43.     m[value]->snapshots.push_back(version++);
  44.   }

  45.   void remove(int value) {
  46.     if (!m.contains(value)) return;
  47.     // already removed.
  48.     if (m[value]->snapshots.size() % 2 == 0) return;
  49.     m[value]->snapshots.push_back(version++);
  50.   }

  51.   bool contains(int value) {
  52.     if (!m.contains(value)) return false;
  53.     return m[value]->snapshots.size() % 2 == 1;
  54.   }

  55.   Iterator iterator() {
  56.     return Iterator(nodes.begin(), nodes.end(), version-1);
  57.   }

  58. private:
  59.   list<Node> nodes;
  60.   unordered_map<int, list<Node>::iterator> m;
  61.   int version;
  62. };
复制代码
回复

使用道具 举报

🔗
fishcrab 2024-8-16 12:57:13 | 只看该作者
全局:
楼上的大家好聪明啊,按奇偶判定时间复杂度是最低的。
我觉得treemap可以的,但不要存每一个element,存的是version和action的对应关系,每次找的时候floor entry 看前面那个action是什么来判断element在不在。
写了一遍代码量好大啊
回复

使用道具 举报

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

本版积分规则

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