Stewart Young
Stewart Young/
🧠
Second Brain
Search
Second Brain
🧠

Second Brain

Data Structures and Algorithms (Java focus)

What are the main data structures and their use cases?
Data structure
What is it?
Use cases
Strings
An immutable object representing character strings.
To store text variables.
Arrays
Arrays are an ordered collection of values. You can query an individual value from the array using an index number. Arrays are declared with fixed size in java and cannot be increased or decreased.
Used to store multiple values in a single variable. E.g. String[], char[], int[], boolean[].
Lists
Lists can be sized dynamically by adding more data, whereas arrays cannot.
Use to store elements of unknown size. It comes with built in methods such as get(), add(), set(), remove(), size().
Maps
Maps are unordered collections of key value pairs, where you can query a value by key. It allows only one null value, and values can be mutated easily.
Used to store key value pairs, and can be useful when lookup efficiency is important and order is not important.
Sets
Sets are unordered collections of unique values. You cannot have two instances of the same value in a set.
Useful for identifying duplicates in data.
Binary Tree
A tree data structure of nodes and edges where each node can have at most two child elements.
Useful for representing data hierarchies and for storing traversable data. Can aid in searching and sorting tasks.
Queue
Stores elements in FIFO order. You are limited to inserting at the end, or retrieving from the front.
Useful for storing order of arrival in the data structure, and for representing “first come first serve” logic.
Stack
Stores elements in LIFO order. You are limited to inserting at the top or retrieving from the top of the stack.
Useful for storing order of arrival data, and for making sure older items are seen to last.
Trie
A trie is a tree where each node can have many children, whereas a binary tree is restricted to one.
Useful for hierarchical and traversable data which are not limited to two options like in a binary tree.
Heap
A heap is a tree-based structure with nodes arranged in a specific order. In a max heap, the root node has the highest value, the bottom nodes hold lowest values. In a min heap the root has the lowest value and the bottom nodes hold the highest values. A binary heap is a complete binary tree, where all levels except the last are completely filled, and the last level has keys as far left as possible, as well as satisfying the heap property (either max or min heap).
Useful for specifically defined the rank of hierarchical data, in either increasing or decreasing order.
LinkedList
A linear data structure where elements are arranged in nodes and elements are linked using pointers and addresses. Acts as a dynamic sized array. Can be singly-linked, doubly-linked, or circularly-linked.
Useful for where a particular relationship between nodes needs to be maintained, and where new nodes may need to be dynamically added upon the original linked list.
Graph
A data structure of nodes and edges. Can be directed, undirected, and weighted.
Useful for storing data that maintains relationships between nodes e.g. similarity, closeness, proximity. For example social data is a great use case of graphs, and has lead to the growth of graph neural network models.
 
What are the time complexities of insert, search, and delete of the main data structures

Java trivia

What other method needs to be overridden when we override the equals() method on a string?
Strings compare the hash code of objects to compare equality. For example, if a = “hi” and b = “hi”, the underlying char array for “hi” is stored in the only one hashable heap of memory. Variables a and b maintain a pointer to this one bucket, instead of storing two instances of “hi”. Hence when doing an equals(), we also need to override the hashCode() method. For example the Integer class overrides equals() to do integer comparison.
What are the different methods of sorting in a SortedMap?
First of all, the SortedMap interface is implemented by TreeMap. TreeMaps by default store items in their natural order, for example String data is alphabetically sorted by key and numeric data is sorted in increasing order by key. You can only sort a SortedMap by key, not by value.
  1. Comparator.reverseOrder(): Or using the default Comparator methods.
  1. Create your own Class to implement the Comparator interface. Useful for when sorting needs to be done on attributes of different objects.
  1. Have the class you are using implement the Comparable interface, and define the compareTo method. Objects will need to be of the same time.
What is the difference in an abstract class and an interface in Java?
TLDR:
  1. If you have a class that needs to provide common functionality to its subclasses and wants to enforce certain methods to be implemented by the subclasses, use an abstract class.
  1. If you want to define a contract that multiple unrelated classes can implement to provide specific behaviors, use an interface. Can have static methods in an interface but not an abstract class.
In Java, both abstract classes and interfaces are used to define abstract types that cannot be directly instantiated. In some cases, a combination of both abstract classes and interfaces may be used in Java to achieve certain design goals. They serve as blueprints for other classes to inherit from or implement. However, there are some key differences between the two:
Abstract Classes:
  • An abstract class is a class that cannot be instantiated on its own. It is meant to be subclassed by other classes.
  • It may have both abstract (unimplemented) methods and concrete (implemented) methods.
  • Abstract methods are declared without a body, using the abstract keyword, and must be implemented by the concrete subclasses.
  • It can have instance variables, constructors, and member methods (both abstract and non-abstract).
  • It allows the use of access modifiers (e.g., public, private, protected) for its members.
  • A subclass can extend only one abstract class since Java supports single-class inheritance.
Example of an abstract class:
abstract class Shape {
    int x, y;

    public Shape(int x, int y) {
        this.x = x;
        this.y = y;
    }

    abstract void draw(); // Abstract method

    void display() { // Concrete method
        System.out.println("Displaying shape at (" + x + ", " + y + ")");
    }
}
Interfaces:
  • An interface is a reference type in Java that provides a contract for the behavior of a class. It cannot be instantiated directly.
  • It only contains abstract methods (implicitly abstract and public) and constants (implicitly public, static, and final).
  • Starting from Java 8, interfaces can have default methods (concrete methods with a default implementation) and static methods.
  • It cannot have instance variables (except constants) and constructors.
  • All the methods declared in an interface must be implemented by the class that implements the interface.
Example of an interface:
interface Drawable {
    void draw(); // Abstract method

    default void display() { // Default method
        System.out.println("Displaying drawable.");
    }

    static void printInfo() { // Static method
        System.out.println("This is a drawable.");
    }
}
What are the naming conventions for Java generics?
  • E - Element
  • K - Key
  • N - Number
  • T - Type
  • V - Value
  • S,U,V etc. - 2nd, 3rd, 4th types
How is a HashMap implemented internally in Java?
The internal implementation of a HashMap in Java is based on an array of linked lists, a.k.a, buckets/hash table.
  1. Hashing: When you insert a key-value pair, the hash code is calculated using hashCode(). The hash code is used to determine in which linked list/bucket the entry is placed.
  1. Bucket/hash table: The HashMap is An array of linked lists (buckets), where each bucket can hold multiple key-value pairs. The number of buckets is typically a fixed size, but may dynamically grow or shrink based on the load factor.
  1. Collision resolution: Different keys can have the same hash code (hash collisions), so HashMap using ”chaining”, where multiple key-value pairs with the same hash code get stored in a linked list associated with that bucket.
  1. Load Factor and rehashing: HashMap has a load factor, #elements:#buckets. When #elements > load factor * current capacity, then the hash map is rehashed to increase the number of buckets, redistributing the entries and reducing the likelihood of collisions.
  1. Redistribution: During rehashing, a new array of linked lists are created using new hash codes created during rehashing.
  1. Iterating over entries: The order of insertion is not guaranteed to be insertion order, it depends on the hash codes and how the elements are distributed across the buckets.
What is the importance of having a good hashing function?
  1. Hash-based data structure performance can have a high collision rate with a poor hashing function, which can lead to increased search times and degraded performance. This is because the keys may not be distributed uniformly.
  1. A good hashing function helps ensure identical keys produce the same hash code, which allows quick identification of duplicates.
  1. In cryptography, the hash function should be resistant to collisions and pre-image attacks (finding an input that gives a specific hash). It should be extremely difficult to find two inputs to give the same hash code, or to reverse engineer the image from a hash code.
  1. Load balancing is improved where a hash function can distribute hashed data evenly across the available buckets.
What is Java reflection
public class ReflectionTutorials {
	public static void main(String[] args) throws Exception {
		Cat myCat = new Cat("Stella", 6);
		Field[] catFields = myCat.getClass().getDeclaredFields();

		for (Field field : catFields) {
			if (field.getName().equals("name")) {
				// if the field is private or final, you get IllegalAccessException
				field.set(myCat, "Estrella");
				// you can do the following if the field is private or final
				field.setAccessible(true);
				field.set(myCat, "Estrella");
			}
		}

		Method[] catMethods = myCat.getClass().getDeclaredMethods();

		for (Method method : catMethods) {
			if (method.getName().equals("meow")) {
				// invokes the meow method on the myCat object
				method.invoke(myCat, // could add any meow method params here as 2nd arg
				);
				method.setAccessible(true);
				method.invoke(null);
			}
			System.out.println(method.getName());
		}
	}
}
What is an Optional in Java?
Optional is a class used to represent the possibility of a value being there or not
When and where not is it good to use Optional?
Good
  • use Optional as a field in a class to represent an optional property
  • use Optional to represent the result of findFirst() or max() where they may not be a result
  • use Optional as a return type for methods where the result may not be present, which makes it clear to callers that the value may be empty
Not good
  • as method parameters
    • Should use null or method overloading instead
  • List<Optional<T>> is unnecessarily complex
  • For flow control - it is not a replacement for conditional statements (if/else)
  • Nesting optionals - don’t put optionals inside another optional
Give a code example of a predicate in Java
Predicate<String> checkIfStringEqualsStewart = s -> s.equals("Stewart");
What are the difference between checked and unchecked exceptions in java?
Checked exceptions need to be explicitly declared, caught and handled. The Java compiler will not compile the code otherwise
IOException, ClassNotFoundException
Unchecked exceptions on the other hand do not, and the compiler does not enforce handling of these
NullPointerException, ArrayIndexOutOfBoundsException
What are different hashing algorithms?
What tools are included in the JDK bin folder for monitoring Java applications?
Compare JDK vs JVM vs JRE
What is the role for a classloader in Java
It loads Java bytecode into memory for the JVM at runtime
This can include loading from the file system, network or other locations in JVM memory
What are wrapper classes in Java?
Classes that provide object representation of primitive types, such as int, double, char, boolean etc
Why do we need wrapper classes in Java?
Having a wrapper class for a primitive type allows data to be used in objects such as collections or in OOP where methods expect an object to be passed
Can allow null values
What is autoboxing in Java?
Integer autoboxedInteger = 42;
int unboxedInt = autoboxedInteger;
What is casting in Java?
Are all strings immutable in Java?
Where are string values stored in memory in Java?
Why should you be careful about string concatenation operator in loops?
What are the differences in String and StringBuffer?
What are the differences in StringBuilder and StringBuffer?
What are some of the different utility methods in the String class?
What is the super class of every class in Java?
What are the most important things to consider when implementing an equals method?
What is the hashCode() method used for in Java?
Explain how we can achieve inheritance in Java? (Inheritance “is a”, Composition “has a”)?
What is method overloading?
What is method overriding?
Is multiple inheritance allowed in java?
How do you define and implement an interface?
Can you extend an interface?
Can a class extend multiple interfaces?
What is an abstract class?
When do you use an abstract class?
Compare abstract classes vs interfaces?
What is the use of this() ?
What is polymorphism in Java?
What is coupling in Java?
What is cohesion in Java?
What is encapsulation in Java?
What is an anonymous class?
What is an inner class?
What are the different access modifiers in Java?
What is use of a final modifier on a class?
What is use of a final modifier on a method?
What is use of a final modifier on a variable?
What is use of a final modifier on an argument?
What is a static variable?
Why should you always use blocks around if statements?
Why is exception handling important?
What design pattern is use to implement exception handling features in most languages?
What is the difference between an error and an exception?
How do you compare two arrays?
What is an enum?
How does garbage collection work in Java?
How do you serialize and object using the serializable interface?
What is the runnable interface in Java?
What is the iterable interface in Java?
What is the cloneable interface in Java?
What is the comparable interface in Java?
Why do we need collections in Java?
What are the most important interfaces in the Collection hierarchy?
How do you sort elements in an ArrayList using the Comparable interface?
How do you sort elements in an ArrayList using the Comparator interface?
What is the Vector class in Java? How is it different from ArrayList?
What is a LinkedList? What interfaces does it implement? How is it different from an ArrayList?
What is the difference between Set and SortedSet interfaces in Java?
What is a HashSet?
What is a LinkedHashSet and how is it different from a HashSet?
What is a TreeSet and how is it different from a HashSet?
What are some examples of implementations of NavigatableSet?
What is the Queue interface?
What is the Dequeue interface?
What is the PriorityQueue interface?
What are Java generics?
Why do we need generics?
How can we restrict generics?
Give an example of a generic method
What is functional programming?
What is a Java Stream?
What are terminal operations in Streams?
What is a predicate in Java?
What are method references in Java?
What are lambda expressions in Java? Give a code example
What is the functional interface and its function?
What is a consumer?

Design Patterns

Singleton
Prototype
Builder
Factory
Facade
Proxy
Iterator
Observer
Dependency Injection
Achieves inversion of control - where a container can determine the program behaviour, rather than the program determining the behaviour itself
Helps improve the modularity, maintainability and testability of software
  1. Constructor injection
  1. Method injection
  1. Property injection

Concurrency

Can you do part of a computation with a parallel stream and part with a sequential steam using the same stream object?
No you can’t. For example, the following would all be in parallel. You would have to collect first after the parallel part, then stream again to sort and then collect.
List<Integer> nums = Arrays.asList(3, 1, 4, 5, 9).parallelStream()
		.map(n -> n * 2)
		.sequential()
		.sorted()
		.collect(Collectors.toList())
What is concurrency vs parallelism?
Concurrency: Multiple tasks can run at the same time
Parallelism: Multiple tasks actually run at the same time
When is parallelism worth doing?
You are introducing a fork join pool, which introduces a significant amount of overhead.
You either needs lots of data or long processing per element.
N * Q > 10000
where:
N = number of elements
Q = time to compute one element
Data needs to be easy to partition. E.g. an Array is good, a linked list is not.
How can you tell which thread is currently doing a particular piece of computation
Using Thread.currentThread().getName()
What is atomicity?
What is a race condition?
What is deadlock?
What is load factor in an application?

Java specific concurrency

Why does CompletableFuture exist in Java?
You can create a future using:
Future<T> ExecutorService.submit(Callable<T> callable)
You have to call .get() , which is blocking, to retrieve the result.
It is difficult to coordinate multiple futures, because you need to wait on one future to complete before completing another and it eventually turns into blocking code.
For example, you could do the following with a regular future:
while(!future.isDone()) {
	System.out.println("I am waiting ... ")
}
but this can result in billions of calls to the future whilst waiting for it to be done.
But with CompletableFuture you can do:
CompletableFuture completableFuture;
completableFuture.complete(T value);
completableFuture.completeFuture(U value);
completableFuture.completeExceptionally(Throwable ex);
Give an example of a synchronous use of CompletableFuture?
public CompletableFuture<Product> getproduct(int id) { 
	try { 
		Product product getLocaI(id); 
		if (product null) { 
			return CompletableFuture.completedFuture(product); 
		}
		else { 
			CompletableFuture<Product> future = new CompletableFuture<>(); 
			Product p = getRemote(id); // Legacy, synchronous 
			cache.put(id, p); 
			future.complete(p); 
			return future; 
		}
	catch (Exception e) { 
		CompletableFuture<Product> future = new CompletableFuture<>(); 
		future.completeExceptionally(e); 
		return future;
	}
}
Why would you chose to implement the Runnable interface over extending the Thread class when doing multithreading?
Because Java only allows you to extend one class, with Runnable you can implement the interface yet still have your class extend another class. After you are finished implementing myRunnable you just have to do:
Thread myThread = new Thread(myRunnable);
Thread myThread2 = new Thread(myRunnable);
myThread.start();
myThread2.start(); // you now have two threads doing work at the same time :)
How to implement atomicity in Java?
How is the volatile keyword used in Java?
How to use synchronized in Java?
What is the difference between synchronized and concurrent collections in Java?
What is a lock and how is different from using synchronized?
How do you create a thread in Java?

Software design

What are SOLID principles?
  1. Single responsibility:
  1. Open-closed:
  1. Liskov-substition:
  1. Interface segregation:
  1. Dependency inversion:
What are the four main principles of object orientated programming?
  1. Encapsulation:
      • Encapsulation refers to the bundling of data (attributes) and methods (behaviors) that operate on the data within a single unit, known as an object.
      • The object's internal state (data) is hidden from the outside world, and access to it is controlled through public methods (getters and setters).
      • Encapsulation helps achieve data protection, as the internal representation of an object can be modified without affecting the external code that uses the object.
  1. Abstraction:
      • Abstraction involves simplifying complex reality by modeling classes based on the relevant characteristics or behaviors of objects.
      • It allows programmers to focus on the essential features of an object and ignore unnecessary details, leading to a more concise and manageable representation.
      • Abstract classes and interfaces are used to define common attributes and behaviors that subclasses can implement or extend.
  1. Inheritance:
      • Inheritance is a mechanism that allows a class (subclass) to inherit properties (attributes and methods) from another class (superclass).
      • Subclasses can reuse and extend the functionality of the superclass, promoting code reuse and hierarchical organization of classes.
      • It facilitates the "is-a" relationship, where a subclass is a specialized version of the superclass.
  1. Polymorphism:
      • Polymorphism allows objects to be treated as instances of their superclass or as instances of their own class, depending on the context.
      • It enables a single interface to represent different types of objects, providing flexibility and extensibility in code design.
      • Polymorphism is achieved through method overriding (dynamic polymorphism) and method overloading (static polymorphism).
What is the difference between inheritance and composition?
Inheritance typically is about extending a class or implementing an interface. It says A is a B
Composition is about a class being composed of other classes. It says A has a B
What are microservices?
What are the pros and cons of microservices?
What is a monolithic application?
What are the pros and cons of monolithic applications?
What is the difference between overriding and extending methods?

Angular

What is TypeScript?
What is Angular?
What is the difference between AngularJS and Angular?
What are the key components of Angular?
  1. Components
      2. ng new frontend
cd frontend
ng generate component hello-world
      <div>
	<h1>Hello, {{ name }}!</h1>
</div>
      hello-world.component.html
      import { Component } from "@angular/core";

@Component({
	selector: 'app-hello-world',
	templateUrl: './hello-world.component.html',
	styleUrls: ['./hello-world.component.css']
})

export class HelloWorldComponent {
	name = 'Angular user';
}
      hello-world.component.ts
      <app-hello-world></app-hello-world>
      src/app/app.component.html
  1. Modules
      2. ng generate module hello
      import { NgModule } from '@angular/core';
import { CommonModule } from '@angular/common';
import { HelloComponent } from './hello-component';

@NgModule({
	declarations: [HelloComponent],
	imports: [CommonModule]
})
export class HelloModule {}
      src/app/hello/hello.module.ts
      import { HelloModule } from './hello/hello.module';

@NgModule({
	declarations: [
		
	], 
	imports: [
		BrowserModule,
		HelloModule
	]
})
      src/app/app.module.ts
  1. Templates
  1. Services
  1. Metadata
What are directives?
What are components?
What is a template?
What is a module?
What is Angular CLI?
What is dependency injection in Angular?
What is metadata?
What is data binding?
What is the difference between constructor and ngOnInit?
What is a service?
What is RxJS?
What is HttpClient and it’s benefits?
What are pipes?
What is subscribing?
What is the difference in a promise and an observable
What is multicasting

Code Style

How many levels of code nesting should be maximum
max of three levels deep
int calculate(int bottom, int top) {
	if (top > bottom) {
		int sum = 0;

		for (int number = bottom; number <= top; number++) {
			sum += number;
		}

		return sum;
	}
	else {
		return 0;
	}
}
Compare this to four deep
int calculate(int bottom, int top) {
	if (top > bottom) {
		int sum = 0;

		for (int number = bottom; number <= top; number++) {
			if (number != 2) {
				sum += number;
			}
		}

		return sum;
	}
	else {
		return 0;
	}
}
 
What are methods for denesting code
  1. Extraction
      2. extract the 4th level of nesting to a helper function
      int filterEven(int number) {
	if (number % 2 == 0) {
		return number;
	}

	return 0;
}

int calculate(int bottom, int top) {
	if (top > bottom) {
		int sum = 0;

		for (int number = bottom; number <= top; number++) {
			if (number != 2) {
				sum += filterEven(number);
			}
		}

		return sum;
	}
	else {
		return 0;
	}
}
  1. Inversion
      2. Involves putting the unhappy paths first, happy paths second. This can hopefully help us remove some of the else blocks
      int filterEven(int number) {
	if (number % 2 == 0) {
		return number;
	}

	return 0;
}

int calculate(int bottom, int top) {
	// sad paths live at the top, you can stack them here
	if (top <= bottom) {
		return 0
	}

	// happy paths live at the bottom
	int sum = 0;

	for (int number = bottom; number <= top; number++) {
		if (number != 2) {
			sum += filterEven(number);
		}
	}

	return sum;
}
      void registerUser(String user) {
	// sad path 1
	String[] parts = user.split(":");

	if (parts.length != 2) {
		throw new IllegalArgumentException("Invalid user sstring :" + user);
	}
	
	// sad path 2
	int userId = Integer.parseInt(parts[0]);
	
	if (userId < 0) {
		throw new IllegalArgumentException("Invalid user id: " + userId);
	}
	
	// happy path
	String userName = parts[1];
	if (users.containsKey(userId)) {
		users.get(userId).setName(userName);
	}
	else {
		users.put(userId, new User(userName));
	}
}
What are some naming conventions to avoid at all costs?
  1. Never abbreviate - don’t use single letters, or don’t abbreviate words
    1. Makes it a lot easier to understand code with no context required
  1. Don’t put types in your names
    1. the types themselves document this without needing to put it in the variable name
  1. Put units in variable names unless the type tells you
      2. e.g. void execute(int delaySeconds) is better than void execute(int delay)
  1. Don’t put types in your types
    1. don’t prefix an int with i, or an interface with I
    2. Don’t use base or abstract in your names (e.g. AbstractX, BaseX)
  1. Refactor if you find yourself naming code “Utils”
What is an early return?
When a certain condition is met (say data == null), we don’t want to walk through all the other steps, we just want to do an early return. It can reduce nesting, make code more readings, and lead better validation checks
Early Return Approach:
def factorial_early_return(n):
	if n < 0:
	  return None  # Return None for negative inputs
	if n == 0:
	  return 1  # Factorial of 0 is 1
	result = 1
	for i in range(1, n + 1):
	  result *= i
	return result
In this early return approach, we check for negative input and return None early. If n is 0, we return 1 early. Otherwise, we calculate the factorial in a straightforward loop.
Heavily Nested and Complex Alternative:
def factorial_complex(n):
  if n < 0:
    return None
  else:
    if n == 0:
      return 1
    else:
      result = 1
      for i in range(1, n + 1):
        result *= i
    return result
In the heavily nested and complex alternative, we don’t use early returns, and the code becomes more nested and less readable. It includes unnecessary else blocks, which can make the code harder to follow as the logic becomes more complex.

Code Security

What are some of the ways we can make our code more secure?
Using strength in depth, increasing the number of security layers, a cyber attacker’s chance of success is decreased
  1. Encrypted sensitive data when being stored in a database
  1. The application has extensive input validation
  1. Servers are patched with the latest security updates
  1. The internal network is segregated into difference zones protected by firewall rules
  1. A firewall separates the internal perimeter from the internet
Let’s take for example a SQL injection attack
  1. Client side validation on the website form the user is using
  1. At the server side, input is filtered and validated for the user
  1. The database connection user is setup securely, uses least amount of permissions needed to perform its operations
    1. Attacker may not have the privileges to delete or modify data even if successful at first layers
  1. The database is queried using parameterised queries
    1. This helps separate user input from the query itself
Going through the application layers, what are the ways we can prevent vulnerabilities at each layer?
  • Data layer: Access controls, Encryption, Backup and restore procedures
  • Application layer: Authentication, Authorisation, Auditing (AAA). Secure coding and hardening
  • Host layer: Hardening, Authentication, Patch Management, Antivirus
  • Internal network: Network segmentation, IPsec (Internet Protocol Security - a secure network protocol suite that authenticates and encrypts packets of data), TLS (Transport layer security), NAT
  • Perimeter layer: Firewalls, Denial of Service
  • Physical layer: Guards, locks, badging systems
What is insufficient validation?
Input parameters that are insufficiently validated can occur when any function requires external input to complete
It can lead to attackers:
  • gaining access to restricted information
  • bypassing security restrictions
  • crashing applications
When attacked, applications may throw exceptions, or throw unexpected errors e.g. when someone puts in a negative value in a banking application
Developers should:
  • consider all potential areas where inputs can be entered
  • assume all input is malicious when building the software
  • ensure security checks performed on the client side are replicated on the server side
  • convert inputs into the appropriate expected data type
Copyright 2023 Stewart Young