CPT挂靠抽中H1B后被RFE

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 265|回复: 6
收起左侧

纯存新题(?)昂赛

[复制链接] |试试Instant~
我的人缘0
tscorpio42 发表于 2018-11-10 12:08:33 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩

2019(10-12月) 码农类General 本科 全职@PureStorage - 校园招聘会 - Onsite  | Other | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
第一轮问的buddy system bitmap。经典。
第二轮问的画圆。不知怎么最后和面试官聊到了一个很压抑的话题。
第三轮问的是一个concurrency问题。
游客,本帖隐藏的内容需要积分高于 200 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.



补充内容 (2018-11-10 12:09):
新人, 求米

评分

参与人数 2大米 +10 收起 理由
dmtalen + 5 很有用的信息!
gggpps + 5 欢迎来一亩三分地论坛!

查看全部评分


上一篇:Google OA
下一篇:高盛hirevue面筋
我的人缘0
kiawe 发表于 2018-11-10 12:12:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
get_id 也是面經題
回复

使用道具 举报

我的人缘0
 楼主| tscorpio42 发表于 2018-11-10 12:14:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
kiawe 发表于 2018-11-10 12:12
get_id 也是面經題

准备的时候没看到。哭了T.T

补充内容 (2018-11-10 12:14):
以为是新的。我错了
回复

使用道具 举报

我的人缘0
kiawe 发表于 2018-11-10 12:16:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (22)
 
 
4% (1)  踩
tscorpio42 发表于 2018-11-10 12:14
准备的时候没看到。哭了T.T

补充内容 (2018-11-10 12:14):

我之前面p家(不是給karat面)也是沒看到面經題... ==“
回复

使用道具 举报

我的人缘0
gggpps 发表于 2018-11-10 12:30:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (51)
 
 
5% (3)  踩
请问画圆是什么题,谢谢
回复

使用道具 举报

我的人缘0
 楼主| tscorpio42 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
gggpps 发表于 2018-11-10 12:30
请问画圆是什么题,谢谢

Given a function dot that draws x,y on a 2d grid, how would you draw a circle?
回复

使用道具 举报

我的人缘0
magicsets 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (337)
 
 
1% (6)  踩
第三题写了份C++的参考代码,主要就是用一个“批发商”producer线程调用get_ids()批量获得id并且缓存起来,然后其他consumer线程从这个批发商这里一个batch一个batch的拿

linux下编译时要加参数 -std=c++14 -pthread

[C++] 纯文本查看 复制代码
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstddef>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <mutex>
#include <queue>
#include <thread>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std::chrono_literals;

// Produce/Consumer阻塞队列
template <typename T>
class ThreadSafeQueue {
 public:
  ThreadSafeQueue()
      : num_waiters_(0) {}

  std::size_t size() const {
    std::lock_guard<std::mutex> lock(queue_mutex_);
    return internal_queue_.size();
  }

  template <typename U>
  void push(U &&element) {
    std::lock_guard<std::mutex> lock(queue_mutex_);
    internal_queue_.emplace(std::forward<U>(element));
    queue_nonempty_condition_.notify_one();
  }

  T popOne() {
    std::unique_lock<std::mutex> lock(queue_mutex_);
    if (internal_queue_.empty()) {
      num_waiters_.fetch_add(1, std::memory_order_relaxed);
      queue_nonempty_condition_.wait(
          lock, [&]{ return !internal_queue_.empty(); });
      num_waiters_.fetch_sub(1, std::memory_order_relaxed);
    }
    T popped_value(std::move(internal_queue_.front()));
    internal_queue_.pop();
    lock.unlock();
    return popped_value;
  }

 private:
  std::queue<T> internal_queue_;
  mutable std::mutex queue_mutex_;
  std::condition_variable queue_nonempty_condition_;
  std::atomic<std::size_t> num_waiters_;
};

// 这个类是用来让多线程的输出不混在一起的
class SyncStream {
 public:
  explicit SyncStream(std::ostream &os)
      : os_(os), lock_(GetMutex(&os)) {}

  template <typename T>
  inline SyncStream& operator<<(const T &value) {
    os_ << value;
    return *this;
  }

 private:
  std::ostream &os_;
  std::lock_guard<std::mutex> lock_;

  static std::unordered_map<std::ostream*, std::mutex>& MutexTable() {
    static std::unordered_map<std::ostream*, std::mutex> mtable;
    return mtable;
  }

  static std::mutex& MutexTableMutex() {
    static std::mutex mtable_mutex;
    return mtable_mutex;
  }

  static std::mutex& GetMutex(std::ostream *os) {
    std::lock_guard<std::mutex> lock(MutexTableMutex());
    return MutexTable()[os];
  }
};

// 简单的计时器
class Timer {
 public:
  void reset() {
    zero_time_ = clock::now();
  }

  double getCurrentTime() const {
    return std::chrono::duration<double>(clock::now() - zero_time_).count();
  }

 private:
  using clock = std::chrono::high_resolution_clock;
  clock::time_point zero_time_;
};

static Timer timer;


using IdBatch = std::vector<int>;

// 题目提供的接口
namespace api {

IdBatch* GetIds(const std::size_t num) {
  static int id_counter = 0;
  std::unique_ptr<IdBatch> ids = std::make_unique<IdBatch>();
  ids->reserve(num);
  for (int i = 0; i < num; ++i) {
    ids->emplace_back(++id_counter);
  }
  // 等待1秒
  std::this_thread::sleep_for(1s);
  return ids.release();
}

};

// “批发商”服务
class Wholesaler {
 public:
  Wholesaler(const std::size_t min_batch_size,
             const std::size_t max_num_retailers)
      : batch_size_(min_batch_size * (1 + kBatchMargin)),
        pool_size_(max_num_retailers * (1 + kPoolMargin)) {}

  IdBatch* allocateIdBatch() {
    return queue_.popOne().release();
  }

  void startService() {
    halt_.store(false);
    while (!halt_.load()) {
      if (queue_.size() < pool_size_) {
        const std::size_t num_batches = pool_size_ - queue_.size();
        const std::size_t num_ids = num_batches * batch_size_;
        std::unique_ptr<IdBatch> batch(api::GetIds(batch_size_ * num_batches));
        SyncStream(std::cout) << "[wholesaler @"
                              << std::fixed << std::setprecision(2)
                              << timer.getCurrentTime()
                              << "s] One group of " << num_ids
                              << " ids has been allocated using the "
                              << "GetIds() api.\n";
        // 这里多做了一次拷贝,更好的方法是利用std::shared_ptr创建IdBatchView,不过代码
        // 太复杂就不写了
        for (std::size_t i = 0; i < num_batches; ++i) {
          auto sub_batch = std::make_unique<IdBatch>(batch_size_);
          std::memcpy(sub_batch->data(),
                      batch->data() + (i * batch_size_),
                      batch_size_ * sizeof(IdBatch::value_type));
          queue_.push(std::move(sub_batch));
        }
      } else {
        std::this_thread::sleep_for(0.5s);
      }
    }
  }

  void stopService() {
    halt_.store(true);
  }

 private:
  // 额外多分配一些ID以消除response time spike的可能性
  static constexpr double kBatchMargin = 0.2;
  static constexpr double kPoolMargin = 1.0;

  const std::size_t batch_size_;
  const std::size_t pool_size_;
  ThreadSafeQueue<std::unique_ptr<IdBatch>> queue_;
  std::atomic<bool> halt_;
};

// “零售商”服务
class Retailer {
 public:
  explicit Retailer(Wholesaler *wholesaler)
      : wholesaler_(wholesaler) {}

  int getId() {
    if (batch_ == nullptr || batch_it_ == batch_->end()) {
      batch_.reset(wholesaler_->allocateIdBatch());
      batch_it_ = batch_->begin();
    }
    return *(batch_it_++);
  }

 private:
  Wholesaler *wholesaler_;
  std::unique_ptr<IdBatch> batch_;
  IdBatch::iterator batch_it_;
};

int main(int argc, char *argv[]) {
  // 这个按原题是调到1000,不过输出就快得没法看了
  const std::size_t requests_per_second = 4;

  const std::size_t us_per_request = 1000000 / requests_per_second;

  // 同时需要GetId的线程数量,原题应该只需要单个线程,不过这里我们允许多线程
  const std::size_t num_threads = 2;

  // 运行“批发商”服务..
  Wholesaler wholesaler(requests_per_second, num_threads);
  std::thread service_thread([&wholesaler] {
    wholesaler.startService();
  });

  // 开始计时
  timer.reset();

  // 等待一秒让批发商从工厂搬运第一组id
  std::this_thread::sleep_for(1s);

  // 运行多个client线程
  std::vector<std::unique_ptr<std::thread>> clients;
  for (std::size_t i = 0; i < num_threads; ++i) {
    clients.emplace_back(std::make_unique<std::thread>([i,
                                                        us_per_request,
                                                        &wholesaler] {
      Retailer retailer(&wholesaler);
      while (true) {
        SyncStream(std::cout) << "[client " << static_cast<char>('A' + i)
                              << " @"
                              << std::fixed << std::setprecision(2)
                              << timer.getCurrentTime()
                              << "s] allocated id = "
                              << retailer.getId() << "\n";
        std::this_thread::sleep_for(std::chrono::microseconds(us_per_request));
      }
    }));
  }

  // 任意键退出
  std::getchar();

  wholesaler.stopService();
  for (auto &client : clients) {
    client.reset();
  }
}


假定有两个client线程,每个线程每秒4个request(通过requests_per_second参数调整),那么输出是这样:
--
[wholesaler @1.00s] One group of 16 ids has been allocated using the GetIds() api.
[client A @1.00s] allocated id = 1
[client B @1.00s] allocated id = 5
[client A @1.25s] allocated id = 2
[client B @1.25s] allocated id = 6
[client A @1.50s] allocated id = 3
[client B @1.50s] allocated id = 7
[client A @1.75s] allocated id = 4
[client B @1.75s] allocated id = 8. check 1point3acres for more.
[client A @2.00s] allocated id = 9
[client B @2.00s] allocated id = 13
[client A @2.25s] allocated id = 10. From 1point 3acres bbs
[client B @2.25s] allocated id = 14
[wholesaler @2.50s] One group of 8 ids has been allocated using the GetIds() api.
[client A @2.50s] allocated id = 11
[client B @2.50s] allocated id = 15
[client A @2.75s] allocated id = 12
[client B @2.75s] allocated id = 16
[client A @3.00s] allocated id = 17
[client B @3.00s] allocated id = 21
[client A @3.25s] allocated id = 18
[client B @3.25s] allocated id = 22
[wholesaler @3.50s] One group of 8 ids has been allocated using the GetIds() api.
[client A @3.50s] allocated id = 19
[client B @3.50s] allocated id = 23
[client A @3.75s] allocated id = 20
[client B @3.75s] allocated id = 24-baidu 1point3acres
[client A @4.00s] allocated id = 25
[client B @4.00s] allocated id = 29
[client A @4.25s] allocated id = 26
[client B @4.25s] allocated id = 30
...

评分

参与人数 1大米 +3 收起 理由
tscorpio42 + 3 仰望C++

查看全部评分

回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-18 04:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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