《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2132|回复: 15
收起左侧

Drive.AI OA 把我虐哭!

[复制链接] |试试Instant~ |关注本帖
lcq123 发表于 2017-7-3 12:37:39 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Drive.AI - 猎头 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚刚做完drive.ai 被虐哭!!!
只能用C++或者Python来写,像我这种Java选手蛋疼了!

一共八道题:三道关于多线程的编程问答,一道数学计算题,一道数据结构选择题,俩道算法题:
我就说一下算法题吧:-google 1point3acres
第一道:implement maystack,这道题不难, 就是需要implement函数  pop(), peek(), init() 还有 buffer()(好像是这个名字),给定主要是最后一个函数用于将一个范围内的stack里面的数值一个个add 一个delta 数值。
第二道算法: 给定一个2D data, 里面是pixel value, 还有一个threshold value S,和一个距离值D,如果adjacent 来个pixel值相离不超过D,被视为在同一个object里面, 如果一个object里面的元素个数小于S,将这个object一切数值归为0, 然后还需要把搜索出来的所有object 赋予一个公共的id, 也就是说要在原来的 2D data values 里面设置id值!(一直test cases 过不去,时间来不及了!)

感觉这家公司招人bar 好高啊!

评分

2

查看全部评分

wendaomumu 发表于 2017-7-3 13:13:47 | 显示全部楼层
请问楼主maystack是啥?另外“如果adjacent 来个pixel值相离不超过D”意思是要求同一个object里面任意两个点距离不超过D是吗?
回复 支持 反对

使用道具 举报

 楼主| lcq123 发表于 2017-7-3 13:21:11 | 显示全部楼层
wendaomumu 发表于 2017-7-3 13:13
请问楼主maystack是啥?另外“如果adjacent 来个pixel值相离不超过D”意思是要求同一个object里面任意两个 ...

不好意思,打错了,是任意相邻俩个pixel
回复 支持 反对

使用道具 举报

 楼主| lcq123 发表于 2017-7-3 13:21:43 | 显示全部楼层
wendaomumu 发表于 2017-7-3 13:13
请问楼主maystack是啥?另外“如果adjacent 来个pixel值相离不超过D”意思是要求同一个object里面任意两个 ...

Maystack 那道题不难,只是比常规的stack多了一个函数
回复 支持 反对

使用道具 举报

头像被屏蔽
wodexiaohao2 发表于 2017-7-3 13:39:49 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

RyanWindaZ 发表于 2017-7-6 09:38:17 | 显示全部楼层
"然后还需要把搜索出来的所有object 赋予一个公共的id, 也就是说要在原来的 2D data values 里面设置id值!"
請問這個id的作用是甚麼?
回复 支持 反对

使用道具 举报

jili 发表于 2017-7-7 02:39:09 | 显示全部楼层
不错啦,至少还有oa, 我和我同学直接被拒简历。。
回复 支持 反对

使用道具 举报

chaohubian 发表于 2017-8-26 07:55:38 | 显示全部楼层
第二题不就是机器学习里KNN分类算法么?我操!
回复 支持 反对

使用道具 举报

LukeDong 发表于 2017-8-26 19:40:17 | 显示全部楼层
第二题……有点想ccl吧
回复 支持 反对

使用道具 举报

chaohubian 发表于 2017-8-27 04:13:51 | 显示全部楼层
  1. class Solution {
  2. public:.1point3acres缃
  3. //这是我第二题的解法,也可以memo之前的 value, id
  4.     class Point {
  5.     public:. from: 1point3acres.com/bbs
  6.         int x, y;
  7.         int value;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         int id;
  9.         Point(int x, int y, int value=0, int id=0) {
  10.             this->x=x;
  11.             this->y=y;
  12.             this->value=value;
  13.             this->id=id;
  14.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.     };. from: 1point3acres.com/bbs
  16.     void test() {
  17.         vector<vector<Point*>> points;
  18.         points.push_back({});
  19.         points[0].push_back(new Point(0, 0, 1));
  20.         points[0].push_back(new Point(0, 1, 1));
  21.         points[0].push_back(new Point(0, 2));. 鍥磋鎴戜滑@1point 3 acres
  22.         points[0].push_back(new Point(0, 3));
  23.         points[0].push_back(new Point(0, 4));
  24.         points.push_back({});
  25.         points[1].push_back(new Point(1, 0, 1));
  26.         points[1].push_back(new Point(1, 1, 1));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.         points[1].push_back(new Point(1, 2));
  28.         points[1].push_back(new Point(1, 3));
  29.         points[1].push_back(new Point(1, 4));
  30.         points.push_back({});
  31.         points[2].push_back(new Point(2, 0));
  32.         points[2].push_back(new Point(2, 1));
  33.         points[2].push_back(new Point(2, 2, 1));
  34.         points[2].push_back(new Point(2, 3));
  35.         points[2].push_back(new Point(2, 4));
  36.         points.push_back({});
  37.         points[3].push_back(new Point(3, 0));
  38.         points[3].push_back(new Point(3, 1));
  39.         points[3].push_back(new Point(3, 2));
  40.         points[3].push_back(new Point(3, 3, 1));
  41.         points[3].push_back(new Point(3, 4, 1));
  42.         points.push_back({});
  43.         points[4].push_back(new Point(4, 0));
  44.         points[4].push_back(new Point(4, 1));
  45.         points[4].push_back(new Point(4, 2));
  46.         points[4].push_back(new Point(4, 3, 1));
  47.         points[4].push_back(new Point(4, 4, 1));
  48.         /*
  49.          1 1 0 0 0
  50.          1 1 0 0 0. 1point 3acres 璁哄潧
  51.          0 0 1 0 0. 1point 3acres 璁哄潧
  52.          0 0 0 1 1
  53.          0 0 0 1 1
  54.          */. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  55.         vector<vector<Point*>> result = pixelClustering(points, 1, 3);
  56.     }
  57.    
  58.     vector<vector<Point*>> pixelClustering(vector<vector<Point*>>& points, int dist, int counts) {. 1point3acres.com/bbs
  59.         if (points.empty() || points.size()==0 || points[0].size()==0) {
  60.             return points;
  61.         }
  62.         vector<vector<Point*>> result=points;
  63.         int newid=1;
  64.         for (int i=0; i<result.size(); i++) {
  65.             for (int j=0; j<result[0].size(); j++) {
  66.                 if (result[i][j]->value==1) {
  67.                     int counter=1;
  68.                     dfsHelper(points, i, j, dist, counter);
  69.                     if (counter<counts) {
  70.                         cleaner(points, i, j, dist);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  71.                     }
  72.                     else {
  73.                         remarker(points, i, j, dist, newid);
  74.                         newid++;
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.         return result;
    . visit 1point3acres.com for more.
  80.     }
  81.    
  82. private:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  83.     void remarker(vector<vector<Point*>>& points, int x, int y, int dist, int newid) {
  84.         points[x][y]->value=2;
  85.         points[x][y]->id=newid;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  86.         if (x>0) {
  87.             for (int delta=1; delta<=dist; delta++) {
  88.                 if (x-delta>=0 && points[x-delta][y]->value==-1) {
  89.                     remarker(points, x-delta, y, dist, newid);
  90.                 }
  91.             }
  92.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  93.         if (x<points.size()-1) {. visit 1point3acres.com for more.
  94.             for (int delta=1; delta<=dist; delta++) {
  95.                 if (x+delta<points.size() && points[x+delta][y]->value==-1) {
  96.                     remarker(points, x+delta, y, dist, newid); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  97.                 }
  98.             }
  99.         }
  100.         if (y>0) {
  101.             for (int delta=1; delta<=dist; delta++) {
  102.                 if (y-delta>=0 && points[x][y-delta]->value==-1) {
  103.                     remarker(points, x, y-delta, dist, newid);
  104.                 }
  105.             }
  106.         }
  107.         if (y<points[0].size()-1) {.1point3acres缃
  108.             for (int delta=1; delta<=dist; delta++) {
  109.                 if (y+delta<points[0].size() && points[x][y+delta]->value==-1) {
  110.                     remarker(points, x, y+delta, dist, newid);. 1point3acres.com/bbs
  111.                 }
  112.             }
  113.         }
  114.     }
  115.     void cleaner(vector<vector<Point*>>& points, int x, int y, int dist) {. 鍥磋鎴戜滑@1point 3 acres
  116.         //clean point value. 1point 3acres 璁哄潧
  117.         points[x][y]->value=0;
  118.         points[x][y]->id=0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  119.         if (x>0) {
  120.             for (int delta=1; delta<=dist; delta++) {
  121.                 if (x-delta>=0 && points[x-delta][y]->value==-1) {
  122.                     cleaner(points, x-delta, y, dist);
  123.                 }
  124.             }
  125.         }. 1point 3acres 璁哄潧
  126.         if (x<points.size()-1) {
  127.             for (int delta=1; delta<=dist; delta++) {
  128.                 if (x+delta<points.size() && points[x+delta][y]->value==-1) {
  129.                     cleaner(points, x+delta, y, dist);
  130.                 }
  131.             }
  132.         }. from: 1point3acres.com/bbs
  133.         if (y>0) {
  134.             for (int delta=1; delta<=dist; delta++) {
  135.                 if (y-delta>=0 && points[x][y-delta]->value==-1) {. From 1point 3acres bbs
  136.                     cleaner(points, x, y-delta, dist);
  137.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  138.             }
  139.         }
  140.         if (y<points[0].size()-1) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  141.             for (int delta=1; delta<=dist; delta++) {
  142.                 if (y+delta<points[0].size() && points[x][y+delta]->value==-1) {
  143.                     cleaner(points, x, y+delta, dist);
  144.                 }
  145.             }
  146.         }
  147.     }
  148.    
  149.     void dfsHelper(vector<vector<Point*>>& points, int x, int y, int dist, int& counter) {
  150.         //set to -1 for clean or remark. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  151.         points[x][y]->value=-1;
  152.         if (x>0) {
  153.             for (int delta=1; delta<=dist; delta++) {
  154.                 if (x-delta>=0 && points[x-delta][y]->value==1) {
  155.                     counter++;
  156.                     dfsHelper(points, x-delta, y, dist, counter);
  157.                 }
  158.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  159.         }
  160.         if (x<points.size()-1) {
  161.             for (int delta=1; delta<=dist; delta++) {
  162.                 if (x+delta<points.size() && points[x+delta][y]->value==1) {
  163.                     counter++;
  164.                     dfsHelper(points, x+delta, y, dist, counter);
  165.                 }. 1point3acres.com/bbs
  166.             }
  167.         }
  168.         if (y>0) {
  169.             for (int delta=1; delta<=dist; delta++) {
  170.                 if (y-delta>=0 && points[x][y-delta]->value==1) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  171.                     counter++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  172.                     dfsHelper(points, x, y-delta, dist, counter);
  173.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  174.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  175.         }
  176.         if (y<points[0].size()-1) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  177.             for (int delta=1; delta<=dist; delta++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  178.                 if (y+delta<points[0].size() && points[x][y+delta]->value==1) {
  179.                     counter++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  180.                     dfsHelper(points, x, y+delta, dist, counter);
  181.                 }
  182.             }
  183.         }
  184.     }
  185. };
复制代码
回复 支持 反对

使用道具 举报

leonsaber 发表于 2017-8-27 05:05:21 | 显示全部楼层
我记得他们家招聘时就好像要C+和Python, 不错了你还有OA,他家连OA都没给我
回复 支持 反对

使用道具 举报

chaohubian 发表于 2017-8-27 07:14:15 | 显示全部楼层
我刚做,第一个算时间,第二个判断正方形,第三个操作2维数据
回复 支持 反对

使用道具 举报

 楼主| lcq123 发表于 2017-8-27 07:24:32 | 显示全部楼层
chaohubian 发表于 2017-8-27 07:14
我刚做,第一个算时间,第二个判断正方形,第三个操作2维数据

这位肯定是一个大神啊!
回复 支持 反对

使用道具 举报

 楼主| lcq123 发表于 2017-8-27 07:26:50 | 显示全部楼层

虽然没认真看,不过感觉这道题有点像number of islander,只不过条件很多,得写很多dfs 处理函数
回复 支持 反对

使用道具 举报

chaohubian 发表于 2017-8-27 07:27:43 | 显示全部楼层
lcq123 发表于 2017-8-27 07:24
这位肯定是一个大神啊!

呵呵,跳大神
回复 支持 反对

使用道具 举报

lidoudou97979 发表于 2017-9-5 15:12:22 | 显示全部楼层
chaohubian 发表于 2017-8-27 07:14
我刚做,第一个算时间,第二个判断正方形,第三个操作2维数据

请问第三题能描述下吗 明天要做了 谢谢啦~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 15:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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