Q. Why string is immutable in java?

The string is Immutable in Java because String objects are cached in String pool. Since cached String literals are shared between multiple clients there is always a risk, where one client’s action would affect all another client.

Since string is immutable it can safely share between many threads and avoid any synchronization issues in java.

Q. What is Java String Pool?

String Pool in java is a pool of Strings stored in Java Heap Memory. String pool helps in saving a lot of space for Java Runtime although it takes more time to create the String.

When we use double quotes to create a String, it first looks for String with the same value in the String pool, if found it just returns the reference else it creates a new String in the pool and then returns the reference. However using new operator, we force String class to create a new String object in heap space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**
* Java program to illustrate String Pool
*
**/
public class StringPool {

    public static void main(String[] args) {
        String s1 = "Java";
        String s2 = "Java";
        String s3 = new String("Java");
        
        System.out.println("s1 == s2 :" +(s1==s2)); // true
        System.out.println("s1 == s3 :" +(s1==s3)); // false
    }
}

Q. What is the difference between abstraction and encapsulation?

• Abstraction solves the problem at design level while Encapsulation solves it implementation level.
• In Java, Abstraction is supported using interface and abstract class while Encapsulation is supported using access modifiers e.g. public, private and protected.
• Abstraction is about hiding unwanted details while giving out most essential details, while Encapsulation means hiding the code and data into a single unit e.g. class or method to protect inner working of an object from outside world.

Q. Can there be an abstract method without an abstract class?

Yes. because methods in an interface are also abstract. so the interface can be use to declare abstract method.

Q. Can we use private or protected member variables in an interface?

The java compiler adds public and abstract keywords before the interface method and public, static and final keyword before data members automatically

1
2
3
4
5

public interface Test {
   public string name1;
   private String email;
   protected pass;
}

as you have declare variable in test interface with private and protected it will give error. if you do not specify the modifier the compiler will add public static final automatically.

1
2
3
4
5

public interface Test {
   public static final string name1;
   public static final  String email;
   public static final pass;
}

• interfaces cannot be instantiated that is why the variable are static
• interface are used to achieve the 100% abstraction there for the variable are final
• An interface provide a way for the client to interact with the object. If variables were not public, the clients would not have access to them. that is why variable are public

Q. When can an object reference be cast to a Java interface reference?

An interface reference can point to any object of a class that implements this interface

interface Foo {
  void display();
}

public class TestFoo implements Foo {

    void display() {
      System.out.println("Hello World");
    }

    public static void main(String[] args) {
      Foo foo = new TestFoo();
      foo.display();
    }
}

Q. What is difference between Heap and Stack Memory in java?

Java Heap Space

Java Heap space is used by java runtime to allocate memory to Objects and JRE classes. Whenever we create any object, it’s always created in the Heap space.

Garbage Collection runs on the heap memory to free the memory used by objects that doesn’t have any reference. Any object created in the heap space has global access and can be referenced from anywhere of the application.

Java Stack Memory

Stack in java is a section of memory which contains methods, local variables and reference variables. Local variables are created in the stack.

Stack memory is always referenced in LIFO (Last-In-First-Out) order. Whenever a method is invoked, a new block is created in the stack memory for the method to hold local primitive values and reference to other objects in the method.

As soon as method ends, the block becomes unused and become available for next method. Stack memory size is very less compared to Heap memory.

Difference

Q. What is DAO factory design pattern in Java?

Data Access Object Pattern or DAO pattern is used to separate low level data accessing API or operations from high level business services.

DAO pattern is based on abstraction and encapsulation design principles and shields rest of application from any change in the persistence layer e.g. change of database from Oracle to MySQL, change of persistence technology e.g. from File System to Database.

Q. What are the differences between ResultSet and RowSet?

A ResultSet maintains a connection to a database and because of that it can’t be serialized and also we cant pass the Resultset object from one class to other class across the network.

RowSet is a disconnected, serializable version of a JDBC ResultSet and also the RowSet extends the ResultSet interface so it has all the methods of ResultSet. The RowSet can be serialized because it doesn’t have a connection to any database and also it can be sent from one class to another across the network.

Q. How can we execute stored procedures using CallableStatement?

CallableStatement interface in java is used to call stored procedure from java program. Stored Procedures are group of statements that we compile in the database for some task. Stored procedures are beneficial when we are dealing with multiple tables with complex scenario and rather than sending multiple queries to the database, we can send required data to the stored procedure and have the logic executed in the database server itself.

A CallableStatement object provides a way to call stored procedures using JDBC. Connection.prepareCall() method provides you CallableStatement object.

Q. What are the differences between Statement and PreparedStatement interface?

JDBC API provides 3 different interfaces to execute the different types of SQL queries. They are,

• Statement – Used to execute normal SQL queries.
• PreparedStatement – Used to execute dynamic or parameterized SQL queries.
• CallableStatement – Used to execute the stored procedures.

1. Statement

Statement interface is used to execute normal SQL queries. We can’t pass the parameters to SQL query at run time using this interface. This interface is preferred over other two interfaces if we are executing a particular SQL query only once. The performance of this interface is also very less compared to other two interfaces. In most of time, Statement interface is used for DDL statements like CREATE, ALTER, DROP etc.

2. PreparedStatement

PreparedStatement is used to execute dynamic or parameterized SQL queries. PreparedStatement extends Statement interface. We can pass the parameters to SQL query at run time using this interface. It is recommended to use PreparedStatement if we are executing a particular SQL query multiple times. It gives better performance than Statement interface. Because, PreparedStatement are precompiled and the query plan is created only once irrespective of how many times we are executing that query.

3. CallableStatement

CallableStatement is used to execute the stored procedures. CallableStatement extends PreparedStatement. Usng CallableStatement, we can pass 3 types of parameters to stored procedures. They are : IN – used to pass the values to stored procedure, OUT – used to hold the result returned by the stored procedure and IN OUT – acts as both IN and OUT parameter. Before calling the stored procedure, we must register OUT parameters using registerOutParameter() method of CallableStatement. The performance of this interface is higher than the other two interfaces. Because, it calls the stored procedures which are already compiled and stored in the database server.

Q. What are the different types of locking in JDBC?

The types of locks in JDBC:

1. Row and Key Locks: Useful when updating the rows (update, insert or delete operations), as they increase concurrency.

2. Page Locks: Locks the page when the transaction updates or inserts or deletes rows or keys. The database server locks the entire page that contains the row. The lock is made only once by database server, even more rows are updated. This lock is suggested in the situation where large number of rows is to be changed at once.

3. Table Locks: Utilizing table locks is efficient when a query accesses most of the tables of a table. These are of two types:
a) Shared lock: One shared lock is placed by the database server, which prevents other to perform any update operations.

b) Exclusive lock: One exclusive lock is placed by the database server, irrespective of the number of the rows that are updated.

4. Database Lock: In order to prevent the read or update access from other transactions when the database is open, the database lock is used.

JDK7

1. 域变量
   默认初始大小：16
   最大长度：1 << 30
   默认加载因子：0.75f
   modCount: 对Map的iterator()操作做一致性校验，如果在iterator操作过程中，map的数值有修改，直接抛出ConcurrentModiifcationException异常
   threshold: table.length * loadFactor。

2. put()方法

   • 如果Key为null，统一放在下标为0的bucket，即table[0]位置的链表，如果是第一次对key=null做put操作，将会在table[0]的位置新增一个Entry节点，使用头插法做链表插入。调用的是putForNullKey()方法:首先选择table[0]位置的链表，然后对链表做遍历操作，如果有节点的key为null，则用新值覆盖旧值，并且返回旧值，否则新增一个key为null的Entry节点。

3. 扩容

   • 扩容后的大小是扩容前的两倍
   • 将数据从旧table迁移到扩容后的新table。为避免碰撞过多，先决策是否需要对每个Entry链表节点重新hash，然后根据hash值计算得到bucket下标，然后用头插法做节点迁移。

4. hash值的计算

   • 使用key的hashCode作为算式(arithmetic)的输入，得到了hash值。
   • 对于两个对象，如果hashCode相同，那么hash值就一定相同。
   • 如果两个对象逻辑相等（内存地址相同），那么hashCode一定相等，反之不一定成立。

5. bucket下标的计算

   • 取模：h & (length-1) h为hashCode
6. hashCode()和hash值
   • Java中hashCode()方法是用来生成hashCode值,hashCode值是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。
   • 把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是哈希值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

7. 为什么HashTable的大小控制为2的幂次数

   • 降低碰撞的概率，使散列更均匀，根据bucket下标的计算公式，当哈希表的长度为2的次幂时，等同于使用表长度对hash值取模，散列更均匀。
   • 表的长度为2的次幂，那么(length-1)的二进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能是1也可能是0，换句话说取模的结果既有奇数又有偶数。
   • 此时h & (length-1)就是h % length

8. get()方法

   • 通过key的hash值计算bucket的下标，然后遍历对应bucket上的链表，得到结果。

9. 遍历Map的方式

   • Iterator迭代器
   • for(Map.Entry entry : testMap.entrySet())
   • foreach(JDK1.8才有，不推荐，因为底层就是方式2)
   • 获取keySet()的迭代器遍历
     以上的底层都是迭代器

10. Iterator的实现

    • HashMap中增加了一个内部类HashIterator，循环哈希table，直到找到不为空的bucket为止。

11. fail-fast策略

    • 在系统设计中，当遇到可能会诱导失败的条件时立即上报错误。
    • modCount域变量用于实现hashMap中的fail-fast。

JDK8

相比与JDK7，JDK8中的HashMap会将较长的链表(大于8)转为红黑树。

1. put()

   • 在JDK7中，新增节点使用的是头插法，但在JDK8中，在链表使用尾插法，防止死链。
   • 若hashTable为null或长度为0，则扩容。
   • 根据index找到bucket，若bucket上没有节点，那么直接新增一个节点，赋给bucket。
   • 若当前bucket上有链表，且头节点匹配，则直接替换。
   • 若当前bucket上为树结构则转为红黑树的插入操作。
   • 若以上都不成立，则对链表进行遍历：有则替换，无则末尾添加。
   • 如果链表长度大于TREEIFY_THRESHOLD，则执行红黑树转换操作。

2. 扩容

   • 如果hashTable为null或长度为0，如果Map中存储的k-v对数量超过了threshold，则触发扩容
   • 不同于JDK7，JDK8在做数据迁移的时候保持了顺序(preserve order)
   • 新的索引值要么和原来的索引值一样，要么是原索引值的两倍，因为h & (length-1)中length-1的低位全是1。例如原先的hashCode为:1010 … 11101(共32位)，将长度从16扩容到32，length-1从1111变为11111，然后根据公式做按位与，得出的结果后四位是一样的，第一位取决于hashCode对应位置上的值。

3. get()

   • 根据key计算hash值，进一步计算得到hashTable的目标index，若此bucket上为红黑树，则在红黑树上查找，否则遍历链表。

HashMap、HashTable

1. HashMap vs HashTable

   • HashMap is non synchronized. It is not-thread safe and can’t be shared between many threads without proper synchronization code whereas Hashtable is synchronized. It is thread-safe and can be shared with many threads.
   • HashMap allows one null key and multiple null values whereas Hashtable doesn’t allow any null key or value.
   • HashMap is generally preferred over HashTable if thread synchronization is not needed

2. Why HashTable doesn’t allow null and HashMap does?
   To successfully store and retrieve objects from a HashTable, the objects used as keys must implement the hashCode method and the equals method. Since null is not an object, it can’t implement these methods. HashMap is an advanced version and improvement on the Hashtable. HashMap was created later.

3. Why HashMap is not thread-safe?

   • Ideologically
     A hash map is based on an array, where each item represents a bucket. As more keys are added, the buckets grow and at a certain threshold the array is recreated with a bigger size, its buckets rearranged so that they are spread more evenly (performance considerations).

   • Technically
     It means that sometimes HashMap#put() will internally call HashMap#resize() to make the underlying array bigger.

   • HashMap#resize() assigns the table field a new empty array with a bigger capacity and populates it with the old items. While this population happens, the underlying array doesn’t contain all of the old items and calling HashMap#get() with an existing key may return null.

其他

1. HashCode怎么算的?
   • memory reference of object in integer form
2. equals()
   • compare the key whether the are equal or not

Q. What is difference between HashMap and Hashtable?

HashMap and Hashtable both are used to store data in key and value form. Both are using hashing technique to store unique keys.

ConcurrentModificationException异常

1
2
3
4
5
6
7
8
9
10

List<String> strings = new ArrayList<String>();
Iterator<String> iterator = strings.iterator();

// 添加元素
// strings.add("...")
// ...

while(iterator.hasNext()){
    System.out.println(iterator.next());
}

错误信息：

1
2
3

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)

分析异常

  问题出现在两个方法上:checkForComodification()和next()，后者是我在程序中调用的方法，前者之前没见过，我决定从头开始查找源码问题。

创造迭代器

  例子中通过strings.iterator()返回一个迭代器，其中strings是一个ArrayList的实例。
  查找ArrayList的源码，并没有iterator()方法，于是找到其父类AbstractList中:

1
2
3

public Iterator<E> iterator() {
        return new Itr();
    }

也就是说创造一个迭代器返回的是一个Itr类型对象的引用。
  来看Itr:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

private class Itr implements Iterator<E> {
    
    int cursor = 0;
  
    int lastRet = -1;

    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size();
    }

    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

其中的成员变量：
cursor: 游标，表示下一个要访问的元素的索引，在next方法中会自增
lastRet: 上一个元素的索引
expectedModCount: 表示对ArrayList修改次数的期望值，初始值为modCount
modCount: AbstractList类中的一个成员变量，表示对List的修改次数(structurally modified)，每次add()和remove()就会加1

解决错误

在Itr的源码中可以看到，迭代器中的操作都要先执行checkForComodificatioin()方法来确定modCount!=expectedModCount,这是保护ArrayList的机制，防止返回错误结果。

错误的原因可能在于创建迭代器之后添加元素也算是产生了结构性的变化。

Q. What is the difference between fail-fast and fail-safe iterator?

fail-fast Iterator

Iterators in java are used to iterate over the Collection objects.Fail-Fast iterators immediately throw ConcurrentModificationException if there is structural modification of the collection. Structural modification means adding, removing or updating any element from collection while a thread is iterating over that collection. Iterator on ArrayList, HashMap classes are some examples of fail-fast Iterator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.ArrayList;
import java.util.Iterator;
 
public class FailFastIteratorExample 
{       
    public static void main(String[] args) {

        //Creating an ArrayList of integers
        ArrayList<Integer> list = new ArrayList<Integer>();
         
        //Adding elements to list
        list.add(1452);
        list.add(6854);
        list.add(8741);
                 
        //Getting an Iterator from list
        Iterator<Integer> it = list.iterator();
         
        while (it.hasNext()) {
            Integer integer = (Integer) it.next();
            list.add(8457);      //This will throw ConcurrentModificationException
        }
    }   
}

Output

1
2
3
4

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at pack1.MainClass.main(MainClass.java:32)

fail-safe Iterator

Fail-Safe iterators don’t throw any exceptions if a collection is structurally modified while iterating over it. This is because, they operate on the clone of the collection, not on the original collection and that’s why they are called fail-safe iterators. Iterator on CopyOnWriteArrayList, ConcurrentHashMap classes are examples of fail-safe Iterator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;
 
public class FailSafeIteratorExample 
{       
    public static void main(String[] args) {

        //Creating a ConcurrentHashMap
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<String, Integer>();
         
        //Adding elements to map
        map.put("ONE", 1);
        map.put("TWO", 2);
        map.put("THREE", 3);
         
        //Getting an Iterator from map
        Iterator<String> it = map.keySet().iterator();
         
        while (it.hasNext()) {
            String key = (String) it.next();
            System.out.println(key+" : "+map.get(key));
            map.put("FOUR", 4); //This will not be reflected in the Iterator
        }
    }   
}

Output

1
2
3
4

TWO : 2
FOUR : 4
ONE : 1
THREE : 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null) {return true;}
        return helper(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }
    public static boolean helper(TreeNode root, long max, long min) {
        if(root==null) {return true;}
        if(root.val>min && root.val<max){
            return helper(root.left,root.val,min) & helper(root.right,max,root.val);
        }
        return false;
        
    }
}

利用左节点小于根节点，右节点大于根节点的性质，不断更新max和min的值，来限定当前节点值的范围，使用Long的原因是因为有些奇怪的测试用例，比如：[2147483647]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int numTrees(int n) {
        if(n==0) {return 0;}
        int[] res = new int[n+1];
        res[0] = 1;
        res[1] = 1;
        for(int i = 2; i < n+1; i++) {
            for(int j = 1; j<= i; j++) {
                res[i] += res[i-j] * res[j-1];
            }
        }
        return res[n];
    }
}

1. 确定一个根节点
2. 小于根节点的值组成左子树，大于根节点的值组成右子树
3. 左子树的组合总数乘以右子树的组合总数，即为当前根节点可能形成的树的总数。

举例：
当n=6，选取根节点为i=3的时候，此时树的可能性为[1,2]组成子树的可能[4,5,6]组成子树的可能,实际上[4,5,6]组成子树的总数就等于[1,2,3]组成子树的总数。
因此可以得出dp公式 F(i, n) = G(i-1) G(n-i)，其中G(i-1)就是左子树，G(n-i)就是右子树。

参考：https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i) 下用户@lizhu5058的解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n<=0) {return new ArrayList<>();}
        return helper(1,n);
    }
    
    public static List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if(end<start) {res.add(null);}
        for(int i = start; i<=end; i++) {
            List<TreeNode> leftList = helper(start,i-1);
            List<TreeNode> rightList = helper(i+1,end);
            for(TreeNode leftNode:leftList) {
                for(TreeNode rightNode:rightList) {
                    // 为了避免重复的答案，在循环中新建一个root
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res; 
    }
}

1. 确定根节点
2. 小于根节点的值生成左子树，大于根节点的值生成右子树
3. 左子树和右子树进行排列组合

递归

94.Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null) {return new ArrayList<>();}
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, List<Integer> res){
        if(root==null) {return;}
        helper(root.left,res);
        res.add(root.val);
        helper(root.right,res);
    }
}

144.Binary Tree Preorder Traversal

1
2
3
4
5
6

public static void helper(TreeNode root, List<Integer> res) {
        if(root==null) {return;}
        res.add(root.val);
        helper(root.left,res);
        helper(root.right,res);
    }

145.Binary Tree Postorder Traversal

1
2
3
4
5
6

public static void helper(TreeNode root, List<Integer> res) {
        if(root==null) {return;}
        helper(root.left,res);
        helper(root.right,res);
        res.add(root.val);
    }

递归方法只需要根据要求改变递归的顺序即可，当递归执行到空节点时返回即可，res.add()保证了每次递归都会添加当前节点，通过调整位置来实现不同序的遍历。

复杂度分析

• 时间复杂度：O(n)。递归函数 T(n) = 2T(n/2)+1。
• 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。