买房小白任秀坡在湾区买房经历(一)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
国内机会:实时大数据分析领域领导者
Web/大数据/机器学习/产品等职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3661|回复: 10
收起左侧

google面经题

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-3-5 11:50:16 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite  | Other | 其他

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

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

x
一道常出现的面经题,拿出来讨论下自己设计接口,使得支持两个funciton:onUpdate(timestamp, price) 和 onCorrect(temistamp, price). 可以理解为有一个时间流,每一个timestamp都对应一个股票的时间,每次调用一次onUpdate的时候,就对我们设计的那个类更新对应的timestamp和price, onCorrect就是修改之前的一个timestamp的price。最后,我们的类要能返回latest price, max price 和 min price。一开始题目描述的太模糊了我都不知道到底要干啥,墨迹半天才知道是想设计一个类,然后中途也写的乱七八糟的,用了两个Deque来存储一个递增和一个递减的序列,类似窗口题的方法。当onCorrect的时候就去看队列里面有没有对应的timestamp,有的话移除然后重新入队。感觉这面面的也不是太好。”
感觉应该是定义一个node class {timestamp, price}, 然后放入maxheap和min heap中吧,但是如果是用java的话,必须要用hash heap才可以吧,这样的话太麻烦了啊
 楼主| bobzhang2004 发表于 2016-3-6 05:00:24 | 显示全部楼层
这个题比较常考啊
回复 支持 反对

使用道具 举报

Ulu2005 发表于 2016-3-15 02:33:03 | 显示全部楼层
不是很懂这里onCorrect具体干什么,既然onCorrect(timestamp, price)给了timestamp,怎么又去更新之前的timestamp的price?是参数里timestamp之前的一个吗?
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-4-1 08:59:15 | 显示全部楼层
Ulu2005 发表于 2016-3-15 02:33
不是很懂这里onCorrect具体干什么,既然onCorrect(timestamp, price)给了timestamp,怎么又去更新之前的tim ...

我也不是很清楚,希望碰到的大神可以具体说说
回复 支持 反对

使用道具 举报

zacharyzhy 发表于 2016-4-1 10:53:14 | 显示全部楼层
听比人说过类似的面经,是说设计一个数据结构,用来存储股票价格,要支持获得到当前位置最大值最小值,另外除了加入新的point以外还要支持对过去的数据点的修改

感觉用TreeMap好像可以解,不过基本就是和hash heap一个思路了
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-4-10 05:52:51 | 显示全部楼层
这道题目不就是用一个hashmap 和一个minHeap和一个maxHeap搞定?
回复 支持 反对

使用道具 举报

chm34 发表于 2016-4-19 04:15:49 | 显示全部楼层
qiuxuxing007 发表于 2016-4-10 05:52
这道题目不就是用一个hashmap 和一个minHeap和一个maxHeap搞定?

请问当onCorrect某个timestamp,肯定需要把这个<timestamp,price> 的pair从heap里删除,再把更新的<timestamp,price>插入到heap里。那么这个删除操作复杂度不是O(N)吗?
回复 支持 反对

使用道具 举报

chm34 发表于 2016-4-19 04:17:16 | 显示全部楼层
zacharyzhy 发表于 2016-4-1 10:53
听比人说过类似的面经,是说设计一个数据结构,用来存储股票价格,要支持获得到当前位置最大值最小值,另外 ...
.1point3acres缃
小弟没有想通如何onCorrect操作可以在logN时间完成,请问可以详细说说吗?非常感谢!!
回复 支持 反对

使用道具 举报

burning_k 发表于 2016-4-19 06:23:03 | 显示全部楼层
chm34 发表于 2016-4-19 04:17
小弟没有想通如何onCorrect操作可以在logN时间完成,请问可以详细说说吗?非常感谢!!

额外用一个hashmap存股票以及它在minheap里的位置,你delete的时候就知道它在哪了,不用seach整个heap。这么做可以让delete变成logN的,不过得自己实现minheap的所有操作,期间要update hashmap.
回复 支持 反对

使用道具 举报

zacharyzhy 发表于 2016-5-2 15:02:21 | 显示全部楼层
chm34 发表于 2016-4-19 04:17
小弟没有想通如何onCorrect操作可以在logN时间完成,请问可以详细说说吗?非常感谢!!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大概写了一下, 其实主要就是用了TreeSet是Red-Black tree实现,所以find,add,remove操作都是O(n)这个性质,省去了自己从头到尾写Heap的麻烦
思路就是TreeSet里面存一个Comparable的东西,然后它自己就会按照你的compare的实现完成sort,然后取first()和last()就是相应的最大最小;然后因为是个Set,因此就不用像HashHeap那样自己记录点在哪儿. Waral 鍗氬鏈夋洿澶氭枃绔,


public class StructureForStockPrice {

    public static void main(String[] args) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        StructureForStockPrice st = new StructureForStockPrice();
        st.onUpdate(1, 10);
        st.onUpdate(2, 15); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        st.onUpdate(3, 5);
        st.onUpdate(4, 20);
        st.onUpdate(5, 12);
        System.out.println(st.max());. From 1point 3acres bbs
        System.out.println(st.min());
        st.onCorrect(2, 3);. more info on 1point3acres.com
        System.out.println(st.max());. From 1point 3acres bbs
        System.out.println(st.min());
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦


    class PricePoint implements Comparable<PricePoint> {
        int price;. Waral 鍗氬鏈夋洿澶氭枃绔,
        int timeStamp;
        public PricePoint(int price, int timeStamp) {
            this.price = price;
            this.timeStamp = timeStamp;
        }

        @Override
        public int compareTo(PricePoint o) {
            if (price == o.price) {
                return timeStamp - o.timeStamp;
            } else {
                return price - o.price;. 鍥磋鎴戜滑@1point 3 acres
            }
        }
    }

    private Map<Integer, Integer> timeStampToPriceMap = new HashMap<>();
    private TreeSet<PricePoint> pricePointTreeSet = new TreeSet<>();

    public void onUpdate(int timeStamp, int price) {

        timeStampToPriceMap.put(timeStamp, price);. visit 1point3acres.com for more.
        pricePointTreeSet.add(new PricePoint(price, timeStamp));
    }. 1point3acres.com/bbs

    public void onCorrect(int timeStamp, int price) {
        PricePoint oldData = new PricePoint(timeStampToPriceMap.get(timeStamp), timeStamp);
        pricePointTreeSet.remove(oldData);
        pricePointTreeSet.add(new PricePoint(price, timeStamp));
        timeStampToPriceMap.put(timeStamp, price);
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    public int min() {-google 1point3acres
        return pricePointTreeSet.first().price;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }. more info on 1point3acres.com
. Waral 鍗氬鏈夋洿澶氭枃绔,
    public int max() {
        return pricePointTreeSet.last().price;
    }
}

回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-3 02:28:05 | 显示全部楼层
burning_k 发表于 2016-4-19 06:23
额外用一个hashmap存股票以及它在minheap里的位置,你delete的时候就知道它在哪了,不用seach整个heap。 ...

不用这么烦吧。。 就维护一个map<stamp, price>存一下修改过的,oncrrect的时候不需要detele from heap,用heap存<stamp, price>按price排序,每次从minheap和maxheap里返回peek()之前看一下head里的stamp在不在那个map里,在的话poll出来再重新插入更新的<stamp, price>,然后再peek一次返回。。这样就是logn了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-20 11:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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