LinkedIn System&Infra 两轮电面

tigermlt

注册一亩三分地论坛，查看更多干货！

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

x

第一轮：
collabedit状况百出，时不时就502 gateway not found。面的题是lc漆撕溜。面试官是印度人，跟他讲了思路（sliding window）他说最后一部分没有太听懂，然后先写代码。我彼边解释边写代码，写完之后本以为面试官对着代码可以看懂，结果竟然还是不懂。。。一开始我以为面试官只是在考察我对sliding window的理解，后来发现他是真的不懂。一

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

用户操作完以后会自动调用finish函数，将数组写入文件。

完全不知道怎么写，当时准备面经的时候也把这题给弃了。求会的人发个答案吧。

然后我直接跟面试官说我不会，就换成了lc散吧零，秒

两轮感觉都不是很好，发跪经一篇。

magicsets

1024 block的这道题目其实是一个比较简化的buffer manager组件，其中用来标记各个block有没有使用过的那部分数据一般称为meta data。

meta data使用什么数据结构其实可以比较灵活，但是最关键的一点是meta data本身也需要作为file的一部分能够被存储到disk上 —— 否则你下次读取那个文件就不知道哪些block被用过了。

很多（数据库）系统中，出于性能考虑，meta data都是直接映射到block上的，也就是使用block的memory定义数据结构——这需要手动进行内存管理——也就是你不能用malloc/new或是std::vector/std::list之类的去定义meta data。

另一个选项就是使用C++标准库中的数据结构（Java类同），然后在save/load的时候serialize/deserialize meta data。

这里贴一份样例代码，都是使用block memory进行手动内存管理的，有三种实现：
(1) bool 数组
(2) bit map
(3) 用一个recycle数组记录未被使用的block

其中(1)和(2)的allocate都是O(n)时间，(2)由于使用了builtin_clz所以会比(1)快很多——但是因为只有1024个blocks，所以也无所谓了...

(3)的allocate是O(1)时间，但是meta data耗用的空间会大一点（3个blocks）

#include <array>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory>
#include <stdexcept>
constexpr std::size_t kBlockSize = 1024;
constexpr std::size_t kNumBlocks = 1024;
using BlockID = std::size_t;
using Block = std::array<char, kBlockSize>;
// abstract class
class StorageManagerInterface {
public:
virtual BlockID allocateNewBlock() = 0;
virtual void writeData(const BlockID block_id, const void *data) = 0;
virtual void deleteBlock(const BlockID block_id) = 0;
};
// 三种实现: bool array, bit map, free list
// -----------------------------------------------------------------------------
// 1. bool array
// -----------------------------------------------------------------------------
class ByteArrayMetaData {
public:
ByteArrayMetaData(void *memory)
: status_(static_cast<bool*>(memory)),
capacity_(kNumBlocks - 1) {
}
std::size_t getNumOfBlocksUsed() const {
return 1;
}
BlockID alloc() {
for (std::size_t i = 0; i < capacity_; ++i) {
if (!status_[i]) {
status_[i] = true;
return i;
}
}
throw std::runtime_error("Out of blocks");
}
void free(const BlockID block_id) {
status_[block_id] = false;
}
private:
bool *status_;
const std::size_t capacity_;
};
// 给bit map使用的一个辅助函数
template <typename T>
inline int LeadingZeroCount(T word);
template <>
inline int LeadingZeroCount<unsigned>(unsigned word) {
return __builtin_clz(word);
}
template <>
inline int LeadingZeroCount<unsigned long>(unsigned long word) {
return __builtin_clzl(word);
}
template <>
inline int LeadingZeroCount<unsigned long long>(unsigned long long word) {
return __builtin_clzll(word);
}
// -----------------------------------------------------------------------------
// 2. bit map
// -----------------------------------------------------------------------------
class BitVectorMetaData {
public:
BitVectorMetaData(void *memory)
: num_bits_(kNumBlocks - 1),
data_(static_cast<std::size_t*>(memory)),
data_size_((num_bits_ >> kHigherOrderShift) +
(num_bits_ & kLowerOrderMask ? 1 : 0)) {
}
std::size_t getNumOfBlocksUsed() const {
return 1;
}
BlockID alloc() {
BlockID ret = num_bits_;
for (std::size_t i = 0; i < data_size_; ++i) {
const std::size_t code = ~data_[i];
if (code) {
const std::size_t offset = LeadingZeroCount<std::size_t>(code);
data_[i] |= kTopBit >> offset;
ret = (i << kHigherOrderShift) | offset;
break;
}
}
if (ret < num_bits_) {
return ret;
}
throw std::runtime_error("Out of blocks");
}
void free(const BlockID block_id) {
data_[block_id >> kHigherOrderShift] &= ~(kTopBit >> (block_id & kLowerOrderMask));
}
private:
static constexpr std::size_t kLowerOrderMask = (sizeof(std::size_t) << 3) - 1;
static constexpr std::size_t kHigherOrderShift = sizeof(std::size_t) == 4 ? 5 : 6;
static constexpr std::size_t kTopBit = static_cast<std::size_t>(1) << kLowerOrderMask;
const std::size_t num_bits_;
std::size_t *data_;
const std::size_t data_size_;
};
// 3. free list
class FreeListMetaData {
public:
FreeListMetaData(void *memory)
: capacity_(kNumBlocks - CalculateNumBlocksUsed()) {
alloc_size_ = reinterpret_cast<std::uint16_t*>(memory);
recycle_size_ = alloc_size_ + 1;
recycle_list_ = recycle_size_ + 1;
}
std::size_t getNumOfBlocksUsed() const {
return CalculateNumBlocksUsed();
}
BlockID alloc() {
if (*recycle_size_ > 0) {
return recycle_list_[--(*recycle_size_)];
}
if (*alloc_size_ < capacity_) {
return (*alloc_size_)++;
}
throw std::runtime_error("Out of blocks");
}
void free(const BlockID block_id) {
recycle_list_[(*recycle_size_)++] = block_id;
}
private:
static inline std::size_t CalculateNumBlocksUsed() {
const std::size_t total_bytes =
sizeof(std::uint16_t) + // alloc_size_
sizeof(std::uint16_t) + // recycle_size_
sizeof(std::uint16_t) * kNumBlocks; // recycle_list_
return (total_bytes + kBlockSize - 1) / kBlockSize;
}
std::uint16_t *alloc_size_;
std::uint16_t *recycle_size_;
std::uint16_t *recycle_list_;
const std::size_t capacity_;
};
template <typename MetaData>
class StorageManager : public StorageManagerInterface {
public:
StorageManager() {
// 读取文件 -- 这里简化为malloc + 置0
stream_ = std::malloc(sizeof(Block) * kNumBlocks);
std::memset(stream_, 0, kNumBlocks * kBlockSize);
// 初始化meta data
meta_data_ = std::make_unique<MetaData>(stream_);
// 定位到数据区域
blocks_ = static_cast<Block*>(stream_) + meta_data_->getNumOfBlocksUsed();
}
BlockID allocateNewBlock() override {
return meta_data_->alloc();
}
void writeData(const BlockID block_id, const void *data) override {
std::memcpy(blocks_ + block_id, data, kBlockSize);
}
void deleteBlock(const BlockID block_id) override {
meta_data_->free(block_id);
}
private:
void *stream_;
std::unique_ptr<MetaData> meta_data_;
Block *blocks_;
};
int main(int argc, char *argv[]) {
std::unique_ptr<StorageManagerInterface> storage_manager;
storage_manager = std::make_unique<StorageManager<ByteArrayMetaData>>();
// storage_manager = std::make_unique<StorageManager<BitVectorMetaData>>();
// storage_manager = std::make_unique<StorageManager<FreeListMetaData>>();
BlockID b1 = storage_manager->allocateNewBlock();
std::cout << "alloc b1 = " << b1 << "\n";
BlockID b2 = storage_manager->allocateNewBlock();
std::cout << "alloc b2 = " << b2 << "\n";
BlockID b3 = storage_manager->allocateNewBlock();
std::cout << "alloc b3 = " << b3 << "\n";
storage_manager->deleteBlock(b2);
std::cout << "delete b2\n";
BlockID b4 = storage_manager->allocateNewBlock();
std::cout << "alloc b4 = " << b4 << "\n";
BlockID b5 = storage_manager->allocateNewBlock();
std::cout << "alloc b5 = " << b5 << "\n";
return 0;
}

复制代码

MacJordan

第一题746吗？。。没有这题呀。。漆撕溜代指新题吗

xinxinzhenbang

我的colabet也出了问题。
这个题据说是要把第一个block做成bitset, 每个byte标志一个block是否可用。
但我个人觉得这题更好的做法是每个block有header指向下一个free block, 类似15213的malloc lab。

xinxinzhenbang

xinxinzhenbang 发表于 2017-12-1 13:04
我的colabet也出了问题。
这个题据说是要把第一个block做成bitset, 每个byte标志一个block是否可用。
但 ...

羡慕楼主可以做两个题，我只做一题真是凉凉。

ivanyang

xinxinzhenbang 发表于 2017-12-1 13:04
我的colabet也出了问题。
这个题据说是要把第一个block做成bitset, 每个byte标志一个block是否可用。
但 ...

collabedit 是真的垃圾.... 我面试的时候就没连上过... 直接换了Google doc...

xinxinzhenbang

ivanyang 发表于 2017-12-1 13:14
collabedit 是真的垃圾.... 我面试的时候就没连上过... 直接换了Google doc...

我也是中途换了google doc

wxl3691

其实collabedit真的是好东西，代码不管对错都可以上，以后skype集成codepad成功后，就是对着视频看脸写代码还要编译通过，想想都觉得刺激。。。。。。。。。。。。。。。。。。

valleyvalley

我面的时候第一轮collabedit一直不sync..然后面试官直接开了一个codepad给我，然后第二轮collabedit直接down掉了打不开。。。又面试官自己开的codepad...codepad这么好用，不知道为什么要用collabedit。。。不过面试官说面完hr会找他们要collabedit的使用感受，估计被淘汰指日可待

F4bwDP6a6WXkB

1024 block 感觉和lc散吧零有点类似吧。能不能hashmap + array来解决，array里面存block的地址。每次删除一个block把array最后一个的数据移过来，然后把size - 1. 这是一种办法还有一种就是不swap数据，每次写的时候遍历一遍所有的block找到第一个为空的。不知道题意我是否理解正确了。

tigermlt

xinxinzhenbang 发表于 2017-12-1 13:04
我的colabet也出了问题。
这个题据说是要把第一个block做成bitset, 每个byte标志一个block是否可用。
但 ...

这题有写好的代码可以参考一下吗？

LinkedIn System&Infra 两轮电面

注册一亩三分地论坛，查看更多干货！

相关帖子

评分

浏览过的版块