Friday 30 January 2015
Wednesday 21 January 2015
Sunday 18 January 2015
Java Memory Model
- Each thread running in the Java virtual machine has its own thread stack.
- The thread stack also contains all local variables for each method being executed (all methods on the call stack). A thread can only access it's own thread stack. Local variables created by a thread are invisible to all other threads than the thread who created it. Even if two threads are executing the exact same code, the two threads will still create the local variables of that code in each their own thread stack.
- The heap contains all objects created in your Java application, regardless of what thread created the object.
- An object may contain methods and these methods may contain local variables. These local variables are also stored on the thread stack, even if the object the method belongs to is stored on the heap.
- As already mentioned, the Java memory model and the hardware memory architecture are different. The hardware memory architecture does not distinguish between thread stacks and heap. On the hardware, both the thread stack and the heap are located in main memory. Parts of the thread stacks and heap may sometimes be present in CPU caches and in internal CPU registers.
- The
volatilekeyword can make sure that a given variable is read directly from main memory, and always written back to main memory when updated. - With non-volatile variables there are no guarantees about when the Java Virtual Machine (JVM) reads data from main memory into CPU caches, or writes data from CPU caches to main memory.
- A synchronized instance method in Java is synchronized on the instance (object) owning the method. Thus, each instance has its synchronized methods synchronized on a different object: the owning instance. Only one thread can execute inside a synchronized instance method. If more than one instance exist, then one thread at a time can execute inside a synchronized instance method per instance. One thread per instance.
- A thread that calls wait() on any object becomes inactive until another thread calls notify() on that object. In order to call either wait() or notify the calling thread must first obtain the lock on that object. In other words, the calling thread must call wait() or notify() from inside a synchronized block.
- Once a thread calls wait() it releases the lock it holds on the monitor object. This allows other threads to call wait() or notify() too, since these methods must be called from inside a synchronized block.
- The
ThreadLocalclass in Java enables you to create variables that can only be read and written by the same thread. Thus, even if two threads are executing the same code, and the code has a reference to aThreadLocalvariable, then the two threads cannot see each other'sThreadLocalvariables.
- As I have mentioned earlier, if two threads are both reading and writing to a shared variable, then using the
volatilekeyword for that is not enough. You need to use synchronization in that case to guarantee that the reading and writing of the variable is atomic.But in case one thread reads and writes the value of a volatile variable, and other threads only read the variable, then the reading threads are guaranteed to see the latest value written to the volatile variable. Without making the variable volatile, this would not be guaranteed.
Wednesday 14 January 2015
An updated comprehensive list of BST
- http://www.geeksforgeeks.org/reverse-level-order-traversal/
- http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
- http://www.geeksforgeeks.org/merge-two-bsts-with-limited-extra-space/
- http://www.careercup.com/question?id=14581972
Tuesday 13 January 2015
LeetCode Solutions : Letter combinations of a phone number
public class Solution {
Map<Integer,List<String>> map;
public List<String> letterCombinations(String digits) {
map = new HashMap<Integer,List<String>>();
this.map.put(2,new ArrayList<String>(Arrays.asList("a","b","c")));
this.map.put(3,new ArrayList<String>(Arrays.asList("d","e","f")));
this.map.put(4,new ArrayList<String>(Arrays.asList("g","h","i")));
this.map.put(5,new ArrayList<String>(Arrays.asList("j","k","l")));
this.map.put(6,new ArrayList<String>(Arrays.asList("m","n","o")));
this.map.put(7,new ArrayList<String>(Arrays.asList("p","q","r","s")));
this.map.put(8,new ArrayList<String>(Arrays.asList("t","u","v")));
this.map.put(9,new ArrayList<String>(Arrays.asList("w","x","y","z")));
return comb(digits);
}
public List<String> comb(String digits) {
List<String> result = new LinkedList<String>();
if(digits.length() == 0) {
result.add(new String(""));
} else if(digits.length() == 1) {
List<String> ret = new LinkedList<String>();
for(String c:map.get(Integer.parseInt(digits)))
ret.add(c);
return ret;
} else {
for(String s : comb(digits.substring(1))) {
for(String c:map.get(Integer.parseInt(digits.substring(0,1))))
result.add(c + s);
}
}
return result;
}
}
Sunday 11 January 2015
LeetCode Solutions
- Word Ladder :
- http://www.programcreek.com/2012/12/leetcode-word-ladder/ -
If you are queueing and removing the element from the dict as done here, then you can calculate the minimum length. But you cannot calculate all possible lengths. As you remove it from the dict, that state is into the queue. All that matters is whether the end is reachable from that state or not. We dont care if we can reach that state from any other state or not. - http://yucoding.blogspot.com/2013/08/leetcode-question-127-word-ladder.html - Double breadth first search. This is a very good post to learn bi directional search.
- Scramble string leetcode : http://www.lifeincode.net/programming/leetcode-scramble-string-java/ Understand the DP part
- Permutations : http://www.lifeincode.net/programming/leetcode-permutations-and-permutations-ii-java/
- K Sum - http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/ -
- Solve the KSum problem better one and also solve the 4sum yourself.
- Combinations(n,k) - http://lifexplorer.me/leetcode-combinations/
- Spiral Matrix : http://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/
Saturday 10 January 2015
Twitter interview questions
- Maze solver
- Gmail architecture design
- http://netlojava.blogspot.com/2013/08/gmail-server-architecture.html
- http://css.dzone.com/news/gmail-architecture-part-1
- Given a two strings, return whether the second is an anagram of a palindrome of the first string.
- Online Machine Learning
- Graph Algorithm
- Bit manipulation
- Get unfair coins using fair coins https://dicedcoins.wordpress.com/2012/07/30/simulate-fair-coins-unfair/
- Determine if a BST is valid or not
- 1) Find the single number in a array, all other elements are paired. 2) Give a array A[k], define the set S{k} := { A[k], A[A[k]], A[A[A[k]]], ... }, write program to count the maximum size of Sks.
- integer N and returns an NxN matrix with incrementing integers in a spiral, from outside in.
- Overlap intervals
- Top k terms in unsorted array
- In order iterative bst traversal
- Questions given a vector of strings of length n with each word having a length of m on average, group all anagrams into a cluster. Do this for the case that n >>>>>> m and in the most efficient way possible. Assume extra space allowed.
- Given a number, tell how many 1s are there in the binary format of this number
- http://stackoverflow.com/questions/2344496/how-can-i-print-out-all-possible-letter-combinations-a-given-phone-number-can-re
- http://www.lifeincode.net/programming/leetcode-letter-combinations-of-a-phone-number-java/
- Tree to ordered double linked list
- Implement hash table
- Given n sets of choices: (1,2,3), (2,3,4), (4,5)
You pick one element from each set of choices.
Generate all possible picking. - Trie
- Subset sum
- Topological sorting
- Implement divide operation using multiply
- http://javahungry.blogspot.com/2014/05/convert-math-number-to-equivalent-readable-word-in-java-code-with-example.html
- http://leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html
- http://rleetcode.blogspot.com/2014/02/combination-sum.html
- 4SUm
- Given two nodes in a binary tree find the number of nodes, between the path to the two nodes
- LRU cache
- Given sorted dictionary, sort the characters
- Given a list of names. Find whether a particular name occurs inside a given tweet or not. If found return true otherwise false Time complexity should be less than O(n). - suffix tree
- Given the pre-order sequence of a binary tree, how many trees can be created from this
- Validate if a tree is BST
- 4 points form a square
- http://www.careercup.com/question?id=14951746
- Design a hashmap
- Design a thread safe hashtable
- Design a collaborative editor - where each participant can go offline
- Given a string representing roman numeral, find and return its numeric value. e.g. XXIV = 24 and so on.
- Top K queries from search logs
- Output : (*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c) Answer Question
- Convert infix expression into postfix. Answer Question
- Write code that walks thru all src code starting from a root dir. and create histogram of number of characters per line across all files.
Thursday 8 January 2015
Generate all permutations of a string in Java
How would you solve the problem recursively ? Suppose you have a permutation(n-1) which returns all permutations of size n-1. You will passfor (int i = 0; i < n; i++) permutation(str.substring(0, i) + str.substring(i+1, n));
Then to every returned string you will addstr.charAt(i).
So you have to deal with an array of strings in return type.Instead you pass thestr.charAt(i) as a part of the input itself and you dont
need to worry about concatenating it at the end. Instead when the length of the second parameter in the permutation becomes 0 you just print the first paramter. public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
} Now you have done it with strings and you are printing it. Suppose you have to return a List<List<Integer>> then how would you do it. Practise this as it will improve your collections.
public class Solution {
List<List<Integer>> ret;
public List<List<Integer>> permute(int[] num) {
ret = new LinkedList<>();
LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 0; i < num.length; i++)
numbers.add(num[i]);
LinkedList<Integer> list = new LinkedList<>();
permute(numbers, list);
return ret;
}
private void permute(List<Integer> numbers, List<Integer> list) {
if (numbers.size() == 0) {
LinkedList<Integer> newList = new LinkedList<>();
newList.addAll(list);
ret.add(newList);
return;
}
for (int i = 0; i < numbers.size(); i++) {
int candidate = numbers.get(i);
numbers.remove(i);
list.add(candidate);
permute(numbers, list);
list.remove(list.size() - 1);
numbers.add(i, candidate);
}
}
Subscribe to:
Posts (Atom)