注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
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;
}
}; |