我的AMAZON面试经历与经验之谈(亚麻伦敦面经)
我的AMAZON面试经历与经验之谈(亚麻伦敦面经)
Category: 面试
C编程练习题: 判断整数是否有连续两个1
题意就是判断一个整数的二进制表达式里是否有连续两个1. 比如13的二进制是1101那么有两个连续的1而9的二进制是1001, 则没有两个连续的1. 我们知道 我们可以用 x & (-x) 来获取一个整数二进制表示里最右边的那个1. 那么我们就可以写一个循环不停的返回最右边的那个1的值, 并且我们记录了上一个1的值, 这样只要有连续两个1, 那么这两个1的值的关系就是两倍. C代码看下面, 复杂度是 O(log N) 因为最多需要 log N 次就可以把一个整数的二进制位过一遍. int inspect_bits(unsigned int number) { int cur, prev …
谷歌的扔鸡蛋问题
这题据说是 GOOGLE的面试题, 但是却真实的被一些软件公司拿来考应聘者. 题意是: 给你两个鸡蛋, 有个100层楼, 你可以把鸡蛋从任意一层楼扔下, 鸡蛋可能破, 也可能不破, 如果不破的话, 你可以继续用这个鸡蛋扔. 你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度. 这两个鸡蛋一模一样. 问你采用什么策略可以使最坏情况下的尝试次数最少? 什么是最差情况? 如果你只有一个鸡蛋, 那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论. 最直接的做法就是从第一层开始试, 然后第二层以此类推, 但是这种方法只需要用到1个鸡蛋即可. 如果第N层鸡蛋没碎但是第N+1层碎了, 答案就是N. 这种情况下最坏需要尝试100次. 如果我们在第50层扔呢? 如果鸡蛋碎了, 那么答案就在第1到第49层, 反之答案就在第51到第100. 鸡蛋碎了, 我们只有一个鸡蛋, …
编程练习题 – 如何合并两个有序的数组?
题意: 合并两个已经排序好的数组. 这也是合并排序的最后一步操作. 还算比较简单的, 你可以从数组的两端开始. 一般来说从小到大合并会比较直观. 我们需要定义指向两个数组的下标, 每次循环就把比较小的那个数字添加到结果中即可. 当其中一个数组已经全部添加完后只需要把另一个数组剩下的元素依次添加到结果中即可. 复杂度是 O(A+B) , 其中A, B分别是两个数组的长度. class Solution { public: /** * @param A: sorted integer array A * @param B: …
ACM题解系列之 – 最小堆栈 (Min Stack)
没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack { public: MinStack() { // write your code here } /* * @param number: An …
逻辑测试系列之三 – SUBT
@justyy 的逻辑测试系列: 逻辑测试系列 – 一种只有4种语句的编程语言 – (1) 逻辑测试系列之二 – DECR 上次添加了 DECR 函数来把 一个变量减一, 我们这次来定义一个 SUBT 函数来实现 把 减法运算, 也就是 X-=Y 如果我们用 C++ 来实现, 大概是这样的: void subt(unsigned int &x, …
逻辑测试系列之二 – DECR
逻辑测试系列 – 一种只有4种语句的编程语言 – (1) 这种只有4条语句的语言能做什么呢? 今天我们来定义一个DECR函数, 该函数就是把 变量 X 减一. DECR(X) { } 要求填写函数体, 使用 INCR, LOOP, ZERO, 和 ASGN 仅有的4个语句. 我们不妨想一下, 已知变量 X 是非负整数, 那么我们只需要 循环 X-1次, …