没结婚也能买房啊!大波士顿地区买房小tips

一亩三分地论坛

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

Quora电面跪经

[复制链接] |试试Instant~ |关注本帖
diyutianshi 发表于 2016-4-20 02:40:52 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类General 博士 全职@Quora - 猎头 - 技术电面  | Fail | 在职跳槽

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

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

x
这是我这段时间面的最差的一次电面了。

本来我一直以为这次电面会focuson machine learning结果只是high level的聊了一下,比如说一个新的question怎么推送给合适的user使得这个question可以尽量比较快的被人回答,我就扯了一堆先offline建一个user topic的interest matrix,然后对这个question我们可以根据query expansion, topic model以及user tag之类的信息找出topic然后利用user topic interest matrix来推送给user云云,面试官好像还很满意,但是什么具体的算法都没聊,本来还挺高兴觉得应该可以很smooth了,结果没想到今天coding全不在状态。

问的问题非常简单,就是一个螺旋矩阵
  1  2 3  4  5
  6  7 8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
要从内往外打出13, 14,9, 8, 7, 12, 17, 18, 19, 20, 15, 10, 5, 4, 3, 2, 1, 6, 11, 16, 21, 22, 23, 24,25这样。

因为之前在InterviewBit上做过,但是我一开始的做法和标程是不一样的,我记得我是用dx, dy做的,标程是用rowBegin, rowEnd, colBegin, colEnd这样做的,我觉得非常巧妙就学习了一下……可是那个原题是从外往内走的……这个是从内往外走的……可是我就一直在rowBegin, rowEnd, colBegin, colEnd的维护上老是错,妈的我觉得自己非常脑残,最后还是他提示了一下才改对的。

后来他就又问了个题目,给一个multiset,类似于{1, 1, 1, 3, 3, 3, 4, 4}的multiset,define neighboring values of increment / decrement of each other,e.g. 3, 4,需要find maximum possible subset sum suchthat there are no two neighboring values,这个题目很简单,就f[0],f[1]的DP就可以了,写完之后很舒服的过了样例,他要我降低空间复杂度,那就改成滚动数组嘛……问题就在于。。。我改了时候手TMD一滑把g[1]从cnt[1]给滑成了1,然后发现结果不对之后我就一直怀疑是我滚动的时候滚动错了……看了两三分钟都觉得这滚动怎么能有错……最后发现是g[1]定义错了……操。。。

哎。。。今天这状态真是太诡异了。。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

 楼主| diyutianshi 发表于 2016-4-20 02:41:44 | 显示全部楼层
不知道为何没显示出来,不过第二题我想写的是"f[i][0], f[i][1]的DP。"
回复 支持 反对

使用道具 举报

snakefly 发表于 2016-4-20 03:17:56 | 显示全部楼层
第一题要实现从内往外走, 那我还是按照从外往里的顺序,但是从n^2 开始放,一直放到1, 这样可以吗。(因为感觉陀螺点中心的位置不好确定)
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 03:38:26 | 显示全部楼层
从外往内走在reverse一下感觉比较清晰
回复 支持 反对

使用道具 举报

 楼主| diyutianshi 发表于 2016-4-20 06:00:16 | 显示全部楼层
snakefly 发表于 2016-4-20 03:17
第一题要实现从内往外走, 那我还是按照从外往里的顺序,但是从n^2 开始放,一直放到1, 这样可以吗。(因 ...

先别想那么多,就假定方阵的长度是N*N,且N是奇数,中心点的位置倒是很好确定……但是后面的update我搞错了 =_=
回复 支持 反对

使用道具 举报

 楼主| diyutianshi 发表于 2016-4-20 06:01:07 | 显示全部楼层
tk1322715 发表于 2016-4-20 03:38
从外往内走在reverse一下感觉比较清晰

哎……我改到一半我也问了这个问题……他说,当然也可以这么做……but I think you are quite there……我为了不让interviewer看不起硬着头皮继续改了下去……其实真的调出来之后发现是很简单的……只是第一次写的时候真的没想清楚,大家要是有兴趣也可以实现一下试试。。。
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 07:06:39 | 显示全部楼层
关于第二题,我自己有个想法。
首先把multiset转换成类似与hash table这样的数据结构。key是set的元素,value是对应key的所有元素的sum。下面是例子:
{1, 1, 1, 3, 3, 3, 4, 4}转化成{1:3,3:9,4:8}。其实准确来说第二个类似于hashtable的数据就够是由两个vector构成的。
真正的结构如下:
第一个vector包含{1,3,4}。 第一个vector必须要从小到大sort好。第二个vector包含{3,9,8};
然后这个问题就和leetcode里面的house robber基本一样了。只是“相邻"这个条件判定稍微改一下就好了。
我查了下multiset的内部实现,用iterator去构造vector的算法只用o(n)就可以办到了。所以整体算法时间空间复杂度就是o(n)



回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 07:18:23 | 显示全部楼层
#include <iostream>. from: 1point3acres.com/bbs
#include <set>
#include <vector>

int main ()
{
  std::multiset<int> myset;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  std::multiset<int>::iterator it;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  // insert some values:
  myset.insert(4);
  myset.insert(4);
  myset.insert(3);
  myset.insert(3);
  myset.insert(3);
  myset.insert(1);
  myset.insert(1);
  myset.insert(1);
  myset.insert(1);

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it). 1point 3acres 璁哄潧
    std::cout << ' ' << *it;
  std::cout << '\n';

  //algorithm to transfor vector to the two vectors
  std::vector<int> key;
  std::vector<int> value;
  for (it=myset.begin(); it!=myset.end(); ++it){
          if(key.size() == 0 || key[key.size() - 1] != *it){
                  key.push_back(*it); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                  value.push_back(*it);
          }
          else{
                  value[value.size() - 1] += *it;
          }
. Waral 鍗氬鏈夋洿澶氭枃绔,  }

  std::cout << "key vector:"<<std::endl;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  for(int i = 0; i < key.size(); i++){
          std::cout<<key[i]<<" ";. 鍥磋鎴戜滑@1point 3 acres
  }
  std::cout<<std::endl;-google 1point3acres

  std::cout << "value vector:"<<std::endl;
  for(int i = 0; i < key.size(); i++){
          std::cout<<value[i]<<" ";
  }
  std::cout<<std::endl;


  return 0;
}
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 07:19:57 | 显示全部楼层
楼上写了一段全套的代码去把multiset转换成我想要的两个vector的数据结构然后输出验证。
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 07:22:20 | 显示全部楼层
diyutianshi 发表于 2016-4-20 06:01
哎……我改到一半我也问了这个问题……他说,当然也可以这么做……but I think you are quite there…… ...

哈哈哈,确实。如果写到那个地步了确实得硬着头皮写完。不过我自己一向不太适应这种类型的题目。感觉算法简单,就是要仔细。
回复 支持 反对

使用道具 举报

gxh1991 发表于 2016-4-20 12:01:12 | 显示全部楼层
已经据了么? 我觉得lz只要把题做出来就可以了啊,关键是要交流好
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-4-22 01:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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