-
YOU ARE FORGETTING TO INCREMENT INDEXES in
while, DRUNK OR SOMETHING JODER!!?? -
ALWAYS THINK ABOUT STACK SPACE!!
-
C'est PAS Scala -- MUST RETURN!!
returnstatement- NO CASE CLASSES! --> Use a constructor!! --
newobject!
-
ALARM BELLS-->
- Every problem has some hint on the data structure, if it has something to do with efficient max/min --> heaps, divide and conquer --> Trees, in place --> quickSort
- Use LONGS to calcualte sum of Integers!
-
Think about DP -- storing solutions!!
-
Use inbuilt functions, UNLESS explicity told to not do so..
-
Put corner case as //TODO at the top- Assert test cases yourself, write assertions
- Use CONSTANTS.
-
Walk through code, not your algo! (Once coded)
- ZINK of corner cases -- Like for Binary search square root, when
x * x == x
- ZINK of corner cases -- Like for Binary search square root, when
-
Mark braces, such as // main beg, //main fin, //func beg etc.
-
Write util methods!!
-
ALWAYS put space over time.
-
Use if-else wisely, rather than lazy if's only.
-
Use Lombok's @getter @setter for POJO
-
Use objects if you have a pointer type requirement, eg. storing the max in a recursive call.
https://www.youtube.com/watch?v=U7Aqf7tMOhY
-
NULL Checks!! -->
head.next != null, should check ifhead != null!!! -
For String, ALWAYS use
.equals, AND NOT==!!!! -
Always do
low + (high-low)/2; instead ofhigh+low/2. -
ALWAYS check the boolean order.. the expression to the left is evaluated first
-
Remember triplebyte?! Binary tree is NOT necessarily balanced!
For long, initialize like Long l = 0L;
To check if an object is an instance of another class, example"
if (value instanceof String)
You can initialize a generic object map, be careful with typecasting!
HashMap<String, Object> map = new HashMap<String, Object>();
//TypeCasting here:
HashMap<String, Object> secondLevelMap = (HashMap<String, Object>) map.get(key);
String strValue = (String) map.get(key)
ACHTUNG! Be sure to add the warning for typecasting!
@SuppressWarnings("unchecked")
- Always override the hashcode implementation of a class if you override the equals method.
Random r = new Random();
int Low = 10;
int High = 100;
int Result = r.nextInt(High-Low) + Low;
- Math.min(a,b) to find the minimum of a and b.
Can combine cases like this:
case '*':
case '/':
return 2;
https://www.geeksforgeeks.org/convert-base-decimal-vice-versa/
- Remember the fractions!!! https://www.geeksforgeeks.org/convert-decimal-fraction-binary-number/
https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit
https://www.youtube.com/watch?v=NLKQEOgBAnw
-
x & ~(x-1) -- What does it do, remember
-
Arithmetic vs Logical Shift https://stackoverflow.com/questions/2811319/difference-between-and
Xor of a with a is zero. So if you have an array like [a,a,b,c,c], XOR-ing all elements will give you be. XOR is associative and commutative.
Negative numbers are represented using a 2's complement form. To obtain the 2's complement of a number:
- Complement the bits
- Add one to the result
== has higher priority than &. You might want to wrap your operations in () to specify your own priority.
For getting is a bit is set or not, check !=0 instead of >0 (because of negative numbers!!)
public boolean isOne(int n, int index) {
int mask = 1 << index;
return ((n & mask) != 0);
}
interface Merger<T extends Comparable<T>> {
static void main(String[] args) {
Merger<Integer> merger = new MergerImpl<Integer>();
List<Integer> merged = merger.mergeLists(
Arrays.asList(1, 3, 5),
Arrays.asList(2, 4, 6)
);
System.out.println(merged);
}
List<T> mergeLists(List<T> l1, List<T> l2);
}
class MergerImpl<T extends Comparable<T>> implements Merger<T> {
@Override
public List<T> mergeLists(List<T> l1, List<T> l2) {
List<T> list = new ArrayList<T>();
return list;
}
}
ACHTUNG! You can ONLY use object types with Collections, no primitive types
So, new HashMap<int, char> is wrong, it must be new HashMap<Integer, Character>
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
if (test != null && !test.isEmpty()) {
// ...
}
Collections.removeAll(), Collections.retainAll(), Collections.sort(), Collections.reverse()
list.size(), map.size()
Implementation-Remember!! How do you get the index of the bucket?
- Consistent Hashing?! https://www.youtube.com/watch?v=jznJKL0CrxM
-- Remember the W+R>P rule, for consistent hashing.
- Always override the hashcode implementation of a class if you override the equals method.
https://www.youtube.com/watch?v=IwUwIrz9Ge8
- Contains method
(hashMap.containsKey(target-nums[i]))
- Add a key
map.put(key, map.get(key) + 1);
- Get the value for a key
map.get(key)
- Iterate over a keyset
for (String key : map.keySet()) {
// ...
}
- Remove a key
map.remove(key)
Comparable example
class Dog implements Comparable<Dog> {
Integer age;
String name;
Dog(Integer age, String name) {
this.age = age;
this.name = name;
}
@Override
public int compareTo(Dog d1) {
return this.age.compareTo(d1.age);
}
}
Comparator example
Comparator<Dog> dogComparator = new Comparator<Dog> () {
public int compare(Dog d1, Dog d2) {
return (d1.age - d2.age);
}
};
- For primitive types
compareTo method
System.out.println("abcd".compareTo("abc"));
- HashSet DOES NOT MAINTAIN ORDER!!
- Remember you cannot get a random element, first convert to list and get(0)
List<String> list = new ArrayList<String>(listOfTopicAuthors);
- Convert an array to a set like this:
Set<T> mySet = new HashSet<T>(Arrays.asList(someArray));
- IMPORTANT!
TreeSet uses comparator to order stuff, HashSet uses equals method. For a specific object, you must define your own hashcode and equals method (can't do one without the other!, remember the contract). Easy way to define a hashcode (remember the wealthfront interview!)
// Just use the inbuilt hashcode()!!!!
@Override
public int hashCode() {
return left.hashCode() ^ right.hashCode();
}
Equals method signature and implementation
@Override
public boolean equals(Object pair1) {
Pair<A,B> myObj = (Pair<A,B>) pair1;
return (this.left.equals(myObj.left) && this.right.equals(myObj.right));
}
Defining a treeSet with comparator (See the comparator class syntax!)
class MySalaryComp implements Comparator<Empl>{
@Override
public int compare(Empl e1, Empl e2) {
if(e1.getSalary() > e2.getSalary()){
return 1;
} else {
return -1;
}
}
}
TreeSet<Empl> salComp = new TreeSet<Empl>(new MySalaryComp());
A new result for every path!! -- When you are returning a List<List<Integer>> remember to create a new list!!
https://www.youtube.com/watch?v=wGbuCyNpxIg has great backtracking explanations.
- Remember why you must UNSET in case of failure.
THIS STOPS NOW! (Remember Atlassian Interview, Duolingo round one)- DO NOT INITIALIZE char with double quotes! STOP IT!
Note that strings are immutable in java, to change, for example to swap characters; conver to charArray[], AB DUBARA MAT BHOOLNA!
ALWAYS USE StringBuilder to append, or put a TODO to come back to it.
Arrays.sort(charArray)is IN PLACE JODER!!
Nice video on Strings: https://www.youtube.com/watch?v=6pLEwJP1Afk
- Remember the use of the keyword intern
- Remember why strings NEED to be immutable
- How do you compare two strings for equal values? IMPORTANT!
- Java 7 substring method memory leak!
- StringBuilder vs '+'; and optimization in Java7
https://www.youtube.com/watch?v=MiqoA-yF-0M
- REPLACE: Convert ab to de, then replace c with f. (abc --> dec --> def)
- INSERTION: Convert abc to de, then insert f at the end. (abc --> de --> +f --> def)
- DELETION: Convert abc to defc, then delete c at the end. (abc --> defc --> -c --> def)
Now come up with the code/algo HDP! Always draw the matrix, and put the empty string as reference at (0,0)
Important- the number of changes for s1[0..i] and s2[0..j] is stored at E[i+1][j+1]. (More on the empty string point above
https://leetcode.com/problems/minimum-window-substring/
Careful of the negative numbers' mod!
- Get character at index
s.charAt(index)
- Get length Note that this is a function length() as opposed to a property (as in case of arrays)
str.length()
- StringBuilder
StringBuilder sb = new StringBuilder();
sb.append("a).append("b");
return (sb.toString());
- Clearing a string!
stringBuilderObj.setLength(0)
- Prepending using StringBuilder sb.insert(0, "prependStuff");
- GOTCHA!
public String substring(int beginIndex,
int endIndex)
Returns a new string that is a substring of this string. The substring begins at the specified beginIndex and extends to the character at index endIndex - 1. Thus the length of the substring is endIndex-beginIndex.
Time complexity for appending
http://www.pellegrino.link/2015/08/22/string-concatenation-with-java-8.html
- Split string by delimiter and convert to the numbers
The delimiter string is a regex expression, and you need to escape in case of special chars. (Think Atlassian interview)
Eg.: plusDelimiter
String expression = "1+2+10+1";
String[] tokens = expression.split(" \\+");
Similary multiplication will be split(" \*"); ( Double backward slash)
Eg.:
for (String s: line.split(",")) {
numbersArray[i][j] = Integer.parseInt(s);
i++;
}
-
Character.isDigit() returns true/false depending on whether the input is a char representing a digit.
-
To find if it is a letter or a digit : https://www.tutorialspoint.com/java/lang/character_isletterordigit.htm
-
forDigit
public static char forDigit(int digit, int radix)
- Convert an int to char
public char intToChar(int i) {
return (char) (i + '0');
}
List<Integer> myQueue = new ArrayList<Integer>();
Add at a particular position, remove from a particular position (useful when you use it to implement Stacks, Queues)
list.add(int index, E element)
remove(int index)
- Create a list from an array
List<String> abc = new ArrayList<String>(Arrays.asList(arrString));
- Convert List to Array -- ACHTUNG, DONT work for primitive types!!
String[] stockArr = new String[stockList.size()];
stockArr = stockList.toArray(stockArr);
String [] countries = list.toArray(new String[list.size()]);
- Iterator
Iterator itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
Can ALSO iterate like this HDP!
for(String value : array)
{
System.out.println(value);
}
- The size of an array cannot be larger than Integer.MAX_VALUE (exact value depends on the compiler)
int[] 1DArray = new int[SIZE];
int[] 2DArray = new int[SIZE1][SIZE2];
// With specific data
int[] data;
data = new int[] {10,20,30,40,50,60,71,80,90,91};
// 2D array
int screen[][] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
Pro Tip: Always Use row and col with 2d Arrays for indexing, instead of x and y, YOU WILL THANK ME LATER
- Get length
array.length
-
Fill Arrays
Arrays.fill() -
Clone/Copy an array
int[] b = a.clone(); - Gets a totally different instance
- ALWAYS check if head is not null
- Problems -- cycle detection and reverse a sublist!
- https://leetcode.com/problems/linked-list-cycle-ii/solution/ -- Remember the diagram!!
Three questions to ask: best approach here: https://stackoverflow.com/questions/354875/reversing-a-linked-list-in-java-recursively
-
What is the reverse of null (the empty list)? null.
-
What is the reverse of a one element list? the element.
-
What is the reverse of an n element list? the reverse of the second element on followed by the first element.
Always check for EmptyStackException- returned by pop and peek
- Remember how stacks is used to evaluate postfix and also the valid string with brackets problem.
- Operator precdence: https://youtu.be/jos1Flt21is?t=4m28s (Remember for parentheses and exponents too!) (exponenets - right to left, division/multiplication- left to right)
- Prefix evaluation- from left to right; for Postfix: right to left
Stack<T> stackNewestOnTop = new Stack<T>();
public E peek() - Get the topmost element WITHOUT removing it.
public E pop() - Remove the topmost element and return that element.
size()- Size of stack
Number of nodes in a tree of height h
2^(h+1) -1
-
ALWAYS check if root is not null
-
Implement Deletion
-
Remember
preOrder,inOrderandpostOrderHDP!! JODER
https://www.youtube.com/watch?v=oSWTXtMglKE
Vital Tip: Lists, Collections maintain their reference in recursion, so you dont have to return explicity. Just keep passing along, building along.
https://www.youtube.com/watch?v=KEEKn7Me-ms
-
Tail recursion https://stackoverflow.com/questions/310974/what-is-tail-call-optimization
-
Iteration vs recursion https://stackoverflow.com/questions/10821059/space-complexity-of-recursive-algorithm
class FreshJuice {
enum FreshJuiceSize{ SMALL, MEDIUM, LARGE }
FreshJuiceSize size;
}
import java.util.logging.Level;
import java.util.logging.Logger;
private final static Logger logger = Logger.getLogger(TemperatureServlet.class.getName());
logger.log(Level.INFO, "New temperature is " + temperature);
logger.log(Level.SEVERE, "Failed with " + e.getMessage());
- A general addition rule
In general, for any base (2,5,10 etc..); say base is b1; the sum of digits results in (d1 + d2 + d3) % base The carry results in (d1 + d2 + d3)/base
CHECA lo!
- Sum of an AP with n terms, first term being a and last term being l.
Sn =1/2 * n(a + ℓ)
-
Sum of GP formula - Do you remember?
-
Combinatorics- Permutation and combination
- Think of the intuition behind combinations
- What is the differnece?
n choose k-- how many ways can you arrange k https://www.youtube.com/watch?v=p8vIcmr_Pqo
- What is the differnece?
- Think of the intuition behind combinations
Quick refresher- https://www.youtube.com/watch?v=bCxMhncR7PU https://www.youtube.com/watch?v=W7DmsJKLoxc
Lemma 1: r-permuations of n without repeats
P(n,r) = n!/(r-n)!
Lemma 3: Nonrepeating r-combinations of a set n
C(n,r) = n!/(n-r)!r!
Remember JODER
nC1 + nC2 + ..... + nCn = 2n
-
Divisibility Rules- Useful - http://www.softschools.com/math/topics/divisibility_rules_2_4_8_5_10/ Eg.: If last two digits are divisible by 4, then the number is as well; for 8 if the last the three digits are divisible, then so is the whole number.
-
GCD and LCM- Remember! EPI Ninja problem -- Base case --> everything divides zero!!
public char digitToChar(int i) {
return (char) (i + 97);
}
https://www.youtube.com/watch?v=SLauY6PpjW4
Merge Sort- Cuidate con este codigo!
if (low < high) {
int mid = low + (high - low)/2;
mergeSort( low, mid );
mergeSort( mid + 1, high);
merge( low, mid, high);
}
- Finding mid like this, avoids overflow:
int m = l+(r-l)/2;
bellman Ford!! -- https://www.youtube.com/watch?v=9PHkk0UavIM
- For n Vertices, there are n(n-1) edges maximum possible (duh..)
- Breadth first - visit all the nodes in the current depth - Level Order Traversal -- We use a Queue- QUEUEnki apne bacche ka khyal rakho bas, woh apne baccho ka khayal khud rakhenge
- Depth first - visit all the nodes till the end- Islands problem - PreOrder traversal etc.
- Topological Sort - STACK
- See different representations and compare pros/cons in terms of space and time complexity https://www.youtube.com/watch?v=k1wraWzqtvQ
- GREAT API!!
-- Priority Queue --
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
See MIT Video -->
- In the worst case, it is
log nto heaapify the shit out of it!- Acthung!! --> Heapifying an array starts from Node
n/2!- Why? As a parent is at (i/2) -- anything AFTER this MUST be a LEAF -- leafs by definition are heapified
- Time complexity -->
max_heapifytakesO(L)--> and number of nodes decrease as you go up
- Acthung!! --> Heapifying an array starts from Node
- Time complexity
Insertion - O(log n), Deletion - O(log n), Extract min - O(1)
- Use java priority queues to implement heaps. Eg.: this uses a string comparator Learn how to define own comparators
See example here: https://stackoverflow.com/questions/683041/how-do-i-use-a-priorityqueue
Comparator<String> comparator = new StringLengthComparator();
PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
- Remember the array representation
The root element will be at Arr[0].
Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[(i-1)/2] Returns the parent node
Arr[(2*i)+1] Returns the left child node
Arr[(2*i)+2] Returns the right child node
- Write basic programs such as delete, extractMin, insert Always use hasLeftChildIndex(), hasRightChildIndex(), hasPArentIndex(), to simplify things..
Best Video!- https://www.youtube.com/watch?v=WOSbx8TRrjw (Remember the husband wife example for race condition)
- Know basic methods, start, run, sleep, wait, join, notify, notifyAll
- There is ALWAYS a main thread, thats the one that spawns all others..
- Concurrent HashMap vs Synchronized HashMap
- Basic tutorial: http://www.vogella.com/tutorials/JavaConcurrency/article.html#nonblocking-algorithms
- http://winterbe.com/posts/2015/04/30/java8-concurrency-tutorial-synchronized-locks-examples/
- Synchronize on the thread-unsafe part only!
- Executor Service- why better? https://ibb.co/eic6Uk Minute 45 from the russian video
- How to call 'Callables': https://ibb.co/mavbUk ; Callable interface example: https://ibb.co/hW1kPk
- Amdahl's peformance law
If F is the percentage of the program which can not run in parallel and N is the number of processes, then the maximum performance gain is 1 / (F+ ((1-F)/n)).
-
Volatile variable - Remember what it is! - Always grab the volatile from the memory, not from the cache/CPU registers http://www.vogella.com/tutorials/JavaConcurrency/article.html#concurrency
-
Simple executor
Executors.newSingleThreadExecutor().execute(new Runnable() {
@Override
public void run() {
// code in here
}
});
- Remember executor service methods such as submit, invokeAll, invokeAny etc.: https://www.youtube.com/watch?v=mRdHvv7zW6M
*The package java.concurrent.atomic contains many useful classes to perform atomic operations. An operation is atomic when you can safely perform the operation in parallel on multiple threads without using the synchronized keyword or locks as shown
https://www.youtube.com/watch?v=AXjmTQ8LEoI
- Practice insertion/deletion/searching on white board- and draw diagrams.
- Careful with where you set isWord == true
Think of all rotations, and do the insertion
MST != Shortest Path
Use priority queue's remove method to implement Tushar Roy's min-heap data structure..
