发个AirBnb电面跪经

Design a Queue with arrayList, 但是有限制条件, arraylist的

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

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

move操作要从头开始，好像记录起来比较麻烦。求大家讨论！

简单点儿方法可以把每个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. }

复制代码

用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.        }

复制代码

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

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

谁知道这题怎么做？

mark留名，同求这一题思路

List<List<>> queue ?

pop, 先看外边的list中最后一个list的大小, 如果是1, 删了当前的list, 返回, 如果不是, 返回当前list最后一个元素
push, 和上边相反, 当前最后一个list的大小是10, 就建个新的.

readman 发表于 2017-5-9 01:44
List queue ?

pop, 先看外边的list中最后一个list的大小, 如果是1, 删了当前的list, 返回, 如果不是,  ...

你这是queue吗？感觉是stack

wxl3691 发表于 2017-5-9 02:45
你这是queue吗？感觉是stack

queue啊 更简单了, pop的时候用iterator, 自动每次都走第一个
push的时候没区别

readman 发表于 2017-5-9 02:48
queue啊 更简单了, pop的时候用iterator, 自动每次都走第一个
push的时候没区别

好的，感谢

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

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

楼主可以看下circular buffer,感觉可以用双指针解决