回复: 1
收起左侧

PureStorage面经

匿名用户-XSEKL  2025-1-15 08:32:52
本楼:   👍  0
0%
0%
0   👎

2025(1-3月) 码农类General 硕士 全职@Pure Storage - Other - 技术电面  | 😐 Neutral 😣 HardWaitList | 在职跳槽

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

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

x
本帖最后由 匿名 于 2025-1-14 16:40 编辑

Just finished the Phone Screen.


Question: O(1) Set.


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

is corrupted
https://docs.google.com/document/d/1wHGs135aODXjuyEN5-tz8sCDb0iCefyQX2HHbToAz8c/edit?tab=t.0


The most difficulty of the O(1) is the clear() part.


Didn't do too well during the phone screen cause I was stuck in implementing O(1) clear() for a while. I eventually came out the idea to bump up the valid threshold everytime a clear() is called. I think it met the requirement of interview question however I do not satisfy with that and consider myself blew it.


My implementation:
int keys[N];
int currentSize = 0;
int VALID_THRESHOLD = 0;


bool lookup(int key)
{
    int offset = valid[ x ];
    if ( offset >= currentSize ) return false;
    if ( keys[ offset ] < VALID_THRESHOLD || keys[ offset ] == -1 ) return false;
    return true;
}


void clear()
{
    currentSize = 0;
    VALID_THRESHOLD += N;
}


Though it is similar to the versioning method which ChatGPT suggested. And I think versioning is much more better version.


Good luck everyone!


--
ChatGPT code:
#include <vector>
#include <stdexcept>

class UnorderedSet {
private:
    std::vector<int> bitmap;  // Tracks the "version" of each key
    int currentVersion;       // Tracks the current version of the set
    size_t size;              // Number of elements currently in the set

public:
    // Constructor: initializes the set with a given key range
    UnorderedSet(size_t range) : bitmap(range, 0), currentVersion(0), size(0) {}

    // Inserts a key into the set
    void insert(int key) {
        if (key < 0 || key >= bitmap.size()) {
            throw std::out_of_range("Key out of range");
        }
        if (bitmap[key] != currentVersion) { // Key is not in the current set
            bitmap[key] = currentVersion;
            ++size;
        }
    }

    // Removes a key from the set
    void remove(int key) {
        if (key < 0 || key >= bitmap.size()) {
            throw std::out_of_range("Key out of range");
        }
        if (bitmap[key] == currentVersion) { // Key is in the current set
            bitmap[key] = currentVersion - 1; // Mark as "removed"
            --size;
        }
    }

    // Checks if a key is present in the set
    bool contains(int key) const {
        if (key < 0 || key >= bitmap.size()) {
            throw std::out_of_range("Key out of range");
        }
        return bitmap[key] == currentVersion;
    }

    // Clears all keys from the set
    void clear() {
        ++currentVersion; // Effectively "resets" the set
        size = 0;
    }

    // Returns the number of elements in the set
    size_t getSize() const {
        return size;
    }
};

上一篇:MongoDB HR 筛选挂经
下一篇:黑车SWE PhD OA
本楼:   👍  0
0%
0%
0   👎
全局:   13
81%
19%
3
感谢楼主分享!
回复

使用道具 举报

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

本版积分规则

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