Menu Sidebar
Menu

Geeksforgeeks

[Google] isPowerof4 O(1)找4的倍数.

Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111.  但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了.

下边是power of 8

 

[Amazon] Add Binary Number By 1 without using + 正数加1不用加号

Bit操作的题, 给一个整数+1,不能用加号. 其实很简单,扫一下整数的每个bit(从低位到高位), 对它做&操作, 如果结果是0, 证明此位是0, 那么我们在这位+1, 如果是1, 那么我们清空此位.

   

Amazon Interview Experience | Set 199 (On-Campus for Internship) 题解

1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1. 二分搜索一下就可以, 注意一下返回-1的条件.

2.给一个二叉树, 找到最长的path. 如果最长不只一个, 返回字典序第一个最长. 这个需要点技巧, 我们自底向上,对树进行递归, 把path 放到一个stack里, 然后如果找到了一个更长的path(stack的size) 就更新一下. 因为最长的path不一定在root的同一侧, 所以最后我们还需要比较一下当前节点左右哪边有最长path.

3. 给一个二叉树, 求任意两个node的path长. 这个是个靠综合概念的题, 首先我们要知道这2个节点并不一定在root的同一侧. 所以我们需要找到两个节点的lca. 其次, 我们要知道root到两个节点分别的长度, 和root到lca的长度, 然后用d_node1 + d_node2 – 2*d_lca就是他们之间的长度.为什么呢? 试想一下, LCA的定义就是最短的两个节点的交点. 那么我们可以证明, 他们之间的path毕竟经过lca, 所以我们通过这个公式计算这两个节点之间的path的长度是可行的.

4. 给一个数组, 数字之间最大的差的绝对值是1, 让你找到一个数字n的第一次出现的坐标, 没有就返回-1 很简单, 我们可以证明, 在开始时, 数字n可能出现的地方, 就是n-nums[0], 如果没有, 就是n-nums[1]…..一直找就可以了.

[…]

Find a pair with maximum product in array of Integers 找出数组中最大乘积的一对

给一个数组, 找出里面的两个数, 使得这两个数的乘积最大.这是geeksforgeeks上的题, 我看原题下面的代码有点复杂, 就重新想了想. 先看两个例子:

但是上面的例子不能完全说明问题, 比如说{0,1,-5}, 这时候, pair应该是0, 1 OR 0, -5. 思路很简单, 通过观察上面的例子, 不难发现, 这个pair和四个数字有关: 数组中, 正数的最大值pmax和第二大值psec, 负数的最大值nmax和第二大值nsec. 而最大值应为Math.max(pmax*psec, nmax*nsec). 代码如下:

需要注意的是else if在判断时候使用, 还有初始化时,应该把值初始为0.

URL to TinyURL 生成短链接

最近好像这个面试题很流行, 因为考点很多, 而且出题人可以从这个题延展到很多基础知识, 所以是很好的面试题, 也是很好的准备基础知识的题, 大概设计的考点如下: Hash vs Encoding: 一般会问, 生成url的时候, 为什么不能通过生成hash来查找? 回答: hash有冲突. 1个tinyurl, 在decode的时候会map到多个url上. Encoding利用了URL中字符串的可能字符为定值(a->z, A->Z, 0->9, 符号不算), 把每位字符转换成数字, 然后对其用62(26(小写)+26(大写)+10(数字))位编码. 确保了唯一性.代码如下:

  如何存储URL: 这个问题就是分布式设计了, 上来要回答设计的出发点,即CAP(Consistency, Availability, Partition(Network Failure)), 中的取舍, 然后设计的corn case, 比如说数据的rollback(Replication)的同时如何确保一致性. 下图是技术vsCAP的说明 转自Github: 存储url时, 数据库会自动生成一个ID, 我们通过这个id, 生成一个全局唯一的id, 这个过程可能包括添加唯一的主机ip地址,或者压缩mac地址, 面试时, 面试官会问如何生成一个全局unique的id, 这时需要考虑数据库的设计, 比如,当用户retrieve的时候, 需要通过这个id, 解析到对应的host上, 并且host还要返回对应的url. 生成唯一的id后, 我们用上边的decode方法, 把id变成String. 返回给用户.

Find kth smallest element in BST 找第k个小(大)的值在BST中

今天geeksforgeeks上刷出来的题.一看不能用stack, 基本就是Morris遍历了. 但是做了一下, 发现需要注意的地方挺多的, 比如当我们算visit的时候, 在rebuild link后, 我们也需要increase counter. 不然打印出来的是The Bottom of Tree 代码:

 

书脊

倾城与倾国, 佳人难再得