风兮风兮
自河东兮
窈窕淑女
在梦中兮
云兮云兮
过天门兮
盈盈笑语
无故人兮
雨兮雨兮
谱心曲兮
诸法空相
无道侣兮
电兮电兮
至河畔兮
无住生心
菩提现兮
风、云、雨、电的读音从一声(阴平)依次到四声(去声),是不是很好玩?
风兮风兮
自河东兮
窈窕淑女
在梦中兮
云兮云兮
过天门兮
盈盈笑语
无故人兮
雨兮雨兮
谱心曲兮
诸法空相
无道侣兮
电兮电兮
至河畔兮
无住生心
菩提现兮
风、云、雨、电的读音从一声(阴平)依次到四声(去声),是不是很好玩?
在加拿大,华人所谓的“报税”一词英文是“to file your tax return”,字面意思就是申请你的退税。一般情况下,对于普通的工薪族,政府通过公司都是在平时多“克扣”一些税款,所以报税的时候会多少退回来一些。而对于那些平时没缴纳税金的人,则是需要补交税款了。
日本的个人所得税处理除了平时公司同样代为扣缴一些税款外,分为两个主要动作:“年末調整”和“確定申告”。对于普通工薪族,往往通过“年末調整”,就已经精算过当年需要缴纳的税金并多退少补了,其本质就是税务机关把这部分责任转嫁给了各公司的会计部门。如果还有其他特殊情况,属于公司的会计部门管不到的,则可以自己向税务署提交“確定申告書”,来最后精算并把税款清算完毕。在加拿大,这部分工作则完全由税务机关CRA来管理,公司不会在年末代为精算。如果欠CRA的税金,则需要在次年4月末之前提交报税的申请材料(企业则需要在3月初完成T4申报),否则会对应缴税款有惩罚性的利息。如果是CRA欠自己税金,则似乎没有什么期限。记得刚来加拿大的时候,感到十分抑郁,除了工作外,没有任何兴趣去做任何事情,所以报税也一直拖到了秋季才勉强处理完。结果CRA除了退还了部分税金外,还附加了一点利息,因为他们把这部分钱多持有了几个月(虽然是我的责任)。当然,这些还是尽早处理完比较好。
直接填表报税是很麻烦的,因为你需要弄清楚所有那些词汇的意思,并正确处理各种数字。很多人都是请会计师代劳。如果想省点费用自己处理的话,市面上有一些报税软件可用,有收费的,也有免费的。我这些年来都是用一款在线的免费报税软件Simple Tax(近来被Wealthsimple收归麾下)。在这方面,日本做得比较好,因为官方提供这种在线的报税软件,大家都可以免费使用。具体的填写方法则是首先把各种材料准备好,然后一一对照填进去就好了,过程很简单(上面我说一直拖着只是因为有点抑郁症的原因,不是说这个工作多难)。如果是2月下旬的话(今年是2月22日起),该软件还可以从CRA提取很多数据直接填进去,免了你自己填很多内容。
对于普通工薪族来说,主要有以下几种材料:
填写完毕后,经过报税软件检验无误后,就可以在线提交给CRA,然后就是等着退税了。上述材料不需要提交给CRA,但是需要自己保存7年,以便在CRA需要查证的时候能够拿出来。
这里强烈建议在CRA注册一个账户,这样就可以方便地在线查询很多税务的信息。还可以把自己的银行账号填写进去,这样,CRA就能尽快地把退税款直接汇入该银行账户,而不是邮寄一张支票。前者不但可以更快地收到退税款,还可以避免因支票在邮寄过程中丢失而带来的麻烦。
另外,对于新移民,刚来加拿大这里的时候,只要翻开中文报纸,往往立即映入眼帘的就是所谓申报海外资产的会计师广告。我多年前也去听过一次,感觉跑那么远白白浪费了时间。这里附带提一下,就是CRA对你的海外资产没有任何兴趣知道,而是只希望你申报自己的海外收入。如果海外资产本身不产生任何收入的话,则不需要申报。对那些做出一副CRA代言人的样子的所谓会计师,直接无视之即可。我们需要的是站在我们的角度帮我们处理税务的会计师,不是用莫名其妙的理由威逼胁迫我们购买其服务的自称的CRA非正式的代言人。很多人主要是怕自己大额汇款到加拿大的时候会有麻烦。其实如果海外税务都处理过了的话,CRA对此没什么兴趣。有兴趣的是其他一些机关,主要是想确认这里没有洗黑钱等非法来源的嫌疑。所以,如果万一被查到的话,只要能说明这都是来自于你自己的正当收入就行了。
由爱生忧,由爱生怖。离于爱者,无忧无怖。
辗转红尘,慧剑如故。安得挥斩,踏上归路。
山峦水雾,如泣如诉。一切皆空,宛如画布。
桃红柳绿,因缘际遇。尘终归尘,土终归土。
心念如织,业识如瀑。舍此心形,留我明悟。
RESP(Registered Education Savings Plans)是为孩子存未来的大学学费的一个账户,除了同样可以用于投资而且可以得到免税增长外,其主要特点包括:
总的来说,RESP相比于RRSP和TFSA优点比较小,所以我一直有点懒得关注。当然,资金足够的话,就一并都投满肯定只有好处而没坏处。对于新移民来说,如果刚开始手头的可投资资金不够多的话,就应该平衡考虑RESP和RRSP、TFSA等账户。具体的以后再讨论。
年满18岁的有SIN的人都可以为某个孩子开设RESP账户,每个孩子可以有多个人为他开户。但是所有账户合计投入金额(不包括政府给的补助和投资增长额)不能超过50,000加元。否则,超额部分会有每月1%的惩罚利率。
账户可以保持36年(“活到老学到老”的原则)。
RESP的主要好处
使用方法
很遗憾的是,我最喜欢的EQBank和Wealthsimple Trade目前不支持RESP账户。所以,这里只推荐Questrade。
Questrade是加拿大最大的网上券商。有美元账户,适合用于美国股票投资。ETF买入不要手续费(但是,需要缴纳交易所收的ECN fee),卖出时有手续费。手续费也比较便宜,$4.95-9.95。同时,该账户还适用于美国股票投资。另外,一个小技巧是用于做美元和加元之间的低手续费兑换:比如先用加元买入多伦多证交所上市的某证券,再找客服转换为在美国上市的同样的证券,然后卖出,就转换成美元了。这种操作比在银行换能省不少手续费,只是需要几天的时间才能完成。还有,需要注意的是,Questrade会收不活跃账户手续费,但很容易避免:只要每个季度都交易一次就可以了。
点击这里开设Questrade账户,如果开设账户(仅限于这里讨论的这些账户,属于“Self-directed”一类的)后的三个月内投入1000加元或以上的资金,根据资金的多少,可以得到25-250加元的奖励(目前的情况,以后有可能改变)。
类似于RRSP,TFSA(Tax Free Savings Account)的名字也有点误导,实际上也是既可以储蓄,又可以投资。
普通账户中capital gain的税收方法是,把capital gain的一半算入你的收入,再按边际税率计算税金。所以,如果工资和capital gain都很高的话,很可能会达到最高税率。这正是TFSA账户的可贵之处。
不建议投资风险高的股票。如果损失了很多钱,就会永久地损失了TFSA额度。因此,TFSA账户比较适合投资稳健的股票。当然了,难道普通账户就要用来去赌吗?我觉得各种账户都应该如此。
我原本觉得应该根据投资组合理论,除了股票外,也加入一些诸如GIC(定存)和债券等低风险金融商品。后来想了一下,完全不必如此。TFSA的关键在于投资的免税增长。那些低风险的金融商品本身也没多少收益,这样,免税与否又有什么关系呢?所以,应该把这类金融商品放在普通账户或干脆存在银行里,而把TFSA账户里的资金完全买成股票(或股票类ETF)!(*1)当然,可以根据市场情况而保存一些现金在TFSA账户,用于在合适的时机买入股票。但这里的要点是,不要把定存、债券等放在这里。可以利用普通账户来做这方面的平衡(除非普通账户里的资金太少,不足以平衡TFSA账户里的股票仓位),否则,TFSA账户使用得就不够有效率。
(*1)2023.09.15后记:从2022年末开使,随着政府开始加息为之前的量化宽松降温,GIC利率越来越高也越来越吸引人了。同时,现在股市处于风险较高的阶段。因此,现在倒是可以投入一些GIC。所以说,什么话都不能说得太绝对了。这个世界总是在不停地变化着的。应该时时审时度势,做出当下最佳的判断。
跟RRSP账户相同,建议在券商开设TFSA账户,而不要在诸如银行、保险公司和其他投资公司开设这类账户。推荐以下两个券商:
Wealthsimple Trade:买卖股票不收手续费,所以适合加拿大股票的投资。美国股票的话,由于没有美元账户,买入时只能用加元,卖出时也只能收到加元,所以有两次货币兑换发生。而偏偏这里的兑换费用较高(1.5%),所以不太适合美国股票投资。美国股票建议使用下述的Questrade账户投资。
点击这里开设Wealthsimple Trade账户,可以得到10加元的奖励(目前的情况,以后有可能改变)。虽说他们也是在设法获得更多的账户,但该公司本身在我心目中是最好的。适合开设RRSP和TFSA账户。
Questrade:加拿大最大的网上券商。有美元账户,适合用于美国股票投资。ETF买入不要手续费(但是,需要缴纳交易所收的ECN fee),卖出时有手续费。手续费也比较便宜,$4.95-9.95。同时,该账户还适用于美国股票投资。另外,一个小技巧是用于做美元和加元之间的低手续费兑换:比如先用加元买入多伦多证交所上市的某证券,再找客服转换为在美国上市的同样的证券,然后卖出,就转换成美元了。这种操作比在银行换能省不少手续费,只是需要几天的时间才能完成。还有,需要注意的是,Questrade会收不活跃账户手续费,但很容易避免:只要每个季度都交易一次就可以了。
点击这里开设Questrade账户,如果开设账户(仅限于这里讨论的这些账户,属于“Self-directed”一类的)后的三个月内投入1000加元或以上的资金,根据资金的多少,可以得到25-250加元的奖励(目前的情况,以后有可能改变)。虽说他们也是在设法获得更多的账户,但该公司本身在我心目中是很好的,仅次于Wealthsimple Trade,对于TFSA账户,如果想投资美国股票的话,建议在Questrade开户。
梦里山崩,心上龙腾
虚空处,方寸之能
蹉跎数载,灯火三更
令妄心和,痴心减,慧心增
有缘可见,无意相逢
现如今,元利贞亨
娑婆可去,极乐能生
念南无佛,南无法,南无僧
在加拿大,投资账户分为两大类:注册投资账户(Registered Investment Account)和非注册投资账户(Non-Registered Investment Account)。这里的“注册”是指对政府注册,因为这类账户往往伴随着享有税务上的延缓或免除等优待,因此,政府需要紧紧地盯住这些账户。非注册投资账户则是那些普通的账户,除了盈利后需要交税外,政府不会理会你做何种操作。
投资账户的一些典型例子:RRSP,TFSA,RESP,RRIF。这里先讨论RRSP。
RRSP(Registered Retirement Savings Plan)名字有点误导,似乎是个储蓄账户。实际上,你可以在该账户内进行投资操作。可能政府更倾向于鼓励人们尽量不要做高风险的操作吧?毕竟其目的是为了补充退休金的不足,也就是为了降低政府在这方面的财政压力。简言之,RRSP就相当于美国的“401(K)”,日本的“確定拠出年金”。具体一点说,就是根据你去年的收入,来决定一个投入额度:收入越高,这个额度就越高,直到到达上限。如果在该额度内把资金投入RRSP账户,则投入的这部分钱会起到抵税的作用(即在计算税金时,先把该金额从收入中扣除),之后在取出时,按取出当年的边际税率课税。同时,RRSP账户内的投资可以享受到免税增长的优待。
所以,需要搞清楚的是,RRSP内的投资不是免税,而是延迟交税。这样,就应该马上想出一个应用场景:如果某一年你没有收入,而且急需用钱,则可以从RRSP账户内取些钱出来,这样可能就不需要交税或只需要缴纳很少的税。当然,这样做的话,你的这部分免税投资额度就永远消失了,因此,如果可以避免的话,尽量不要在退休之前取钱出来(下面会给出解释)。
RRSP的额度可以通过登入你的CRA账户或查看CRA在审查完你的报税后给你的通知(称为“Notice of Assessment”)来确定。其计算方法是你的去年收入的18%,加上一个上限,再加上你以前尚未使用的额度。该额度的英文名称是“RRSP Contribution Limit”,相当于上述通知里的“RRSP Deduction Limit”。把钱投入RRSP时,不要超过该额度,否则会有惩罚性的利息产生:如果超过的金额在2000加元以下,CRA会容忍之;否则,会每月对其征收1%的惩罚性税款。
总结一下RRSP的两大好处:
首先,投入该账户的资金可以抵税,也就是降低需要缴纳的税金。这里有一个小技巧:如果某一年收入不高,而预计今后有可能会比较高,那么这一年投入的RRSP可以先不申报,而是留待日后工资高的时候用。不是说当年投入RRSP的金额就一定要当年用于抵税。这样做的原因是收入高的年份边际税率更高,因此,如果抵税的话,效果会更好,甚至有可能把税率拉下一档。
其次,RRSP账户内的投资可以得到免税的增长。不像在普通投资账户里那样,资本利得和股息都要被收税,在RRSP账户里,这些都是免税的。直到从账户里取钱的时候,这部分金额才会按你当年的边际税率被课税。这一点从长期的角度来看,是十分重要的,因为省出来的税金也会在这些年里得到指数增长。
因此,使用了上述的应用技巧(在收入少或没收入的年份,从RRSP账户取出一些钱用),就只能享受到第一个好处,而放弃了这部分钱所带来的第二个好处(免税的投资增长)。因此,只要还有其他的途径(比如有定存等账户的钱),且不是急需钱用,就尽量不要从RRSP账户里取钱。
对于从RRSP账户中取钱,应该注意如下几点:
根据上述两点,自己的各个账户要维持一个好的平衡,不可偏废。这也是有时提早取出一些RRSP会比较好的原因之一。如果平时RRSP账户里有很多钱,而其他普通账户里几乎没钱的话,一有点风吹草动,就会被迫从RRSP账户里支取。这样就不太好,因为被迫紧急取出往往不如预先有规划地取出更可控。
如果配偶没有收入,也就是配偶本身没有RRSP额度,那么有收入的那方可以把自己的额度用于配偶(即投入配偶RRSP账户,帮配偶积攒退休金)。其结果是(假设“自己”是夫妻二人中高收入的那方,“配偶”是低收入或零收入的那方):
2007年,政府推出“Pension Income Splitting”,允许退休者将其收入(退休金)的50%划归其配偶的收入。所以,从退休后节税的角度上来看,配偶RRSP已经被取代。但它还是有一些特殊的应用场景的:
简而言之,HBP(Home Buyer’s Plan)就是可以免税地从RRSP账户取一些钱出来用于买房子的一个政策。可取出的上限是35,000加元。应用HBP时需要满足如下条件:
从买房的两年后开始,需要在15年内把这笔钱逐渐还回去。每年要还满2,300加元或更多。不足的部分算入当年的收入来交税。如果以前的HBP额度还清了,再次满足4年内未曾住自己的房子等条件的话,还可以再次使用HBP。
这些账户可以在以下几种地方开设:
这是我推荐的地方。其中,网上券商能更好一些,因为各种费用都更低,甚至免费。我推荐的(以及我自己在用的)有以下两家:
Wealthsimple Trade:买卖股票不收手续费,所以适合加拿大股票的投资。美国股票的话,由于没有美元账户,买入时只能用加元,卖出时也只能收到加元,所以有两次货币兑换发生。而偏偏这里的兑换费用较高(1.5%),所以不太适合美国股票投资。
点击这里开设Wealthsimple Trade账户,可以得到10加元的奖励(目前的情况,以后有可能改变)。虽说他们也是在设法获得更多的账户,但该公司本身在我心目中是最好的。适合开设RRSP和TFSA账户。
Questrade:加拿大最大的网上券商。有美元账户,适合用于美国股票投资。ETF买入不要手续费(但是,需要缴纳交易所收的ECN fee),卖出时有手续费。手续费也比较便宜,4.95-9.95加元。同时,该账户还适用于美国股票投资。另外,一个小技巧是用于做美元和加元之间的低手续费兑换:比如先用加元买入多伦多证交所上市的某证券,再找客服转换为在美国上市的同样的证券,然后卖出,就转换成美元了。这种操作比在银行换能省不少手续费,只是需要几天的时间才能完成(如果该证券不会突然大跌的话)。还有,需要注意的是,Questrade会收不活跃账户手续费,但很容易避免:只要每个季度都交易一次就可以了。
点击这里开设Questrade账户,如果开设账户(仅限于这里讨论的这些账户,属于“Self-directed”一类的)后的三个月内投入1000加元或以上的资金,根据资金的多少,可以得到25-250加元的奖励(目前的情况,以后有可能改变)。虽说他们也是在设法获得更多的账户,但该公司本身在我心目中是很好的,仅次于Wealthsimple Trade,但在美国股票投资和Wealthsimple Trade不支持的账户类型(比如配偶RRSP和RESP)方面,是一个很好的补充。
我的观点:What?!Are you kidding?
在银行账户里做投资的手续费最贵。一个不太恰当但很好理解的比喻:在银行账户里做投资,就好比找剪羊毛工给你理发,找切肉工给你动手术。所以,银行账户还是用于其本来的目的吧(储蓄),投资的话还是找专业的券商比较好。
我的观点:What?!Are you kidding?
除了最基本的保险(比如医疗保险、车险、火险等等)外,我不建议买任何保险商品(请自行把这句话重复3遍)。在我的观念里,其他的保险就是智商税。如果说在银行账户里做投资只是在手续费上宰你的话,那么在保险公司做投资则是首先从本金上狠狠砍你一刀,然后再说手续费的事。所以,跟银行一样,保险也应该用于其本来的目的(就是保险),而不要用于投资等其他莫名其妙的目的。如果有人劝你买其他类的保险,那么为了你口袋里的钱着想,尽量跟他保持距离吧。
这些是最容易通过各种各样的甚至意想不到的渠道找到你的那类。对此,我没什么经验,也不想有经验。我们毕竟是在做十分长期的投资吧?如果这些公司的寿命没有这么长怎么办?就算他们破产后有相关的保险来赔偿你,那也很麻烦不是?本着“多一事不如少一事”的原则,我完全不建议在这里开设账户。还是前面那句话,专业的事情就找专业的(也就是券商)去做。当然,这些公司会声称他们就是最专业的,甚至你不懂都会代你投资。相信我(作为一个在投行等金融圈混迹多年的人),他们不是。他们在乎的永远都只是怎样从你那里赚到钱。如果说有哪家公司可能会跑路的话,那么上述四类中,这类是最有可能的。
以前在日本时,经过那么多年的努力和不断尝试以及生活的际遇,我逐渐找到了一个比较niche的领域,就是FinTech,或者更直接的说法,就是Quant IT,因为一方面我喜欢做程序员,另一方面我又喜欢股票投资。但自从到了加拿大的大温哥华地区后,就难以找到类似的职位了,于是只好去做普通的IT工作。这样,就离开了自己的最佳区域。虽说我们要勇于走出自己的舒适区域,可是如果舒适区域就是最佳区域呢?唯一可以聊以自慰的是,我至少在没到这里的时候就已经找到了一份程序员的工作,比其他一些生活多年都未能找到自己的专业工作的移民来说,情况还算好一些。
在经过一番闯荡,跳槽到目前这家公司后,因为公司希望我们以合同工的形式加入来降低雇佣风险,我就注册了自己的公司,老板和打工仔都是我自己。后来,公司的人事部门发出了一个招聘启事,我看到里面的条件好像照着我的简历写的一样,可能是暗示想把我转变成正式员工吧?职位是开发经理。我觉得来这里后生活乱糟糟的,没心情去做经理来管理别人,同时也比较喜欢目前的“皮包公司”的状态,就没申请。后来一个印度女同事坐到了这个职位,开会时我有点惊讶地发现,她手下管理的人比我预计的还多不少。不过,她开始时好像有点缺乏安全感,对中国传统文化——包括糟粕部分——还是有点了解的我,当然可以设法避免被她“杯酒释兵权”地清算,不过还是有点大意了。我还以为会从外面招一个来呢。
现在的工作是为银行编写和维护一个用于开户的云端系统。我所对应的客户是加拿大的一家银行。不知道这家银行本身如何,但跟我们有关的人比较讨厌,就是对IT毫无经验却又毫不讲理地蛮横的那么一个人。这种性格,当然是一个女性经理——没有歧视女性的意思,但根据生活中的经验,显然这种性格的女人的比例要比男人高得多。后来,那边也感觉这样整天跟我们针锋相对的也不是回事,就又调来另一位号称懂技术的人,让她处于该经理和我们之间,充当缓冲层。她的确能明白点,但显然距离懂技术还是有一段的距离。总之,从我们的角度看,就是客户似乎永远也不能满意,我有一种Gaslighting被害的感觉。好在后来我对该银行对我们的评分几乎都无视了,反正我的雇主又不是他们,而是这家开发软件的公司。我的一位同样是女性的同事则不满于此,在几个月前辞职了。不管怎么说,我本身也没有喜欢受虐的M倾向,于是也开始考虑寻找下一份工作。
大温这边IT工作的情况是,有几家美国的大公司(如亚马逊、微软等),其他的就是一大堆的中小公司。亚马逊的一个猎头找到我,问我是否有兴趣应聘他们的一个职位。我在当时那种有点郁闷的心情下,难免容易受到这类诱惑,就开始准备面试。开始时需要在网上做一个在线技术测试。我只好捡起数据结构等多年不看的内容(把一些用于快速复习的内容归结在了这几篇文章中)。但是,由于我并非赋闲在家,而是还有一份工作,因此,没有太多的时间用于准备这个,所以要求该猎头把考试时间延后一些,她也同意了。到时间后,我发现那个链接已失效,联系猎头,她说她会处理的。但后来就不再有音信了。可能是她大意了,但系统不允许在短期内重新申请了吧?总之,这次机会就无疾而终了。
然后,是一家创立于美国硅谷的在线家具公司A。也是让我先做一个网上测试,我费了些时间和心力做完了,记得里面有一个颇有些难度的关于图的遍历的题。结果,他们说给我的题错了!又发来另一个链接,而且是另一个在线技术测试公司的题。这次的题居然简单得多(太坑爹了)。后来,进入在线面试阶段,他们认为我缺少一些诸如微服务等的经验,以及缺乏诸如“高屋建瓴”的那种经验(以前在投行的时候,经常是我自己从设计到实现一整套系统好不好?就非得自己只说些空话大话,让其他人去努力实现,才算高屋建瓴吗?),就面试失败了。
另一份工作是北美的一个很大的电器连锁店B的IT工作。同样是先做一个在线测试,令我惊讶的是,这些题居然很简单。之后是在线面试,结果一个对技术很热衷的华人小伙居然让我当场写一段关于树的遍历的代码,也是能在线编译并执行的那种。好在我写了出来。后来就是跟诸如管理层的面试,感觉不太好,令我恶心(不怪该公司,是我自己)的是,居然顺着他们的所谓企业文化说了一些有违自己个性的话。虽说是高级程序员的工作,但他们也是认为我缺乏诸如微服务的经验,也缺乏一些管理经验,就提出了一个低一些的工资。我当然没必要到那里去拿比现在更低的工资,因为我毕竟不是年轻人了,一方面就算能增长一些经验,对我来说也没多少年的用处了,另一方面,对于年龄较大的人来说,如果公司给的工资低,就说明他们不会拿你当回事儿的,我又何必去妄自菲薄呢?于是就拒绝了这份offer。
结果就是,目前还是在从事着这份工作。有时候发现,最好的经常就是现在所拥有的,但经常因为“这山看那山高”的心理而做一些没必要的挣扎,这样反而让自己的情况每况愈下。退一步反思一下自己,我觉得自己是无意中被“套路”了,认为就得去那种有名的公司才对得起自己这么多年来的努力和自己的经验。可是,在加拿大抑郁的生活中,偶尔想起来统计一下自己的资产状况,才更加意识到自己竟会如此犯傻。总之,这就是我“老夫聊发少年狂”的一次经历。其实,维持着目前的工作,在这份工作被解约后再去找一份新工作,而把因换工作而浪费的时间(准备和参加面试,熟悉新的环境,等等)用于更有意义的事情上,才是更好的选择。
另外,我发现在加拿大(至少是在大温地区)找工作,有点像是个玄学问题。上面的几次经验还多少能说得清,但经常是,我自己也不知道为什么能得到一些工作,而不能得到另一些。在我做目前这份工作之前,我面试过另一家加拿大的公司,还没开始面试,他们就认为我的工资过高(后来网上了解了一下,很多人都抱怨他们大量找新移民,且把工资压得很低),说如果我同意应聘“中级程序员”的话,他们会很高兴面试我。我告诉猎头,那就这样吧。结果面试中级程序员,他们也认为我不合格。我不相信他们能比我高多少(甚至是,他们就高吗?),但对这些公司,没必要花时间去想为什么,就抛之脑后即可。我在从事目前这份工作1年多了,在一次招聘会上,见他们还是在招这个职位。后来,又有猎头给我介绍工作,我隐隐觉得公司名有点耳熟,就查了一下以前的Email,发现正是这家公司,就立即拒绝了。
还有一个硅谷的公司,不是那种高大上的公司,而是拉一伙人去做外包项目的公司。一个项目跟加拿大和美国的电力系统有关,我去应聘,也是在线测试等比较简单地通过了,之后在线面试莫名其妙地失败了。有可能是我要的对他们来说有点高了?
同样的,我也参与过公司招聘新人的技术面试。我不像其他公司那样喜欢问一些技术难题,好像难不倒应聘者就没面子一样。我一般是问很基本的问题,如果真的是程序员,不用特别准备也应该很容易地答上来。结果,面试了三四个人,就有一个是我的前同事的人能勉强全答上来。而且我的问题清单从来没用完过,那位前同事在答同样多的题的情况下比其他应聘者都好。但一个team lead却认为其他几个应聘者更好,因为他们说得比较流畅。我的反对意见是,他们根本连这么基本的问题都做不出来,怎么指望他们能来这里实际做出什么贡献呢?结果几个都被拒绝了……这也能从一个侧面看出,通过一个面试是多么的困难。
经常有面试问题是二维网格问题,比如迷宫问题、迷宫最短路径问题、N皇后问题等等。求解时主要有以下要素:
总体的搜索可以有深度优先(DFS)和广度优先(BFS)之分。
根据我自己的经验,在有限的时间内解答这类问题时,要注意以下几点:
二维数组的行列顺序
二维数组是按照先行后列的顺序存储的:
void func(int[][] data) { if (data == null || data.length = 0 || data[0].length == 0) { // ... return; } int rows = data.length; int cols = data[0].length; for (int r = 0; i < rows; ++r) { // 或者更好的写法是:c < data[r].length // 但这类问题一般都是个矩形区域,因此把cols提前定好,代码更简洁 for (int c = 0; c < cols; ++c) { data[r][c] = 0; } } // ... }
循环变量名称
循环变量名称似乎根本不是个问题,一般会用i和j来表示。但在有限时间而且缺乏IDE帮助debug的情况下,对于二维格子问题,很容易引起思维混乱。我自己就有一次在线测试时,因为把行和列弄颠倒了,导致时间到了还无法把程序调通。后来自己“复盘”的时候,才发现原因所在。
因此,建议把变量名称弄得一看就懂:
例如:
for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { data[r][c] = 0; } }
搜索相邻的格子
一般我会按东西南北四个方向编写:
// N if (r > 0) { backtrack(r - 1, c); } // S if (r < rows - 1) { backtrack(r + 1, c); } // W if (c > 0) { backtrack(r, c - 1); } // E if (c < cols - 1) { backtrack(r, c + 1); }
这样看似很有效率,但很啰嗦,而且在情急之下容易犯错。我经常会因为拷贝粘贴的代码中没改完全而导致程序不能通过,而之后要用肉眼去观察一遍来找出错误的话,很费时间。因此,在效率没有多少区别的情况下,程序越简短越好。
// N S W E private static final int[] rowOffsets = {-1, 1, 0, 0}; private static final int[] colOffsets = { 0, 0, -1, 1}; private void backtrack(int[][] data, int[][] visited, int r, int c) { // ... int rows = data.length; int cols = data[0].length; BiPredicate<Integer, Integer> isValid = (row, col) -> row >= 0 && row < rows && col >= 0 && col < cols; // 尝试搜索相邻的格子 for (int i = 0; i < rowOffsets.length; ++i) { int r1 = r + rowOffset[i]; int c1 = c + colOffset[i]; if (isValid.test(r1, c1) && !visited[r1][c1]) { backtrack(data, visited, r1, c1); } } // ... }
有人喜欢在枚举相邻格子时,按东南西北的顺序转一圈。在我看来似乎没什么必要。最重要的是简单且不易弄错,所以我都是选择按北、南、东、西的顺序轮转。当然,每个人习惯不同,可以选择自己最舒适的顺序。
总结:对于编程来说,最好是从一开始就不要把bug放进去,否则要找出来就需要花费成倍的时间。因此,要选择各种一看就懂的方式写代码,防止写到中间自己都迷糊了。另外,为了避免查找bug的时间过长,应该尽量写简短的代码(当然不是那种为了短而短的十分缺乏可读性的那种)。
// 排序 int[] array = {3, 4, 1, 2, 5}; Arrays.sort(array); // T = O(n * log2(n)) List<Integer> list = Arrays.asList(array); Collections.sort(list); // 使用ArrayList的话,T = O(n * log2(n)) list.sort(null); // 上面的函数调用这个函数,其内部实现方法是先把列表转换为数组再排序 // 因为如果是链表,直接排序的时间复杂度为O((n ^ 2) * log2(n))。 // array和list转换 List<String> list = Arrays.asList(array); String[] array = list.toArray(new String[0]); // max & min Map<String, Integer> map = ...; // 找出具有最大value值的key String max = Collections.max( map.entrySet(), Comparator.comparingInt(Map.Entry<String, Integer>::getValue)).getKey(); // 或者 max = Collections.max( map.entrySet(), Map.Entry.comparingByValue()).getKey(); // 这些其实没什么必要,面试时记不住就用循环解决 // string String str = "aaa bbb ccc"; String[] parts = str.split(" "); // {"aaa", "bbb", "ccc"} String[] parts1 = str.split(" ", 2); // {"aaa", "bbb ccc"} String[] parts2 = str.split(" ", -1); // -1的意思是不要删除最后面的空字符
另外,Java的Collection由于只接受对象形式的元素(就是说不能用基本数据类型的元素),加上其维护代码的开销,性能往往比数组差。比如int[]比ArrayList<Integer>要快,尤其是在比拼算法所用时间的情况下尤为明显。
“Stack”是Java中关于栈的旧API。现在应该使用Deque。LIFO。
Deque<String> stack = new ArrayDeque<>(); stack.push("abc"); String s1 = stack.peek(); String s2 = stack.pop();
普通的队列,在Java中一般是以LinkedList的方式实现的。Queue常用于广度优先搜索算法。FIFO。
Queue<String> queue = new LinkedList<>(); queue.offer("abc"); // enqueue String s = queue.poll(); // dequeue
Priority Queue常被用来在不排序的情况下取最大的或最小的几个值。如果有n个数据元素,要取前k个(k<n)最小的元素,用排序法的话T=O(n * log2(n)),而用Priority Queue的话,则为T=O(n * log2(k)),这样就能快一些。方法是往queue里逐个放入数据元素,如果queue的长度大于k,则把一个元素移出(也就是最大的那个或最小的那个,取决于Priority Queue的设定方式。这样,剩下的就是k个最小的或最大的元素。
Priority Queue的时间复杂度:enqueue和dequeue操作为O(log2(k)),查看(peek)最前面的元素为O(1)。
PriorityQueue<Elem> queue = new PriorityQueue<>(Comparator.comparingInt(Elem::getValue)); for (Elem elem : list) { queue.offer(elem); if (queue.size() > k) { queue.poll(); } }
上面的代码中的queue.poll()会把Elem.getValue()返回值最小的元素移出。要想移出最大的,则改为Comparator.comparingInt(elem -> -elem.getValue())。
另一个应用的例子:合并k个有序列表。一般的算法为取各列表的第一个元素,找到最小的那个,加入新列表,然后把最小元素的下一个元素作为它原所属列表的第一个元素。不断重复,直到用完所有列表的元素。这样做的话,T=O(N * k),其中N为所有列表中的元素总数,k为列表个数。因为每次从k各元素中取最小值为O(k),而对所有元素都要进行一次这样的操作,故为O(N * k)。
可以用Priority Queue进行优化:把各列表的第一个元素加入queue;取出最前面的元素加入新列表,并把它的下一个元素加入queue。这样的话,每次enqueue和dequeue操作为O(log2(k)),对所有元素做这种操作,总体的时间复杂度T=O(N * log2(k)),比上述的O(N * k)要快。
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.val)); for (ListNode node : lists) { if (node == null) { continue; } queue.offer(node); } ListNode dummyHead = new ListNode(0); ListNode prev = dummyHead; while (!queue.isEmpty()) { ListNode node = queue.poll(); prev.next = node; prev = node; if (node.next != null) { queue.offer(node.next); node.next = null; } } return dummyHead.next; }
题外话:另一种十分简单的解法是Divide & Conquer:合并两个有序列表(按第一种思路)的时间复杂度是O(n),n是两个列表中的元素总和。可以把k个列表两两分组,并将其合并成一组更长的列表;然后继续两两分组合并,直到最后只剩一个列表为止。这看起来跟体育比赛分组类似,没什么特别的,但观察一下的话,一共有log2(k)轮的分组,每轮都要遍历所有N个元素,因此,时间复杂度也是O(N * log2(k))。
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } int i = 0; List mergedList = new ArrayList<>(); // 两两分组合并。merge2()的作用是普通的合并两个有序列表。 while (i < lists.length) { ListNode node1 = lists[i]; if (++i < lists.length) { mergedList.add(merge2(node1, lists[i++])); } else { mergedList.add(node1); } } return mergeKLists(mergedList.toArray(new ListNode[0])); }
HashMap经常用来提高程序的效率。写入(put)、查找(contains)和取值(get)都为O(1)。这里有一些简单写法:
// 计数:记录相同词语出现的次数 Map<String, Integer> map = new HashMap<>(); for (String s : list) { map.merge(s, 1, Integer::sum); // 如果没有,值设为1;否则,在原来的基础上加1 } // map的值为一个列表。如果不存在,创建列表。 // key为字符串,value为储存字符串索引位置的列表 Map<String, List<Integer>> map = new HashMap<>(); for (int i = 0; i < list.size(); ++i) { map.computeIfAbsent(list.get(i), k -> new ArrayList<>()).add(i); }
// Unary bitwise complement (~) int n = ~5; // ~0101 --> 1010 // Bitwise AND (&) int m = 0b0001; int result = n & m; // 1010 -> 0000 // Bitwise inclusive OR (|) result = n | m; // 1011 // Bitwise exclusive OR (XOR) (^) result = n ^ 0b1111; // 1010 --> 0101 // Signed left shift (<<): shift once results integer x 2 result = 8 << 1; // 16 result = -8 << 1; // -16 // Signed right shift (>>): shift to right and fill 0 on left, but keep leftmost bit. // shift once results integer / 2 result = 8 >> 1; // 4 result = -8 >> 1; // -4 // Unsigned right shift (>>>): shift to right and fill 0 on left. result = 8 >>> 1; // 4 result = -8 >>> 1; // 2147483644
一些常用的用法:
// 乘或除2的n次方 int result = 3 << 4; // 3 * (2 ^ 4) result = 32 >> 3; // 32 / (2 ^ 3) // 判断奇偶 boolean isEven = (123 & 1) == 0; // 注意由于优先级的原因,应使用括号 // 判断某位是否为1(比如每个位表示一种flag) int mask = 0b0010; boolean isSecondBitFromRightSet = (7 & mask) == mask; // 7 = 0b0111, 7 & mask = 0b0010 // XOR: // a XOR a = 0 // a XOR 0 = a // a XOR b XOR c = a XOR (b XOR c) // a XOR b XOR b = a
Trie又名“前缀树”,用于根据前缀查找词汇。典型的应用包括:自动完成、拼写检查、IP路由、解字谜等等。哈希表虽说查找的时间复杂度为O(1),但在查找相同前缀的词汇时就缺乏效率了。而且如果输入了大量的词汇的话,还有因哈希冲突而导致的效率下降。
如果输入的词汇数量为n,查找的前缀长度为m,那么查找的时间复杂度为O(m)。
这里是一个简单的实现:
public class Trie { public static class Node { private String word; private final Map<Character, Node> childrenMap = new HashMap<>(); public Node() { // empty } public boolean hasChild(char c) { return childrenMap.containsKey(c); } public Node getChild(char c) { return childrenMap.get(c); } public Node addChild(char c) { return childrenMap.computeIfAbsent(c, k -> new Node()); } public void setWord(String str) { this.word = str; } public String getWord() { return word; } } private final Node root = new Node(); public Trie() { // empty } // 输入一个词汇 public void insert(String word) { Node node = root; for (char c : word.toCharArray()) { node = node.addChild(c); } node.setWord(word); } // 查看是否有该词汇 public boolean search(String word) { Node node = root; for (char c : word.toCharArray()) { node = node.getChild(c); if (node == null) { return false; } } return node.getWord() != null; } // 查看是否有以该前缀开始的词汇 public boolean startsWith(String prefix) { Node node = root; for (char c : prefix.toCharArray()) { node = node.getChild(c); if (node == null) { return false; } } return true; } }
如果词汇的组成字符是有限的(比如小写英文单词由26个字母组成),另一种实现方法是用一个数组代替Trie.Node中的HashMap。我个人不太喜欢这种方法。但是用Java语言的时候,讽刺的是这种方法往往能快一点点。
public static class Node { private static final int N = 26; // 字符总数 private Node[] links = new Node[N]; // 查找时用索引 int i = c - 'a'; // 用flag代替上面的字符串能节省点空间。 // 用字符串的目的是在需要得到词汇时不用从头遍历到目前结点,而是能直接拿到 private boolean end = false; // ... private int getIndex(char c) { return c - 'a'; } public boolean contains(char c) { return get(c) != null; } public Node get(char c) { return links[getIndex(c)]; } // ... }