一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1649|回复: 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 | 显示全部楼层

这个算法貌似是错误的,
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果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 | 显示全部楼层
楼主能解释一下第一题. from: 1point3acres.com/bbs

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

万分感谢
回复 支持 反对

使用道具 举报

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

只包含2个distinct ASCII character 是什么意思?
能否举个例子?
. From 1point 3acres bbs
万分感谢
回复 支持 反对

使用道具 举报

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

使用道具 举报

johnnywsd 发表于 2014-4-6 08:03:08 | 显示全部楼层
# -*- coding: utf-8 -*- 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
""". more info on 1point3acres.com
given an integer ,find 最小长度minlen 的expression of integer, minlen 定义为多少个完全平方数相加
例如 14 = 1 + 4 + 9, minlen = 3
"""
. From 1point 3acres bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
def minlen(target):. 鍥磋鎴戜滑@1point 3 acres
    i = 1
    f = [0] * (target + 1)
    while i * i <= target:
        f[i] = 1
        i += 1

    for i in range(1, target + 1):. 1point3acres.com/bbs
        tmp_min = i
        j = 1
        while j * j <= i:
            tmp = f[i - j * j] + 1
            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 -*-
"""-google 1point3acres
given an integer ,find 最小长度minlen 的expression of integer, minlen 定义为多少个完全平方数相加
例如 14 = 1 + 4 + 9, minlen = 3
"""
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

def minlen(target):
    i = 1
    f = [0] * (target + 1)
    while i * i <= target:
        f[i] = 1
        i += 1

    for i in range(1, target + 1):
        tmp_min = i
        j = 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        while j * j <= i:. from: 1point3acres.com/bbs
            tmp = f[i - j * j] + 1
            tmp_min = min(tmp_min, tmp)
            j += 1
        f[i] = tmp_min. more info on 1point3acres.com
    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:. 1point3acres.com/bbs
             return 1
     k = int(math.sqrt(n))
     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

多谢提醒!

>>> def f(n):
...     k = int(math.sqrt(n))
...     if n==k**2:
...             return 1
...     minlen=9999
...     while k>math.sqrt(n/2)-1:
...             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, 2016-12-7 02:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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