Thursday, January 21, 2016

Discuss Internals of Hashmap in Java

Fig1. - Pictorial view for HashMap Internals.
Important Facts about HashMap
  1. HashMap is a container of pairs
  2. HashMap is list of Buckets arranged by hashcode of key
  3. When a bucket gets too large, hashmap implementation will change that bucket implementation to something like TreeMap, simply by checking number of elements in each bucket. This allows faster lookup when there are too many hash collisions
  4. Get, Put and Remove method offers Big O (1) time complexity (constant runtime), assuming the hash function disperses the elements properly among the buckets
  5. Load factor (default value of 0.75) decides when hashmap will regrow, when capacity reaches of the hashmap is 75% (0.75 is load factor) full, then hashmap will double its size
  6. Size of hashmap is always expressed in 2n to allows faster hashcode calculations using bitwise operator instead of modulus operator. Even if you provide a different capacity at the time of hashmap construction, it will automatically be adjusted to nearest 2n
  7. Capacity and Size are two different things - size is actual number of elements present in hashmap, capacity is size of its internal table at any given point in time. Capacity grows when size becomes equal to capacity x load factor
  8. As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
  9. Bucket uses TreeNode instead of normal Node if it contains elements more than specified in TREEIFY_THRESHOLD, which is defaulted to 8
  10. The iterators returned by all of this class’s “collection view methods” are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
HashMap is defined as Array of Nodes as shown below

transient Node<K,V>[] table;

Wednesday, January 20, 2016

How to find if the Linked List contains any Cycle/Loop?

DetectCycle in LinkedList using two pointers.

This solution is “Floyd’s Cycle-Finding Algorithm” as published in “Non-deterministic Algorithms” by Robert W. Floyd in 1967. It is also called “The Tortoise and the Hare Algorithm”. 

O(n) time complexity
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

Steps

  1. Use two pointers fast and slow
  2. Move fast two nodes and slow one node in each iteration
  3. If fast and slow meet then linked list contains cycle
  4. if fast points to null or fast.next points to null then linked list is not cyclic 
Java Source Code

public class CycleFreeLinkedList<T> {
    private Node<T> first;
    private Node<T> last;

    public CycleFreeLinkedList() {
        first = new Node<>();
    }

    public void appendToTail(T data) {
        final Node l = last;
        final Node<T> newNode = new Node(data);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }

    public void appendNodeToTail(Node<T> node) {
        final Node l = last;
        final Node<T> newNode = node;
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }

    public void detectCyclic() {
        Node fast = first;
        Node slow = first;

        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            //if fast and slow pointers are meeting then LinkedList is cyclic
            if (fast == slow) {
                throw new CyclicNodeException(fast.toString());
            }
        }
    }

    @Override
    public String toString() {
        detectCyclic();
        StringBuilder output = new StringBuilder();
        Node current = first.getNext();
        while (current != null) {
            output.append(current).append(" -> ");
            current = current.getNext();
        }
        return output.toString();
    }

    public static class Node<T> {
        Node next;
        T data;

        public Node() {
        }

        public Node(T data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    public static class CyclicNodeException extends RuntimeException {

        public CyclicNodeException(String msg) {
            super("There is a cyclic node in the list at - " + msg);
        }
    }
}

Unit Test to detect Loops/Cycle

public class CycleFreeLinkedListTest {

    @Rule
    public ExpectedException thrown= ExpectedException.none();

    @org.junit.Test
    public void testIsNotCyclic() throws Exception {
        CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
        linkedList.appendToTail("101");
        linkedList.appendToTail("201");
        linkedList.appendToTail("301");
        linkedList.appendToTail("401");

        System.out.println("linkedList = " + linkedList);
    }

    @org.junit.Test
    public void testIsCyclic() throws Exception {
        CycleFreeLinkedList<String> linkedList = new CycleFreeLinkedList();
        linkedList.appendToTail("101");

        Node<String> cycle = new Node<>("201");

        linkedList.appendNodeToTail(cycle);
        linkedList.appendToTail("301");
        linkedList.appendToTail("401");
        linkedList.appendNodeToTail(cycle);

        thrown.expect( CyclicNodeException.class );
        thrown.expectMessage("There is a cyclic node in the list at - Node{data=401}");

        System.out.println("linkedList = " + linkedList);
    }
}

Is it safe to iterate over an ArrayList and remove its elements at the same time ? When do we get ConcurrentModificationException & hidden Iterator?

Iterator returned by the ArrayList (and many other collection types) is fail-fast. If the list is structurally modified at anytime after the iterator is created, in any way except through the Iterator’s own remove() method, the iterator will throw ConcurrentModificationException and thus fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Structural Modification
A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely changing the values associated with a key that an instance already contains is not a structural modification.” - Java Docs
Further, the structural modification could happen either from single thread or from multiple threads. The behavior of ArrayList would be different in both the cases as mentioned below.
Single Threaded Scenario
Never call list.remove(element) to remove a item from list while traversing it. Rather use Iterator.remove() mehtod.
private List<String> list = new ArrayList<>(asList("first", "second", "third", "fourth"));
public void unsafeMethod() {
    for (String item : list) { // Will throw ConcurrentModificationException
    list.remove(item);
  }
}

public void safeMethod() {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) { // safe to call iterator.remove()
    String item = iterator.next();
    iterator.remove();
 }
}
Multi-Threading Scenario
ArrayList implementation is not thread-safe because it provides no synchronization mechanism for protecting
the shared state of its fields. If multiple threads access an ArrayList instance concurrently, and at least one of
the threads modifies the list structurally, it must be synchronized externally. This is typically accomplished by
synchronizing on some object that naturally encapsulates the list.
If no such object exists, the list should be “wrapped” using the Collections.synchronizedList() method. This is
best done at creation time, to prevent accidental unsynchronized access to the list :
List list = Collections.synchronizedList(new ArrayList(...));
public void safeMethod() {
    synchronized(list) {
    ...rest of the code as shown in previous method
}
Hidden Iterators
There are certain ArrayList methods which uses Iterators in a hidden form the API user. size() and toString()
are few of them. So care must be taken to call these methods from synchronized block in case of multi-threaded scenario.
Java 8 provides a safer method to conditionally remove items from stream using a filter
List<String> names = new ArrayList(asList("munish","ravneesh", "rajneesh"));
names.removeIf(name -> "munish".equalsIgnoreCase(name));
System.out.println("names = " + names);
Though lambda makes removal quite compact, but the operation is not thread-safe and must not be used in multi-threaded environment without explicit synchronization in place.

Is Java Pure Object Oriented Language?

What is OOP (Object Oriented Programming) ?
Object-oriented programming (OOP) is a programming paradigm based on the concept of “objects”, which are data structures that contain data, in the form of fields, often known as attributes; and code, in the form of procedures, often known as methods. - Wikipedia
Java follows Object Oriented Paradigms except in few cases, which are -
  1. Java has primitive types which are not objects like int, float, char, etc. But Java has added wrapper classes for most of these that can used in Collections Framework like Integer, Double, Character, etc. So Java has support for OOP after these Wrapper classes.
  2. Java 8 added lambda expressions which are like function pointers, they are not typically allowed as per OOP
Popular Object Oriented Languages are - Python, C++, Java, .Net, Ruby, Objective-C, SmallTalk, etc.
But in my opinion, 100% object oriented doesn’t mean much, really !

Top 50 Java Interview Questions for Freshers (0-3 Years experience)

Popular Java Interview Questions for Freshers Interview (0-3 years of java experience)

Core OOP Concepts

  • Is Java pure Object Oriented Programming Language ? Check Answer
  • What is difference between String, StringBuilder and StringBuffer ?
  • Is it possible for a Java method to inline swap two int or integer values ? Discuss pass-by-reference vs pass-by-value ?
  • What is difference between JRE and JDK
  • What is difference between 32bit and 64bit JDK ? Does size of primitive type changes between these two variants ?
  • How Garbage Collection Works ? What are different Space partitions inside JVM (PermGen, Eden Space, etc)
  • If a method throws Nullpointer exception in super class, can subclass method override it to throw RuntimeException ?
    Answer : http://javainterviews.scribbleit.in/core-java/java-method-override-rules-for-runtime-exceptions

Collections Framework

Q. What is the criteria for a class to be eligible for key in Hashmap ?

Answer : http://javainterviews.scribbleit.in/core-java/class-criteria-for-making-it-hashmap-key

Q. What are benefits of making a class Immutable ? How will you make a class Immutable ?

Answer : http://javainterviews.scribbleit.in/core-java/concept-of-immutable-class-in-java-concurrency

Q. What is difference between ArrayList and Vector? Which one shall be preferred?

Answer : http://javainterviews.scribbleit.in/core-java/vector-vs-arraylist-java-collections

Q. Discuss how Hashtable works ?

Answer : http://javainterviews.scribbleit.in/core-java/discuss-internals-of-concurrent-hashmap-in-java

Q. Write code to remove entries from hashmap while iterating over it ?

Answer : http://javainterviews.scribbleit.in/core-java/add-remove-entries-from-hashmap-during-iteration

Q. What is difference between fail-safe and fail-fast iterators ? Give example of each in Java Collections framework ?

Answer : http://javainterviews.scribbleit.in/core-java/fail-safe-vs-fail-fast-iterator-in-java-collections

Concurrency & multi-threading

  • The difference between sleep and wait in Java?
  • Difference between Callable and Runnable interface ? Check Answer
  • Explain visibility and atomicity problems faced in multi-threaded environment?
  • What is use of Volatile variables in Java ? Explain working of volatile with respect to register cache & main heap memory?
  • Can volatile keyword be used to make a non-atomic operation as atomic?
  • What is difference between wait() and sleep() method in Java?
  • How will you implement a thread-safe singleton in Java?
  • Which one of the following would be easy to write? thread-safe code for for 10 threads or 2 threads?
  • How do you call wait() method? using if block or loop? Why? Provide a example for your explanation.
  • How do you take thread dump in Java on Windows and Unix machine?
  • What is a thread local variable in Java?
  • Write wait-notify code for producer-consumer problem?
  • What is an immutable object? How and why do you create an Immutable object in Java?

Database

  • How will you join two Tables A and B where data in Table B is optional, i.e. even if no matching record exists in Table B, rows of Table A shall appear in the query result ?
    Answer : Hint is Left Outer Join between A and B
  • How will you find nth highest salary from Employee Table using SQL ?

Cracking Java Interviews 3rd Edition - Table of Contents

Cracking Core Java Interviews, 3rd Edition

230+ Real Interview Questions on Core Java 8, Concurrency, Algorithms, Data Structures, Design Problems, Spring, Hibernate, Puzzles & Sample Interview Questions for Investment Banks, Startups and Product based companies.

  • Core Java (Collections, Concurrency & multi-threading, Lambda, Streams)
  • Hibernate & Spring Problems
  • OO Design Problems.
  • Data structure and Algorithm problems
This book tries to fill in the knowledge gaps for Java developers appearing for interviews in investment banking domain (RBS, BlackRock, UBS, Morgan Stanley, CitiGroup, Credit Suisse, Barclays Capital, Goldman, J.P. Morgan, Bank of America & Nomura, HSBC), product company (Oracle, Adobe, Markit), or service sector companies (Wipro, Infosys, HCL, Sapient, TCS). This book contains collection of Java related questions which are considered important for the interview preparation. A fair try has been given to address the Question, otherwise references has been provided for in depth study.

Table of Contents

Core Concepts, Spring & Hibernate14

Q 1. What are good software practices for developing Scalable, Testable and Maintainable Software ?14
Q 2. What are good books for reference on Java Programming ?14
Q 3. What is Growth Road Map for a Java Developer?15
Q 4. Why should I choose Java for Software Development? What are Pros and Cons of Java 8 ?16
Q 5. What is difference between 32 bit and 64 bit versions of Java?16
Q 6. What are four basic principles of OOP?17
Q 7. What are the key paradigms for Developing the Clean Object Oriented Code?17
Q 8. How much important is requirement gathering in software development process?17
Q 9. What is Logarithm? Why is it relevant in Software Development?19
Q 10. What do you understand by Big O notation, why is it important in software development ?20
Q 11. How would you determine the Time Complexity of a given algorithm, are there any general guidelines?21
Q 12. What is a sorting algorithm ? List down sorting algorithms by their time & memory complexity in Big O notation ? When do we call a sorting algorithm ‘Stable’?22
Q 13. Why Prime Numbers are given much importance in writing certain algorithms like hashcode()?27
Q 14. What is left shift <<, right shift >> and Unsigned right shift >>> operator in Java? How are these useful?28
Q 15. What is 2’s complement notation system for Binary Numbers?30
Q 16. How Heap space is divided in Java. How does Garbage Collector cleans up the unused Objects ? Why shouldn’t we use System.gc() command in production code?31
Q 17. What is difference between Stack and Heap area of JVM Memory? What is stored inside a stack and what goes into heap?35
Q 18. What is a Binary Tree? Where and why is this used in Java Programs?36
Q 19. Discuss implementation and uses of TreeSet Collection?36
Q 20. How does Session handling works in Servlet environment?37
Q 21. How can one handle relative context path while coding the web applications? For example, your web application may be deployed at a different context path in Tomcat, how will you make sure static/dynamic resources works well at custom context path ?38
Q 22. How will you write a Recursive Program?39
Q 23. How many elements a complete binary tree could hold for a depth of 10? 39
Q 24. Explain working of a hashing data structure, for example HashMap in Java.40
Q 25. Discuss internal’s of a concurrent hashmap provided by Java Collections Framework.41
Q 26. Why do we need Reader Classes when we already have Streams Classes? What are the benefit of using a Reader over a stream, in what scenario one should be preferred. 43
Q 27. Discuss Visitor, Template, Decorator, Strategy, Observer and Facade Design Patterns?44
Q 28. What is a strong, soft, weak and Phantom reference in Java? Where are these used?46
Q 29. What are database transaction Isolation levels?48
Q 30. What is difference between Primary key and Unique Key?49
Q 31. Why do we need indexing on Database Table Columns ?49
Q 32. What are clustered and non-clustered indexes in Sybase Database?50
Q 33. How would you handle lazily loaded entities in web application development using hibernate?50
Q 34. What are OneToOne, OneToMany and ManyToMany relationship mappings in database design?51
Q 35. How would you implement ManyToMany mappings with the self entity in JPA?52
Q 36. What is Inner Join, Left Outer Join and Right Outer Join?53
Q 37. How will you list all the Customers from Customer Table who have no Order(s) yet?54
Q 38. How would you fetch Employee with nth highest Age from Employee Table using SQL?54
Q 39. Question: What is difference between Drop, Truncate and Delete Table commands in SQL?54
Q 40. What are Inheritance strategies in JPA?55
Q 41. How will you handle Concurrent updates to an database entity in JPA i.e. when two users try to update the same database entity in parallel?55
Q 42. What are different types of Http Codes ?56
Q 43. What is difference between HTTP Redirect and Forward?56
Q 44. How will you check the owner information of a given domain name in web ?57
Q 45. What happens when you type www.google.com in your browser’s address bar from an Indian Location?58
Q 46. What is Idiom for Creating a Hibernate Transaction ?60
Q 47. Why do we need Spring Framework ?60
Q 48. What is Inversion of Control (or Dependency Injection)?60
Q 49. What is Bean Factory in Spring?61
Q 50. What is Application Context?61
Q 51. What are different types of Dependency Injection that spring support ? or in other words what are the ways to initialize beans in Spring ?61
Q 52. What are different Bean Scope in Spring ?61
Q 53. What are some important Spring Modules ?61
Q 54. How will you load hierarchy of property files in Spring Context ?62
Q 55. How to efficiently generate ID’s for an Entity in Hibernate/JPA ?62
Q 56. How to handle Bean Post Initialization and Pre Destroy Tasks in Spring Framework ? For example resource loading after bean construction and resource cleanup before shutdown of spring context ?63
Q 57. How will you handle batch insert in hibernate for optimal usage of memory, network and CPU ?64
Q 58. How will you operate on records of a large database table with million of entries in it using Hibernate ?65
Q 59. Do you think Hibernate’s SessionFactory and Session objects are thread safe ?65
Q 60. What is difference between Hibernate’s first and second level cache ?66
Q 61. What is syntax of Cron Expression ?66
Q 62. Explain Stream API introduced in Java 8 ?67
Q 63. Most useful Code Snippets in Java 8 ?68
Q 64. How will you configure custom sized ThreadPool for stream parallel operation in Java 8 ?72
Core Java Questions73
Q 65. What are new Features added in Java 8 ?73
Q 66. What is difference between method overloading, method overriding, method and variable hiding?74
Q 67. What is Order of calling constructors in case of Inheritance?75
Q 68. When should we choose Array, ArrayList, LinkedList over one another for a given Scenario and Why?76
Q 69. We have 3 Classes A, B an C. Class C extends Class B and Class B extends Class A. Each class has an method add(), is there a way to call A’s add() method from Class C ?77
Q 70. Why wait is always used inside while loop as shown in the below snippet ? Discuss all the probable reasons.
public synchronized void put(T element) throws InterruptedException {
while(queue.size() == capacity) {
wait();
}
queue.add(element);
notify();
}78
Q 71. We have a method which iterates over a Collection. We want to remove certain elements from that collection inside the loop in certain criteria is matched, How should we code this scenario ?79
Q 72. We are writing an API which will accept a Collection as an argument and duplicate an element in the Original Collection if certain criteria in met. How would you code such an API method ?80
Q 73. If hashcode() method of an object always returns 0 then what will be the impact on the functionality of software ?80
Q 74. Iterator interface provides remove() method but no add() method. What could be the reason for such behavior?
81
Q 75. What does Collections.unmodifiableCollection() do ? Is it a good idea to use it safely in multi-threading scenario without synchronization, Is it immutable ?81
Q 76. If we don’t override hashcode() while using a object in hashing collection, what will be the impact ?82
Q 77. How would you detect a DeadLock in a running program ? 82
Q 78. How would you avoid deadlock in a Java Program ?82
Q 79. Question : How would you produce DeadLock in Java ?83
Q 80. Which data type would you choose for storing currency values like Trading Price ? What’s your opinion about Float, Double and BigDecimal ?84
Q 81. How would you round a double value to certain decimal Precision and Scale ?86
Q 82. How great is the Idea of synchronizing the getter methods of a shared mutable state ? What if we don’t ?87
Q 83. Can the keys in Hashing data structure be made Mutable ?87
Q 84. Is it safe to iterate over collection returned by Collections.synchronizedCollection() method, or should we synchronize the Iterating code ?88
Q 85. What are different type of Inner classes in Java ? How to choose a type with example ?89
Q 86. When should we need a static inner class rather than creating a top level class in Java Program?89
Q 87. Is it possible to write a method in Java which swaps two int/Integer ?90
Q 88. What all collections utilizes hashcode() method ?90
Q 89. Provide a diagram for collections framework.91
Q 90. What is Immutable Class. Why would you choose it ? How would you make a class immutable ?92
Q 91. Why shouldn’t we prefer mutable static variables in our Java Code ?92
Q 92. Discuss Exception class hierarchy in Java. When should we extend our custom exception from RuntimeException or Exception ?93
Q 93. How does method parameter passing works in Java ? Does it pass-by-reference or pass-by-value ?94
Q 94. How does an ArrayList expands itself when its maximum capacity is reached ?94
Q 95. What is StringPool In Java ?94
Q 96. What is instance level locking and class level locking ?95
Q 97. Explain threading jargons ?96
Q 98. What is float-int implicit conversion while doing calculation on mixed data type in Java?97
Q 99. Discuss Comparable and Comparator ? Which one should be used in a given scenario ?97
Q 100. How would you sort a collection of data based on two properties of an entity in Java, analogical to SQL’s Order by firstField, SecondField desc ?98
Q 101. What are the best practices for handling TimeZone in database transactions ?99
Q 102. How would you convert time from One Time Zone to another in Java ?99
Q 103. Will WeakHashMap’s entry be collected if the value contains the only strong reference to the key ?100
Q 104. Why HashMap’s initial capacity must be power of two ?101
Q 105. Can we traverse the list and remove its elements in the same iteration loop ?101
Q 106. Do I need to override object’s equals() and hashcode() method for its use in a TreeMap ?101
Q 107. Implement a BlockingQueue using intrinsic locking mechanism.102
Q 108. Is there a way to acquire a single lock over ConcurrentHashMap instance ?102
Q 109. How will you implement a Blocking Queue using Lock and Condition Interface provided in JDK?102
Q 110. How would you cancel a method execution after time-out expires using Java Future?103
Q 111. Java already had Future interface, then why did they provide Completable Future class in Java 8 ?104
Q 112. What is difference between intrinsic synchronization and explicit locking using Lock ?106
Q 113. What are Stamped Locks ? How they are useful in Optimistic Scenario where thread contention is rare ?107
Q 114. What is difference between Executor’s submit() and execute() method ?109
Q 115. How will you find out first non-repeating character from a string ? For example, String input = “aaabbbeggh”, answer should be ‘e’109
Q 116. What is difference between Callable and Runnable Interface?110
Q 117. What will happen when an exception occurs from within a synchronized code block ? Will lock be retained or released ?110
Q 118. What is difference between sleep(), yield() and wait() method?110
Q 119. How does Generics work in Java? 112
Q 120. What are Upper and Lower bounds in Generics? Where to choose one?113
Q 121. Discuss memory visibility of final fields in multi-threading scenario.114
Q 122. Where would you use LinkedHashSet provided by Java Collections?116
Q 123. What do you think is the reason for String Class to be Immutable?116
Q 124. How is String concatenation implemented in Java using + operator?
for example, String name = “munish” + “chandel”116
Q 125. Which Java data type would you choose for storing sensitive information, like passwords, and Why?117
Q 126. What is difference between StringBuilder and StringBuffer ?117
Q 127. What is difference between using Serializable & Externalizable Interfaces in Java?117
Q 128. How would you design Money Class in Java?118
Q 129. Where should we use GET, PUT, POST and DELETE method?119
Q 130. What is difference between HashMap, TreeMap and LinkedHashMap?119
Q 131. How would you write high performing IO code in Java? Can you write a sample code for calculating checksum of a file in time efficient manner?120
Q 132. We have an Application and we want that only Single Instance should run for that Application. If Application is already running then second instance should never be started. How would you handle this in Java?123

Concurrency in Java

Q 133. What is Concurrency? How will you implement Concurrency in your Java Programs?124
Q 134. There are two Threads A and B operating on a shared resource R, A needs to inform B that some important changes has happened in R. What technique would you use in Java to achieve this?
SOLUTION125
Q 135. What are the different states of a Thread? What does those states tells us?126
Q 136. Question: What do you understand by Java Memory Model? What is double-checked locking? What is different about final variables in new JMM?127
Q 137. Is i++ thread-safe (increment operation on primitive types)? 131
Q 138. What happens when wait() & notify() method are called?131
Q 139. Discuss about volatile keyword and Java Memory Model?132
Q 140. What is a CAS? How does it help writing non-blocking scalable applications? Tell something about Atomic Package provided by Java 1.6133
Q 141. There is a object state which is represented by two variables. How would you write a high throughput non-blocking algorithm to update the state from multiple threads?134
Q 142. How would you implement AtomicFloat /AtomicDouble using CAS?135
Q 143. How LongAdder and LongAccumulator are different from AtomicLong & AtomicInteger ?137
Q 144. Can we implement check & update method (similar to compare and swap) using volatile alone?137
Q 145. How will you track the largest value monitored by different threads in an non-blocking fashion (using Atomic Operations) ?137
Q 146. What is difference between Fork/Join framework and ExecutorService ?138
Q 147. How does ForkJoinPool helps in writing concurrent applications ? Please provide few examples for RecursiveTask and RecursiveAction.138
Q 148. How will you calculate Fibonacci Sequence on a multi-core processor ?141
Q 149. How will you increment each element of an Integer array, utilizing all the cores of processor ?142
Q 150. You are writing a multi-threaded software piece for NSE for maintaining the volume of Trades made by its individual brokers (icici direct, reliance ). It’s highly concurrent scenario and we can not use lock based thread safety due to high demand of throughput. How would handle such scenario?143
Q 151. Calculate the time spread for 10 threads - Suppose T1 started earliest and T5 finished last, then the difference between T5 and T1 will give time spread. 144
Q 152. What are fail-fast Iterator? what is fail safe?146
Q 153. There is a stream of words which contains Anagrams. How would you print anagrams in a single bucket from that stream?147
Q 154. Describe CopyOnWriteArrayList? Where is it used in Java Applications?148
Q 155. There are M number of Threads who work on N number of shared synchronized resources. How would you make sure that deadlock does not happen?148
Q 156. Are there concurrent version for TreeMap and TreeSet in Java Collections Framework?148
Q 157. Is it safe to iterate over an ArrayList and remove its elements at the same time ? When do we get ConcurrentModificationException & hidden Iterator?149
Q 158. What is ThreadLocal class, how does it help writing multi-threading code? any usage with example?150
Q 159. How would you implement your own Transaction Handler in Core Java, using the EntityManager created in last question?151
Q 160. What is AtomicInteger class and how is it different than using volatile or synchronized in a concurrent environment?152
Q 161. You are writing a server application which converts microsoft word documents into pdf format. Under the hood you are launching a binary executable which does the actual conversion of document. How would you restrict the parallel launch of such binaries to 5 in Java, so as to limit the total load on the server.153
Q 162. What are common threading issues faced by Java Developers?155
Algorithms & Data Structures 156
Q 163. ​Given a collection of 1 million integers ranging from 1 to 9, how would you sort them in Big O(n) time?156
Q 164. Given 1 million trades objects, you need to write a method that searches if the specified trade is contained in the collection or not. Which collection would you choose for storing these 1 million trades and why?157
Q 165. I have an Integer array where every number appears even number of time except one. Find that number.157
Q 166. how would you check if a number is even or odd using bit wise operator in Java?158
Q 167. How would you check if the given number is power of 2?158
Q 168. What is a PriorityQueue? How is it implemented in Java? What are its uses?159
Q 169. What is difference between Collections.sort() and Arrays.sort()? Which one is better in terms of time efficiency?160
Q 170. There are 1 billion cell-phone numbers each having 10 digits, all of them stored randomly in a file. How would you check if there exists any duplicate? Only 10 MB RAM is available to the system.160
Q 171. What is a Binary Search Tree? Does Java provide implementation for BST? How do you do in-order, pre-order and post-order Traversal of its elements?161
Q 172. What is technique to sort data that is too large to bring into memory ?162
Q 173. Check if a binary tree is a Binary Search Tree or not?162
Q 174. How would you convert a sorted integer array to height balanced Binary Search Tree?
Input: Array {1, 2, 3}
Output: A Balanced BST
2
/ \
1 3163
Q 175. How would you calculate depth of a binary tree?164
Q 176. Calculate factorial using recursive method.164
Q 177. How will you swap two numbers using XOR operation?
SOLUTION164
Q 178. You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger. But it is not possible to directly compare two nuts or two bolts. Given an efficient method for solving the problem.165
Q 179. Your are give a file with 1 million numbers in it. How would you find the 20 biggest numbers out of this file?165
Q 180. Reverse the bits of a number and check if the number is palindrome or not? 166
Q 181. How would you mirror a Binary Tree?166
Q 182. How to calculate exponentiation of a number using squaring for performance reason?166
Q 183. How will you implement a Queue from scratch in Java?168
Q 184. How will you Implement a Stack using the Queue?169
Q 185. How would you implement a simple Math.random() method for a given range say (1-16)?170
Q 186. How an elevator decides priority of a given request. Suppose you are in an elevator at 5th floor and one person presses 7th floor and then 2nd presses 8th floor. which data structure will be helpful to prioritize the requests? 170
Q 187. How would you multiply a number with 7 using bitwise hacks?171
Q 188. What is best way to search an element from a sorted Integer Array? What will be its time complexity?171
Q 189. How would you reverse a Singly linked List?172
Q 190. How would you count word occurrence in a very large file ? How to keep track of top 10 occurring words?173
Q 191. What is difference between synchronized HashMap and a hashtable?176
Q 192. What is difference between Iterator and LisIterator?176
Q 193. What do you understand by Token Bucket Algorithm. What is its use ?177
Q 194. How will you implement fibonacci series using Iterative & Recursive approach in Java 8 ?179
Q 195. How will you write a multi-threaded HttpDownloader program using Java 8 ?182
Q 196. How will you find first non-repeatable character from a String using Java 8 ?183
Q 197. How will you find Word Frequency in sorted order for a collection of words ?183
Q 198. How will you calculate MD5 hash of a given String in Java ?184

Object Oriented Design

Q 199. What are the key principles when designing a software for performance efficiency ?185
Q 200. How would you describe Producer Consumer problem in Java ?185
Q 201. How would you implement a Caching for HttpDownloader Task using Decorator Design Pattern ?187
Q 202. Write Object Oriented design for library management system.188
Q 203. Design ATM machine.190
Q 204. Design a web crawler that will crawl for links(urls).191
Q 205. Design Phone Book for a mobile using TRIE (also known as prefix tree).192
Q 206. How would you resolve task’s inter dependency, just as in maven/ant.
Let’s consider the following task dependencies.
Here first row states that task 3 is dependent on task 1 and task 5, and so on. If the two consecutive tasks have no dependency, then they can be run in any order.
The output should look like - [1, 5, 3, 2 ,4] or [1, 5, 3, 4, 2]194
Q 207. How would you sort 900 MB of data using 100 MB of RAM ?
What is external sort ?198
Q 208. How would you design minimum number of platforms so that the buses can be accommodated as per their schedule ?
Bus Schedule for a given Platform201
Q 209. There is a pricing service which connects to Reuters & Bloomberg and fetches the latest price for the given Instrument Tics. There could be multiple price events for the same Stock and we need to consider the latest one. Design a service to show prices for the Top 10 stocks of the Day ?203
Q 210. Design a parking lot where cars and motorcycles can be parked. What data structure to use for finding free parking spot in Parking Lot program? Assume there are million of parking slots.203
Q 211. Implement the classes to model two pieces of furniture (Desk and Chair) that can be constructed of one of two kinds of materials (Steel and Oak). The classes representing every piece of furniture must have a method getIgnitionPoint() that returns the integer temperature at which its material will combust. The design must be extensible to allow other pieces of furniture and other materials to be added later. Do not use multiple inheritance to implement the classes.205
Q 212. How would you simulate a digital Clock in Object Oriented Programming Language?207
Q 213. How would you design an elevator system for multi story building? Provide with request scheduling algorithm & Class diagram for the design.210
Q 214. Given two log files, each with a billion username (each username appended to the log file), find the username existing in both documents in the most efficient manner?210
Q 215. Design DVD renting system, database table, class and interface.211

Puzzles & Misc

Q 216. Why man holes are round in shape ?212
Q 217. Solve two egg problem ?212
Q 218. There are 100 doors all closed initially.
1st iteration opens all doors (1x multiplier)
2nd iteration opens 2,4,6,8 .. doors (2x multiplier)
3rd iteration opens 3,6,9,12 … doors (3x multiplier) and so on.
In the end of 100 iterations, which all doors will be in open state ?213
Q 219. What is probability of a daat, hitting closer to centre of a circle rather than circumference ?214
Q 220. What is financial Instrument, Bond, equity, Asset, future, option, swap and stock with example each ?214
Q 221. Toolkit & Resources for a Java Developer.215
Q 222. Sample Unsolved Interview Questions.216
Q 223. Sample Unsolved Puzzles ?221
Q 224. Few sample UNIX questions.224
Q 225. Top Java Interview Questions ?226
Q 226. What is the Typical Interview Coverage for Core Java Candidate ?227
Q 227. What is the art of writing resume ?227
Q 228. Sample Questions on Swings framework.228
Q 229. What are the Interview questions that most candidates answer wrongly ?


Buy my ebook from Shunya Foundation -
http://shunyafoundation.com/cracking-java-interviews-3rd-edition-ebook

Tuesday, January 19, 2016

What is difference between HashMap, LinkedHashMap and TreeMap?

All three classes (HashMap, TreeMap and LinkedHashMap) implements Map interface, and therefore represents mapping from unique key to values. But there are different usage scenarios for each of them -

1. HashMap is a hashing data structure which works on hashcode of keys. Keys must provide consistent implementation of equals() and hashCode() method in order to work with hashmap. 

Time complexity for get() and put() operations is Big O(1).

2. LinkedHashMap is also a hashing data structure similar to HashMap, but it retains the original order of insertion for its elements using a LinkedList. Thus iteration order of its elements is same as the insertion order for LinkedHashMap which is not the case for other two Map classes. Iterating over its elements is lightly faster than the HashMap because it does not need to traverse over buckets which are empty.

LinkedHashMap also provides a great starting point for creating a LRU Cache object by overriding the removeEldestEntry() method, as shown in the following code snippet.

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

Time complexity for get() and put() operations is Big O(1).

3. TreeMap is a SortedMap, based on Red-Black Binary Search Tree which maintains order of its elements based on given comparator or comparable. 

Time complexity for put() and get() operation is O (log n).