一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1772|回复: 12
收起左侧

G家

[复制链接] |试试Instant~ |关注本帖
zxzczvb 发表于 2014-4-3 05:27:49 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
刚面完, 面试官像一具尸体一声不吭, LZ仿佛和尸体自言自语了50分钟···· 攒rp求pass
游客,本帖隐藏的内容需要积分高于 50 才可浏览,您当前积分为 0。 查看如何攒积分

评分

6

查看全部评分

本帖被以下淘专辑推荐:

raosuper 发表于 2014-6-12 13:33:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地

这个算法貌似是错误的,

如果n = 75, 你的程序返回的是 4 , 8*8 + 3*3 + 1*1 + 1*1 = 75

实际最优解是  3 :  7*7 + 5*5 + 1*1 = 75
回复 支持 1 反对 0

使用道具 举报

lihan96163 发表于 2014-4-3 09:53:20 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主能解释一下第一题
. 1point 3acres 璁哄潧
只包含2个distinct ASCII character 是什么意思?
能否举个例子?
. more info on 1point3acres.com
万分感谢
回复 支持 反对

使用道具 举报

lihan96163 发表于 2014-4-3 09:53:30 | 显示全部楼层
楼主能解释一下第一题

只包含2个distinct ASCII character 是什么意思?
能否举个例子?

万分感谢
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-4-3 10:35:31 | 显示全部楼层
第二题,dp转移的时候可以枚举平方数,dp[i] = dp[j + (i - j)], (i - j) = k * k <= i, 这样复杂度就是O(n*n^(1/2))了,不知道还有更好的性质或者优化么
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2014-4-6 08:03:08 | 显示全部楼层
# -*- coding: utf-8 -*-
"""
given an integer ,find 最小长度minlen 的expression of integer, minlen 定义为多少个完全平方数相加. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
例如 14 = 1 + 4 + 9, minlen = 3
"""


def minlen(target):
    i = 1
    f = [0] * (target + 1). visit 1point3acres.com for more.
    while i * i <= target:
        f[i] = 1
        i += 1
. 1point 3acres 璁哄潧
    for i in range(1, target + 1):
        tmp_min = i
        j = 1
        while j * j <= i:. more info on 1point3acres.com
            tmp = f[i - j * j] + 1. from: 1point3acres.com/bbs
            tmp_min = min(tmp_min, tmp)
            j += 1
        f[i] = tmp_min
    print f
    return f[target]
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2014-4-6 08:03:34 | 显示全部楼层
# -*- coding: utf-8 -*-
"""
given an integer ,find 最小长度minlen 的expression of integer, minlen 定义为多少个完全平方数相加. from: 1point3acres.com/bbs
例如 14 = 1 + 4 + 9, minlen = 3
"""


def minlen(target):. From 1point 3acres bbs
    i = 1
    f = [0] * (target + 1). visit 1point3acres.com for more.
    while i * i <= target:
        f[i] = 1
        i += 1. 1point 3acres 璁哄潧
. 1point 3acres 璁哄潧
    for i in range(1, target + 1):. From 1point 3acres bbs
        tmp_min = i. Waral 鍗氬鏈夋洿澶氭枃绔,
        j = 1
        while j * j <= i:
            tmp = f[i - j * j] + 1
            tmp_min = min(tmp_min, tmp). 1point3acres.com/bbs
            j += 1-google 1point3acres
        f[i] = tmp_min. From 1point 3acres bbs
    print f.鐣欏璁哄潧-涓浜-涓夊垎鍦
    return f[target]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

walnutti 发表于 2014-4-18 13:40:44 | 显示全部楼层
“follow up: character可能有1 billion 怎么办”。楼主能解释下第一题这个followup么?多谢。
回复 支持 反对

使用道具 举报

renchaorevee 发表于 2014-4-21 13:14:44 | 显示全部楼层
第二个用Greedy Algorithm 会更容易把
回复 支持 反对

使用道具 举报

afaris 发表于 2014-6-11 23:43:26 | 显示全部楼层
2.

def f(n):
     if n==1:
             return 1
     k = int(math.sqrt(n)). 鍥磋鎴戜滑@1point 3 acres
     if n==k**2:
             return 1
     return 1+f(n-k**2)
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
almost constant time
回复 支持 反对

使用道具 举报

afaris 发表于 2014-6-12 16:22:23 | 显示全部楼层
raosuper 发表于 2014-6-12 06:33
这个算法貌似是错误的,

如果n = 75, 你的程序返回的是 4 , 8*8 + 3*3 + 1*1 + 1*1 = 75
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
多谢提醒!. 鍥磋鎴戜滑@1point 3 acres

>>> def f(n):
...     k = int(math.sqrt(n))
...     if n==k**2:
...             return 1-google 1point3acres
...     minlen=9999
...     while k>math.sqrt(n/2)-1:.1point3acres缃
...             if minlen>1+f(n-k**2):
...                     minlen = 1+f(n-k**2)
...             k-=1
...     return minlen

回复 支持 反对

使用道具 举报

tianyang1011 发表于 2014-6-22 02:45:47 | 显示全部楼层
非常感谢楼主啊!~~,我被问了这一题~~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-22 19:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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