Notes

7 flashcards · Programming Languages · by Steven Bui

1. Basic binary search algorithm

   Approach: Find the left and right indices. Make a for-loop while left <= right. Calculate the mid index carefully, and make checks for if the middle index is equal to, greater than, or less than the index next to it accordingly. Update the left or right bounds accordingly to mid +/- 1. TRICK: Less than = change Left bound (plus 1 because left is good) Code: public boolean algorithm(int[] array, int target) { ....int left = 0; ....int right = array.length - 1; ....while (left <= right) { .......…

2. Queue

   Used for breadth-first search (BFS) Initialized with a LinkedList Queue<Integer> queue = new LinkedList<>(); Queue methods: offer(E):...adds to the queue poll():........removes from the queue peek(): ....gets the head of the queue TRICK: A queue is your OPP

3. Breadth first search (BFS)

   Approach: First, create a queue using a LinkedList, and add the root to the queue. Create a List<List> to return as well. In a while-loop while the queue is not empty, the principle is that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. Right before going into a for-loop inside of the while-loop that runs for the number of nodes in the level, create an ArrayList to add the contents of the level in. Then, inside of the for-loop, add each node's…

4. Depth first search (DFS)

   Approach: In a main function, create a list to store the results of the traversal. Call a helper method with the root and the list. In the helper function, return if the root is null. If not, you can either do a preorder, in-order, or post-order traversal. For pre-order, add the root's value to the list, then call the helper function on root.left, and then call the helper function on root.right. Code: public List<Integer> main (TreeNode root) { ....List<Integer> rtn = new ArrayList<>(); ....hel…

5. Strings

   char array to String: String s = new String(array[]) StringBuilder to String: String s = sb.toString()

6. HashMaps

   getOrDefault: If the first parameter returns false for map.containsKey(), then return the second parameter int grade = map.getOrDefault("Steven", 0) keySet: returns a Set object of just the keys Set<Integer> set = map.keySet(); values(): Returns a Collection object of just the values Collection<Integer> collection = scores.values(); List<Integer> list = new ArrayList<>(collection);

7. Stacks

   Iterating over a stack: prints out '1 2 3' (bottom of the stack up to the top) Stack<String> stack = new Stack<>(); stack.push("1"); stack.push("2"); stack.push("3"); for (String s : stack) ....System.out.println(s);