Competitive programming and Coding interviews requires candidates to have strong command on any one programming language to translate the problem solution to code. Ideally it would be good to learn multiple programming languages, but because the "Language Agnostic" interview policy adopted by many tech companies, it is generally fruitless to spend time and effort to master multiple languages instead of focusing on one language & algorithms.
Java language is predominantly used by many for coding interviews due to its simple syntax and widely available help online. Below are some of the commonly used code, functions, hints, tricks which come handy during coding interview.
It is very important to note that different Java Online IDE's used for the interviews, which have different level of support for various standard library methods, hence be prepared to use alternative API's in order to carry out a given operation. Further in some interviews the interviewee is not even provided a java compiler, but just a simple text editor (Codepad). The interviewee is expected to run and debug the code in mind to determine correctness of the code which can be very challenging.
Basics
The default value of char primitive type variable is '\u0000'.
Swapping two variables without temp variable
a = a + b b = a - b a = a - b
Alternative approach to swap using XOR operation
x = x ^ y; y = x ^ y; x = x ^ y;
The break statement can be used to exit from a single loop. To break from multiple loops, use return statement or use break with a label for the outer loop as below.
outerloop:
for (int i=0; i < 5; i++) {
for (int j=0; j < 5; j++) {
if (i * j > 6) {
System.out.println("Breaking");
break outerloop;
}
System.out.println(i + " " + j);
}
}
Pass By Value
Arguments in Java are always passed by value regardless of the original variable type. Each time a method is invoked, a copy for each argument is created in the stack memory and the copy version is passed to the method. A copy of variable is created in the stack for Primitive type. For Object type, a new reference or pointer is created inside the stack memory, which points to the actual object data. Hence any change to the reference inside the method is actually changing the reference of the copies and not the original references. When defining an arraylist or any collection in java, a reference is created inside the stack that points to multiple objects inside the heap memory. When the list is updated in the called method, then the original list reference can see the modification, since both references are pointing to the same object in memory.
String or Character operations
String Tokenization is used to process each token string one at a time.
import java.util.StringTokenizer;
StringTokenizer tokenizer = new StringTokenizer(str, ",");
while (tokenizer.hasMoreElements()) {
tokens.add(tokenizer.nextToken());
}
The split() method of String is used to tokenize string and store result in array.
String[] info = someString.split("\\s+"); // split by space
String[] fragments = info[1].split("\\."); // split by dot
Each alphabet character has a numeric value, for example numeric value of alphabet 'a' is 10.
Character.getNumericValue('a')
The substring() method returns a new string that is a substring of given string based on the passed indexes.
String substring(int beginIndex) String substring(int beginIndex, int endIndex)
To reverse a String use the StringBuilder's reverse method as below.
new StringBuilder("String to reverse").reverse().toString();
Given a string containing a prefix word, return remaining substring.
if(string.startsWith(word)) {
String remainingString = string.substring(word.length());
}
Math Library
The Math library is Java has very useful methods for performing any mathematical operations.
- Math.abs(num): Returns the absolute value.
- Math.ceil(num): Returns the smallest integer that is greater than or equal to the argument
- Math.floor(num): Returns the largest integer that is less than or equal to the argument.
- Math.max(a, b) and Math.min(c, d): Returns the largest and smallest of the two arguments respectively.
- Math.pow(a, b): Returns the value of the first argument raised to the power of the second argument.
- Math.round(a): Returns the closed int or long (as per the argument)
- Math.random(): Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0
Arrays
Print Array elements for debugging purposes
System.out.println(Arrays.toString(array));
Initialize or set all elements of array with one value
int[] intarry = new int[n+1]; Arrays.fill(intarry, -1); Arrays.fill(intarry, 0);
Arrays can be copied in entirely or partially. The copyOf() method copies entire array, while the copyOfRange() method copies the subset of the specified array. The arrays can be of either primitive or object type.
Arrays.copyOf(original[], int newLength) and Arrays.copyOfRange(original[], int from, int to)
Array elements can be sorted using sort()
char[] charArray = string.toCharArray(); java.util.Arrays.sort(charArray);
The Arrays.binarySearch()(SET 1 | SET2) method is used to apply binary search on a sorted array.
Convert int array to List of Integer using IntStream.boxed() which box each element of the stream to an Integer.
List<Integer> list = Arrays.stream(arr)
.boxed()
.collect(Collectors.toList());
We can also use IntStream.of() to get IntStream from integer array.
List<Integer> list = IntStream.of(arr) // returns IntStream
.boxed()
.collect(Collectors.toList());
Converting primitive integer array to an Integer array.
Integer[] boxedArray = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Comparable and Comparator
Comparable object is capable of comparing itself with another object. The class (of element to be compared) itself must implements the java.lang.Comparable interface and override the compareTo method to compare its instances. Comparable compares "this" reference with the object specified in the compareTo(T o) method.
Comparator is an external class from the element type that is to be compared. Multiple separate classes implementing Comparator are created to compare by different members. The Collections.sort() method takes Comparator argument which invokes the compare() to sort objects. Comparator compares objects of two different class passed to the compare(T o1,T o2) method. Comparator also provides built in method such as naturalOrder() and reverseOrder() for natural ordering, reversed() to reverse ordering of the comparator.
Both compareTo() method of Comparable and compare() method of Comparator return integer with:
negative = first argument (or this object) is less than the (second) argument.
positive = first argument (or this object) is greater than the (second) argument.
zero = both objects are equal
If sorting of objects needs to be based on natural order then use Comparable whereas if sorting needs to be done on attributes of different objects, then use Comparator.
Collections and Lists
Sort collection elements using sort method
Collections.sort();
Sort collection elements using sort method
Collections.copy(List<T> dest, List<T> src) copies specified collection.
The Collections.rotate() to rotate a collection or an array by a specified distance.
The Collections.frequency() method can be used to get the frequency of a specified element in a collection or an array.
The Collections.binarySearch() used to apply binary search on a collection based on comparators.
The Set collection does not have index, hence to get the first element from a Set we use Iterator.
HashSet<String> hashSet = new HashSet<String>();
Iterator<String> iter = hashSet.iterator();
if (iter.hasNext()) {
String value = iter.next();
}
LinkedHashSet is subclass of HashSet that guarantees insertion-order.
SortedSet is a set in which the elements are stored in some sorted order.
NavigableSet extends the SortedSet interface with navigation (searching) methods.
Queue<E> extends the Collection interface to maintain a collection whose elements need to be processed in some way, i.e., insertion at one end and removal at the other, usually as FIFO. E.g. PriorityQueue<E>, LinkedList<E>.
The offer(E e) method of Queue Interface inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. This method is preferable to add() method since this method does not throws an exception when the capacity of the container is full since it returns false.
The peek() method returns the object at the top of the current queue, without removing it, while the poll() method returns the object at the top and removes it. If the queue is empty then both peek() and poll() methods returns null. The remove() method is returns the top object from the queue and throws NoSuchElementException if the queue is empty.
The LinkedList implementation uses a doubly-linked list and, Insertions and deletions are very efficient. If frequent insertions and deletions occur inside a list, a LinkedList can be more efficient. LinkedList class also implements two other interfaces that allow it to be used for stacks and different kinds of queues.
PriorityQueue is implementation for a queue with priority ordering.
Deque<E> extends the Queue interface to maintain a queue whose elements can be processed at both ends. E.g. ArrayDeque<E>, LinkedList<E>. Deque inherits the offer method from Queue interface which is similar to offerLast. It allows to insert from the front and end, as well as remove from the front and the end from the constant time.
Deque<Integer> deque = new ArrayDeque<>(); deque.offerFirst(val); deque.offerLast(val);
Maps
HashMap is implemented as a hash table, and there is no ordering on keys or values. HashMap is same as Hashtable, except that it is unsynchronized and permits nulls.
TreeMap is a map, sorted by the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. It is an efficient way of sorting and storing the key-value pairs. The storing order maintained by the TreeMap must be consistent with equals just like any other sorted map, irrespective of the explicit comparators.
LinkedHashMap is a subclass of HashMap with an additional feature of preserving the insertion-order of the elements.
Print Map key-value pairs using java8
map.forEach((key, value) -> System.out.println(key + ":" + value));
Simple way to increment or update values in a Map.
map.put(sum, map.getOrDefault(sum, 0) + 1);
The putIfAbsent is handy method to only put the key and value if it doesn't exists.
map.putIfAbsent(first_key, value);
The ceilingEntry() method call returns an entry with the least key greater than or equal to key, or null if there is no such key.
Integer value = map.ceilingEntry(dollar - sum).getValue();
Threads
The Thread.start() method sets the thread in Ready-to-run state and makes it eligible for running. It waits for its turn to get CPU time. Once picked by thread scheduler it goes in Running state.
The sleep() causes the currently running thread to temporarily pause its execution and transit to the Sleeping state. The Sleep method does not relinquish any lock that the thread might have. After the sleep time, the thread transitions to the Ready-to-run state where it takes its turn to run again.
The yield() method may cause the current thread in the Running state to transit to the Ready-to-run state, relinquishing the CPU and giving other threads in the Ready-to-run state a chance to run. The thread is then at the mercy of the thread scheduler as to when it will run again, which is possible if there are no threads in the Ready-to-run state. The yield() method is an advisory method, and comes with no guarantees that the JVM will carry out the call's bidding. A call to the yield() method does not affect any locks that the thread might hold.
The wait() and notify() methods can only be executed on an object whose lock the thread holds (synchronized object). When a thread invokes the wait() method on the object whose lock it holds, it leaves the Running state and transits into Waiting-for notification state. The thread relinquishes the ownership of the object lock on which the wait() method was invoked, which can then be acquired by other threads. A thread in the Waiting-for-notification state is awakened by:
- Another thread invokes the notify() method on the object of the waiting thread, and the waiting thread is selected as the thread to be awakened.
- The waiting thread times out.
- Another thread interrupts the waiting thread
The notify() method on an object relinquishes the lock from the current thread, and wakes up another thread waiting for the same object's lock. After being notified, the waiting thread first transits to the Blocked-for-lock-acquisition state to acquire the lock on the object, and then to the Ready-to-run state.
A thread can invoke the join() method on another thread in order to wait for the other thread to complete its execution before continuing. Thread calling join waits until other thread completes its execution, or waiting thread is timeout or interrupted.
Bit Manipulation
Check if the number is even or odd without using the % operator, with bitwise & operation.
System.out.println((a & 1) == 0 ? "EVEN" : "ODD" );
Fast Multiplication or Division by 2.
n = n << 1; // Multiply n with 2 n = n >> 1; // Divide n by 2
0110 + 0110 is equivalent to 0110 * 2, which is equivalent to shifting 0110 left by 1.
0100 equals 4, and multiplying by 4 is just left shifting by 2. So we shift 0011 left by 2 to get 1100.
If we XOR a bit with its own negated value, we will always get 1. Therefore, the solution to a^(~a) will be a sequence of 1s.
~0 is a sequence of 1s, so ~0 << 2 is 1s followed by two Os. ANDing that with another value will clear the last two bits of the value.
x ^ 0s = x x ^ 1s = ~x x ^ x = 0 x & 0s = 0 x & 1s = x x & x = x x | 0s = x x | 1s = 1s x | x = x
A positive number is represented as itself while a negative number is represented as the two's complement of its absolute value (with a 1 in its sign bit to indicate that a negative value).
To find two's complement, we invert the bits in the positive representation and then add 1. For example, 3 is represented as 011 in binary. Flip the bits to get 100, add 1 to get 101, then prepend the sign bit (1) to get 1101.
In a logical right shift, we shift the bits and put a 0 in the most significant bit. It is indicated with a >>> operator.
In an arithmetic right shift, we shift values to the right but fill in the new bits with the value of the sign bit, which has the effect of(roughly) dividing by two. It is indicated by a > > operator.
The right shift operator ">>" keeps the sign bit intact i.e. first or most significant bit never lost, doesn't matter how many times you shift. On the other hand unsigned right shift operator ">>>" doesn't preserve sign of original number and fills the new place with zero, hence its also known as right shift with zero fill.
A sequence of all ls in a(signed) integer represents -1.
Binary bits is can be used instead of array of flags and enables to easily check if any flag is true. In order to check that no bits in the integer are 1, we just compare the integer to 0. There is actually a very elegant way to check that an integer has exactly one bit set to 1. If we subtract 1 from it and then AND it with the new number, we should get 0.
var1 = 010010 var2 = 000010 010010 & 111101 = 000000
The below method shifts 1 over by i bits, creating a value that looks like 00010000. By performing an AND with num, we clear all bits other than the bit at bit i. Finally, we compare that to 0. If that new value is not zero, then bit i must have a 1. Otherwise, bit i is a 0.
boolean getBit(int num, int i) {
return ((num & (1 << i)) != 0);
}
SetBit shifts 1 over by i bits, creating a value like 00010000. By performing an OR with num, only the value at bit i will change. All other bits of the mask are zero and will not affect num.
int setBit(int num, int i) {
return num | (1 << i);
}
An efficient trick to determine if a number is a power of 2:
boolean isPowerOfTwo(int x) {
// First x in the below expression is for the case when x is 0
return x!=0 && ((x&(x-1)) == 0);
}
Regular Expressions
import java.util.regex.Matcher;
import java.util.regex.Pattern;
Pattern pattern = Pattern.compile("(.*)(\\d+)(.*)", Pattern.CASE_INSENSITIVE);
Matcher matcher = pattern.matcher("order is for QT3000!");
if (matcher.find( )) {
System.out.println("Found value: " + matcher.group(0) );
System.out.println("Found value: " + matcher.group(1) );
System.out.println("Found value: " + matcher.group(2) );
}
I/O Operations
Get input from system input.
Scanner scanner = new Scanner(System.in); String myString = scanner.next(); int myInt = scanner.nextInt(); scanner.close();
No comments:
Post a Comment