亚麻店面面经

Job Hunting Interview
, , , , ,
1
  1. Explanation about work at current company employed with - discussion of product, responsibilities, biggest difficulties and how they were overcome, a few Amazon Leadership Principles.
  2. Given a binary tree, count the number of nodes. Discussed the recursive and iterative approach, and runtime.
  3. Given an array [16, 18, 6, 7, 4, 1] return the “leaders”. An item is a leader if it is the larger than all numbers to its right. In this example it would be [18, 7, 1] for the leaders. Discussed different approaches and runtimes, eventually doing it in O(n) .
2

感谢分享。
第三题有个问题：为什么例子答案不是[18, 7, 4] 而是[18, 7, 1] ?

3

感觉应该是 [18, 7, 4]

4

我的代码

  public static List<Integer> leaders(int... nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums) {
            while (!stack.isEmpty() && num > stack.peek()) {
                stack.pop();
            }
            stack.push(num);
        }
        List<Integer> leaders = new ArrayList<>(stack.size());
        while (!stack.isEmpty()) {
            leaders.add(stack.pollLast());
        }
        return leaders;
    }
    
    public static void main(String[] args) {
        System.out.println(leaders(16, 18, 6, 7, 4, 1));
        System.out.println(leaders(19, 18, 10, 7, 4, 1));
        System.out.println(leaders(1, 5, 10, 15, 20));
    }
1 个赞
5

如果不要求按照array里面的顺序，可以直接倒序遍历比较当前最大值即可。
如果一定要求按照顺序可以用一个stack，接住所有的leaders再pop到vector里面。

#include <vector>
#include <iostream>

using namespace std;

vector<int> getLeaders(vector<int> nums) {

    vector<int> res;
    if (nums.empty()) {return res;}

    int indexEnd = nums.size() - 1;
    int tempMax = nums[indexEnd];

    for (int i = indexEnd; i >= 0; i--) {

        if (nums[i] > tempMax) {

            res.push_back(nums[i]);
            tempMax = nums[i];
        }
    }
    return res;
}


void print_vect(vector<int> v) {

    for (int i : v) {
        cout << i << ", ";
    }
    cout << endl;
}


int main(){
    vector<int> v1 {16, 18, 6, 7, 4, 1};
    vector<int> v2 {19, 19, 10, 7, 4, 1};
    vector<int> v3 {1, 5, 10, 15, 20};

    print_vect(getLeaders(v1));
    print_vect(getLeaders(v2));
    print_vect(getLeaders(v3));
   
    return 0;

}
6

报个店面过经

问假如让你实现queue，该怎么实现。coding: O(1)时间enque,deque,max的queue