一亩三分地论坛

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

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

Online Coding Challenge

[复制链接] |试试Instant~ |关注本帖
纠结帝 发表于 2014-9-29 13:15:33 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 实习@ - Other - 在线笔试 |Other

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

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

x
Hackerrank 上面的一小时两题. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
两道都很简单 但是估计还是跪了

1. input: a list of number
    output: two strings
    Exp: [1, 3, 2, 3, 4, 1] output: a: 000101   b:110000
    解释:a的第一位是0 因为在list[0]的左边没有和list[0]同样数值的数. visit 1point3acres.com for more.
              a的最后一位是1 因为在list[5]的左边有和list[5]同样数值的数(1)
              b比较的是右边不是左边

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我用的是最小白的方法 就不解释了

2.Find the smallest number with just 0 and 1 which is divided by a given number.. visit 1point3acres.com for more.
ex input 4 -> output 100. 鍥磋鎴戜滑@1point 3 acres
我用的也是最小白的方法,但是不知道为什么只过了一个testcase 其他都挂了
用的python
求解法!
  1. user_input = raw_input()
  2. rst = '0'
  3. def no_other(a):
  4. #  print a
  5. #  print '2' in a
  6.   if '2' in a:
  7.     return False
  8.   if '3' in a:
  9.     return False
  10.   if '4' in a:
  11.     return False
  12.   if '5' in a:
  13.     return False
  14.   if '6' in a:
  15.     return False
  16.   if '7' in a:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.     return False
  18.   if '8' in a:
  19.     return False
  20.   if '9' in a:
  21.     return False
  22.   return True
  23. def q2(n):
  24.   n = int(n)
  25.   if n == 1:
  26.     print 1
  27.     return
  28.   for i in range(1,100000): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.     if no_other(str(n*i)):
  30.       print n*i
  31.       return
  32. q2(user_input)
复制代码
birdor 发表于 2014-10-1 08:24:19 | 显示全部楼层
纠结帝 发表于 2014-9-30 08:31
居然忘记看学长的回复了!. from: 1point3acres.com/bbs

第二个解法学长能再写详细一点吗.....

第二个解法只是一个小优化。在第一个解法中,计算
  1. S[k, m] = S[0, t] || S[1, t] || .. || S[k - 1, t]
复制代码
的时候,你要对右端 k 项进行逐一检验对吧?这是一个 for 循环语句。事实上这个循环是可以避免的,只需要用另一个变量 G[k, m] 记录 S[0, t], S[1, t] ... 中最早出现 1 的是哪一个。在递推的过程中不断更新 G,这样计算 S[k, m] 的时候只需要引用 G[k - 1, m] 而不需要进行循环检验了。于是时间复杂度降到了 O(k * N)。
回复 支持 1 反对 0

使用道具 举报

shinichish 发表于 2014-9-29 14:23:33 | 显示全部楼层
第二题用暴力破解只能过test case 11.。。。其他全部TLE。。。期待答案!
btw,lz面的哪家公司?
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2014-9-29 14:46:43 | 显示全部楼层
第二题貌似用dfs可以解,例如输入是i,假设x*i=answer,然后从个位起求x的每一位数,当前进位c=0,base=1,x=0 搜索步骤如下. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

(1)假如x!=0并且x*i符合答案的要求,则当前的min=x*i并返回,假如x*i大于某个数,就认为这次搜索失败,直接返回
(1)if c>0 则 a=10-c,b=11-c,则分别对满足d*i%10==a or d*i%10==b 两种情况的d进行处理,令,x=base*d+x ,c=d*i/10,base=base*10,跳到步骤1,没有符合的直接返回

手算了一下,好像7,17,12这几个数都无解
回复 支持 反对

使用道具 举报

birdor 发表于 2014-9-29 15:46:36 | 显示全部楼层
动态规划。

假设 n > 1,令 S[k, m] = 1 表示存在最高位是第 k 位的由 0 和 1 组成的模 n 余 m 的整数,S[k, m] = 0 则表示不存在。
S[0, 1] = S[0, 0] = 1,S[0, m] = 0 (1 < m < n)
设 t = (m - 10^k) % n,对于 k > 0,有
S[k, m] = S[0, t] || S[1, t] || .. || S[k - 1, t]. more info on 1point3acres.com
这样,一旦出现 S[k, 0] == 1,则说明题目要求的整数找到了。为了构造出这个整数,设一个变量 p 表示状态继承的路径 (链表):
p[k, m] =
(1) NULL 如果 S[k, m] == 0. more info on 1point3acres.com
(2) min{r} 如果 S[r, t] == 1 且 r < k. 1point3acres.com/bbs
这样,该答案的第一个 1 出现在 k 位,第二个 1 出现在 p[k, 0] 位,第三个 1 出现在 p[p[k, 0], (0 - 10^k) % n] 位……. 1point3acres.com/bbs

以上方法状态量有 n*k,状态转移时间 k,算法时间复杂度 n*k^2,比较慢。可以进行如下优化:

令 G[k, t] = min{r} 其中 S[r, t] == 1 且 r <= k,那么
G[0, 1] = G[0, 0] = 0,G[0, m] = Inf (1 < m < n)
S[k, m] =
(1) 0 如果 G[k - 1, t] = Inf
(2) 1 如果 G[k - 1, t] < Inf-google 1point3acres
G[k, m] = min{G[k - 1, t], k}
这样,状态量依然是 n*k,状态转移 1,算法时间复杂度 n*k,比较好。

回复 支持 反对

使用道具 举报

 楼主| 纠结帝 发表于 2014-9-29 21:12:57 | 显示全部楼层
shinichish 发表于 2014-9-29 14:23
第二题用暴力破解只能过test case 11.。。。其他全部TLE。。。期待答案!
btw,lz面的哪家公司?

是啊 你怎么知道? 你在kacherrank上面也做过?
面的twitter 你呢?
回复 支持 反对

使用道具 举报

TonyJang 发表于 2014-9-29 22:25:08 | 显示全部楼层
T家OA实在hackerrank上?
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-30 00:59:14 | 显示全部楼层
纠结帝 发表于 2014-9-29 21:12
是啊 你怎么知道? 你在kacherrank上面也做过?
面的twitter 你呢?

SnapChat的OA第二问也是这个问题,当时就是死活过不去,现在还不知道怎么解
回复 支持 反对

使用道具 举报

 楼主| 纠结帝 发表于 2014-9-30 01:02:56 | 显示全部楼层
shinichish 发表于 2014-9-30 00:59
SnapChat的OA第二问也是这个问题,当时就是死活过不去,现在还不知道怎么解

原来是这样
那snapchat有给你结果了吗?

我明天还有一个OA在hackerrank上面的
能不能share一下你snapchat oa的面经?
谢谢!
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-30 04:36:43 | 显示全部楼层
纠结帝 发表于 2014-9-30 01:02
原来是这样
那snapchat有给你结果了吗?

没有。。。你要面?. 鍥磋鎴戜滑@1point 3 acres
SnapChat的OA是Valid Sukudo,leetcode上的原题~~很简单的
回复 支持 反对

使用道具 举报

 楼主| 纠结帝 发表于 2014-9-30 04:51:22 | 显示全部楼层
shinichish 发表于 2014-9-30 04:36
没有。。。你要面?
SnapChat的OA是Valid Sukudo,leetcode上的原题~~很简单的

没有 还没有考虑过snapchat 直接投简历应该会被拒 但是也没有找到内推的学长学姐

第二个问题我找到了几个答案 但是还没有搞明白
http://stackoverflow.com/questio ... vided-by-a-given-nu

http://www.51nod.com/question/index.html#!questionId=33
回复 支持 反对

使用道具 举报

birdor 发表于 2014-9-30 07:40:18 | 显示全部楼层
纠结帝 发表于 2014-9-30 04:51
没有 还没有考虑过snapchat 直接投简历应该会被拒 但是也没有找到内推的学长学姐

第二个问题我找到了 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这是一个背包问题,解法我已经写在上面了啊。
回复 支持 反对

使用道具 举报

 楼主| 纠结帝 发表于 2014-9-30 08:31:00 | 显示全部楼层
birdor 发表于 2014-9-30 07:40
这是一个背包问题,解法我已经写在上面了啊。

居然忘记看学长的回复了!
.1point3acres缃
第二个解法学长能再写详细一点吗.....

谢谢!
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-30 12:31:28 | 显示全部楼层
纠结帝 发表于 2014-9-30 04:51
没有 还没有考虑过snapchat 直接投简历应该会被拒 但是也没有找到内推的学长学姐
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二个问题我找到了 ...

不懂+1.。。好像是背包问题。。研究一下。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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