CS101 Flashcards
define log,N
k in the expression 2^k = N
ex
2^4 = 16 -> log_2_,16 = 4
log_2_N = k -> 2^k = N
Big O - O(logN)
+ a problem where the number of elements gets halved each time
+ like binary search
define declarative programming
declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Big 0 of recursive function with multiple recursive calls
int f ( int n ){
if ( n<= 1 ) { return 1; }
return f(n-1) + f(n-1);
}
O(2^n)
Permutations cardinality
factorial
ex: “abcd” permutations have cardinality of 4! = 432*1
ex: Different ways we can give olympic medals to 8 athletes?
+ 8 different athletes can get gold, then 7 remaining can get silver, then 6 remaining can get bronze
+ 876 = 336
Print permutations recursively with backtracking
public void testPerms() {
String s = “abc”;
permute(s.toCharArray(), 0, s.length() - 1);
}
private void permute(char[] arr, int left, int right) {
if (left == right) {
System.out.println(String.valueOf(arr));
} else {
for (int i = left; i <= right; i++) {
swap(arr, left, i);
permute(arr, left + 1, right);
swap(arr, left, i);
}
}
}
private void swap(char[] arr, int left, int right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
+ O(nn!) runtime
+ we call permute n times in the first call, then n-1 times in the first level of recursion, then n-2 … so nn-1*n-2..1 which is n!
+ then the printing of the string happens once for each permutation so n * n!. ??? I don’t believe!!!
Formula for calculating big-0 runtime of functions with recursive calls
O(branches^n)
ex: fibonacci -> 1,1,2,3,5,8… has 2 branches per level so O(2^n)
int fib(n){
assert n >= 0;
if( n < 2 ) return 1;
return fib(n-2) + fib(n-1);
}
java shift operator
int twoToTheZero = 1;
int twoToTheThird = twoToTheZero «_space;3;
-2^-3
-2^-3
= 1/-2 * 1/-2 * 1/-2
= -1/8
O(sqrt(n)) vs O(log,n)
for large n, O(sqrt(n)) is much larger than O(log,n)
O(sqrt(n)) example algorithm
func(a){
for( int i = 0; i * i < a ; i ++ ){
print("im i^2 " + i*i)
}
}2^7
128
2^8
256
2^10
1024 Bytes = 1KB
2^16
65,536 Bytes = 64KB
2^20
1,048,576 Bytes = 1MB
approx 1 million
2^30
1,073,741,824 Bytes = 1GB
approx 1 billion
2^32
4,294,967,296 Bytes = 4GB
approx 4 billion
2^40
1,099,511,627,776 Bytes = 1TB
approx 1 trillion
java signed int max and min
max
+ (2^31)-1
+ 2,147,483,647
+ approx 2 billion
min
+ -(2^31)
+ -2,147,483,648
+ approx negative 2 billion
6 optimize and solve techniques
1) remove duplicate work
2) DIY - try to solve an example and see how you naturally did it
3) simplify and generalize
4) base case and build
5) data structure brainstorm
6) work towards the best conceivable runtime
algorithm for printing the matching elements in two arrays
go through first array and place each element into a hashtable
go through second array and lookup each element
O(N+M)
if they’re the same size O(2N) aka O(N)
int stringToInt(String str, int base)
ex:
stringToInt(“11”,2) returns 3
private static int stringToInt(String str, int base) {
//TODO check nulls empties base is 2 to 16
int ret = 0;
int exp = 0;
for (int i = str.length() - 1; i >= 0; i--) {
int digit = charToVal(str.charAt(i));
//TODO check digit range
ret += digit * Math.pow(base, exp++);
}
return ret;
}
mergesort implementation
private void mergeSort(int[] list) {
//TODO error check input
if (list.length <= 1) {
return;
}
int[] left = new int[list.length / 2];
int[] right = new int[list.length - left.length];
System.arraycopy(list, 0, left, 0, left.length);
System.arraycopy(list, left.length, right, 0, right.length);
mergeSort(left);
mergeSort(right);
merge(list, left, right);
}
private void merge(int[] list, int [] left, int [] right){
int iLeft = 0, iRight = 0, iTarget = 0;
while (iLeft < left.length && iRight < right.length) {
if (left[iLeft] < right[iRight]) {
list[iTarget++] = left[iLeft++];
} else {
list[iTarget++] = right[iRight++];
}
}
System.arraycopy(left, iLeft, list, iTarget, (left.length - iLeft));
System.arraycopy(right, iRight, list, iTarget, (right.length - iRight));
}
Heap stored as an array
define methods to determine index of relative nodes
root(), parent(i), left(i), right(i)
root() { return 0; }
parent(i) { return (int) Math.floor(((double)i - 1) / 2); }
left(i) { return ( i * 2 ) + 1; }
right(i) { return ( i * 2 ) + 2; }
Min Heap usage
only used to keep track of a min
note: datastructures that need to keep track of midpoints or medians can maintain an min and max heap
Min Heap sort add
place new number in bottom right of tree and switch with parent as long as parent is less than new node
Min Heap sort remove
+ pop off root
+ place last node at root
+ swap with the lower value child if either child is less than last node
HashTable worst case and common case lookup
worst case O(N)
+ worst case it turns into an unsorted list
common case O(1)
+ compute hash code, index = hash % bucketcount , search for actual item in the bucket
big-O for:
n/2 + n/8 + n/16 + n/32 + … + 2 + 1
O(n)
ex: n = 32 expands would be 16+8+4+2+1 which is limited at n
big-O for:
1 + 2 + 3 + 4 + … + n
O(n^2)
1 + 2 + 3 + … + n = n * ( n + 1 ) / 2
drop the constant 1/2 and you get n^2
java char size
2 bytes
2^16 or over 65,000 distinct values
unicode
japanese and chinese require more chars so optionally multiple 2-byte sequences represent a single chinese char. UTF-8, UTF-16.
java byte size
8 bit two’s compliment signed integer
inclusive range -(2^15) to (2^15)-1
-32768 to 32767
java short size
16 bit two’s complement signed integer
inclusive range from -(2^7) to (2^7)-1
-128 to 127
java 7 bitwise operators
AND (&)
OR (|)
Ex-OR (^)
left shift (<>)
unsigned right shift (»>)
bitwise complement (~)
java standard method to copy array
arraycopy(char [] src, int srcPos, char [] dest, int destPos, int length)
code to use a fastrunner to detect a loop in a linked list
walk = head
run = head
while( run != null && run.next != null ){
walk = walk.next
run = run.next.next
if ( run == walk ) { break; }
}
if( run == null ) {
// no loop in list
}
Describe stack ordering and list methods
Stack ordering Last In First Out
methods: push(item), pop(), peek(), isEmpty()
Describe queue ordering and list methods
Queue ordering First In First Out
methods: add(item), remove(), peek(), isEmpty()
Reverse linked list iteratively
public Node reverseIterative(Node head) {
if (head == null || head.next == null) {
return head; // empty or 1 elem. nothing to do
}
Node leader = head.next;
Node follower = head;
follower.next = null;
while (leader != null && follower != null) {
Node scout = leader.next;
leader.next = follower;
follower = leader;
leader = scout;
}
return follower;
}
Reverse linked list recursively
Node reverse(Node head) {
if (head == null || head.next == null) {
return head; // new reversed list head
}
Node scout = head.next;
head.next = null; // tail node must point to null
Node result = reverse(scout);
scout.next = head;
return result;
}
depth first search
void dfs(Node root) {
if (root == null) {
return;
}
root.visit();
root.visited = true;
for (Node child : root.children) {
if (child.visited == false) {
dfs(child);
}
}
}breadth first search
public void breadthFirstSearch(Node root) {
assert root != null;
List queue = new ArrayList<>(); //FIFO
root. visited = true;
queue. add(root);
while (!queue.isEmpty()) {
Node n = queue.remove(0);
n.visit();
for (Node child : n.children) {
if (child.visited == false) {
child.visited = true;
queue.add(child);
}
}//for
}//while
}
is there an incomplete level in a binary tree - iterative
//return true if there are no incomplete levels above the last level
public static boolean checkBalanceLoose(Node root) {
assert root != null;
int nodeCount = 0;
int level = 1;
List currentLevel = new ArrayList<>();
currentLevel.add(root);
while (currentLevel.isEmpty() == false) {
List nextLevel = new ArrayList<>();
for (Node n : currentLevel) {
if (n.left != null) {
nextLevel.add(n.left);
}
if (n.right != null) {
nextLevel.add(n.right);
}
nodeCount++;
if (nodeCount <= (Math.pow(2, level - 1) - 1)) {
return false;
}
}
level++;
currentLevel = nextLevel;
}
return true;
}
Binary tree - check if the height of any subtree differs by more than 1
NlogN solution
private int maxDepth(Node root) {
if (root == null) {
return -1;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// True if heights of any node's subtrees
// never differ by more than 1.
// NlogN because each node is visited once for
// every node above it
public boolean checkBalanceLoose(Node root) {
if( root == null ){
return true;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
if( Math.abs(leftDepth-rightDepth) > 1 ) {
return false;
}
return checkBalanceLoose(root.left) &&
checkBalanceLoose(root.right);
}
Binary tree - check if the height of any subtree differs by more than 1
O(n) solution
private int maxDepth(Node root) throws UnbalancedException{
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
if( Math.abs(leftDepth - rightDepth) > 1 ){
throw new UnbalancedException();
}
return Math.max(leftDepth,rightDepth) + 1; }
// True if hieghts of any node's subtrees
// never differ by more than 1.
// O(n) time because each node visited once
public boolean checkBalanceLoose(Node root) {
boolean balanced = true;
try{
maxDepth(root);
}catch(UnbalancedException e){
balanced = false;
}
return balanced;
}
Transactions define ACID
Transactions are atomic, consistent, isolated, and durable (ACID) modules of execution.
Describe Isolation levels
Transactions specify an isolation level.
The isolation level defines the degree to which one transaction must be isolated from modifications made by other transactions.
Isolation levels are described in terms of which concurrency side effects, such as dirty reads or phantom reads, are allowed.
Isolation levels - serializable
The highest isolation level, serializable, guarantees that a transaction will retrieve exactly the same data every time it repeats a read operation, but it does this by performing a level of locking that is likely to impact other users in multi-user systems.
Isolation levels - read uncommitted
The lowest isolation level, read uncommitted, can retrieve data that has been modified but not committed by other transactions. All concurrency side effects can happen in read uncommitted, but there is no read locking or versioning, so overhead is minimized.
Isolation Level Read Uncommitted - Side effects allowed by
Dirty Reads, Non-Repeatable Reads, Phantom Reads
Isolation Level Read Committed - Side effects allowed
Non-Repeatable Reads, Phantom Reads
Isolation Level Repeatable read - Side effects allowed
Phantom Reads
Isolation Level Serializable - Side effects allowed
No side effects allowed
Describe Phantom Reads
Transaction A reads a range of data.
Transaction B inserts into the same range of data and commits.
Transaction A reads the same range and now has more results.
Describe Non-Repeatable Reads
Transaction A reads a column from a row.
Transaction B updates and commits a column in that row.
Transaction A reads same column from same row again and gets a new value as updated by Transaction B.
Describe Dirty Reads
Dirty reads are just like Non-Repeatable reads except you don’t even need to commit the changed data for the corrupt data to be read.
Transaction A reads a column from a row.
Transaction B updates the same column from the same row. Transaction B does not commit.
Transaction A reads the updated uncommitted data from Transaction B.
Transaction B rolls back. Making a liar out of Transaction A’s second read.
Microservices
Stateless
Organized around business purpose, not software implementation or layers
Datastore is not shared
Print topological order of directed unconnected graph
//return true if there is a cycle
//print topological order
public boolean dfsCycle(DirectedGraph graph) {
List complete = new ArrayList<>();
boolean isCycle = _dfsCycle(graph.nodes.values(), new ArrayList(), complete);
complete.stream().forEach(n -> {
System.out.println(n.data);
});
return isCycle;
}
private boolean _dfsCycle(Collection nodes, List visiting, List complete) {
for (Node n : nodes) {
if (visiting.contains(n)) {
return true; //cycle exists
}
if (complete.contains(n)) {
continue;
}
visiting.add(n);
if (_dfsCycle(n.adjacent, visiting, complete)) {
return true; // cycle exists
}
visiting.remove(n);
complete.add(0, n); // topological sort every node comes before it's outgoing edges
}
return false; // no cycle
}
Formula for combination. Pick 3 team members out of a pool of 5.
Formulat for permutations. Pick a winner, place, and show out of 5 race horses.
combination = Pool ! / Team! (Pool - Team)!
permutations = Field! / (Field - Podium)!
print permutations without backtracking
permutations(“”, “abc”)
void permutation(String prefix, String word) {
if (word.isEmpty()) {
System.err.println(prefix);
} else {
for (int i = 0; i < word.length(); i++) {
String newPref = prefix + word.charAt(i);
String remainder = word.substring(0, i)
\+ word.substring(i + 1);
permutation(newPref, remainder);
}
}
}
bitwise operations - check if n’th bit of number is set
// check if bit x of num is set. first bit is 0
boolean isSet(int num, int bit){
int mask = 1 << bit;
return (num & mask ) != 0;
}bitwise operation - set n-th bit of integer
// set n-th bit of integer. first bit is 0
int setBit(int num, short bit){
return num | ( 1 << bit );
}bitwise operation - clear n-th bit of integer
// clear n-th bit of integer. first bit is 0
int clearBit(int num, int bit) {
int mask = ~(1 << bit);
return num & mask;
}bitwise operation - clear most significant bits
// clear most significant bits through i. first i is zero.
// i = 0 clears all bits
int clearMostSigBits(int num, int i) {
int mask = 1 << i;
mask = mask - 1; // ex: 0000 -> 1111, 0100 -> 0011
return num & mask;
}bitwise operation - clear least significant bits
// clear least significant bits. 0 clears first bit
int clearLeastSigBits(int num, int i) {
int mask = -1 << (i + 1);
return num & mask;
}bitwise operation - make a mask over a range i..j in the middle of a bitfield
1) int leftMask = -1 << ( i + 1 ) \+ now the left is all 1's up to i \+ 11110000 2) int rightMask = ( 1 << j ) - 1 \+ now the right is all 1's up to j \+ 00000011 3) int fullMask = leftMask | rightMask \+ 11110011
bitwise operation - clear the least significant 1
n &= (n - 1)
n = 1001000 n-1 = 1000111 &= 1000000
Find the path to a node in an unsorted binary tree
private boolean findPath(List path, Node root, int target) {
if (root == null) {
return false;
}
path.add(root);
if (root.data == target) {
return true;
}
if (root.left != null && findPath(path, root.left, target)) {
return true;
}
if (root.right != null && findPath(path, root.right, target)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
sum of fibonacci numbers
f1 + f2 + f3 + … + fn =?
f1 + f2 + f3 + … fn = f(n+2) -1
two ahead in the sequence minus 1
code to sum fib numbers up to but not including n.
Assert.assertEquals(0, sumFib(0));
Assert.assertEquals(0, sumFib(1));
Assert.assertEquals(1, sumFib(2));
Assert.assertEquals(2, sumFib(3));
Assert.assertEquals(7, sumFib(5));
public int sumFib(int last) {
if( last < 2 ){
return 0;
}
int sum = 1;
int prev = 0;
int cur = 1;
for (int i = 2; i < last; i++) {
int nxt = cur + prev;
sum += nxt;
prev = cur;
cur = nxt;
}
return sum; }
java int to string
public String intToString(int num) {
// todo if negative then prepend a '-' and mult by -1
StringBuilder sb = new StringBuilder();
while (num > 0) {
sb.append(num % 10);
num /= 10;
}
StringBuilder sbReturn = new StringBuilder();
for (int i = sb.toString().length() - 1; i >= 0; i--) {
sbReturn.append(sb.charAt(i));
}
return sbReturn.toString(); }
java the decimal part of double to string
private String decimalPlacesToString(double dbl) {
StringBuilder sb = new StringBuilder();
int intpart = (int) dbl;
double decpart = dbl - intpart;
if (decpart > 0) {
sb.append(".");
}
while (decpart > 0) {
decpart *= 10;
sb.append((int) decpart);
decpart -= (int) decpart;
}
return sb.toString(); }
