在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1045|回复: 1
收起左侧

shopkick second round phone interview

[复制链接] |试试Instant~ |关注本帖
sumingche 发表于 2014-2-22 08:59:46 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类General 硕士 全职@Shopkick - 网上海投 - 技术电面  | Other |

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

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

x
Shopkick 第二轮面试,server组的人面试我,开始讲了一大堆他做的project如何如何fancy.
然后问我的全是数据库的内容,问我index内部实现是什么,我说b, b+树,问我使用b+树的优点,我说可以降低时间复杂度,降低到logn,.1point3acres网
并且每一块都是一个page size,并且可以减少IO 查询次数,然后又问我还有什么choice嘛,我说hashmap,他说为什么index不采用hashmap
而使用b+树,我说建hashmap需要额外的空间(其实我感觉建个树,额外指针也需要空间,但是我实在不知道为什么了),于是呢 他就问我如何进行
range search 举了个例子
how do we query for rows that have a date in the year 2013?
然后我说用sql应该这样写
select * from a where data >= "2013-01-01" && data <="2013-12-31" -- what's the complexity if we have a hash index vs. a tree index?
他说这样查找的话,hashmap的时间复杂度是多少,我说是o(n),因为要遍历,他说我get point啦,然后rangquery的程序
来源一亩.三分地论坛.
Index is a hash table where the key is the column to be indexed; value is primary key. Waral 博客有更多文章,

index on name:. visit 1point3acres for more.
hash {
  "Foo" => 1,
  "Bar" => 2,
}.留学论坛-一亩-三分地
. 1point3acres
index on name (as tree):
   Foo (1).本文原创自1point3acres论坛
  /   
Bar (2)

struct Node {
  int key,.1point3acres网
  int value,
  Node *left,
  Node *right
.1point3acres网
}
. from: 1point3acres
t  =
     7
   /   \
  3     10
/ \    / \.1point3acres网
1   2  9   13. 留学申请论坛-一亩三分地

rangeQuery(t, 4, 10) => ?
rangeQuery(t, 8, 12) => ?
...

rangeQuery(t, -1, 15) => ?

rangeQuery(root, minKey, maxKey) -> returns all nodes that have keys falling between minKey and maxKey (inclusive)

public class Solution{
    ArrayList<Node> al = new ArrayList<Node>();
    public ArrayList<Node> rangeQuery(root, minKey, maxKey){

        if(root == null) return al;
        if(root.key <= maxKey && root.key >= minKey) {
             al.add(root);
             rangeQuery(root.left, minkey, maxKey);
             rangeQuery(root.right ,minkey, maxKey);
        }
        else if(root.key > maxKey){. 围观我们@1point 3 acres
            rangeQuery(root.left, minKey, maxKey);
        }
         else if(root.key < minKey){. 1point3acres
            rangeQuery(root.right,minKey, maxKey);
        }
        return al;
    }
}
-google 1point3acres
写的时候有点紧张,有点小bug,等号忘加了,并且arraylist.add()写成 arraylist.get()了,这个错误实在是不该哦,他说这些错误不太重要,因为在IDE上能改过来,他说要清楚index的实现,这个很重要。自己觉得这一轮应该很难过,
这些小公司基本就的bug free.有点瑕疵,onsite基本就没戏,学到了一点,hashmap只有搜索某一item的时候,才是
最快的,但是search a range 就不太适用了,以前在国内学过数据库,但是没想到index实现的问题,cmu 15615如果
能好好学过的话,这次面试就该过了~
来源一亩.三分地论坛.


补充内容 (2014-2-25 22:13):. more info on 1point3acres
很开心,最后有onsite啦

评分

6

查看全部评分

大屁股妖 发表于 2014-5-13 05:14:29 | 显示全部楼层
明天就要去面这个逗比shopkick了..楼主有onsite的面经吗?感谢..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 06:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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