码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居西雅图。


Tag: Career


  1. 楠哥甲午年末的跳槽总结【楠哥原创】

    楠哥的帖子只在一亩三分地和我个人的某个人迹罕至的博客发表,转载、引用请注明作者、出处。谢谢。原帖发于http://www.1point3acres.com/bbs/thread-125808-1-1.html 好久没有在地里发干货了,趁着跳槽之间的gap,来总结一下跳槽这段经历。 背景介绍 可能对这个id熟悉的人,应该已经了解我基本信息了。简单说来就是川大本科,哥大Master,都是CS专业。毕业后于2013年初入职微软,据这次跳槽正式离职工作总计两年零十天。2014年11月Google电面,1…

    Career, Technical继续阅读

  2. Pow(x, n)

    指数计算应该是递归程序设计的入门级题目,但是在一场面试中写一个bug-free的代码还是需要多多注意边界条件。首先是底数的正负会影响结果,其次是指数的正负,也会影响结果。因为函数原型是pow(int x, int n),所以指数一定是整数。题目的一个简单思路是使用一个循环计算n遍x的乘积,但是这样的计算复杂度太高。如果我们想计算pow(x,16),我们需要做15次乘法,这样的开销很大。使用分治法换一个角度考虑,pow(x,16)其实可以分成两个pow(x,8)的乘积,同样的,pow(x,8)可以…

    Technical, Career继续阅读

  3. Valid Parentheses

    括号题目是一类经典的算法题目,有很多变形。这类题目乍一看上去没有什么思路,但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。 合法括号的判断问题是指在一串由()[]和{}组成的字符串中,判断括号是否合法。比如{()[]}是一个合法序列,但是(])就是非法的。该题目的解决可以使用栈来完成。当发现一个左括号([{时,将其压入栈中;当扫描到一个右括号时,判断栈顶元素(java中使用peek()函数)是否是与当前元素匹配的括号字符。如果不匹配,则整个字符串不合法;如果匹配,…

    Technical, Career继续阅读

  4. Climbing Stairs

    爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是:给定一个n个台阶楼梯,每次可以上一个或者两个台阶,请问最终可以有多少种方法爬到顶层。使用递归的思路解决是,到达第K个楼梯的方法数目是到达地k-1个楼梯的方法数与到达地k-2的楼梯的方法数的和。所以,如果函数原型是int cal(int n),那么我们可以得到递归规则是cal(k)=cal(k-1)+cal(k-2)。边界条件是cal(1)=1,cal(2)=2。但是,这样计算会有很多的重复性计算,所以可以使用动态规划来解决。如…

    Technical, Career继续阅读

  5. Balanced Binary Tree

    判定平衡二叉树的题目是一道基本的数据结构题目,在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。 可以使用一个递归函数,递归的判断每个节点的左子树和右子树的高度是否相差1,但是这样的算法会产生很多次重复的计算,效率并不高。另外一种方法是设计一个递归函数,返回以每个节点为根的二叉树的高度,当左右子树返回的高度相差超过1时,则返回-1表示该树不平衡。这样的算法时间复杂度为O(n)。该算法的Java实现如下。 public class Soluti…

    Technical, Career继续阅读