一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1797|回复: 10
收起左侧

google面经题

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

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

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

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

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
听比人说过类似的面经,是说设计一个数据结构,用来存储股票价格,要支持获得到当前位置最大值最小值,另外 ...

小弟没有想通如何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那样自己记录点在哪儿

. more info on 1point3acres.com
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);. visit 1point3acres.com for more.
        st.onUpdate(4, 20);
        st.onUpdate(5, 12);
        System.out.println(st.max());
        System.out.println(st.min());
        st.onCorrect(2, 3);
        System.out.println(st.max());
        System.out.println(st.min());
    }


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

        @Override
        public int compareTo(PricePoint o) {
            if (price == o.price) {
                return timeStamp - o.timeStamp;
            } else {. visit 1point3acres.com for more.
                return price - o.price;
            }
        }
    }

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

    public void onUpdate(int timeStamp, int price) {

        timeStampToPriceMap.put(timeStamp, price);
        pricePointTreeSet.add(new PricePoint(price, timeStamp));
    }

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

    public int min() {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        return pricePointTreeSet.first().price;
    }

    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了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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