f(n) = O(g(n))
g(n)
is the asymptotic upper bound off(n)
.
f(n) = Θ(g(n))
g(n)
is the asymptotic tight bound off(n)
.
f(n) = Ω(g(n))
g(n)
is the asymptotic lower bound off(n)
.
O(1)
: ConstantO(log n)
: LogarithmicO(n)
: LinearO(n log n)
: LoglinearO(n^2)
: QuadraticO(n^c)
: PolynomialO(c^n)
: ExponentialO(n!)
: Factorial
&
: AND|
: OR^
: XOR~
: NOT<<
: Binary Left Shift>>
: Binary Right Shift>>>
: Zero Fill Right Shift
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
- Computers typically store integers in two's complement representation.
- Range of unsigned numbers that can be stored with
N
bits is0
-+(2^N - 1)
. - Range of signed numbers that can be stored with
N
bits in two's complement representation is-(2^(N - 1))
-+(2^(N - 1) - 1)
. - Binary representation of
-K
isconcat(1, bin(2^(N - 1) - K))
.
- In an arithmetic right shift (
>>
), the bits are shifted and the sign bit is put in the MSB. - In a logical right shift (
>>>
), the bits are shifted and a0
is put in the MSB.
boolean getBit(int num, int i) {
return ((num & (1 << i)) != 0);
}
int setBit(int num, int i) {
return num | (1 << i);
}
int clearBit(int num, int i) {
int mask = ~(1 << i);
return num & mask;
}
int clearBitsMSBThroughI(int num, int i) {
int mask = (1 << i) - 1;
return num & mask;
}
int clearBitsIThrough0(int num, int i) {
int mask = (-1 << (i + 1));
return num & mask;
}
int toggleBit(int num, int i) {
return num ^= (1 << i);
}
int updateBit(int num, int i, boolean setBit) {
int value = setBit ? 1 : 0;
int mask = ~(1 << i);
return (num & mask) | (value << i);
}
num = num << n; // multiply
num = num >> n; // divide
- Big Endian stores the MSB in the smallest address.
- Little Endian stores the LSB in the smallest address.
- The stack is used for static memory allocation while the heap is used for dynamic memory allocation.
- Variables allocated on the stack have their memory allocated at compile time and access is very fast.
- Variables allocated on the heap have their memory allocated at runtime and accessing this memory is slightly slower.
- A process is an instance of a program in execution. It is an independent entity to which system resources are allocated. Each process executes in a separate address space and one process cannot access the data of another process. However, inter-process communication is possible using pipes, files, sockets etc.
- A thread is a particular execution path of a process. It exists within a process and shares the process' resources. Multiple threads within the same process will share the same heap space but each thread still has its own registers and its own stack.
- A mutex is like a lock. Mutexes are used in parallel programming to ensure that only one thread can access a shared resource at a time.
- Semaphores are more general than mutexes. They differ only in that a semaphore's integer may start at a number greater than 1. The number at which a semaphore starts is the number of threads that may access the resource at once.
A deadlock is a situation where a thread is waiting for a resource that another thread holds, while the second thread is waiting for the resource held by the first thread (or an equivalent situation with several threads). Since each thread is waiting for the other to unlock the resource, both threads remain waiting forever.
- Mutual Exclusion: Only one process can access a resource at a given time (or there are limited number of the same resource).
- Hold and Wait: Processes already holding a resource can request additional resources without releasing their current resources.
- No Preemption: One process cannot forcibly remove another process' resource.
- Circular Wait: Two or more processes form a circular chain where each process is waiting on another resource in the chain.
Deadlocks can be prevented by removing any one of the four conditions above. However, most deadlock prevention algorithms focus on avoiding circular wait.
- Long-Term Scheduler: Determines which programs are admitted into the system for processing. It selects processes from the queue and loads them into memory for execution.
- Short-Term Scheduler: Selects a process among the processes that are ready to execute and allocates the CPU to one of them. Its main objective is to increase system performance according to certain criteria.
- Medium-Term Scheduler: Responsible for removing processes from memory in case of long waits (for eg. I/O wait). The suspended process is moved to secondary storage and swapped for another process in the queue. Once the wait is over, the suspended process is swapped back in for continued execution.
The Observer pattern involves having observers register for changes to subjects. Whenever the subject changes, each of the registered observers is notified as opposed to the observers continuously polling the subject's state.
public class Subject {
private List<Observer> observers = new ArrayList<>();
private int state;
public int getState() { return state; }
public void setState(int state) {
this.state = state;
notifyAllObservers();
}
public void attach(Observer observer) {
observers.add(observer);
}
public void notifyAllObservers() {
for (Observer observer : observers) {
observer.update();
}
}
}
public abstract class Observer {
protected Subject subject;
public abstract void update();
}
public class BinaryObserver extends Observer {
public BinaryObserver(Subject subject) {
this.subject = subject;
this.subject.attach(this);
}
@Override
public void update() {
System.out.println("Binary String: " + Integer.toBinaryString(subject.getState()));
}
}
public class HexaObserver extends Observer {
public HexaObserver(Subject subject) {
this.subject = subject;
this.subject.attach(this);
}
@Override
public void update() {
System.out.println("Hex String: " + Integer.toHexString(subject.getState()).toUpperCase());
}
}
The Singleton pattern ensures that a class has only one instance and ensures access to that instance through the application. It can be useful when you need a global object with exactly one instance.
public class Singleton {
private static Singleton _instance = null;
protected Singleton() { ... }
public static Singleton getInstance() {
if (_instance == null) {
_instance = new Singleton();
}
return _instance;
}
}
The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate. The Factory method can also be implemented with a parameter representing which class to instantiate.
public class CardGameFactory {
public static CardGame createCardGame(String type) {
if (type.equalsIgnoreCase("POKER")) {
return new PokerGame();
} else if (type.equalsIgnoreCase("BLACKJACK")) {
return new BlackJackGame();
}
return null;
}
}
Model‐view‐controller (MVC) is a design pattern commonly used in user interfaces. The goal is to keep the "data" separate from the user interface. Essentially, a program that uses MVC uses separate programming entities to store the data (the "model"), display the data (the "view") and modify the data (the "controller"). In MVC, the view usually makes heavy use of listeners to listen to changes and events in the model.