一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 949|回复: 6
收起左侧

凌鹰电面挂经

[复制链接] |试试Instant~ |面试经验, 美国面经, linkedin, 码农类general
我的人缘0

分享帖子到朋友圈
cqzxlong | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (21)
 
 
8% (2)    👎

2020(1-3月) 码农类General 硕士 全职@Linkedin - Other - 技术电面  | Fail/Rej | 在职跳槽

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

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

x
本帖最后由 cqzxlong 于 2020-1-25 02:48 编辑

面的system and infra,面完就知道挂了,昨天收到拒信,说Concurrency and Multi-Threading没答好

开头互相介绍,然后开始做题,大概有这些Process vs Thread,Context switch in thread and process,What is thread safe,Inter-process communication,Final vs finally vs finalize, semaphore vs mutex,还有一些其他的不记得了,问了大概20分钟

然后开始做题,还是那道Retain Cache的题,秒了然后手动跑了几个例子开始问follow up
1. 如果这个cache
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
种情况,希望有知道的大佬提供一些想法

顺便吐槽一下,这个coordinator实在是太不专业了,周五早上面试,周四下午5点才发来confirmation,本来都以为取消了

Anyway,求大米

评分

参与人数 3大米 +12 收起 理由
黄瓜太郎 + 2 很有用的信息!
convexopt + 1 欢迎分享你知道的情况,会给更多积分奖励!
清道神君 + 9

查看全部评分


上一篇:Whova phone screening
下一篇:微软昂赛 面经
我的人缘0
convexopt 2020-1-29 13:18:45 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (11)
 
 
0% (0)    👎
谢谢分享。关于followup 2我提一点想法抛砖引玉:
1 首先我觉得访问DataSource(在实际情况里就是访问数据库)的主要问题不是慢而是并发的压力。
    比如有一个key的读请求很多,那么这个key一旦被更新,缓存被失效,如果此时所有的缓存get请求
    都变成一个数据库的读请求,会对数据库造成过大的压力(所谓缓存雪崩)。

2 不知道楼主是怎么回答锁的问题。这类缓存一般会对锁shard,比如用hash值mod 64,减少竞争。

3 解决这个问题我有两个思路
   i.  当get请求发现key不存在或失效时,本线程先拿(sharded)锁,然后执行从DataSource载入数据
       的操作。这样即使有大量线程get同一个key,也只产生了一个数据库请求。数据库请求完成后释放这个锁,
       然后其他线程被unblock,就可以从缓存里读数据了。如果线设计成异步的接口,比如c++可以返回一个
       std::shared_future,由读数据库的线程来set。

   ii. 另一个常见的技巧是租约,这样不但可以协调同一个进程的get请求,还能用于不同进程乃至机器。做法是
       读数据库给缓存更新的时候需要请求一个token,同一时间只能有一个token。拿不到token的话,还可以
       考虑返回一个stale值,由应用决定接不接受。
回复

使用道具 举报

我的人缘0
liuqing91118 2020-2-1 05:41:45 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
从DataSource拿值会不会是应该加一个读写锁, 因为如果大量的请求是读的话 可以使用读写锁 这样可以做到大量的读请求可以同时获得锁而不是被block 只有当写操作发生的时候才会block住 如果还是太慢可以lock by bucket 这样写的时候也不是block所有 不知道面试官是不是这个意思
回复

使用道具 举报

我的人缘0
linda90321 2020-1-29 03:53:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (30)
 
 
3% (1)    👎
同面试前一天下午三四点才收到确认
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
看来做backeend/infra 并发很重要。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎
[Java] 纯文本查看 复制代码
package easy;

import java.util.*;
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class RetainBestCache<K, T extends Rankable> {
    int entriesToRetain;
    private Map<K, T> cache;
    private TreeMap<Long, Set<K>> rankingKeySetMap;
    Semaphore semaphore;
    DataSource<K,T> ds;

    /* Constructor with a data source (assumed to be slow) and a cache size */
    public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
        cache = new HashMap<>();
        rankingKeySetMap = new TreeMap<>();
        this.ds = ds;
        this.entriesToRetain = entriesToRetain;
        semaphore = new Semaphore(entriesToRetain);
    }
    /* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
     * retrieves it from the data source. If the cache is full, attempt to cache the returned data,
     * evicting the T with lowest rank among the ones that it has available
     * If there is a tie, the cache may choose any T with lowest rank to evict.
     */
    public T get(K key) {
        //implement here
        if(cache.containsKey(key)){
            return cache.get(key);
        }
        return fetchFromDS(key);
    }

    private T fetchFromDS(K key){
        if(cache.size() >= entriesToRetain){
            evitLowestRank();
        }
        T object = ds.get(key);
        try{
            semaphore.acquire();
            cache.put(key, object);
            long score = object.getRank();
            if(!rankingKeySetMap.containsKey(score)){
                rankingKeySetMap.put(score, new HashSet<>());
            }
            rankingKeySetMap.get(score).add(key);
        }
        catch (InterruptedException e){

        }
        finally {
            semaphore.release();
        }
        return object;
    }

    private void evitLowestRank(){
        Map.Entry<Long, Set<K>> entry = rankingKeySetMap.firstEntry();
        K key = entry.getValue().iterator().next();
        entry.getValue().remove(key);
        cache.remove(key);
        if(entry.getValue().size() == 0){
            rankingKeySetMap.remove(entry.getKey());
        }
    }
}
    /*
     * For reference, here are the Rankable and DataSource interfaces.
     * You do not need to implement them, and should not make assumptions
     * about their implementations.
     */
    public interface Rankable {
        /**
         * Returns the Rank of this object, using some algorithm and potentially
         * the internal state of the Rankable.
         */
        long getRank();
    }
    public interface DataSource<K, T extends Rankable> {
        T get(K key);
    }
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎
我的想法是用Semaphore 优化
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-17 07:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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