一亩三分地论坛

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

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

TripAdvisor

[复制链接] |试试Instant~ |关注本帖
yangzeyao 发表于 2015-9-30 04:15:05 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@TripAdvisor - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
通过LinkedIn投,面试的是social组的一个Team Leader。
1. 刚刚工作两个月为什么跳槽?(多谢另一篇帖子里一位仁兄的建议,这次回答的不错)
2. 因为我上一个project也是social的,非常专业的问了project里面的三个部分是怎么做的。(这部分感觉他满意度一般,因为我有点不能get到他的点,需要他重复)
3. LinkedList和ArrayList分别是什么(continuous和pointer) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4. 他们的cons和pros(random access和manipulation time complexity两方面回答的)
5. 在sorted arraylist里面search一个element,time complexity多少?
6. 如果在sorted linkedlist里面,时间复杂度又是多?(这个答的最不好,我想了很久有没有lgn的解法,最后没想到。然后说如果用同样的算法的话,为了能够找到mid元素,依次需要n/2, n/4, n/8 ... 的time,但是我跟她说我忘了等差数列求和公式了 ...)然后他继续问,如果不需要让你用原来的算法呢。(我说就先扫一遍,用hashmap<ele position, address of ele>记录。然后再用lgn的算法就可以了。)他说他like it,但是(哎),如果这个函数只是偶尔调用一次,复杂度是多少?我说n。他说那为什么不直接扫一遍?(有道理,不过要是需要经常访问的话,还是一个hashmap比较好)-google 1point3acres
7. 桶排序(题目写到一半就看出是个桶排序,然后就说,我知道桶排序算法,just let you know if you want to test my algorithm ability)。他说换一道
8. public class LocationTag
{
.鐣欏璁哄潧-涓浜-涓夊垎鍦   public int locationId;  // fenway park =12345, logan airport = 5678 ,hotel commonwealth = 6789
   public int tagId;       // luxury = 1, resort = 2, ballpark = 3, wifi = 4

   public LocationTag(locationid, tagId){}
}
-google 1point3acres
// given a list of location ids, and a list of locationTags, return the list of tagIds
// that match the location Ids. more info on 1point3acres.com
//
//  getTags([12345], [LocationTag(12345,2), LocationTag(12345,2)] = [2,2] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
//. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

public List<Integer> getTags(List<Integer> locationIds, List<LocationTag> locationTags)
{
    // make contents in locationIds into set. 鍥磋鎴戜滑@1point 3 acres
    HashSet<Integer> st = new HashSet<>();. 1point 3acres 璁哄潧
    for (int i=0; i<locationsIds.size(); i++) {
        st.add(locationIds.get(i));
. more info on 1point3acres.com    }

    List<Integer> res = new ArrayList<>();
    for (int i=0; i<locationTag.size(); i++) {
        if (st.contains(locationTags.get(i).locationID)) {. 1point 3acres 璁哄潧
            res.add(locationsTags.tagId);. From 1point 3acres bbs
        }
    }
    return res;
}


9. 完


补充内容 (2015-9-30 04:19):
Sorted LinkedList 的 search问题,不知道大家有没有更好的方法?

补充内容 (2015-9-30 22:58):
pass. The next step in our hiring process, involves a short (1-2 hr) homework problem that we would like you to complete and send back..鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-10-9 06:08):
今天收到onsite:)  因为补充有字数限制,所以homework的题目写在回复里了。PS.今天上班的时候老板把我叫过去说,要么好好干好么就辞职,加上前些天被fb和linkedin简历拒。接到这个onsite的时候简直激动的热泪盈眶
. 1point 3acres 璁哄潧
补充内容 (2015-11-6 05:11):.鏈枃鍘熷垱鑷1point3acres璁哄潧
onsite面经见回复

补充内容 (2015-11-12 07:05):
昨天收到offer。跟hr打电话的时候要求extend deadline,对方很不开心。问什么时候有official offer,她说昨天或者今天。结果都下班了还没发来,发邮件也没回,而且Google面的也不是很好,哎。
 楼主| yangzeyao 发表于 2015-10-9 06:18:39 | 显示全部楼层
题目和下面这篇帖子一样,只是稍微换了一下说法. more info on 1point3acres.com
http://www.1point3acres.com/bbs/ ... adio%26sortid%3D192

思路是:
用hash map把hotel的名字和对应的所有deals都存起来
每次对所有的deal根据输入条件搜索discont,并记录最大的(类似于遍历找最大值)

难点:
1. c++文件的输入和存储(当时不会这个导致挂在了two sigma最后一轮,现在想起来心还绞痛)
2. 因为文件里存的是日期范围,输入的时候给的却是入住天数,所以有一个日期到天数的转换。需要考虑,闰年,2月之类的特殊情况(这里我用到了time_t, ps:我用的c++)
3. main函数的参数输入,以及make file文件的编写

总的来说思想很简单,但是编写起来比较耗时耗力而且繁琐。代码查重比较容易,就不贴了。希望前面说的清楚
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-6 05:11:19 | 显示全部楼层
onsite面经:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第一轮:. visit 1point3acres.com for more.
1. 问了一些基础知识以及behavior,但是忘了具体问题了。
2. 一个integer的二进制表示有多少个1,用经典的x&(x-1)做的,但是忘了是不是对负数也好使了。但是又忘了负数的二进制推导公式了,问面试官也笑而不语,当时小紧张。幸亏记得x&-x是返回最后一位非零digit,现场推导了一下,是正数-1取反。然后分别用正负数过了一遍程序。面试官很满意.鐣欏璁哄潧-涓浜-涓夊垎鍦
3. 给一个数组a和一个k,返回所有的x使得x和x-k都在a里面。我第一反应是问了一个特别脑残的问题,x需要在a里面么?面试官笑而不语说,你说呢?然后在纸上记录了些什么,我猜可能是脑残读不懂题之类的。然后用hashset的方法两个loop做出来。follow up有超多,如何提高space complexity,还有判别语句的顺序对性能的影响,一个loop能不能搞定,等等旁征博引的很多问题。面试官比较满意。
4. 经典问题,输入一个网址之后发生了什么,一共11部,cc原题,但是忘http那步了,面试官很nice直接告诉了。然后继续问,http里面包含了哪些东西,一般怎么load picture,这个我之前没有编过,但是根据实际经验,都是先看到text再看到picture,所以应该是在第一个http里面只是包含了picture的网址,需要再次http请求什么的。面试官比较满意。

第二轮:
1. 好多behavior问题,印象中面试官不满意的是what are you looking for. 其实就是为什么离开现在的工作。这个问题一直没有找到一个合适的回答,毕竟工作3个月跳槽比较不好说。我把我的回答贴在下面,不知道大家有没有更好的建议:First of all, I have to say I kind of enjoy my current work and life. But I decided to leave before I stared to work here because I hope I could have more challenging and interesting opportunities. So it is not because I found here is not good after I came, it is because I have my plan for my career. I want to start to work as soon as possible after I graduated so that I could build my experience in industry. If I won’t start to work until I find the perfect job, I may spend several months more to get it. Meanwhile, the only thing I do basically is interview, but it won’t help me improve a lot especially comparing with industry experience. Also, by doing this, instead of interviewing every day without thinking, I could take my time to summarize previous interviews without rushing. That helps me to show my skills and ability better. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. 好多好多好多基础知识问题。其中答得不好的是:他问我什么语言最熟,想显摆一下就说,c++,java,python随便问。然后他说,java里面的interface,然后说了说。接着问,abstract。然后我只对,c++的abstract有印象,所以就说了说c++的,这个他应该不是很满意。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
3. 给一个数组a,返回一个index这个index之前的element都比a[index]小,之后的都比a[index]大。时间复杂度O(n)。用三个变量,flag,curMax,和res,分别记录,当前是否发现这样的index,当前发现的最大值,和当前符合输出要求的res。第一遍没写好,然后又用了不少时间才解出来。感觉面试官反应一般。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4. 如何处理同事间的不同意见。面试官比较满意。
这轮behavior回答的一般般,熟练多种语言显摆失败,算法题时间有点长。哎,写到这里感觉要挂了,呵呵。

第三轮
感觉还挺奇怪的,ta的lunch也算是一轮面试,主要用来给新的面试官练手。本来不应该问technology问题,但是问了好多,印象比较深刻的除了project里面的技术问题,还有hashmap的内部实现bloom filter和优缺点。
这个面试官的逻辑语言表达能力是目前为止见过最弱的,交流相对不顺畅。. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres
第四轮
实现LinkedList类,有insert,delete,search,犯了三个比较naive的错误,展现出一点careless的缺点,面试官略有不爽。然后深入分析,各种可能的实现方法,分别分析,三个方法的时间复杂度和总的空间复杂度。最后一个follow up,属于design方面的,但是太复杂了,感觉不画图描述不清,见谅。
面试官最后说good luck,感觉不是很满意。
. from: 1point3acres.com/bbs
HR
TA的hr非常有意思,无论你答的好不好,都会说你回答的很好,她进来就说you kill them, 明天或者下周就有消息了,一脸期待的看着我希望我表达一下兴奋,但是太累了,懒得演了,就说thank you。
.1point3acres缃
之前论坛里面说,提供三餐,但是好像只有lunch。不过办公环境很好,做的东西很有意思。
题目都很简单,但是follow up不仅多而且杂,感觉有被challenge到。. 1point 3acres 璁哄潧
等消息吧。
回复 支持 反对

使用道具 举报

Stupidog 发表于 2015-11-6 11:44:53 | 显示全部楼层
“3. 给一个数组a,返回一个index这个index之前的element都比a[index]小,之后的都比a[index]大。时间复杂度O(n)。用三个变量,flag,curMax,和res,分别记录,当前是否发现这样的index,当前发现的最大值,和当前符合输出要求的res。第一遍没写好,然后又用了不少时间才解出来。感觉面试官反应一般。”. 1point3acres.com/bbs
.1point3acres缃
请问这道题目空间复杂度有什么要求呢?
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 00:22:35 | 显示全部楼层
Stupidog 发表于 2015-11-6 11:44. from: 1point3acres.com/bbs
“3. 给一个数组a,返回一个index这个index之前的element都比a小,之后的都比a大。时间复杂度O(n)。用三个 ...

没说,我给的是O(1)
回复 支持 反对

使用道具 举报

Stupidog 发表于 2015-11-7 02:39:22 | 显示全部楼层
yangzeyao 发表于 2015-11-7 00:22
没说,我给的是O(1)

能分享一下具体思路么?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我只能想到用2个额外的array,一个存从左到右扫描,当前的Max,另一个存从右到左扫描,当前的Min。
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 04:34:36 | 显示全部楼层
Stupidog 发表于 2015-11-7 02:39
能分享一下具体思路么?

我只能想到用2个额外的array,一个存从左到右扫描,当前的Max,另一个存从右 ...

用三个变量,flag,curMax,和res,分别记录,当前是否发现这样的index,当前发现的最大值,和当前符合输出要求的res。
回复 支持 反对

使用道具 举报

Stupidog 发表于 2015-11-7 05:07:07 | 显示全部楼层
yangzeyao 发表于 2015-11-7 04:34
用三个变量,flag,curMax,和res,分别记录,当前是否发现这样的index,当前发现的最大值,和当前符合输 ...

嗯,不好意思,这个看到在你原帖里面也写了,不过自己没办法看懂... 具体问题是,如果只是从左向右进行扫描,记录curMax的话,如何确定array[index]比剩下的元素都要小呢?
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 05:22:35 | 显示全部楼层
int curMax = -1;
int res = 0;
bool flag = false;
for (int i=0; i<a.size(); i++) {
    if (curMax==-1 || a>a[curMax]) {curMax=i;}. Waral 鍗氬鏈夋洿澶氭枃绔,
    if (a[res] > a) {flag = false;}
    if (flag==false && a>=curMax) {flag=true;res=i;}
    return flag==true ? res : -1;
}

补充内容 (2015-11-7 05:23):
return flag==true ? res : -1; 在外面
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 05:24:08 | 显示全部楼层
Stupidog 发表于 2015-11-7 05:07
嗯,不好意思,这个看到在你原帖里面也写了,不过自己没办法看懂... 具体问题是,如果只是从左向右进行扫 ...

int curMax = -1;
int res = 0;
bool flag = false;
for (int i=0; i<a.size(); i++) {
    if (curMax==-1 || a>a[curMax]) {curMax=i;}
    if (a[res] > a) {flag = false;}
    if (flag==false && a>=curMax) {flag=true;res=i;}
}
return flag==true ? res : -1;
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 05:27:00 | 显示全部楼层
Stupidog 发表于 2015-11-7 05:07
嗯,不好意思,这个看到在你原帖里面也写了,不过自己没办法看懂... 具体问题是,如果只是从左向右进行扫 ...
  1. int curMax = -1;. from: 1point3acres.com/bbs
  2. int res = 0;
  3. bool flag = false;
  4. for (int i=0; i<a.size(); i++) {
  5.     if (curMax==-1 || a[i]>a[curMax]) {curMax=i;}
  6.     if (a[res] > a[i]) {flag = false;}
  7.     if (flag==false && a[i]>=a[curMax]) {flag=true;res=i;}. 1point 3acres 璁哄潧
  8. }
  9. return flag==true ? res : -1;
复制代码

补充内容 (2015-11-7 05:27):
不知道为什么[]总打不出来,看这个代码版好了
回复 支持 反对

使用道具 举报

Stupidog 发表于 2015-11-7 05:44:17 | 显示全部楼层
yangzeyao 发表于 2015-11-7 05:27
补充内容 (2015-11-7 05:27):
不知道为什么[]总打不出来,看这个代码版好了

明白了,很赞的解法!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个解法应该是假设只有1个(或0个)符合条件的array element,如果有多个的话,会返回第一个吧?
回复 支持 反对

使用道具 举报

 楼主| yangzeyao 发表于 2015-11-7 05:45:10 | 显示全部楼层
Stupidog 发表于 2015-11-7 05:44
明白了,很赞的解法!

这个解法应该是假设只有1个(或0个)符合条件的array element,如果有多个的话 ...
-google 1point3acres
恩,是的
回复 支持 反对

使用道具 举报

Stupidog 发表于 2015-11-7 05:48:40 | 显示全部楼层
yangzeyao 发表于 2015-11-7 05:45. 1point3acres.com/bbs
恩,是的

多谢啦,祝offer快快到手
回复 支持 反对

使用道具 举报

jjwqf 发表于 2015-11-7 05:59:52 | 显示全部楼层
lz在linkedin上投,是直接投给HR还是在公司的linkedin上申请职位的,大概过了多久?谢谢
回复 支持 反对

使用道具 举报

julia1006 发表于 2015-11-20 12:34:32 | 显示全部楼层
楼主写的好详细~~谢谢~~很有用~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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