| The Java Collection library is one of the most frequently used libraries.The LIFO access mechanism used by a stack has many practical uses. For example, Evaluation of expressions / syntax Parsing, validating and parsing XML, undo sequence in a text editor, pages visited history in a web browser, etc. Here are a few Java based interview questions and answers on a stack. Q. What LIFO implementation would you use in Java? A. The Vector based Stack class is a legacy and the Javadoc documentation for this class states that Deque should be used instead because it provides better LIFO operation support. Implementations of Deque are typically expected to perform better than Stack. J2SE 5 introduced a Queue interface and the Deque interface extends this interface. The Deque interface supports should be pronounced "deck" rather than "de-queue" and is not related to dequeue used to indicate removal from a queue. The double-ended queue supports addition or removal of elements from either end of the data structure, so it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). Note: The legacy Vector class uses internal synchronization, and it is rarely good enough for actual consistency, and can slow down execution when it is not really needed. The new java.util.concurrent package provides a more efficient way of thread-safety. Q. Can you write a program to evaluate if a given string input has proper closing bracket for every opening bracket? A. Firstly, think of the pseudo code. The pseudo-code goes as follows. 1. Store every opening parenthesis (i.e. a LHS parenthesis) in a stack. This will enable LIFO. 2. When you encounter a closing parenthesis (i.e. RHS parenthesis ), pop the last entry, which should be the corresponding opening parenthesis. 3. If not found, then the parentheses are not matched. If required, draw a diagram as shown below. |
Here is a sample program to illustrate a Stack (i.e. LIFO) in action in evaluating if a program has balanced parentheses. The enum constants class that defines the parentheses.
public enum PARENTHESIS {
LP((), RP()), LB({), RB(}), LSB([), RSB(]);
char symbol;
PARENTHESIS(Character symbol) {
this.symbol = symbol;
}
char getSymbol() {
return this.symbol;
}
}
Now, the stack in action using its LIFO mechanism to marry a closing parenthesis (i.e RHS) with an opening parenthesis (i.e. LHS). If you find any LHS parenthesis, push it into a stack, and when you find a RHS parenthesis, pop the stack to see if you have a corresponding LHS parenthesis.
import java.util.ArrayDeque;
import java.util.Deque;
public class Evaluate {
//stores the parentheses
final Deque<character> paranthesesStack = new ArrayDeque<character>();
public boolean isBalanced(String s) {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == PARENTHESIS.LP.getSymbol() ||
s.charAt(i) == PARENTHESIS.LB.getSymbol() ||
s.charAt(i) == PARENTHESIS.LSB.getSymbol())
paranthesesStack.push(s.charAt(i)); // auto boxing takes place
// push the opening parentheses
//for each RHS parenthesis check if there is a matching LHS Parenthesis
//if the stack is empty or does not have a matching LHS parenthesis then not balanced.
else if (s.charAt(i) == PARENTHESIS.RP.getSymbol()){
if (paranthesesStack.isEmpty() || paranthesesStack.pop() != PARENTHESIS.LP.getSymbol())
return false;
}
else if (s.charAt(i) == PARENTHESIS.RB.getSymbol() ) {
if (paranthesesStack.isEmpty() || paranthesesStack.pop() !=PARENTHESIS.LB.getSymbol() )
return false;
}
else if (s.charAt(i) == PARENTHESIS.RSB.getSymbol()) {
if (paranthesesStack.isEmpty() || paranthesesStack.pop() != PARENTHESIS.LSB.getSymbol())
return false;
}
}
return paranthesesStack.isEmpty(); //if the stack is empty, then all matched well, otherwise not matched.
}
}
Note: ArrayDeque is not thread-safe and does not allow for elements of the data structure to be null. The concurrent package has BlockingDeque and LinkedBlockingDequeue.
Finally, a simple JUnit class to test. You need to have the junit-xxx.jar in the classpth. The version xxx I used was 4.8.2.
import junit.framework.Assert;
import org.junit.Before;
import org.junit.Test;
public class EvaluateTest {
Evaluate eval = null;
@Before
public void setUp(){
eval = new Evaluate();
}
@Test
public void testPositiveIsBalanced(){
boolean result = eval.isBalanced("public static void main(String[] args) {}");
Assert.assertTrue(result);
}
@Test
public void testNegativeIsBalanced(){
boolean result = eval.isBalanced("public static void main(String[ args) {}"); // missing ]
Assert.assertFalse(result);
result = eval.isBalanced("public static void main(String[] args) }"); // missing {
Assert.assertFalse(result);
result = eval.isBalanced("public static void main String[] args) {}"); // missing (
Assert.assertFalse(result);
}
}
Tip: When testing, test positive and negative scenarios.
Note: The above example is shown to illustrate how a LIFO mechanism can be used to determine if the parentheses are balanced. The actual implementation is far from being optimum. Where ever there is a large block of if-else or switch statements, one should think about an object oriented solution.
Q. Why Deque interface is different from other collection classes?
A. In Deque, You can insert and delete the objects from the both start and end of the the collection. Whereas in a normal collection, inserts/deletes are happening at last only.
Q. What are the different ways to look at the trace of your program execution?
A.
1. Java is a stack based language, and the program execution is pushed and popped out of a stack. When a method is entered into, it is pushed into a stack, and when that method invokes many other methods, they are pushed into the stack in the order in which they are executed. As each method completes its execution, they are popped out of the stack in the LIFO order. Say methodA( ) invoked methodB( ), and methodB( ) invoked methodC ( ), when execution of methodC( ) is completed, it is popped out first, and then followed by methodB( ) and then methodA( ). When an exception is thrown at any point, a stack trace is printed for you to be able to find where the issue is.
2. A Java developer can access a stack trace at any time. One way to do this is to call
Thread.currentThread().getStackTrace() ; //handy for tracing
You could get a stack trace of all the threads using the Java utilities such as jstack, JConsole or by sending a kill -quit signal (on a Posix operating system) or <ctrl><break> on WIN32 platform to get a thread dump. You could also use the JMX API as shown below. ThreadMXBean is the management interface for the thread system of the JVM.
ThreadMXBean bean = ManagementFactory.getThreadMXBean();
ThreadInfo[] infos = bean.dumpAllThreads(true, true);
for (ThreadInfo info : infos) {
StackTraceElement[] elems = info.getStackTrace();
//...do something
}
The thread dumps are very useful in identifying concurrency issues like dead locks, contention issues, thread starvation, etc.
Q. Is recursive method calls possible in Java?
A. Yes. Java is stack based and because of its LIFO (Last In First Out) property, it remembers its caller. So it knows whom to return when the method has to return.
Q. How would you go about analyzing stack traces correctly?
A.
1. One of the most important concepts of correctly understanding a stack trace is to recognize that it lists the execution path in reverse chronological order from most recent operation to earliest operation. That is, it is LIFO.
2. The stack trace below is simple and it tells you that the root cause is a NullPointerException on ClassC line 16. So you look at the top most class.
Exception in thread "main" java.lang.NullPointerException
at com.myapp.ClassC.methodC(ClassC.java:16)
at com.myapp.ClassB.methodB(ClassB.java:25)
at com.myapp.ClassA.main(ClassA.java:14)
3. The stack trace can get more complex with multiple "caused by" clauses, and in this case you usually look at the bottom most "caused by". For example,
Exception in thread "main" java.lang.IllegalStateException: ClassC has a null property
at com.myapp.ClassC.methodC(ClassC.java:16)
at com.myapp.ClassB.methodB(ClassB.java:25)
at com.myapp.ClassA.main(ClassA.java:14)
Caused by: com.myapp.MyAppValidationException
at com.myapp.ClassB.methodB(ClassB.java:25)
at com.myapp.ClassC.methodC(ClassC.java:16)
... 1 more
Caused by: java.lang.NullPointerException
at com.myapp.ClassC.methodC(ClassC.java:16)
... 1 more
The root cause is the last "caused by", which is a NullPointerException on ClassC line 16
4. When you use plethora of third-party libraries like Spring, Hibernate, etc, your stack traces "caused by" can really grow and you need to look at the bottom most "caused by" that has the package relevant to you application like com.myapp.ClassC and skip library specific ones like org.hibernate.exception.*.
Q. Can you reverse the following numbers {1, 4, 6, 7, 8, 9}?
A. There are a number of ways to achieve this. Speaking of LIFO, the following example illustrates using a stack based implementation.
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class ReverseNumbers {
public static void main(String[] args) {
Integer[] values = {1, 4, 6, 7, 8, 9};
Deque<integer> numberStack = new ArrayDeque<integer>(10);
for (int i = 0; i < values.length; i++) {
numberStack.push(values[i]); // push the numbers in given order
}
Integer[] valuesReversed = new Integer[values.length];
int i = 0;
while (!numberStack.isEmpty()) {
valuesReversed[i++] = numberStack.pop(); // pop it - as this happens in reverse order
// i++ is a post increment i.e.
// assign it and then increment it
// for the next round
}
System.out.println(Arrays.deepToString(valuesReversed));
}
}
The output will be
[9, 8, 7, 6, 4, 1]
0 comments:
Post a Comment