一亩三分地论坛

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

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

Quora电面跪经

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

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

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

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

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这样。
. more info on 1point3acres.com
因为之前在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]定义错了……操。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
哎。。。今天这状态真是太诡异了。。。




评分

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};. from: 1point3acres.com/bbs
然后这个问题就和leetcode里面的house robber基本一样了。只是“相邻"这个条件判定稍微改一下就好了。
我查了下multiset的内部实现,用iterator去构造vector的算法只用o(n)就可以办到了。所以整体算法时间空间复杂度就是o(n). 1point 3acres 璁哄潧



回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-4-20 07:18:23 | 显示全部楼层
#include <iostream>
#include <set>
#include <vector>

int main ()
.鏈枃鍘熷垱鑷1point3acres璁哄潧{
  std::multiset<int> myset;
  std::multiset<int>::iterator it;

. 1point3acres.com/bbs  // insert some values:
  myset.insert(4);. 1point 3acres 璁哄潧
  myset.insert(4);
  myset.insert(3);
  myset.insert(3);
  myset.insert(3);
  myset.insert(1);. 1point 3acres 璁哄潧
  myset.insert(1);
  myset.insert(1);
  myset.insert(1);.1point3acres缃

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
. from: 1point3acres.com/bbs   std::cout << '\n';. From 1point 3acres bbs
. 1point3acres.com/bbs
  //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{. visit 1point3acres.com for more.
                  value[value.size() - 1] += *it;. 1point3acres.com/bbs
          }
. from: 1point3acres.com/bbs   }

  std::cout << "key vector:"<<std::endl;. 鍥磋鎴戜滑@1point 3 acres
  for(int i = 0; i < key.size(); i++){
          std::cout<<key[i]<<" ";
  }. 1point 3acres 璁哄潧
  std::cout<<std::endl;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  std::cout << "value vector:"<<std::endl;
  for(int i = 0; i < key.size(); i++){
          std::cout<<value[i]<<" ";. 1point3acres.com/bbs
  }. From 1point 3acres bbs
  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只要把题做出来就可以了啊,关键是要交流好
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 19:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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