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

一亩三分地论坛

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

Coursera跪经 9/25

[复制链接] |试试Instant~ |关注本帖
royyjzhang 发表于 2016-9-26 00:54:33 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类General 硕士 全职@Coursera - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
第一题是magic binary string,题目可以在这里看到http://www.1point3acres.com/bbs/thread-202232-1-1.html. visit 1point3acres for more.
根据贪心把1的个数最多的放在靠前的位置,如果1的个数一样多就把长度更长的放在前面,莫名其妙有runtime error
  1. string maxMagicBS(string s) {.留学论坛-一亩-三分地
  2.         int n = s.length(), i, j, currentone, leftone, rightzero;
  3.         vector<Node> adjs; 来源一亩.三分地论坛.
  4.         Node now, temp;. From 1point 3acres bbs
  5.         string result;
  6.         if (n == 0) {
  7.                 return s;.本文原创自1point3acres论坛
  8.         }
  9.         i = 0;
  10.         currentone = 0;
  11.         leftone = 0;
  12.         while (i < n) {
  13.                 if (s[i] == '0') {
  14.                         if (currentone != 0) {
  15.                                 j = i + 1;
  16.                                 while ((j < n) && (s[j] == '0') && (j - i + 1 <= currentone)) {
  17.                                         j++;. from: 1point3acres
  18.                                 }.1point3acres网
  19.                                 if (adjs.size() == 0) {
  20.                                         leftone = currentone - j + i;
  21.                                 } 来源一亩.三分地论坛.
  22.                                 if (currentone != 0) {
  23.                                         now.right = j - 1;
  24.                                         now.left = i - (j - i);
  25.                                         now.numofone = i - now.left;
  26.                                         currentone = 0;
  27.                                         adjs.push_back(now);. visit 1point3acres for more.
  28.                                 }. 一亩-三分-地,独家发布
  29.                                 i = j;
  30.                         }
  31.                         else {
  32.                                 j = i + 1;
  33.                                 while ((j < n) && (s[j] == '0')) {
  34.                                         j++;
  35.                                 }
  36.                                 if (j == n) {. from: 1point3acres
  37.                                         i = j;
  38.                                 }
  39.                                 else {.1point3acres网
  40.                                         if (!adjs.empty()) {
  41.                                                 now = adjs[adjs.size() - 1];
  42.                                                 now.right = i;
  43.                                                 adjs.pop_back();
  44.                                                 while ((!adjs.empty()) && (now.numofone-(now.right-now.left+1) < 0)) {
  45.                                                         temp = adjs[adjs.size() - 1];
  46.                                                         adjs.pop_back();
  47.                                                         now.numofone += temp.numofone;. From 1point 3acres bbs
  48.                                                         now.left = temp.left;
  49.                                                 }
  50.                                                 if ((adjs.empty()) && (now.numofone - (now.right - now.left + 1) < 0)) {
  51.                                                         leftone--;
  52.                                                         now.left--;
  53.                                                         adjs.push_back(now);. 牛人云集,一亩三分地
  54.                                                 }
  55.                                         }
  56.                                         i++;
  57.                                 }. 1point3acres
  58.                         }
  59.                 }
  60.                 else {. 围观我们@1point 3 acres
  61.                         i++;. from: 1point3acres
  62.                         currentone++;
  63.                 }
  64.         }
  65.         rightzero = n - 1 - now.right;
  66.         for (i = 0; i < adjs.size(); i++) {
  67.                 for (j = i + 1; j < adjs.size(); j++) {
  68.                         if (adjs[i].numofone < adjs[j].numofone) {
  69.                                 now = adjs[i];. From 1point 3acres bbs
  70.                                 adjs[i] = adjs[j];
  71.                                 adjs[j] = now;
  72.                         }
  73.                         else if ((adjs[i].numofone == adjs[j].numofone) && (adjs[i].left - adjs[i].right + 1 < adjs[j].left - adjs[j].right + 1)) {
  74.                                 now = adjs[i];. 1point3acres
  75.                                 adjs[i] = adjs[j];
  76.                                 adjs[j] = now;
  77.                         }
  78.                 }. 一亩-三分-地,独家发布
  79.         }
  80.         if (leftone != 0) {
  81.                 result += '1'*leftone;
  82.         }
    . 留学申请论坛-一亩三分地
  83.         for (i = 0; i < adjs.size(); i++) { 来源一亩.三分地论坛.
  84.                 result += s.substr(adjs[i].left, adjs[i].right - adjs[i].left + 1);-google 1point3acres
  85.         }. 留学申请论坛-一亩三分地
  86.         if (rightzero != 0) {
    . more info on 1point3acres
  87.                 result += '0'*rightzero;
  88.         }
  89.         int check = 0;
  90.         for (i = 0; i<n; i++) {. 一亩-三分-地,独家发布
  91.                 check = check + (result[i] - s[i])*i;. Waral 博客有更多文章,
  92.         }
  93.         return result;
  94. }
复制代码
第二题是number of distinct sub-palindrome
用dp+计算在该位置回文字符串的半径,这样对于一个找到的回文字符串,算了左半边就不用算右半边了。
每个位置根据左半边的情况有以下四种情况的右半边
1. 左半边的位置不是回文字符串,那右半边对称位置也不是
2. 左半边的回文字符串被包含在整个回文字符串中,右半边同样被包含
3. 左半边的回文字符串半径大于在整个回文字符串半径,右半边应当将长度减小
4. 右半边字符串的半径可能更大,该情况会在之后计算中解决

然后用set检测是否有重复。

这个能过
  1. int para(string str) {
  2.         set<string> check;
  3.         int l = str.length(), result = 0;
    . from: 1point3acres
  4.         if (l == 0) {. 一亩-三分-地,独家发布
  5.                 return 0;
  6.         }
  7.         if (l == 1) {
  8.                 return 1;
  9.         }
  10.         vector<vector<int>> dp(2, vector<int>(l+1, 0));
  11.         str = "@" + str + "#";
    . visit 1point3acres for more.
  12.         for (int j = 0; j<=1; j++) {
  13.                 int r = 0;
  14.                 dp[j][0] = 0;
  15.                 int i = 1;. 1point 3acres 论坛
  16.                 while (i <= l) {. 1point 3acres 论坛
  17.                         while (str[i - r - 1] == str[i + j + r])
  18.                                 r++;. 一亩-三分-地,独家发布
  19.                         dp[j][i] = r;
  20.                         int k = 1;. from: 1point3acres
  21.                         while ((dp[j][i - k] != r - k) && (k<r)) {. more info on 1point3acres
  22.                                 dp[j][i + k] = min(dp[j][i - k], r - k);
  23.                                 k++;
  24.                         }
  25.                         r = max(r - k, 0);
  26.                         i += k;
  27.                 }
  28.         }. 留学申请论坛-一亩三分地
  29.         str = str.substr(1, l);
  30.         check.insert(string(1, str[0]));
  31.         result++;
  32.         for (int i = 1; i<l; i++) {
  33.                 for (int j = 0; j <= 1; j++) {
  34.                         for (int r = dp[j][i]; r>0; r--) {
  35.                                 if (check.find(str.substr(i - r - 1, 2 * r + j)) == check.end()) {
  36.                                         check.insert(str.substr(i - r - 1, 2 * r + j));
  37.                                         result++;
  38.                                 }
  39.                         }
  40.                 }. 1point3acres
  41.                 if (check.find(string(1, str[i])) == check.end()) {
  42.                         check.insert(string(1, str[i]));
  43.                         result++;
  44.                 }
  45.         }
  46.         return result;
  47. }
复制代码
跪求攒人品

评分

1

查看全部评分

窗外一棵树 发表于 2016-9-26 01:34:00 | 显示全部楼层
楼主这是 OA 还是电面? 现在已经换成面题了吗
回复 支持 反对

使用道具 举报

 楼主| royyjzhang 发表于 2016-9-26 05:48:43 | 显示全部楼层
窗外一棵树 发表于 2016-9-26 01:34
楼主这是 OA 还是电面? 现在已经换成面题了吗

这是60分钟的OA
回复 支持 反对

使用道具 举报

头像被屏蔽
cococecil 发表于 2016-9-26 06:02:24 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
cococecil 发表于 2016-9-26 06:42:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| royyjzhang 发表于 2016-9-26 07:15:07 | 显示全部楼层
cococecil 发表于 2016-9-26 06:02
貌似第一题可以从后到前O(n)?
int cnt = 0;
output = str2number(str);

这个从后向前的算法不行,可以试试看例子11011000,这是题目提供的标准样例,从你这个算法来看的话只有到str[0]才会发生交换,但这个和题目中只要相邻的magic string就能交换的原则是违背的。这个样例中10,1100两个是可以交换的magic string,输出是11100100
回复 支持 反对

使用道具 举报

enemydodo 发表于 2017-10-10 10:35:21 | 显示全部楼层
赞楼主,zszszszszszsz
回复 支持 反对

使用道具 举报

cszhazha 发表于 2018-1-6 14:29:33 | 显示全部楼层
不过第一题第三个testcase就过不了啊
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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