发个AirBnb电面跪经

runningMajia 发表于 2017-5-9 07:17
arraylist的长度最多为10 这个指的所有arraylist么？
如果不是的话，那只需要maintain一个2d的ArrayList o ...

是所有的arraylist，所以感觉很麻烦的样子

382851453 发表于 2017-5-9 06:02
楼主可以看下circular buffer,感觉可以用双指针解决

你是说一个headIndex一个tailIndex吗？是这样的，考虑到嵌套arraylist还是好复杂的感觉

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

runningMajia 发表于 2017-5-9 07:46
不用嵌套的话， 可以试试HashMap, key 是从0到n记录目前有多少个list的id，value就是最大长度为10的Array ...

我提过这个方法，面试官提示说HashMap的实现也是用array,所以也受10个的限制...

ecneralc 发表于 2017-5-9 08:45
我提过这个方法，面试官提示说HashMap的实现也是用array,所以也受10个的限制...

面试官的hint是啥？必须要用多层嵌套吗
a家题目太麻烦了也

好麻烦。。。

简单点儿方法可以把每个array最后一个item存下一个array的指针，这样每个size为10的array可以存9个元素。在空间上没有很高效，但是实现起来容易一些。
我的意思如下：

1. class Main {
   
2.     static final int LIMIT = 5;
   
3.     List<Object> list = new ArrayList<>();
   
4.     int head = 0;
   
5.     int tail = 0;
   
6.     int count = 0;
   
7. 
   
8.     public void enqueue(Integer item) {
   
9.         if (tail == LIMIT - 1) {
   
10.             list.add(new ArrayList<Object>());
    
11.             List<Object> newList = (List<Object>) list.get(LIMIT - 1);
    
12.             newList.add(item);
    
13.             tail = 0;
    
14.         } else {
    
15.             list.add(item);
    
16.         }
    
17.         tail++;
    
18.         count++;
    
19.     }
    
20. 
    
21.     public Integer peek() {
    
22.         if (count == 0) {
    
23.             return null;
    
24.         } else {
    
25.             return (Integer) list.get(head);
    
26.         }
    
27.     }
    
28. 
    
29.     public Integer pop() {
    
30.         if (count == 0) {
    
31.             return null;
    
32.         } else {
    
33.             Integer res;
    
34.             if (head == LIMIT - 1) {
    
35.                 List<Object> tmp =  (List<Object>) list.get(head);
    
36.                 list.clear();
    
37.                 list = tmp;
    
38.                 head = 0;
    
39.             }
    
40.             res = (Integer) list.get(head);
    
41.             head++;
    
42.             count--;
    
43.             return res;
    
44.         }
    
45.     }
    
46. 
    
47.     public Integer size() {
    
48.         return count;
    
49.     }
    
50. 
    
51.     public void test() {
    
52.         Main m = new Main();
    
53.         m.enqueue(1);
    
54.         m.enqueue(2);
    
55.         m.enqueue(3);
    
56.         System.out.println(m.peek());
    
57.         System.out.println(m.pop());
    
58.         System.out.println(m.peek());
    
59.         System.out.println(m.pop());
    
60.         m.enqueue(4);
    
61.         m.enqueue(5);
    
62.         m.enqueue(6);
    
63.         m.enqueue(7);
    
64.         m.enqueue(8);
    
65.         m.enqueue(9);
    
66.         System.out.println(m.peek());
    
67.         System.out.println(m.pop());
    
68.         System.out.println(m.peek());
    
69.         System.out.println(m.pop());
    
70. 
    
71.     }
    
72. 
    
73. 
    
74. 
    
75.     public static void main(String[] args) {
    
76.         Main test = new Main();
    
77.         test.test();
    
78.     }
    
79. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

用linkedinlist 是比较清晰的了吧，试着写了写，有不对的，欢迎提意见

1. public class QueueWithFixedSizeArray {
   
2.        int fixedSize;
   
3.        int total;
   
4.        class ListNode{
   
5.             ListNode next;
   
6.             int[] arr;
   
7.             int index;
   
8.             public ListNode(int size){
   
9.                 arr = new int[size];
   
10.                 index = 0;
    
11.            }
    
12.        }
    
13.        ListNode head;
    
14.        ListNode tail;
    
15.        public QueueWithFixedSizeArray(int fixedSize)
    
16.        {
    
17.            this.fixedSize = fixedSize;
    
18.            total = 0;
    
19.            head = new ListNode(fixedSize);
    
20.            tail = head;
    
21.        }
    
22. 
    
23.        public void offer(int x)
    
24.        {
    
25.            // add to the tail
    
26.            if(tail.index ==5)
    
27.            {
    
28.                ListNode next = new ListNode(fixedSize);
    
29.                next.arr[next.index] = x;
    
30.                next.index++;
    
31.                tail.next = next;
    
32.                tail = next;
    
33.            }
    
34.            else
    
35.                tail.arr[tail.index++] = x;
    
36.        }
    
37. 
    
38.        public int  poll()
    
39.        {
    
40.            if( head.index == 0)
    
41.            {
    
42.                if(head.next != null && tail != head) {
    
43.                    head = head.next;
    
44.                }
    
45.                else
    
46.                     return -1; //not find
    
47.            }
    
48.            int res = head.arr[0];
    
49.            System.arraycopy(head.arr, 1, head.arr, 0, head.arr.length-1);
    
50.            head.index--;
    
51.            return res;
    
52.        }

复制代码

better1016 发表于 2018-9-24 05:57
用linkedinlist 是比较清晰的了吧，试着写了写，有不对的，欢迎提意见
[mw_shl_code=bash,true]public cla ...

没啥问题貌似，其实网上查一下queue的标准也是类似的结果，都是linkedlist