Airbnb

airbnb_2017_fall

-------------------------
倒水

往一个int array 代表海拔的格子里倒水，打印出倒水后的

int[] 海拔， int 水数量， int

倒得位置。

Example:
int[] 海拔 {5,4,2,1,2,3,2,1,0,1,2,4}
水数量8， 倒在位置5

比较开放的题，一些条件要跟面试官探讨，比如左边还是右边优先。

例子：

handle the water drop by drop。 there are infinitely high walls on the left and right 

水先向左走，走到不能走。call it leftMost 

如果leftmost的水比开始点低，leftMost水+1，done 

如果leftmost的水不比开始点低，水向右走，走到不能走，call it rightMost 

如果rightmost的水比开始点低，rightMost水+1，done 

如果rightmost的水不比开始点低，leftMost水+1，done

public static void main(String[] ss) {
        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};
        fillWater(a, 5,8);

        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void fillWater(int[] land, int pos, int water) {

        while (water > 0) {
            int left = pos;
            while (left > 0 && land[left - 1] <= land[left]) {
                left--;
            }

            if (land[left] < land[pos]) {
                land[left]++;
                water--;
                continue;
            }

            int right = pos;
            while (right < land.length - 1 && land[right + 1] <= land[right]) {
                right++;
            }

            if (land[right] < land[pos]) {
                land[right]++;
            }else {
                land[left]++;
            }

            water--;
        }
    }

另一个变种是把最终的图形（墙跟水）都打印出来

-----------------------------
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273149

题目是给你公式，比如偶数的话除2，奇数的话就变成3*n+1，对于任何一个正数，数学猜想是最终他会变成1。每变一步步数加1，给一个上限，让找出范围内最长步数。
第一题是这样的：比如7，变换到1是如下顺序：7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1, 总共需要17步。

很直接， 没什么好说的。用一个map减少重复计算

public static void main(String[] ss) {
//        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};

        System.out.println(findLongestSteps(7));
    }

    private static int findLongestSteps(int num) {
        Map<Integer, Integer> map = new HashMap<>();

        int longest = 0;

        for (int i = 1; i <= num; i++) {
            longest = Math.max(findSteps(i, map), longest);
        }

        return longest;
    }

    private static int findSteps(int num, Map<Integer, Integer> map) {
        if (num <= 1) return 0;

        if (map.containsKey(num)) return map.get(num);

        int rt = 0;
        if (num % 2 == 1) rt = findSteps(3 * num + 1, map);
        else rt = findSteps(num / 2, map);

        rt++;
        map.put(num, rt);
        return rt;
    }

----------------------------------------------------
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=279191

Design a Queue with arrayList, 但是有限制条件, arraylist的长度最多为10, queue不限制长度。纠结了很久不知道怎么做，是不是先把max size设置成10，然后发现overflow了在扩大成10个arraylist，以此类推到100, 1000... 但是这样的话，queue的remove操作要从头开始，好像记录起来比较麻烦。求大家讨论！

用linked list来做，每个node包含一个list，长度不能超过定值

class MyQueue {

    private Node head;
    private Node tail;
    private int indexHead;
    private int indexTail;

    public MyQueue() {
        head = new Node();
        tail = head;
        indexHead = 0;
        indexTail = 0;
    }

    public int pop() {
        int rt = head.list.get(indexHead);
        indexHead++;

        if (indexHead == 5) {
            head = head.next;
            indexHead = 0;
        }

        return rt;
    }

    public int peek() {
        return head.list.get(indexHead);
    }

    public void push(int val) {
        tail.list.add(val);
        indexTail++;
        if (indexTail == 5) {
            tail.next = new Node();
            tail = tail.next;
            indexTail = 0;
        }
    }
}

----------------------------------------------------



----------------------------------------------------



----------------------------------------------------