Apr 24
工作这几年,面试了很多人,也结合了自己工作的经验,有一些心得,但是没有深入地思考过。

正好看到两位大佬的总结,很有共鸣,做个梳理,作为一面镜子,照照自己。



~ 张一鸣:我面了两千个年轻人,发现混的好的都有这5种特质

  @ https://www.toutiao.com/i6681549238490366472

点击在新窗口中浏览此图片


~ 谢熊猫君:如何辨认身边的聪明人?

  @ https://mp.weixin.qq.com/s/jvqMxdHRRBhhWl29fj3RHg

点击在新窗口中浏览此图片
Apr 24
这是罗凯同学内部《Go 快速入门》课程第五讲的作业。

第一题:使用 channel 完成打印1000以内的素数

package main

import "fmt"

func prime(c chan<- int) {
    i := 2
    for {
        isPrime := true
        for j := 2; j < i; j += 1 {
            if i % j == 0 {
                isPrime = false
            }
        }
        if isPrime {
            c <- i
        }
        i += 1
    }
}

func main() {
    c := make(chan int)
    go prime(c)
    for {
        p := <-c
        if p >= 1000 {
            break
        }
        fmt.Println(p)
    }
}



第二题:等价二叉查找树,来自 Go tour:https://tour.go-zh.org/concurrency/7

原题使用 tree.New(1) 来生成一个包含10个元素的二叉查找树,简单的实现可以基于这一点,正好从channel里读出10个数字。

以下这个版本的实现更复杂一些,不假定二叉查找树的长度,所以加一个 wrapper,用来 close channel 。

package main

import (
    "fmt"
    "golang.org/x/tour/tree"
)

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}

func WalkWrapper(t *tree.Tree, ch chan int) {
    Walk(t, ch)
    close(ch)
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
    c1 := make(chan int)
    c2 := make(chan int)
    go WalkWrapper(t1, c1)
    go WalkWrapper(t2, c2)
    for {
        v1, ok1 := <-c1
        v2, ok2 := <-c2

        if ok1 == false && ok2 == false {
            return true
        } else if ok1 == false || ok2 == false {
            return false
        } else {
            if v1 != v2 {
                return false
            }
        }
    }
}

func main() {
    t1 := &tree.Tree{&tree.Tree{nil, 1, nil}, 2, &tree.Tree{nil, 3, nil}}
    t2 := &tree.Tree{&tree.Tree{&tree.Tree{nil, 1, nil}, 2, nil}, 3, &tree.Tree{nil, 4, nil}}
    fmt.Println(t1)
    fmt.Println(t2)
    fmt.Println(Same(t1, t2))

    t3 := tree.New(1)
    t4 := tree.New(1)
    fmt.Println(t3)
    fmt.Println(t4)
    fmt.Println(Same(t3, t4))
}
Mar 31

LeetCode 69 - x 的平方根 不指定

felix021 @ 2019-3-31 15:34 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(180) | Via 本站原创
这是罗凯同学布置的 Golang 学习作业。

这题之前用 Python 刷过,用的是二分法,在 [1, n / 2] 区间内,找到第一个 x,使得 x ^ 2 <= n < (x + 1) ^ 2 ,用的是 STL 中 lowerbound 的算法。

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception("invalid input")
        if x < 2:
            return x
       
        left = 1
        length = x / 2
        while length > 1:
            half = length / 2
            middle = left + half
            if middle * middle > x:
                length = half
            else:
                left = middle
                length = length - half
        return left


罗凯同学提到,应该使用牛顿迭代法来完成。这个方法是听说过的,但是早就忘了,于是到 wikipedia 去找了一下:

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

求函数 f(x) 的零点,可以通过选取曲线上的任意一个点 x0 开始,然后计算 x1 = x0 - f(x1) / f'(x1) 的方式迭代,通常得到一个比 x0 更接近零点的 x1 。通过不断迭代,最终我们能找到一个零点 xn 。

对于求平方根,我们是要找到一个 x,使得 x ^2 - n = 0,也就是这里的 f(x) = x ^ 2 - n, f'(x) = 2 * x (勉强还记得这个求导公式……)

有了这个,答案就呼之欲出了:

import "math"

func mySqrt(x int) int {
    f := func (i float64) float64 {
        return i * i - float64(x)
    }
    g := func (i float64) float64 {
        return 2 * i
    }
    var i float64 = 1.0
    for math.Abs(f(i)) > 1e-6 {
        i = i - f(i) / g(i)
    }
    return int(math.Floor(i))
}


做完以后,我想起 Quake III 的作者 John Carmack 的 平方根倒数速算法,摘录一段内容:( src: https://blog.csdn.net/zyex1108/article/details/53540824 )

引用

Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。该系列的游戏不但画面和内容不错,而且即使计算机配置低,也能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克(John Carmack)。事实上早在90年代初DOS时代,只要能在PC上搞个小动画都能让人惊叹一番的时候,John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励,doom, doomII, Quake...每次都把3-D技术推到极致。他的3D引擎代码资极度高效,几乎是在压榨PC机的每条运算指令。


这个平方根倒数算法正是其中的一个例子。在3D游戏引擎中,求取照明和投影的波动角度与反射效果时,常需计算平方根倒数,而求平方根的常用算法效率较低。


Carmack 通过使用一个惊为天人的魔术常量 0x5f3759df,只需要做 1 次迭代(Quaker III源码中的为了提高精度的第二次迭代被注视掉了),就能得到一个足够精度的平方根,大幅提高了 3D 引擎的运行效率。

关于这个魔术常量,Carmack 表示并不是他自己发明的,至今为止仍未能确切知晓算法中所使用的特殊常数的起源。但 Carmack 凭一己之力,撑起了一个 3D 引擎的时代,以至于在1999年,登上了美国时代杂志评选出来的科技领域50大影响力人物榜单,并且名列第10位。

感兴趣的同学,可以在 Wikipedia 的 平方根倒数速算法 了解更多细节:

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95
Mar 20

GVim 在查看模式关闭输入法 不指定

felix021 @ 2019-3-20 16:49 [IT » 软件] 评论(0) , 引用(0) , 阅读(157) | Via 本站原创
困扰了很久的问题,搜了一下才发现解决起来很简单:

将 ESC 映射为 “ESC 并且设置关闭 IM ”

引用
inoremap <ESC> <ESC>:set iminsert=0<CR>


感谢:Tony's blog
Mar 12
这篇文章用于展示微软有多蠢。

除了环境光感应调整屏幕亮度之外,Surface Pro 还有一个傻逼特性,叫做 Adaptive Contrast(有些地方翻译为自适应亮度)。

这是 Intel 显卡驱动中实现的一个功能,在屏幕显示的内容亮度较低的时候(例如打开一个暗色调的图片),自动降低屏幕的亮度用于省电。

结果就是体验烂到爆炸。微软自作聪明起来,简直比苹果还蠢。

而且找不到关闭选项:Surface Pro 6 上的 Intel 驱动程序没有独立的控制面板,官网下载的驱动程序无法直接安装 —— 得先删除显卡,然而还是没有显卡控制面板。

微软技术支持服务上有人提出这个问题,官方人员的回答Windows自带的帮助功能一个尿性:都是套路,且毫无卵用。

网上可以搜到很多无效解决方案:

1. 设置 - 系统 - 显示 - “当光线变化时自动调节亮度”

误:不是这个功能。

2. 控制面板 - 系统和安全 - 电源选项 - 更改计划设置 - 更改高级电源设置 - 显示 - 启用自适应亮度 - 关闭

误:无效

3. 注册表编辑器 - 找到下述注册表键值 - 从 9240 修改为 9250

[HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control\Class\{4d36e968-e325-11ce-bfc1-08002be10318}\0001] FeatureTestControl

误:早期版本的 Surface Pro 上有 0001 这个项,但 Surface Pro 6 没有(只有 0000 ,而且 value 是 8200 而不是 9240 )。新建一个 0001 ,设置 FeatureTestControl = 9250 无效。

最后终于找到这里:https://mikebattistablog.wordpress.com/2016/05/27/disable-intel-dpst-on-sp4/

应该修改 0000 项里的 FeatureTestControl  ,这是一个 bitfield,其中从低到高的第 5 个 bit 表示是否启用  Intel Display Power Saving Technology (DPST)。将这个 bit 修改为 1 ,就可以禁用 DPST。

最终,将 0000 下的 FeatureTestControl  从 8200 改为 8210 ,并重启以后解决问题。
Mar 6

TourDeBabel 不指定

felix021 @ 2019-3-6 11:54 [IT » 其他] 评论(0) , 引用(0) , 阅读(200) | Via 本站原创
转自:https://code.google.com/archive/p/windows-config/wikis/TourDeBabel.wiki
原文:https://sites.google.com/site/steveyegge2/tour-de-babel

(无意中翻出了很多年前看过的这篇文章,发现是在google code上的,那就转载作为存档吧)

通天塔导游

(译注:圣经记载:在远古的时候,人类都使用一种语言,全世界的人决定一起造一座通天的塔,就是巴别塔,后来被上帝知道了,上帝就让人们使用不同的语言,这个塔就没能造起来。 巴别塔不建自毁,与其说上帝的分化将人类的语言复杂化,不如说是人类自身心灵和谐不再的分崩离析。之所以后来有了翻译,不仅是为了加强人类之间的交流,更寄达了一种愿望,希望能以此消除人际的隔阂,获求来自心灵的和谐及慰藉。真正的译者,把握血脉,抚平创痕,通传天籁,开启心门。)

这是我写的旋风式的编程语言简介—我本来为亚马逊开发者杂志本月的期刊写的,但是发现我写的东西没法…见人。

首先,我偶尔一不小心口出脏话,或者对上帝不恭的话,所以对很官方很正式的亚马逊上发表是不合适的; 所以我就把它塞到我的博客里了,我的博客反正没人看的。除了你以外。是的,只有你会看,你好啊。

其次,这是一项进行中的工程,现在只是东打一耙西搞一下,还没有精加工过的。又一个把它写到博客里的很大的理由。不需要很好,或很完整。就是我今天想说的一些话。请随便!

我的旋风式简介会讲C,C++,Lisp,Java,Perl,(我们在亚马逊用到的所有语言),Ruby (我就是喜欢),和Python,把Python加进来是因为—好吧,你看了就知道了,现在我可不说。

C

你必须懂C。为哈? 因为出于所有现实的理由,这个世界上你过去,现在,将来会用到的每一台计算机都是一台冯·诺曼机器,而C是一种轻量级的,很有表达力的语法,能很好的展现冯·诺曼机器的能力。
Feb 25

使用DNSPOD的API实现动态域名 不指定

felix021 @ 2019-2-25 14:47 [IT » 网络] 评论(0) , 引用(0) , 阅读(268) | Via 本站原创
0. 你得有一个 dnspod 帐号,并且把你的域名(例如 test.com )解析迁移过去(略)

1. 添加一个子域名的 A 记录,例如 ddns.test.com 指向 127.0.0.1

  $ export domain=test.com
  $ export subdomain=ddns

2. 生成一个token:参考官方说明 https://support.dnspod.cn/Kb/showarticle/tsid/227/

【务必注意】需要用生成的 ID 和 Token 这两个字段来组合成一个完整的 Token,组合方式为:"ID,Token"(用英文半角逗号分割),比如官方示例中,完整的 Token 为:13490,6b5976c68aba5b14a0558b77c17c3932 。

  $ export token=13490,6b5976c68aba5b14a0558b77c17c3932

3. 获取必要信息: 域名和子域名的ID

  $ curl -X POST https://dnsapi.cn/Record.List -d "login_token=${token}&format=json&domain=${domain}&sub_domain=${subdomain}"

返回结果为:{"status":{...}, "domain":{"id":640001, "name":"test.com", ...}, "info":{...}, "records":[{"id":"355300007", "name":"ddns", ...}]}

记录下对应域名的id 和子域名的id

  $ export domain_id=640001
  $ export subdomain_id=355300007

4. 获取外网ip

  $ wanip=`nc ns1.dnspod.net 6666`

5. 更新记录

  $ curl https://dnsapi.cn/Record.Ddns -d "login_token=${token}&format=json&domain_id=$domain_id&record_id=$record_id&sub_domain=$sub_domain&record_line=默认&value=$wanip"

= 完 =

(其实没完)其中 1、2、3 做完以后

6. 把 4、5 可以写到一个脚本里

  $ vi dnspod.sh
#!/bin/bash

domain_id=640001
record_id=355300007
sub_domain=ddns

wanip=`nc ns1.dnspod.net 6666`
curl https://dnsapi.cn/Record.Ddns -d "login_token=${token}&format=json&domain_id=$domain_id&record_id=$record_id&sub_domain=$sub_domain&record_line=默认&value=$wanip"


7. 设置 crontab

  $ crontab -e

引用
*/15 * * * * sh /path/to/dnspod.sh


=完=
Jan 29
TLDR版本:https://leetcode-cn.com/explore/ ,注册一个帐号开始做题就行了。

== 以下是正文 ==

作为一个程序员,编码能力是基础的基础。

我比较幸运,在大学的时候参加了学校的 ACM/ICPC 集训队,接触了 ACM/ICPC 比赛。这是一个针对大学生编程能力的世界级比赛,要求在几个小时的时间里完成若干道不同难度的题目,其中很多题目不仅需要复杂的算法、有各种特殊情况需要考虑,而且还有变态级的效率要求。强如楼教主(楼天城),也仅在 2009 年获得世界总决赛的第二名。

此外,从我观测到的结果来看,但凡从集训队走出去的成员(无论其竞赛成绩如何),**其毕业后的第一份工作(通常都是 BAT )乃至之后的发展,都显著高于计算机专业的平均水平**。

虽然在集训队里有教练,也有大神,但日常学习主要还是靠自己。看书学习固然是一种方式,但是比较枯燥,也不容易衡量自己的学习成果。另一方面,由于赛事多年的发展和积淀,国内参赛实力较强的大学(例如北大、杭州电子科技大学、华中科技大学)都创建了自己的在线测评系统(英文名叫 Online Judge,简称 OJ)。

OJ 上沉淀了多年来的竞赛题目,每一个题目都包含相应的题面、输入说明、输出要求、基础测试用例;用户按要求编写代码后,将代码提交给 OJ,系统会在后台启动自动化测试,告知测评结果。

由于 OJ 系统的存在,做题变成了一种乐趣,通过努力解决了一个问题,系统会给出红色的 Accepted 字样,就像一种奖赏;而在这个过程中,也可以直接地看到自己的进步。

工作以后,我非常庆幸当年自己在 OJ 系统刷过这些题,夯实了编程能力,在工作中能够完成更高质量的代码。而在过去几年的面试过程中,我发现很多来应聘的程序员,往往只能应对简单的情况,处理不好边界问题、例外情况、运行效率带来的挑战。

遗憾的是,由于学校自建的 OJ 往往都是学生自己开发、自己维护(我也写过一个,维护过几年,深有体会),体验较差,对存量题目的组织、整理也比较随意(往往只是简单的罗列),而且由于比赛是英文环境,题面往往也都是纯英文的,给竞赛圈之外的同学带来了一定门槛。

所幸,近年来,第三方(商业公司、志愿者社区)的 OJ 系统也逐渐完善,其中一个我很喜欢的平台是 LeetCode ,大约成立于 2008 年吧,上面的题多是业内 TOP 公司的面试题,很多人通过刷这些题来应聘喜欢面试算法的 NTMGBA 系列公司(注:Netease,Tencent,Microsoft,Google,Baidu,Alibaba/Amazon)。

相比各个学校维护的 OJ 平台,LeetCode 的体验令人称道:

* 支持多种语言,包括 PHP、Python、Go、Rust、Javascript,甚至还有基于 MySQL 的题目
* 推出了完整的中文版,包括纯中文的题面
* 对题目做了细致的整理,打上各种标签,包括难度(简单、中等、困难)、话题(字符串、堆/栈、贪心算法、动态规划等)
* 通过合集的方式,将题目整理归档(例如腾讯精选50题、初级算法、中级算法等)
* 对于错误的情况,给出明确的错误原因,及相应的输入输出数据,方便自我纠正
* 许多题目有详尽的官方解答,即使不会做也能够直接学习

LeetCode 上的题目大致可以分成两种(参考 CoolShell 博客说明):

1. 算法题。大多是套路题,每道题目都需要特定的算法,例如BFS、DFS、动态规划、回溯等。通过做这些题,能够让自己对这些最基础的算法的思路有非常扎实的了解和训练,也能很好地锻炼自己的思维能力(烧脑)。

2. 编程题。比如:atoi,strstr,add two num,括号匹配,字符串乘法,通配符匹配,文件路径简化,Text Justification,反转单词等等。这些题目的题面都很简单,大部分程序员都能读懂,但是魔鬼藏在细节中,具体的实现往往需要考虑多种情况。通过做这些题,可以非常好的训练自己对各种情况的考虑,以及对程序代码组织的掌控能力(其实就是其中的状态变量)。程序中的状态正是程序变得复杂难维护的直接原因。

每个程序员内心都有一个大神梦,但是别忘了,大神也是从菜鸟一步一个脚印走过来的,而 LeetCode 就是一个很好的垫脚石,共勉。
分页: 1/97 第一页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]