传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2448|回复: 12
收起左侧

G家

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

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

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

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

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

评分

6

查看全部评分

本帖被以下淘专辑推荐:

raosuper 发表于 2014-6-12 13:33:57 | 显示全部楼层
afaris 发表于 2014-6-11 07:43
2.. from: 1point3acres.com/bbs

def f(n):
. visit 1point3acres.com for more.
这个算法貌似是错误的,

如果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 | 显示全部楼层
楼主能解释一下第一题

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

万分感谢
回复 支持 反对

使用道具 举报

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))了,不知道还有更好的性质或者优化么
回复 支持 反对

使用道具 举报

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
""". from: 1point3acres.com/bbs


def minlen(target):
    i = 1
    f = [0] * (target + 1)
    while i * i <= target:
        f[i] = 1. Waral 鍗氬鏈夋洿澶氭枃绔,
        i += 1

    for i in range(1, target + 1):
        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 -*-
"""
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:.1point3acres缃
        f[i] = 1
        i += 1

    for i in range(1, target + 1):
        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]. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

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)). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
     if n==k**2:
             return 1
     return 1+f(n-k**2)
. from: 1point3acres.com/bbs
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

多谢提醒!. visit 1point3acres.com for more.

>>> def f(n):. 鍥磋鎴戜滑@1point 3 acres
...     k = int(math.sqrt(n))
...     if n==k**2:
...             return 1
...     minlen=9999
...     while k>math.sqrt(n/2)-1:. from: 1point3acres.com/bbs
...             if minlen>1+f(n-k**2):
...                     minlen = 1+f(n-k**2)
...             k-=1
...     return minlen

回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-23 08:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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