LinkedIn System&Infra 两轮电面

tigermlt

xinxinzhenbang 发表于 2017-12-1 13:06
羡慕楼主可以做两个题，我只做一题真是凉凉。

我第一轮也只做了一道题，感觉对面印度小哥全程装傻。不管我怎么解释都说不懂，然后跑了两个test case还再不停地写test case，感觉就是想找一个让我的代码不work。然后各种浪费时间。遇到这样的人我也很无奈。。。

tomdarling

请问楼主 lc漆撕溜是哪个题呀？

asdwb

wxl3691 发表于 2017-12-1 13:29
其实collabedit真的是好东西，代码不管对错都可以上，以后skype集成codepad成功后，就是对着视频看脸写代码 ...

fb 面试用的codepad也是不能编译的

wxl3691

asdwb 发表于 2017-12-3 23:37
fb 面试用的codepad也是不能编译的

那个codepad感觉面试官那边是可以测的，codepad有这功能。。。。。。。

asdwb

wxl3691 发表于 2017-12-4 02:40
那个codepad感觉面试官那边是可以测的，codepad有这功能。。。。。。。

进fb的那个界面第一句话就是不能编译只是share的文档，面的时候很随意，随便给了个函数的接口，给样例都不打注释，想到啥直接写就好。

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;
}

复制代码

123的树

楼主，746是哪一题呀？还有这个岗位有问一些os之类的问题吗

xinxinzhenbang

老哥能不能分享下timeline啊

zhangxiangyu7

123的树发表于 2017-12-4 09:24
楼主，746是哪一题呀？还有这个岗位有问一些os之类的问题吗

笑了楼主指的是期食溜我一上来也蒙住了

yikehongxin

楼主，请问有总结好的面经么？如果有，能开个帖子发出来么？我给你加米

LinkedIn System&Infra 两轮电面

评分

浏览过的版块