Amazon Interview Questions

A collection of Amazon interview questions.

Interviewer 1

  1. number of islands (one dimensional).
  2. is palindrome (recursive)
  3. valid parenthese (stack, follow up o(1) space)
  4. design a deck.

Interviewer 2

  1. word break
  2. 找一个array的第二大的数

Interviewer 3

  1. paint house
  2. reverse link list

Interviewer 4

  1. 给两个列表，每个列表装着一样的元素，合并两个列表，并要求短的列表的元素把长列表元素尽可能均衡分开。比如列表为AAAAA和BBBBBB，返回BABABABABAB；又比如AAAAAA和BBBB，返回AABABABABA。
vector<char> mergeArray(vector<char> &A, vector<char> &B) {
    int lenA = A.size();
    int lenB = B.size();
    if (lenA < lenB) return mergeArray(B, A);
    if (lenB == 0) return A;
    char a = A[0];
    char b = B[0];
    vector<char> merged_array;
    //lenB + 1: the number of groups
    int group_size = lenA / (lenB + 1);
    int remainer = lenA % (lenB + 1);
    //思想就是平均每个组放group_size个，然后前remainer组每个组多放一个把余数放完
    for (int i = 0; i < lenB + 1; i++) {
        if (i < remainer) {
            for (int j = 0; j < group_size + 1; j++) {
                merged_array.emplace_back(a);
            }
            //放b之前要看是不是已经放完了，比如AAA, BB和AAA, BBB怎么区分
            if (merged_array.size() == lenA + lenB) break;
            merged_array.emplace_back(b);
        }
        else {
            for (int j = 0; j < group_size; j++) {
                merged_array.emplace_back(a);
            }
            if (merged_array.size() == lenA + lenB) break;
            merged_array.emplace_back(b);
        }
    }    
    return merged_array;
}

Interviewer 5

    coding题      Ex: input: {1, 2, 3, 4 ,5}
                        interval = 2
    1.    找出interval数量         output: 3      有三个interval {1， 2} {3， 4} {5}
    2.    打印interval                {1， 2}                
                                             {3， 4}
                                             {5}
    3. 2Darray            跟第二题一样，光赋值给2Darray就好了

第一题math 直接搞定-google 1point3acres
return array.length % k == 0 : array.length / k : array.length / k + 1;
二三题一样，可以用nested for loop直接搞定，
  1. Question（貌似是OOD），我在一顿锤扭，问amazon checkout system，what kind of difficulties amazon may counter？
    我就想出这三个：1.The atomicity of a transaction    2.Transaction security    3.Network connection

    原题是checkout system， what difficulties in this procedure? 是从你点击了checkout开始时一直到shipped的过程
举例： checkout时 item outofstock怎么办 这个问题是最容易，也是最经常出现的
          还有非常多的问题在这里面，我是因为经常用amazon买卖东西，所以对amazon这个system的缺陷比较了解

Interviewer 6

  1. find occurences in a sorted array -- lintcode 原题

Interviewer 7

  1. convert in to roman
  2. convert roman to int
  3. maximun subarray

Interviewer 8

  1. Merge Interval
2GB的file如何sort，如果内存不够用。（这时，小哥意味深长的说，在这个年代2GB可能不是问题，但是我当时的电脑只有256MB内存）。
external sort， k way merge.
然后让我描述一下，整个的过程是如何进行的。最后让分析整个的时间复杂度

以two-way merge sort为例：

2-way merge sort:

four external disks: M records every time. say, M = 3

Da1: 83, 94, 11, 96, 12, 35, 17, 99, 28, 58, 41, 75
Da2:

//output
//first run:
Db1: 11, 83, 94
Db2: 12, 35, 96
//second run:
Da1:
Da2:
Db1: 11, 83, 94  || 17, 28, 99
Db2: 12, 35, 96  || 41, 58, 75
//3rd run
Da1: 11, 12, 35, 83, 94, 96
Da2: 17, 28, 41, 58, 75, 99

//4th run:
Da1:
Da2:
Db1: 11, 17, ......
Db2:
//DONE!

//most time will be spent on reading data from disk to memeory and output data to disk

Improvement:
1.  一大缺点是K路合并需要2K的磁盘。saving disks using polyphase merge sort.  
    A polyphase merge sort is an algorithm which decreases the number of runs  
    at every iteration of the main loop by merging runs   
    into larger runs. It is used for external sorting.
2. using replacement selection to generate the run.

K-way merge sort应用：merge K sorted list

class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        priority_queue<ListNode*, vector<ListNode*>, mycom> myque;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
        for(int i=0; i<lists.size(); i++) {
            if(lists[i])
                myque.push(lists[i]);
        }
        while(!myque.empty()) {
            ListNode *p = myque.top();
            cur->next = p;
            myque.pop();
            cur = cur->next;
            if(p->next) {//加入该节点的下一个节点
                myque.push(p->next);
            }
        }
        return dummy.next;
    }
private:
    struct mycom{//self defined comparison object
        bool operator() (ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };
};

Interviewer 9

  1. Data Stream Median
  2. 给一个数组，数组里有一个peak value,大概就像这样：{1,3,5,4,2}，问我怎么在里面找指定的数.
    我就说binary search先把peak的index找出来然后在peak以左和peak以右分别进行binary search. 笔记上有

Interviewer 10

  1. sort array to binary search tree
  2. merge two sorted arrays， one is ascending , the other is descending

Interviewer 11

  1. In place sort， 不用temp。
    Quick sort用了O(logn)的栈空间不知道算不算。。。
    heap, selection, insertion, 都是in-space的。如果说不用temp是
    指不能交换的话只能insertion了，没有交换操作。
    selection是用了N次交换的，heap操作的时候也要交换。或者他的意思是
    a=a+b; b=a-b; a= a-b这样来实现a b的交换？要问清楚。
  2. 给0 － 99 中的一数表示 cents 的总数，
    问最少几个美国硬币和是这个数。
    输出表示每个硬币数量的字符串。
    ex： 7 输出 1 nickel, 2 pennies。
    string exchange(int cents) {
string coin_str;
if (cents > 25) {
coin_str += to_string(cents / 25) + " quater(s) ";
cents = cents - (cents / 25) * 25;
}
if (cents > 10) {
coin_str += to_string(cents / 10) + " dime(s) ";
cents = cents - (cents / 10) * 10;
}
if (cents > 5) {
coin_str += to_string(cents / 5) + " nickle(s) ";
cents = cents - (cents / 5) * 5;
}
if (cents > 0){
coin_str += to_string(cents) + " penny(s) ";
}
return coin_str;
}
  3. OOD： 设计 kitchen table。

Interviewer 12

  1. 链表删一个节点. We can't really delete the node, but we can kinda achieve the same effect by instead removing the next node after copying its data into the node that we were asked to delete.
    void deleteNode(ListNode* node) {
     auto next = node->next;
     *node = *next;
     delete next;
 }
  2. 在数组中找duplicate element

Interviewer 13

  1. Search in Rotated Sorted Array 要问有没有重复的元素
  2. Validate Binary Search Tree

Interviewer 14

  1. Most interesting project
  2. What data structures did you use in your projects?. from: 1point3acres.com/bbs
  3. What design patterns did you use in your projects?
  4. Why we use design patterns?
  5. Why we use inheritance rather than composition? (composition 不知道给跪了。。)
  6. Coding: return a list containing all perfect number in a given range from input. Perfect number is: sum of all its positive divisors == number * 2 不难但是没做过。 两个 for loop 搞定。注意 corner case。最后要优化一点。复杂度 quadratic 当时没想出来更好的解法。
     public static boolean isPerfectNumber(int number) {
     int sum=0;         
     for(int i=1; i<=number/2; i++) {
         if(number%i == 0) {
             sum += i;
         }
     }
     if(sum==number) { 
         return true;
     }else {
         return false;
     }
 }
  7. Any question?.

Interviewer 15

  1. LRU. follow ups:让你扩展到一个distributed in memory cache system怎么设计

Interviewer 16

  1. is a string palindrome
  2. is a binary palindrome
    //binary to int, int to binary
string binaryString(int num) {
 string b_str="";
 int mask = 1;
 while (num > 0) {
     char c = num&mask ? '1' : '0';
     b_str.push_back(c);
     num = num >> 1;
 }
 reverse(b_str.begin(), b_str.end());
 return b_str;
}
int binaryInt(string s) {
 int num = 0;
 for (int i = 0; i < s.length(); i++) {
     if (s[i] == '1') {
         num += (1 << (s.length() - i - 1));
     }
 }
 return num;
}
  3. Compare Version Numbers

Interviewer 17

  1. 合并链表
  2. 括号匹配 Valid Parentheses

Interviewer 18

  1. Count the number of 1s in an binary integer

Interviewer 19

  1. input: aabccc output: 2ab3c 然后讨论可以不可以再优化
  2. reverse string. 让我说出所有想到的方法 然后讨论复杂度 然后挑了其中一种写code

Interviewer 20

  1. 3sum
  2. Binary Tree Level Order Traversal变体，加了实际应用背景。

Interviewer 16

Interviewer 16

Interviewer 16

Interviewer 16

Interviewer 16

Interviewer 16

Interviewer 16

results matching ""

    No results matching ""