30 Java Beginner Level Algorithms Interview Questions & Answers

This question tests your understanding of both an array and stack data structures.

Stack is a Last-In-First-Out (LIFO) data structure. All element operations are on one end of the stack, called the stack top. An entry can not be reached as long as there are entries on top of it, i.e. entries inserted after itself.

An array can be used by adding elements to its consecutive cells starting from its first cell at index 0. In such an implementation, a pointer variable, say `stackTop`, should be maintained always to point to the next available cell, i.e. the index that is 1 greater than the index of last element inserted to the stack. So by this, all array cells with indexes less than stackTop hold entries in them, and all those with greater indexes are empty.

The following code shows the overall logic of the 3 main stack operations. The boilerplate code to cover the edge cases that the stack is full or empty are omitted.

Object[] stack = new Object[MAX_STACK_SIZE]; 
int stackTop = 0;

When a new entry is made to the stack, i.e. `push(entry)` operation, it is placed at the cell that `stackTop` currently shows. The `stackTop` value is incremented after that:

stack[stackTop++]=entry;

`pop()` operation removes and returns the element at the top of the stack. It is the logical inverse of `push()`:

return stack[--stackTop];

`peek()` returns the top element like `pop()` does, but without removing it:

return stack[stackTop];

Each of these operations have the complexity O(1), which is the complexity of core stack data structure. O(1) is called constant time. The time taken is not dependent on the size of the input.

This question tests your understanding of trees in general, and the binary search tree structure in relation to its use.

A binary tree (or any tree for this case) of height K can have as few as K+1 nodes with only one of them a leaf. This is the case that the tree is in the shape of a linked list - all of its nodes but the single leaf have exactly one child. So, the minimum possible value of N is 1, regardless of the value of K.

A tree of specific height has maximum number of leaf nodes when it is full, i.e. all of its tree levels have as many nodes as there can be. A binary tree of height K has K+1 levels, with the root node at the top level.

On a full tree, every node except the leaves have 2 child nodes. When this is the case, the number of nodes are doubled from one level to the next-- root is the only node at level-0, level-1 has 2 nodes, .. level-K has 2*K nodes. The maximum possible number of leaf nodes on a binary tree of height K is 2*K.

The answer wouldn't change for the binary search tree structure. The updates on a binary search tree do not impose any limitations on its structure. The two extreme cases described above can occur in binary search trees as well.

This is an open-ended question to test your knowledge of in-place algorithms also to see whether it is thorough enough for you generate an example explaining it.

An in-place algorithm is an algorithm that doesn't use additional memory to process the input while it could use the input itself for its execution. The purpose of an in-place algorithm is to save memory space during execution.

A typical example is reversing an array. Consider an algorithm to reverse the values stored in an array `inArray` so that, in the `outArray` the first cell will hold value at the last cell of `inArray`, the second cell will hold the value at second-from-last cell of `inArray`, .. and so forth. Following is a way of coding this:

public static String[] reverse(String[] inArray) {
		String[] outArray = new String[inArray.length];
		for (int i=0; i<inArray.length; i++)
			outArray[outArray.length-i-1]=inArray[i];
		return outArray;
	}

The method `reverse()` declares and uses an array as large as its parameter array. However, a solution can be worked out on `inArray` itself without generating another array for storing the result of the algorithm or any of its intermediary steps. The following code is the in-place version of the `reverse()` method. `reverseInPlace()` provides an in-place solution without degrading the runtime efficiency:

"Whenever the hashCode() of two objects return the same value, their equals() method invoked on one another must return true."

This question explores your understanding of the <Key,Value> entry structure of HashMap for its efficient use. This question also relates to the overall understanding of hashCode() & equals() contract.

At first glance, this rule seems like the hashCode()&equals() contract but it isn't, nor is it any part of this contract. This rule is to avoid a poorly implemented hashCode().

hashCode of a key object, i.e. the value returned by its hashCode() method is the value internally used by HashMap to decide which bucket to place the entry with that key. If hashCode-s of two objects are equal even though these two objects are not equal to the outside world (i.e. their equals() method don't return true on one another), these two objects collide. They are placed into the same bucket even though they aren't equal by the business logic. When this happens, the access time of HashMap degrades, because it requires extra time to sift through the entries in a bucket even when the bucket of that entry is found.

Eg.: Consider the extreme case that hashCode() method returns a constant value for all objects. MyKey.hashCode() in teh following code is such an example. The hashCode-s of all MyKey objects are equal even when the objects aren't equal by the application logic:

	class MyKey{
		...
		public int hashCode() {
			return 5;
		}
		...
	}

If the class MyKey is used for the Key type in a HashMap<Key,Value>, then all the entries would go to a single bucket of this HashMap and its access time would no longer be O(1).

Debugging and root cause analysis are vitally important aspects of being a software developer. Often more time is spent debugging and analyzing other people's code than is spent writing new code.

In this question, the interviewer examines your familiarity with the basic concepts of the HashMap structure so as to put it into effective use. They also want to see how you break down an issue and identify why this happens and what happens if this occurs.

A collision is 2 or more entries going into the same bucket in HashMap.

A bucket in a HashMap is a cell of the array backing up that HashMap. Which bucket the new entry will go to depends on the key of that entry. In the ideal case, each entry is placed into an empty bucket so that there are no collisions. However, there is no 100% guarantee to avoid collisions especially for poorly overridden hashCode() of the key.

When a collision happens, i.e. when a new entry goes to an already occupied bucket, it is kept there as an additional entry. In Java 1.7 and earlier, these colliding entries were kept as a linked list. Since Java 1.8, they still are kept as a list if they are few in number. When the number of colliding entries exceeds 8, Java 1.8+ tears down the list and forms a binary search tree to store them. A binary search tree is preferred in such a case to take advantage of its faster access time, O(log n), as opposed to linear (O(n)) access of the list.

This question examines your understanding of the <Key,Value> entry pair of HashMap.

Yes, you can. Only the keys in <Key, Value> pairs have to be unique. A Value can be stored in two or more entries in a HashMap, each time with a different Key. HashMap doesn't have any control values.

An interviewer wants to determine if you understand the fundamentals of HashMap. They will often ask a question similar to this and expect you to elaborate and talk more about the methods of HashMap such as; put() or remove().

This demonstrates deeper understanding and allows you to showcase your knowledge and thinking process. Technical interviewers like to hear more detail than they originally asked for.

This question examines your understanding of a balanced binary search tree which is an important data structure for storing ordered values.

A binary tree is a tree where each node has at most 2 children and thus 2 subtrees rooted at these children. In a balanced binary tree, the difference between the heights of these two subtrees is kept less than a small constant. With this, the tree tends to fill its current levels, i.e., tends to be a full tree before it grows vertically in height. The access time of a full tree is O(log (n)) and is fastest possible. In an ordinary binary tree, on the other hand, there isn't any control on the structure and the tree can grow only in depth, like a linked list, making its access time O(n).

The balanced binary tree has additional overhead for maintaining its balance upon insertions and deletions. Still, the improved access time makes the balanced tree much more preferable especially in the applications where the tree entries are looked up more often than updates.

It impresses technical interviewers when you define the best and worst case scenarios in terms of time complexity for a given data structure. It is a good way to take control of the interview and demonstrate your extra knowledge in other areas. For example, in answering this question it may be beneficial to also outline that due to the structure of a balanced binary tree the time complexity will always be O(log (n)). The same cannot be said for a binary search tree. This is why in certain scenarios a balanced binary tree is preferrable.

This question tests your understanding of the key-value entry pair structure of HashMap.

No, duplicate keys are not allowed in HashMap. The key in a <Key,Value> entry pair is a unique reference to the Value, also to the location of that pair in the HashMap. When there is an attempt to put an entry with an existing key, the existing entry will be replaced with the new one. In such a case, the `put()` method of HashMap returns the existing entry that has been deleted.

HashMap does not allow for duplicate keys however, it does allow duplicate values. This means there can be multiple different keys with the same values.

HashMap also allows a null key, however as this is a key there can only be one null key per HashMap. You can have multiple null values.

This question relates to understanding the memory usage of 3 of the most frequently used data structures in Java.

LinkedList is the most memory efficient data structure among the 3.

ArrayList stores its entries on an array of fixed size. It is very likely that some of the cells of this array aren't used, and thus the memory allocated to these cells is wasted.

HashMap also stores the entries in an array. HashMap wastes even more memory than ArrayList in order to avoid collisions. The length of the internal array of HashMap is always kept larger than the number of its entries so that a new entry to be made is less likely to be placed in an already occupied cell.

LinkedList, on the other hand, keeps as much memory as the object it keeps as its elements and doesn't waste additional memory.

The interviewer in a technical interview really wants to see if you understand data structures and some of the pros and cons when using them. As a Java developer it is very important to have a well reasoned thought process when selecting what data structure is best for your specifications.

When selecting data structures to use for a specific situation it is often best to ask yourself what will make my code more readable and will satisfy the performance requirements of the task.

		Stack<Integer> myStack = new Stack<>();
		
		myStack.push(1);
		myStack.push(2);
		myStack.peek();
		myStack.push(2);
		myStack.push(1);
		myStack.pop();

This question tests your understanding of the stack data structure and its operations.

The answer is 1 2 2. `push(int)` operation inserted its parameter to the top of the stack, `pop()` removed the entry at the stack top. `peek()` doesn't update the stack content.

Also note that a stack is a list structure and can store duplicate values.

A follow up question often asked in technical interviews about Stacks is to explain the difference between LIFO and FIFO. LIFO stands for Last In First Out and refers to the element that is removed using the `pop()` method. Therefore if an integer is last to be pushed to a Stack it will be the element that is removed when the `pop()`method is called.

The Stack in this example is an example of LIFO.

FIFO stands for First In First Out. If the stack in this example was FIFO then the answer to this question would be: 221. This is due to the `pop()` method removing the first entry to the stack which in this case was 1. Hence first in first out.

Technical interviewers often ask slight variations of questions after you give the correct answer in order to test your knowledge of other concepts or terminology.

This question tests your understanding of 3 of the frequently used data structures in Java - LinkedList, ArrayList and HashMap.

ArrayList and HashMap are backed by an array.

ArrayList is a list structure that is implemented on an array. It uses the direct indexing feature of arrays to provide constant time access to list elements by their positions.

HashMap is also backed by an array for the advantage of its direct index (positional) access. However, HashMap puts this advantage at use for accessing the entries by the key objects without having to know their positional indices in the internal array.

HashMap achieves this by using a hash function that turns each key object into an array index. With this, the HashMap users store, access and update the entries in an array only by using keys that are relevant and meaningful in the business logic.

This question relates to your understanding of algorithmic complexity concepts and Big-O notation.

O(1/n), O(n^2) and O(log n). A polynomial function f(n)=A*n^k for some constants A and k can be found for each of them so that g(n)<f(n) where O(g(n)) always holds no matter how big n is. This isn't the case for the other 3 Big-O asymptotic values.

In more practical terms, O(1/n), O(n^2) and O(log n) each grow, as n grows, at most as fast as some polynomial function of n, and never any faster than that.

This question tests your understanding of 3 of the most frequently used Java data structures, and the binary search algorithm.

The correct answer is ArrayList.

HashSet isn't structured to retain any order of its elements. It can't be used at all for this task.

ArrayList and LinkedList both retain the order of their entries. However, binary search requires lookup of the entries by their positional indexes. Positional search is linear, i.e. O(n) on LinkedList. On the other hand, ArrayList, uses an array to store and maintain its entries and provides O(1) access to them, which makes it much preferable for this purpose.

It is very important that you are comfortable selecting data structures that best suit a particular scenario. The interviewer will want to hear why and how you came to your conclusion. Time and Computational complexities are often a good starting point when answering these kinds of quesitons.

The interviewer wants to see your understanding of HashSet and TreeSet data structures and whether you are comfortable with using them to solve real world problems.

TreeSet and HashSet are both Sets - they each implement java.util. Set and don't allow duplicate entries.

HashSet doesn't maintain any order of its elements. It is a basic set structure, and provides O(1) time element operations by internally using a HashMap to store its entries.

TreeSet, on the other hand, guarantees the value order of its elements. At any given time, the TreeSet elements are in sorted order, and this order isn't broken during element updates. TreeSet achieves this by using a binary search tree, namely the Red-Black tree. As a result of this, all its element operations are O(log n).

So, whenever distinct values need to be processed within their value order, TreeSet is useful. Otherwise, HashSet is much preferable for its constant asymptotic processing time.

This interview question tests whether or not you have a good grasp of Java Collections framework as to its overall structure and main components.

Collection and Map in java.util package. All data structures in core Java are descendants of these two interfaces. Collection and Map are two separate hierarchies within themselves - they don't extend one another.

The data structures in Map hierarchy hold key-value pairs as entries. In Collections hierarchy, each entry is a single object.

There are several other interfaces in Java Collections. Two most frequently used ones are `Set` and `List`. They both are descendants of Collection. Set interface signifies the role that the Collection entries do not repeat, whereas List signifies that the order of entry is maintained in the Collection. Set does not maintain order of its entries, and List does not impose element uniqueness.

In the Map "klan", the key components in the key-value entry pairs are unique-- keys never repeat in a data structure implementing Map. However, no such restriction on values. A value in a key-value entry pair can exist in 2 or more such pairs, each time with a different key.

Suppose you have an integer array `myArray` of length 16, declared as `int [] myArray = new int[16];`. How can you increase its length to 32?

The short answer; you can't. Java array lengths are fixed when the array is created in memory. You can never change the size of an array. You can however, create another array of length 32 and assign it to the same variable, as follows:

myArray = new int[32];

int myMethod(List<Integer> myList) {
	Set<Integer> mySet = new HashSet<>();
	for (int i:myList)
		if (i>-1 && i<10)
			mySet.add(i);
	return mySet.size();
}

In the above code: `myMethod(myList)` counts the number of single digit integers (i.e. integers between 0 and 9 inclusive) that exist in `myList` and returns the result. `myMethod’ uses a Set to keep track of the values 0..9, so it only counts the distinct values in this range with no regard to multiple occurrences of each of these values.

The following is an implementation of `myMethod` without the use of a Set. `myMethodWithArray` uses a boolean array `theArray` of length 10. `myMethodWithArray` uses `theArray` in such a way that, for any 0 <= i <= 9 `theArray[i]` tells whether `i` exists in `myList`:

Recursion is a common concept examined when completing technical interviews. A recursive function is a function defined in terms of itself via self-referential expressions.

This means that the function will continue to call itself and repeat its behaviour until some condition is met to return a result.

Below is 'myMethod': Explain what it does and write it's non-recursive version.

int myRecMethod(int n) {
        if (n > 0) 
            return n * myRecMethod(n-1);
        return 1;
 }

`myRecMethod(n)` returns the n factorial, n! Of positive integers, returns 1 if n<1.

Following is an implementation of `myRecMethod` without recursion:

int myMethod(int n) {
	if (n<1)
		return 1;
	int result = n; 
	while (--n>0)
		result*=n;		
	return result;
}

The correct answer is DFS. A DFS algorithm, as its name implies, traverses nodes at levels below the current node before it processes the rest of the nodes at the same level.

BFS does the opposite-- exhausts all known nodes at a level before it traverses a node in the level below. Since T is full, all of its leaves are at the same tree level. BFS reaches a leaf only after all internal nodes are traversed, while DFS reaches a leaf the soonest can be.

The correct answer would be O(n). Since the values to be sorted are in a bound range, a linear time algorithm like Radix sort can be used to sort them.

This is a very common example of an interview question designed to test your knowledge and your understanding of sorting algorithms as well as your ability to select a suitable algorithm for specific requirements.

In many technical interviews the interviewer will often attempt to determine if you are aware of the differences between computational complexity also referred to as space complexity and the time complexity of a given algorithm. It is particularly useful to familiarise yourself with some of the more common algorithms such as bubble and merge sort.

The complexity of an optimum algorithm is O(n*(log n)). This is the fastest algorithm to sort a given group of values by comparison. An example for such an algorithm is Merge-Sort.

Below are the time complexities associated with other algorithms:

Bubble Sort: O(n)
Selection Sort: O(n^2)
Heapsort: O(n*log(n))
Insertion sort: O(n)

These are some of the most common algorithms examined in technical interviews. It is helpful to learn the time complexities associated with these algorithms.

A palindrome is a word, phrase, or sequence that reads the same backward as forwards, e.g. madam.

	public static boolean isPalindrome(char[] word, int index) {
		if (index>=word.length/2) 
			return true;
		if (word[word.length-index-1]!=word[index])
			return false; 
		return isPalindrome(word, ++index);
	}

In order to call this method, use the following code:

	public static boolean isPalindrome(char[] word) {
		if (word==null)
			return false;
		return isPalindrome(word, 0);
	}

The computational complexity is O(n) for both `ArrayList` and `LinkedList`, where n is the size of the list.

The only way to see whether a given object is in an `ArrayList` or a `LinkedList` is to check each of its elements to see whether it is the one being searched. `ArrayList` provides direct (constant time) access by position index. However, `contains()` is a search for an entry without knowing its position in the list.

The correct answer is `add()` operation is faster on LinkedList than on TreeSet.

On a LinkedList, add() appends the given value to the end of the list. This operation takes constant, i.e. O(1) time.

TreeSet is a balanced binary search (BST) tree and maintains its elements in the order of their values. The add() operation inserts the given value in its place among the ordered elements and such operation on a balanced BST is O(log n).

contains() and remove() both take longer on LinkedList (O(n)) than on TreeSet (O(log n)).

		List<Integer> myList = new LinkedList<>(aColln);
		myList.addAll(aColln);
		
		Set<Integer> mySet = new HashSet<>(aColln);
		mySet.addAll(aColln);

This questions highlights the difference between the data structures, LinkedList and HashSet:

The correct answer would be: 2 elements in `mySet` and 4 in `myList`.

The 2 entries in `aColln` are added to both `mySet` and `myList` twice – 1) using their constructor while they are instantiated, 2) using their `addAll()` operation.

The`List` data structure allows duplicates, and there now are 4 elements in `myList`: {5, 7, 5, 7}.

However, a `Set` doesn’t allow duplicate entries. Since the `addAll()` operation attempted to add the same values as the ones already in `mySet`, it took no effect and `mySet` has 2 elements, {5,7} in the end.

A binary tree is a data structure in which each node has at most two children.

Therefore, there is only one path between any two nodes on a binary tree or any tree in general. There aren't any loops on a tree, so no alternate paths between nodes. In fact, trees are graphs in which there is exactly one node between each node pair.

To visualise this start off with a single node and draw two children nodes from that node. And then draw a further two children nodes from these nodes. Then you will see that only one path exists between any two nodes on the tree.

The four operations are as follows:

1) remove(String)
2) add(String)
3) size(String)
4) equals(Object)

remove(String) takes longer on LinkedList than on HashSet.

Removing an element in a List involves locating that element in the list and this operation is a linear search, O(n).

HashSet internally uses a Map structure to store its elements. Entry search in a HashMap is O(1). Element deletion is also O(1) in the average case and O(log n) in the worst case, still faster than O(n) time of LinkedList.remove().

The other operations have the same complexity on LinkedList and HashSet. add(String) and size(String) take O(1), and equals(Object) takes O(n) time on both.

In technical interviews it is important to recognise and account for the "Big O" when making decisions regarding what data structures you will use and what operations you will carry out on those data structures.

In computer science there are two kinds of complexity:

1. Time Complexity
2. Computational complexity

Both of these are measured using "Big O" notation. In technical interviews the interviewer may refer to the "Big O" of an algorithm in which case it is often useful to determine whether they mean time or computational complexity.

`ArrayList` data structure is backed by an array and direct access of indexed elements of an array takes constant, i.e. O(1) time. O(1) means that the time taken does not increase relative to the size of the data structure.

`LinkedList`, on the other hand, is a sequence of objects linked one after the other without any indexing for direct access. In order to reach a k-th element, the `get()` operation of `LinkedList` starts from its first element and traverses the links one after the other until it reaches the k-th position. This is a linear search and takes O(n) time where n is the size of the list. O(n) means that the time taken increases linearly in proportion to the size, n, of the data structure.

Binary trees and binary search trees are both examples of data structures.

The difference between a binary tree and a binary search tree is that a binary tree is any tree in which every node has at most 2 children.

A binary search tree is a specific type of binary tree. In a binary search tree, the value that is stored on any given node is greater than the value on its left child, and is less than the value on its right child. As a result, all nodes on the LHS of a node have smaller values, and those on its RHS have larger ones. This makes it more efficient to search and find a value on a Binary Search Tree, and hence the name "Search".

In a technical interview it is sometimes asked: "Give me an example of a non-linear data structure". The Binary Tree is a good example to provide when answering this question.

Map<String, String> myMap = HashMap<String, String> ();
put(“apple”, “apple”); 
put(“orange”, “orange”); 
put(“apple”, “orange”); 
put(“grapes”, “apple”);

Data structures are an important part of almost every technical interview. It is important to know the various types of data structures as well as have the ability to use them effectively.

In this question we look at the HashMap data structure. HashMaps store data in "Key : Value" pairs. You can access the data using an index or another type such as a String.

The code shows 4 put() operations. A put() method is used to insert a mapping into a HashMap.

After executing the code, we'll find there are now the following 3 entries in `myMap`:

{"orange":"orange", "apple":"orange", "grapes":"apple"}. 

The trick to this question is although there are 4 put() operations made, the third of these operations are made on the same key "apple" as the first one and replaced the previous entry that has been made on this key.

The key = "apple" originally was set to have the value = "apple". However, the third put() operation on the hashmap replaced the value associated with the key="apple" entry to the value = "orange". We can see this via the output.