Java - AbhiAgarwal/notes GitHub Wiki
Java Usual Size Limits
- Heap - 512MB
- Stack - 8.9MB
- 1 Billion Operations is ~roughly 1 second
Arrays
Arrays.fill(myArray, 0), fills the array with all zeros
- Java = Arrays.sort(myArray), Quicksort which is O(nlogn) or O(n^2)
- C++ = IntroSort, Quicksort then if not good then Heapsort
- Java = Collections.sort uses Stablesort
ArrayList
ArrayList x = new ArrayList(number of elements);
- initial is 10, & unbounded growth thereafter
- appending is O(1)
- when resize occurs all elements are copied to new array O(n)
- so when the size becomes too large then it allocates a new array
- sometimes you could initialize it as your constraint
Uses for ArrayList
- Sort
- Arrays.sort(myArray), quicksort O(nlogn)
- Collections.sort(myList) merge sort O(nlogn)
- Search
- Unsorted list O(n) Arrays.binarySearch(), Collections.binarySearch()
- Sorted list, Binary Search O(nlogn)
Bitmask
There is a BitSet Class in Java
- Mask is data that is used for bitwise operations, particularly in a bit field, ie: 1&1
- Insertion
- Inserting 7 into S
- long S = 0;
- S |= (1<<7)
Hash Table
- Load Factor is one of the parameters for the constructor & initialization
- Insertion, fetch, removal, membership O(1) (EXPECTED)
- Typically faster than the Tree
- for(Entry<K,V> e : myHashTable.getEntries()) for you to help maintain your keys
- LinkedHashMap vs LinkedHashSet in Java
Binary search tree
- Self-balancing binary tree
- TreeSet & TreeMap
LinkedList - just use an ArrayList
Priority Queue
- Push, Pull O(logn)
- Implemented Using Binary Heap
Red-Black Tree
- Implement own Red-Black tree & then use Binary Search
Union-find
- Union, find O(n)