Top Most Java Interviews Frequently Asked Puzzles

Interview puzzles is the best way to check person's analytical skills. In investment banking job you need analytical skill to perform day to day job. It is not only applicable to traders , but some level of analytical skills is required by people who are developing these systems for understand business. Now a days it is become common practice to ask 1-2 puzzles during investment bank interview to check the candidate's analytical skills. The best way to clear this round is practice common puzzles and understand the logic to solve them. 

1) Fibonacci in Java:

The input will be number n and the output should be sum for 0 to n. for example

for n =4 the result should be 0+1+2+3+4 = 10

	public class FibonacciNumber {
	public static int fibonacci(int n) {
	if (n < 2) {
	return n;
	}
	else {
	return fibonacci(n-1)+fib(n-2);
	}
	}
	}

view raw Fibbonacci.java hosted with ❤ by GitHub

2) String Reverse

The input String "abcde" should return "edcba".

	public reverse(String word) {
	char[] chs = word.toCharArray();
	int i=0, j=chs.length-1;
	while (i < j) {
	// swap chs[i] and chs[j]
	char t = chs[i];
	chs[i] = chs[j];
	chs[j] = t;
	i++; j--;
	}
	}
	//Another way using java utility.
	import org.apache.commons.lang.StringUtils;
	String reverseWords(String sentence) {
	return StringUtils.reverseDelimited(StringUtils.reverse(sentence), ' ');
	}

view raw reverseString.java hosted with ❤ by GitHub

3) Reversing a linked list in Java

Here is example of revering the linked list in java using recursive function:

	public class ListNode {
	String data = "";
	ListNode next = null;
	public ListNode(String data, ListNode node) {
	this.data = data;
	this.next = node;
	}
	// reverse
	public static ListNode reverse (ListNode list){
	if (list == null) return null;
	if (list.next == null) return list;
	ListNode secondElem = list.next;
	list.next = null;
	ListNode reverseRest = reverse(secondElem);
	secondElem.next = list;
	return reverseRest;
	}
	public static void main(String[] args) {
	ListNode node3= new ListNode ("node3",null);
	ListNode node2= new ListNode ("node2",node3);
	ListNode node1= new ListNode ("node1",node2);
	System.out.println(" Last Item : "+node1.next.next.data+"\n");
	ListNode reverseList = ListNode.reverse(node1);
	System.out.println("First Item "+reverseList.data);
	}
	}

view raw listNode.java hosted with ❤ by GitHub

4) Find the missing number in Java

You have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot?

Try it for practice. please suggest the answer .

[Trick sum of n numbers is n*(n+1)/2]

	import java.util.*;
	public class MissingNumber {
	public static void main(String...strings){
	Set numberSet = new HashSet();
	// Max number in the sequence
	int k = 50;
	// put the numbers
	for(int i=0;i<=50;i++){
	numberSet.add(i);
	}
	// Remove random number
	int i = (new Random()).nextInt(50);
	System.out.println(" Removing number -->"+i);
	numberSet.remove(i);
	// find the current sum
	int sum =0;
	for(int m : numberSet){
	sum= sum +m;
	}
	// Find the missing number
	int l = ((k)*((k+1))/2)- sum;
	System.out.println(" Missing number -->"+l);
	}
	}

view raw MissingNumber.java hosted with ❤ by GitHub

5) Write a substring function in Java

String test= "AA BB CC BB BB CC BB";

String[]{"BB", "CC", "AA"}

Result shd be BB=4; CC=2 and AA=1

Since B occurred 4 times C did 2 times and A only 1 time.

This basic problem can be asked in different ways like, You have multiple words in new paper and find out the frequency of words in one page of news paper?

	public static String[] sortingData(String data) {
	String[] strings = data.split(" ");
	// Finding distinct values
	HashMap map = new HashMap();
	for (String s : strings) {
	Integer i = map.get(s);
	if (i != null) {
	map.put(s, i+1);
	} else {
	map.put(s, 1);
	}
	}
	// Ordering using Collections
	TreeMap sort = new TreeMap(Collections.reverseOrder());
	for (Entry e : map.entrySet()) {
	sort.put(e.getValue(), e.getKey());
	}
	return sort.values().toArray(new String[0]);
	}

view raw sortingString.java hosted with ❤ by GitHub

6) Reverse a String in Java

Reverse the String by java function without recursion and with recursion

	//Reverse the String by java function without recursion
	public static String reverseString(String str){
	if(str==null || str.length()==1)
	return str;
	int i = str.length();
	char[] reverse = new char[i];
	for(int j=0;j;j++)
	reverse[j]= str.charAt(i-j-1);
	}
	return new String(reverse);
	}
	//Reverse the String by java function with Recursive Function
	public static String reverse(String str) {
	if ((null == str) || (str.length() <= 1)) {
	return str;
	}
	return reverse(str.substring(1)) + str.charAt(0);
	}

view raw StringReverse.java hosted with ❤ by GitHub

7) Find one string inside another in Java

We can use String.indexOf( subString ) and it will return the first index of substring;

for Last Index : lastIndexOf(String str)

8) Algo for finding largest number in Array of Integer

Easy one, Check the integer one by one and find the largest number.

9) Java Runtime method invocation question:

Example : Tell the output of this

	class Base {
	protected int i;
	Base() {
	add(1);
	}
	void add(int v) {
	i += v;
	}
	}
	class Extension extends Base {
	Extension() {
	add(1);
	}
	void add(int v) {
	i += v * 2;
	}
	}
	public class Example {
	public static void main(String[] args) {
	System.out.println(" " + bogo(new Extension()));
	}
	static int bogo(Base b) {
	return b.add(8);
	}
	}

view raw RuntimeMethodBinding.java hosted with ❤ by GitHub

Answer is : 20 .

10) Suppose you have a large file with lots of words. How would you find the unique words and their count? What kind of data structure u will use? What will be the time complexity and space complexity?

We need to take care of two things counting the words and second duplicate. the best performance will be using hash function.

	import java.util.*;
	public class Freq {
	public static void main(String[] args) {
	Map m = new HashMap();
	// Initialize frequency table from command line
	for (String a : args) {
	Integer freq = m.get(a);
	m.put(a, (freq == null) ? 1 : freq + 1);
	}
	System.out.println(m.size() + " distinct words:");
	System.out.println(m);
	}
	}

view raw WordFrequency.java hosted with ❤ by GitHub

11) A train is one mile long. It travels at the rate of one mile a minute through a tunnel which is also one mile long. Can you say how long it will take for the train to pass completely through the tunnel? 

Answer : 2 minutes

it will take two minutes if you count the time for it to completely pass through the tunnel. One minute to pass through the tunnel and another one minute to drag itself out of the tunnel completely so two minutes nice question though well logical.

12) Convert String = "98989" into an integer without using any library functions in java.

Give fastest way to do it and explain why your method is best.

// converting string to number using ascii code

	// converting string to number using ascii code
	public static int convertStringToInt(String num){
	int result=0;
	int zeroAscii=48;
	int nineAscii=57;
	for(char c: num.toCharArray()){
	if(c>=zeroAscii && c<=nineAscii){
	result=result*10+(c-zeroAscii);
	}else
	return -1;
	}
	return result;
	}

view raw charToNumber.java hosted with ❤ by GitHub

13) Write a program to shuffle a deck of 52 cards and shuffle them equally to 4 players.

	package com.learning.puzzle;
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.Random;
	import java.util.Set;
	/*
	* Write the code to shuffle a deck of 52 cards,
	* and shuffle them equally to 4 players
	*/
	class Card {
	public enum Rank {
	DEUCE, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE
	}
	public enum Suit {
	CLUBS, DIAMONDS, HEARTS, SPADES
	}
	private final Rank rank;
	private final Suit suit;
	private Card(Rank rank, Suit suit) {
	this.rank = rank;
	this.suit = suit;
	}
	public Rank rank() {
	return rank;
	}
	public Suit suit() {
	return suit;
	}
	public String toString() {
	return rank + " of " + suit;
	}
	private static final List<Card> protoDeck = new ArrayList<Card>();
	// Initialize prototype deck
	static {
	for (Suit suit : Suit.values())
	for (Rank rank : Rank.values())
	protoDeck.add(new Card(rank, suit));
	}
	public static ArrayList<Card> newDeck() {
	return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
	}
	}
	public class RandomCards {
	private Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
	public RandomCards() {
	}
	public static void main(String[] args) {
	ArrayList<Card> player1 = new ArrayList<Card>();
	ArrayList<Card> player2 = new ArrayList<Card>();
	ArrayList<Card> player3 = new ArrayList<Card>();
	ArrayList<Card> player4 = new ArrayList<Card>();
	ArrayList<Card> deck = Card.newDeck();
	Random random = new Random();
	int j = 1;
	for (int i = 0; i < 52; i++) {
	int temp = random.nextInt(52);
	if (j == 1) {
	player1.add(deck.get(i));
	j++;
	continue;
	} else if (j == 2) {
	player2.add(deck.get(i));
	j++;
	continue;
	} else if (j == 3) {
	player3.add(deck.get(i));
	j++;
	continue;
	} else if (j == 4) {
	player4.add(deck.get(i));
	j = 1;
	continue;
	}
	}
	System.out.println(" Player 1 " + player1);
	System.out.println(" Player 2 " + player2);
	System.out.println(" Player 3 " + player3);
	System.out.println(" Player 4 " + player4);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Answer this puzzle by comments.

Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time?

for example you have 4 stairs and you can climb like

1,1,1,1

1,1,2

1,2,1

2,1,1

2,2

so in overall 5 ways for 3 stairs.

Top Most Data Structure questions for Java developer

'Data Structure questions' or 'Java Algorithm questions' is covered in this topic. These questions are always asked by interviewer if they are from CS background. This is very useful to understand java collection sorting and searching algorithm so that we can use correct collection type in our application. It help us to understand how indexes work in database and how the data retrievals become so fast due to B Tree data structure.

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Example -- 8 6 7
Compare 8 and 6 and re arrange to 6,8,7
Next number compare 8 and 7 and rearrange 6,7,8
This process continues till there is no swaping
Output : 6,7,8

Average : n^2 and 

worst case  n lon(n)

Quick Sort: Pivot

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.

2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3.  Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Average:  n log n

Worst : n^2

Merge Sort

a merge sort works as follows

1.   Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2.   Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

Example 4 8 9 0

Devide till single element :   4  ||  8 ||  9  || 0

Group into 2 :                        4 8  ||  0  9

Merge these 2 list :             0 4 8 9

Avg case :  n ( log n )

Worst case: n long (n)

Binary Search tree:

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

· The left subtree of a node contains only nodes with keys less than the node's key.

· The right subtree of a node contains only nodes with keys greater than the node's key.

· Both the left and right subtrees must also be binary search trees.

· There must be no duplicate nodes.

Best case :  O (1)
Avg case : O (log n )

Worst case : O (log n)

SkipList:

  A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in lists.A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. 

         If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/p, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total expected cost of a search is which is when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.