An array is a collection of data of the same type which are stored at contiguous memory locations.
Declaration
int arr[] = new int[20];
Initialization
int [] arr = new int[]{1, 2, 3, 4, 5}
Time Complexity
Accessing an element | O(1) |
Adding an element | O(n) |
Removing an element | O(n) |
Arrays class
asList(
): Converts array into ArrayListbinarySearch()
: Performs a binary search on the arraysort(<array>)
: Sorts array in ascending order
Questions
- On which memory arrays are created?
Stack Memory - How many ways to find duplicate elements in an array?
- Brute Force Method – O(n2)
- Using HashSet- O(n)
- Using HashMap- O(n)
- How to search an element in an array
- Bruteforce – O(n)
- Arrays.binarySearch() -> log(n)
- Difference between Array & Arraylist
Array is static and Arraylist is dynamic - What is the equilibrium index of an array
If the sum of lower indices is equal to the sum of higher indices is called the same - Advantages & Disadvantages of an array
(Advantages)
* Can store multiple elements of the same types under a single variable
* Fetch elements using the index
(Disadvantages)
* Mandatory to declare size before using
* static in nature – can’t increase or decrease memory location
* Insertion/deletion are costly O(n)
* allocate more memory than required
Question:
- Is Unique: Check if string has all unique character
- 44 hash table (set)
- 117 (vector / arraylist)
- 132 (n log n)
- Check Permuation: given two string check if one is permutation of other
- 1 : descbie what is means by permutation)
- 84 -> nlogn , another soln is n with some space
- 122 -> hash table
- 131 -> two string that are permutations would have same character, but in different order, can you make the order same?
- URLify: write a method to replace spaces with %20
- 53
- 118
- Palindrome Permutation: given a string write a function to check if it is a permutationof palinrome.
eg: I/P: Tact Coa
Output: true (permutations: “taco cat”, “atco cta”, etc.)- 1.6, 121, 134, 136
- One Away: three types of edits to perform : insert, remove, replace
eg: pale, ple -> true
Pales, pale -> true
Pale, bake -> false- 23
- 97
- 130
- String compression: eg: aabcccccaaa -> a2b1c5a3 (if compressed is not smaller return original
- 92
- 110
- Rotate matrix: given image in NxN, rotate image by 90 degrees, In place
- 51
- 100
- zero matrix: if element in MXN is 0, make entire row and column to 0
- 17
- 74
- 102
- String Rotation: isSubstring method to check for substring is given, for two string s1 and s2 write code to shcek if s2 is a rotation of s1 using only one call to isSubstring (waterbottle is a rotation of erbottlewat”
- 34
- 88
- 104
Collection of the same type of data
- Calculate item index O(1)
- Insert or Delete items at the beginning: O(n)
- Insert or Delete item in middle O(n)
- Insert or Delete item at end O(1)