实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回 : 商.

you can only get 60pts with this algorithm

【 在 yesim (yesim) 的大作中提到: 】
: 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
: 商.
: function(int x,y){
:   n=x;k=0;
:   while(n>y){
:     n=n-y;
:     k++;
:   }
:   return k;
: }
: ...................

汽车出租（Car Rental Agency）的系统的oo设计

设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

abstract calss car
calss BMW extends car
calss Honda extends car
....

interface CarManager
class <T extends Car> CarManagerImpl {
  List T search(Class<T> clazz){
   
  }

  T search(Class<T> clazz){
   
  }
 
}

class User {
  List<UserCar> usercarList;

  User();
 
  boolean Rent(T entry){
    usercarList.add
  }

}

class <T extends Car> UserCar {
  List<UserCar> usercarList;
  ......
 
}


class Monitor implement Runnable {
  public boolean doMonitor{
    List<UserCar> usercarList = UserCar.getUsercarList(String condition)
    for(User user : usercarList){
      sendEmail(getUser().getEmail());
  }
}

讨论：反转一个整数，如12345->54321

反转一个整数，如12345->54321
当时写了个这么个东西（面试官假设输入是正整数）：
int reverse(int n) {
   res = 0;
   while(n != 0) {
      res *= 10;
      res += n % 10;
      n = n / 10;
   }
   return res;
}

然后面试官问，如果n<0怎么办；我说判断一下，然后把n = -n，然后重复；
问题就在这里，他说不行，正确的做法是n = -1 * n；我不明白为什么是这样？


n为负数，你想把它整成整数
不用 n = -1 * n;  用啥？
或者你用  n = 0 - n; 也行

-n 编译都不通过

居然都不做防止溢出的？
正负数的溢出不等

The syntax
n = -n;
is valid in C and C++.
 

find the shortest substring covering all given characters.

A long string text, given some characters, find the shortest
substring covering all given characters.
请问大家有没有想法，谢谢

quick thoughts：

两个指针p,q，先前进q直到cover了所有characters，记录当前长度
然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
maintain最短长度

需要用一个map维护出现的字符

复杂度O(n)因为相当于scan了2次

假设str[0..n-1]表示整个字符串。基本思路是从str[0]开始，以每个位置作为substring的起点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，如何每次只用O(1)来确定substring长度。

我想可以用一个辅助数组记录每种字符出现在字符串中的位置。例如字符a出现在str[0]和str[20]两个地方。假设当前已经确定以str[0]为起 点的substring长度。接下来应该确定以str[1]为起点的substring长度。该substring丢弃了str[0]，所以必须要至少在 str[20]结束，否则字符a没被cover。这就是基本思路。

我用一个例子解释整个算法。假设字符串包括0到9的数字，整个串如下
0247324596818329654001378
第一步扫描字符串，记录下每种字符位置，如下
0：0，19，20
1：11，21
2：1，5，14
3：4，13，22
4：2，6，18
5：7，17
6：9，16
7：3，23
8：10，12，24
9：8，15

第二步，以str[0]为起点，substring的终点在str[11].
接下来，以str[1]为起点，因为丢弃了str[0]，即字符0，那么从辅助数组可以找到下一个字符0出现在str[19]，因此substring结束于str[19]。
这样每次substring起点往后一个字符，用O(1)时间可以确定结束位置。

面经

Amazon 面试题
grep不愧为Amazon的最爱问题。
两次电面都问OOD...不容易。


在网上申请的SDE职位。一共两轮电话面试，一轮onsite。

第一轮电话面试：
1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
good hash function”，“什么是load factor”。

2、算法：删除一个给定数列中重复的元素。

* 这道题看起来简单但是还是很多陷阱啊。。。
比如删除是什么意思？只是把array element mark为一个不可能的值（比如-1），还是
输出一个崭新的没有重复的数列。

3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
，让我写好以后发到他邮箱里。

k=i+j
a[i],b[j],c[k]

int ii=jj=kk=0;
while(kk<k){
        if(a[ii]>b[jj]){
                c[kk]=b[jj];
                jj++;
        } else {
                c[kk]=a[ii];
                ii++;                  
        }
        kk++;
}


4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

第二轮电话面试：
1、Favorite project。

2、你最喜欢的排序算法，它是怎么工作的，有什么优点和缺点。我说的是选择排序，
他又问有什么排序算法比它的时间复杂度小，并且同样要描述一下它们是怎么工作的。

3、算法、写代码：
给了两个数组，要求找出他们之中相同的元素，并且将相同的元素存储在一个新的数组
里，再输出。如果数组里有重复的元素，比如array1中有四个5，array2中有两个5，那
么新数组里只存储两个5。要求我写代码，再念给他听。

4、OOD：设计restaurant reservation系统。

5、好像是一个开放性问题，我没有完全理解：log file中存储了很多order的信息，每
个order都有一个oid，字符串格式（xxx-xxxxxxx-xxxxxxx）。要求从log file中把所
有的oid都提取出来，问我怎么做。

on-site：
一、给定一篇文章，用户想要搜索一个单词，要求给出搜索单词的建议（就像一般的搜
索引擎的那种功能）。要求描述算法、复杂度并写代码。

二、先问了几个行为问题。然后问了两个简单的链表问题，单链表中查找倒数第n个数
和判断链表中是否有环。编程题问的是boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
http://en.wikipedia.org/wiki/Boggle

三、午餐，一个经理问了一些简历上的projects和实习的经历，然后又介绍了一下他们
组的工作。他说这次面试我的主要是Kindle组的。

四、不是Kindle组的，我估计是传说中的bar raiser。第一个问题是给了一个很大的文
件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
复。然后是一个开放性问题：一台服务器每过三天就要挂一次，需要重启才能再次使用
，每次重启需要一分钟的时间；问有什么方法能解决这个问题。

* 服务器那个题我答的不好，因为老是不知道他在问什么，他想要的答案是什么。反正他
给了我很多提示，比如可以用交替使用两台机器，还需要一个load balancer，这样可
以在一台服务器挂的时候正好用上另一台正常工作的服务器，再重启挂的这个机器。


五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
商。
--

文件找重复的那道题我觉得可以用hashtable，也可以external sorting。hashtable有
个问题是如果内存中放不下这个哈希表的话怎么办？我说可以使用多台机器，每台存放
一定范围内的数字（类似于MapReduce中map的过程），然后再分别对每个机器处理。


上来就一个问题,设计一个网上预定飞机票的系统

讨论了50分钟左右,弄的很细,每个class里有啥variable,啥method,都要说. 比如
Controller class谁去call, 怎么用Controller class. 还有内存怎么寸(不用数据库,
全存memory里),用什么数据结构,(他提出hashtable),什么作为key,什么作为value
一开始还好,后来纠结在一个如何给用户一个指定日期的航班信息,因为我没有存日期,
最后时间快到了,他让我把想好的设计发邮件给他...