DEV Community: Tammy Vo

Array vs ArrayList

Tammy Vo — Wed, 01 May 2024 17:06:56 +0000

The decision between using an ArrayList and a traditional array depends on various factors, including flexibility, ease of use, performance, and memory management.

Flexibility: ArrayLists offer more flexibility than arrays because they can dynamically resize themselves. You don't need to specify the size of an ArrayList upfront, unlike arrays where you must declare the size when you initialize them.
Ease of use: ArrayLists provide convenient methods for adding, removing, and accessing elements. They have built-in methods like add(), remove(), get(), etc., which makes manipulating data easier compared to arrays, where you have to manually manage resizing and shifting elements.
Performance: Arrays typically offer better performance in terms of accessing elements since they provide direct access to any element based on its index. ArrayLists, on the other hand, have some overhead associated with dynamic resizing and object wrapping, which might affect performance in performance-critical applications.
Memory management: Arrays tend to be more memory-efficient than ArrayLists because ArrayLists use an underlying array to store elements along with additional metadata to manage resizing and other operations. However, this difference might not be significant unless you're dealing with very large datasets or memory-constrained environments.

Here are some scenarios where you might prefer one over the other:

Use an array when you know the size of the data structure beforehand and need direct access to elements with minimal overhead.
Use an ArrayList when you need a dynamically resizable data structure, especially if you're dealing with a collection of objects whose size might change frequently.
In performance-sensitive applications, such as low-level system programming or high-frequency trading systems, where every CPU cycle counts, you might opt for arrays to minimize overhead.

In most other cases, where ease of use and flexibility are more important than absolute performance, ArrayLists provide a more convenient option.
Ultimately, the choice between an ArrayList and an array depends on the specific requirements and constraints of your application.

Top K Frequent Elements

Tammy Vo — Tue, 26 Dec 2023 05:16:44 +0000

Objective:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Pattern: Arrays and Hashing

Approach:

Create a HashMap that holds the element as the key and frequency as the value.
Iterate through the input array and store in HashMap.
Since HashMap is not ordered, use a Priority Queue to keep track of the K most frequent elements.

For Priority Queue:

Queue <Integer> pq = new PriorityQueue<>((a, b) -> hashMap.get(b) - hashMap.get(a));

The PriorityQueue is initialized with a custom comparator using a lambda expression (a, b) -> hashMap.get(b) - hashMap.get(a).

Here's what each part does:

hashMap.get(b) - hashMap.get(a): This is the custom comparator. It compares two integers a and b based on their corresponding values in a HashMap named hashMap. The elements with higher values in the HashMap will have a higher priority in the PriorityQueue. So, the PriorityQueue will be a min-heap based on the frequencies stored in the HashMap.
(a, b) -> ...: This is a lambda expression defining a Comparator. It takes two parameters a and b (representing elements in the PriorityQueue) and returns the result of the subtraction of their corresponding values in the HashMap. If the result is negative, a has a higher priority; if positive, b has a higher priority; if zero, they have equal priority.

So, in summary, this line of code creates a PriorityQueue of integers (Queue pq) with a custom comparator based on the frequencies stored in the HashMap (hashMap). The elements with higher frequencies will have higher priority in the PriorityQueue.

Big-O Notation:

Time Complexity: O(N + M * log(M) + K * log(M))
Counting frequency = O(N)
Priority Queue = O(M * log(M))
Result array = O(K * log(M))

Space Complexity: O(M)
HashMap = O(M)
Priority Queue = O(M)

Note: N is total/all elements in input array, M is unique elements in input array, and K is specified value.

Code:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // input: array and k value. 
        // output: top k frequency 
        int [] result = new int [k];

        // hashmap <num, freq>
        Map <Integer, Integer> hashMap = new HashMap<>();

        // go through nums array, add freq to hashmap
        for(int i = 0; i < nums.length; i++){
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i],0)+1);
        }

        // priority queue
        Queue <Integer> pq = new PriorityQueue<>((a, b) -> hashMap.get(b) - hashMap.get(a)); 

        // go through hashmap, add to priority queue
        for(int key: hashMap.keySet()){
            pq.add(key);
        }

        // return k max values and add to result array
        for(int i = 0; i < k; i++){
            result[i] = pq.poll();
        }

        return result;
    }
}

Java Fundamentals

Tammy Vo — Tue, 02 Aug 2022 22:37:00 +0000

What is an object?
An instance of a class.
Each object contains a state and behavior.
State and behaviors are created through fields and methods.

What is a class?
A class acts as a template/blueprint that describes the state and behavior of an object.

Constructors:

How do you call a constructor?
Use keyword new, this will instantiate a new object.
Constructor is a method that makes your object.

What is default constructor?
Default constructor is a constructor that is not declared explicitly inside the class, or is defined but has no body or parameters that creates the objects for you.

When you want to create an object with certain attributes then you want to create a constructor that takes in those attributes instead of having to set it every time.

If you define another constructor (with arguments), default constructor will not be generated. If you still want one, you need to define it yourself.

Keywords:

this and super keywords:

Use the keyword this. to set the fields to that instance of the object if the input and field have the same name.

Use the keyword "super()" to call the parent's constructor and methods when using an inheritance relationship.

Limitation on calling super - you can't call super() on a private method.

static keyword:

YouTube Resource: Static in Java - How to use the Static Keyword

The static keyword means the value is the same for every instance of the class.
Without the static keyword, we need to create an instance of the class to access the method or variable within that class.
With the static keyword, we do not need to instantiate an object. However, the field and method need to also be static to be accessed.

final

What does final mean in method headings?
The final keyword is a non-access modifier used for classes, attributes and methods, which makes them non-changeable (impossible to inherit or override).

The combination of static final in Java is how to create a constant value.

4 Pillars of OOP in Java:

Abstraction
Encapsulation
Inheritance
Polymorphism

Abstraction:
Hide code implementation details from the user. We can do this by using abstract classes or interfaces.

Interface vs Abstract class
YouTube Resource: Abstract Classes and Methods - Learn Abstraction in Java

Abstract Class - Use keyword extends - Using inheritance concept.

An abstract class allows you to create functionality that subclasses can implement or override.
Cannot instantiate an abstract class aka not call the constructor of an abstract class because the purpose of is an abstract class is to create subclasses that is used and instantiated.

Interfaces - Use keyword implements - Overrides methods from interface.

An interface only allows you to define functionality with unimplemented methods. Subclasses can then implement all functionalities from the interface.

Encapsulation:
Keep fields private, have public methods to access those private fields: Getters and setters.
Reuse objects without allowing open access to the data system.

Inheritance:
Parent class and child class. The child class can extent the parent class and inherit all the fields and methods that the parent contains. Great for code reusability.

Polymorphism:
Method overloading: Have different methods with the same name and different numbers of parameters.

Method overriding: Same method name and number of parameters is overridden with new context. This can happen during inheritance where the child class overrides a parents class.

Example:
We have a sound() method in parent class that prints "papa bear voice". Child class that extends the parent class, but we want the sound() method to print "baby bear voice". We would override the method.

Access Modifiers:

Where it can be accessed in your application.
Help restrict the visibility of classes, variables, methods, constructors, and etc.

YouTube Resource: Java Access Modifiers - Learn Public, Private, Protected and Default

Default: can be accessed within same package.

int element = 30;

Public: can be access anywhere, including different packages.

public int element = 30;

Private: can only be accessed within the class. Class and interface cannot be private.

private int element = 30;

Protected: can only be accessed within same package, subclasses are also allowed.

protected int element = 30;

The Object class is the parent class of all the classes in java by default. In other words, it is the topmost class of java.

What are some of the methods in Java Object class?

toString() - returns the string representation of this object.
hashCode() - returns the hashcode number for this object.
equals(Object obj) - compares the given object to this object.

What is the difference between == and .equals()?

Use == operators for reference comparison (address comparison)
Use .equals() method for content comparison.

Why don't you use == to compare strings in Java?

Using == will compare the reference whether it is the same object, not the value of the strings. So we need to use .equals()

What is difference between HashMap and Map?
Map is an interface.
HashMap is a class.
HashMap class implements the Map interface.

Map has two implementations:
HashMap and TreeMap

What is a JDK and JRE?

JDK(Java Development Kit) is used to develop Java applications. JDK also contains numerous development tools like compilers, debuggers, etc.
JRE(Java Runtime Environment) is the implementation of JVM(Java Virtual Machine) and it is specially designed to execute Java programs.

100 days of SwiftUI - Day 1 & 2

Tammy Vo — Sat, 23 Jul 2022 16:08:00 +0000

100 days of SwiftUI - Day 1 - Simple Types

100 days of SwiftUI - Day 2 - Simple Types Part 2

Variables:

To create a new variable we need to use "var" to initialize and define.

var operatingSystem = "macOS"

Strings and Integers:

Swift is type safe.
Strings and Integers can not be mixed.
If there are larger numbers, we can use underscores as thousand separators making it easier to read.

var str = "Hello"
var age = 25
var population = 8_000_000

Multi-line String:
Start and end with three double quote marks for multi-line strings, this will include line breaks.

var str1 = """
This goes
over multiple
lines
"""

// This way will not show new line breaks in output
var str2 = """
This goes \
over multiple \
lines
"""

Doubles and booleans:
Doubles will hold a decimal value:

var pi = 3.141

Booleans will hold a true or false value:

var isCool = true

String interpolation:
Place any type of variable inside your string by adding a backslash \

var score = 85
var str = "Your score was \(score)"
var results = "The test results are here: \(str)"

Constants
Use the let keyword to create constants. Constants can be set once and never changed.

let taylor = "swift"

Type annotations
Swift assigns each variable and constant a type based on what value it’s given when it’s created.

To be explicit about the data type, we can assign it:

let album: String = "Reputation"
let year: Int = 1989
let height: Double = 1.78
let taylorRocks: Bool = true

Sliding Window Technique

Tammy Vo — Sat, 23 Jul 2022 02:29:00 +0000

When to use: Aims to reduce the use of nested loop and replace it with a single loop. Reduces the time complexity from O(n^2) to O(n).

Two types of sliding window:

Fixed window length k: the length of the window is fixed and you will be asked to find something in the window. For example, the maximum sum or maximum average of each window.
First we start by getting the sum of the k sized window and keep track of the max value then sliding it by removing from the left and adding to the right.

class Solution {
    public double findMaxAverage(int[] nums, int k) {

        double maxAverage = 0;
        int sum = 0;

        for(int i = 0; i < k; i++){
            sum += nums[i];
        }

        maxAverage = sum;

        for(int i = k; i < nums.length; i++){
            sum += nums[i] - nums[i - k];
            maxAverage = Math.max(maxAverage, sum);
        }

        return maxAverage/k;
    }
}

Dynamic-size sliding window: The window size is not fixed and is also known as the two-pointers technique.
However, in a dynamic sliding window problem, the right pointer will be continuously changing unlike a traditional two pointer problem where the right pointer is initialized as the end of the list/array. Usually you will be asked to find the subarray that meets the criteria.

Longest Consecutive Sequence

Tammy Vo — Thu, 21 Jul 2022 17:17:00 +0000

Leetcode Problem: Longest Consecutive Sequence

Objective:

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Pattern: Arrays and Hashing

Approach:

Create a set to store the elements.
Get the start of the sequence. The start of a sequence does not have a left neighbor.
Once we identify a start of a sequence, we can check if the next value exists in the set.
Keep track of the length of the sequence.
Return the max length.

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each element.

Space Complexity: O(n)
We use a Set data structures to store n elements.

Code:

class Solution {
    public int longestConsecutive(int[] nums) {
        // use hashset to store n values
        Set <Integer> hashSet = new HashSet<>();

        // maxLength to keep track of longest consecutive sequence 
        int maxLength = Integer.MIN_VALUE;

        // edge case 
        if (nums.length == 0 || nums.length == 1){
            return nums.length;
        }

        // add all elements into hashset 
        for(int i : nums){
            hashSet.add(i);
        }

        // get the first sequence 
        for(int curr : nums){
            // does left exist in hashMap
            // if it does not then it is the start of a sequence 
            if(!hashSet.contains(curr - 1)){
                int count = 1; 
                boolean flag = true;
                while(flag == true){
                    if(hashSet.contains(curr + 1)){
                        count++;
                        curr++;
                    } else {
                        flag = false;
                    }
                    maxLength = Math.max(maxLength, count);
                }
            }
        }
        return maxLength;
    }
}

Two Pointer Technique

Tammy Vo — Wed, 20 Jul 2022 12:40:41 +0000

When to use: Optimal way to solve problems related to arrays, strings and linked list in O(N) time.

Arrays/Strings: Two pointers, each starting from the beginning and the end until they both meet.
Example Problem: Two Sum II - Input Array Is Sorted

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer technique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}

Linked List: One pointer moving at a slow pace, while the other pointer moves at twice the speed.
Example Problem: Linked List Cycle

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

Linked List Cycle

Tammy Vo — Wed, 20 Jul 2022 12:39:00 +0000

Leetcode Problem: Linked List Cycle

Objective:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Pattern: Two Pointer Technique

Approach:

Edge case: If input is null then the list is empty so a cycle does not exist.
Create two pointers both starting at head. One pointer moving at a slow pace, while the other pointer moves at twice the speed.
If the slower pointer ends up catching up to the faster pointer then return true because there is a cycle.
If the faster pointer reaches a null then return false because there is no cycle.

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each element.

Space Complexity: O(1)
We do not use any additional data structures for storage.

Code:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

Group Anagrams

Tammy Vo — Tue, 19 Jul 2022 22:37:44 +0000

Leetcode Problem: Group Anagrams

Objective:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Pattern: Arrays and Hashing

Approach:

Create a 2D list for the result.
Create a HashMap: key = sorted word, value = list of anagrams.
Iterate through the input string array and sort the input.
If the sorted input is not in hashmap or edge case where the sorted input equals the non-sorted input then add the sorted input as the key and the non-sorted input as an anagram.
If the sorted input already exists as a key in the hashmap, then get the sorted key and add the non-sorted input into the anagram list.
Iterate through the hashmap and add each anagram list into the result list. Return result.

Big-O Notation:

Time Complexity: O(m * nlog(n))
We have iterate n times for each string.
We sort each string using Arrays.sort() which is O(n log(n)).

Space Complexity: O(n * m)
We use additional data structures for storage.
We have a 2D list to store the result.
We have a hashmap to store elements.

Code:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // input: string array 
        // output: 2D list 
        List<List<String>> result = new ArrayList<List<String>>();

        Map <String, List<String>> hashMap = new HashMap<>();

        for(String str : strs){
            char [] array = str.toCharArray();
            Arrays.sort(array);

            String sortStr = str.valueOf(array);

            // edge case if current == key then add to key. 
            if(sortStr == str || !hashMap.containsKey(sortStr)){
                List <String> anagram = new ArrayList<>();
                anagram.add(str);
                hashMap.put(sortStr, anagram);
            } else {
                hashMap.get(sortStr).add(str);
            }
        }

        // add anagram list into result 
        for(String s : hashMap.keySet()){
            result.add(hashMap.get(s));
        }

        return result;
    }
}

Journey to becoming an iOS Developer

Tammy Vo — Tue, 19 Jul 2022 17:20:00 +0000

Day 0

Prerequisites:
Will Power
Xcode - download from the Mac App Store

Here are 7 things we will be covering:

Core Skills
Extension skills
Common Mistakes
Learning Resources
Connecting to the community
How long will it take
Preparing to apply for a job

Resources:
Hacking with Swift

Valid Parentheses

Tammy Vo — Tue, 19 Jul 2022 03:31:31 +0000

Leetcode Problem: Valid Parentheses

Objective:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Pattern: Stack

Approach:

Use a hashmap to store the paired brackets: key = closed bracket and value = open bracket.
If the hash map does not contain current character then it is an open bracket. Use a stack to store the open brackets.
Check if the stack is empty this prevents closing brackets to be added first, in this case it is not valid.
Check the top of the stack by popping it and if top character is not matched with closing bracket in hashmap then return false.
If stack is empty then return true because it is a valid parentheses.
If stack is not empty then return false.

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each character in the string.

Space Complexity: O(n)
We use a hash map data structures for storage.

Code:

class Solution {

    public boolean isValid(String s) {
        // use stack to store opening brackets
        Stack <Character> stack = new Stack<>();

        // use a hashmap to store pairs 
        Map <Character, Character> hashMap = new HashMap<>();
        hashMap.put(')','(');
        hashMap.put('}','{');
        hashMap.put(']','[');

        // iterate through s
        // add open brackets to the stack
        // if stack is empty or top char is not a match to c 
        // return false 

        for(char c : s.toCharArray()){
            if(!hashMap.containsKey(c)){
                stack.push(c);
            } else if(stack.isEmpty() || stack.pop() != hashMap.get(c)){
                   return false;
                }
            }
        return stack.isEmpty();        
    }
}

Container With Most Water

Tammy Vo — Thu, 07 Jul 2022 22:52:37 +0000

Leetcode Problem: Container With Most Water

Objective:

Given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Pattern: Two Pointer Technique

Approach:

Set a left and right pointer. left pointer = 0, right pointer = array.length - 1.
Create a maxArea variable to keep track of maximum area between left and right pointers.
Create a width variable to keep track of the width between left and right pointers.
Calculate the for the max area, get the shorter pointer and multiple it by the width.
If left < right pointer then increment left pointer and decrement width.
If left > right pointer then decrement right pointer and decrement width.

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each element.

Space Complexity: O(1)
We do not use any additional data structures for storage.

Code:

class Solution {
    public int maxArea(int[] height) {

        int left = 0;
        int right = height.length - 1;
        int maxArea = Integer.MIN_VALUE;
        int width = height.length - 1; 

        while(left < right){
            int less = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, less * width);

            if(height[left] <= height[right]){
                left++;
            } else if (height[left] > height[right]) {
                right--;
            }

            width--;
        }
        return maxArea;
    }
}