Recently I was invited to a face to face interview at a well-known IT company after I have passed the telephone round. This time I was asked using state machine to design a CD-Player at the beginning. It was not that difficult, I don’t know what made me not able to answer this question. I think maybe I was too nervous after I heard this unexpected opening question and felt not confident with the state machine which I had studied at the university many years ago. After I came back home, I quickly painted it down on the paper:
Maybe some details we can discuss after the first draft, it will depend on what exactly the requirements would be, nevertheless an experienced software developer should be able to carry out at least the first draft. I think the interviewer was quite disappointed about my reaction.
After that I was asked some basic Java API, Memory and Algorithm questions such like how do Garbage Collector, Comparable interface and HashMap work, what is transient, what is finalize, how to create Stack Overflow, what happens when new objects are instantiated and what’s the difference between Stack and Heap and so on… I was also asked to design an algorithm to reverse a string. This algorithm design was toooooo basic to me, we can simply traverse the chars in the String start from the tail:
public static String reverse1(String s) {
String res = "";
for (int i = s.length() - 1; i >=0; i--) {
res += s.charAt(i);
}
return res;
}
Or if we want to do something different, we can also push each char into the Stack and then pop them out. I spent little time implemented it below:
public String reverse(String s){
Stack<Character> stack = new Stack<>();
StringBuilder res = new StringBuilder(s.length());
for(char c:s.toCharArray()){
stack.push(c);
}
while(!stack.isEmpty()){
res.append(stack.pop());
}
return res.toString();
}
To the Memory and Java API questions, my answer was not complete enough, I want to write down the complementary here: when we instantiate (new) an object with java, the object will be created on heap which has not only big size but also can be extended by operating system if necessary, the stack which is small, has fixed size, keeps the primitives, method invocation and the references — in other words it keeps the address where the corresponding object allocated, that’s also explained why even we make the fields/reference final can not prevent a mutable object from being modified. For example, by invoking the getDate() method below we can reach the Date Object in the heap, since Date Object is mutable, we can change it over the reference. The correct design is, we should return a clone of the date object to make the MyImmutableOject like String which is ideal to be a key of HashMap and simultaneously thread safe.
public final class MyImmutableObject{
//Object still mutable since only the reference is final
private final Date date = new Date();
public Date getDate(){
return this.date;
}
}
Actually the objects can also be created on stack if they are created during method invocation and are only used in that method, these objects don’t need to be garbage collected since they will in any case disappear after the life cycle of the method invocation.
public void method(){
Object o = new Object(); // will be created on stack
...
}
The HashMap technology relies on the hashCode() and equals() method that are in the Object Class which make hashmap being able to provide O(1) time complexity for searching a value using key. After the hashcode is calculated, it is added to the “bucket” in the Map.Entry which is a LinkedList before Java 8. I’ve heard if reach some threshold, this LinkedList data structure in HashMap can be replaced by a balanced binary tree in Java 8, which will provide O(logN) time complexity by using the binary search. Compare to the LinkedList which is linear and time complexity is O(N), the balanced binary tree can notablely improve the performance when collision happens.
For the sake of clarity, I want to shortly explain here why HashMap needs a LinkedList in the bucket: since the hashcode can not guarantee the uniqueness, meaning there might be multiple keys with same hashcode in one bucket which is called collision, thus the keys with same hashcode will be put into a LinkedList, so that when collision happens HashMap is able to call the keys.equals() method to traversal the List for finding the correct key, that’s the background.
The most embarrassing thing was that the interviewer asked me to design a “child clock”, however he didn’t tell me the concrete requirements of the application at the beginning by intention, since he wanted to observe my reaction, whether I would ask my “customer” about the “specification” and I fell in his trap as he “expected”…
Well, getting a job is definitely not my final goal but becoming a better programmer is! This interview is novel to me, opened my eyes and made me notice that I could be better. If you could also learn something from my experience, I am not wasting my time. 🙂
rekinyZ's Blog 