Find the second highest number in an array

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. Can you find the second highest number in a given number?

For example: 

Input:  { 3, 5, 9, 7, 6, 8 };
Result: 8

A. A naive approach is to sort the array in descending order and then get the second element from the array. Sorting impacts performance, and  a better approach would be to

1) Have two variables to store highest & second highest numbers, and initialize them to minimum value.
2) Loop through each number in the array
3) If the "current number" > highest, make the current highest to second highest, and make the current value the highest.
4) else If the "current number < highest", but greater than the second highest then make "current number" the second highest.

public class SecondHighestNumber {

 public static void main(String[] args) {
  int[] numberArray = {3, 5, 9, 7, 6, 8};
        System.out.println(findSecondHighest(numberArray));
 }

 static int findSecondHighest(int[] numbers) {
  // initialize to the smallest value possible
  int highest = Integer.MIN_VALUE;
  int secondHighest = Integer.MIN_VALUE;

  for (int i = 0; i < numbers.length; i++) {

   //if highest number is found
   if (numbers[i] > highest) {
    secondHighest = highest; //make current highest to 2nd highest
    highest = numbers[i];    //make current value to highest
   } else if (numbers[i] > secondHighest)
    // replace the second highest
    secondHighest = numbers[i];
  }
  
  return secondHighest;
 }

}

Output:

8




Q. Is there anything wrong with the above code? What if you have duplicate numbers?

For example: int[] numberArray = {3, 5, 9, 7, 9, 8}; out put will be 9. If that is the expected behavior then it is fine. What if you want it to return 8 instead of 9?

A. Here is the slight revised solution that Ignores the equally highest numbers.

public class SecondHighestNumber {

 public static void main(String[] args) {
  int[] numberArray =  {3, 5, 9, 7, 9, 8};
        System.out.println(findSecondHighest(numberArray));
 }

 static int findSecondHighest(int[] numbers) {
  // initialize to the smallest value possible
  int highest = Integer.MIN_VALUE;
  int secondHighest = Integer.MIN_VALUE;

  for (int i = 0; i < numbers.length; i++) {
   
   //if highest or equally highest number is found
   //ignore the equally highest
   if (numbers[i] >= highest) {
    if(numbers[i] > highest) {
      secondHighest = highest; //make current highest to 2nd highest
      highest = numbers[i];    //make current value to highest
    }
   } else if (numbers[i] > secondHighest)
    // replace the second highest
    secondHighest = numbers[i];
  }
  
  return secondHighest;
 }

}

Output:

8

Core Java coding question to find 2 numbers from an array that add up to the target

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. Given an array of integers, find two numbers such that they add up to a specific target number?

For example,

Given numbers: {2, 3, 8, 7, 5}
Target number:  9
Result: 2 and 7

A. There are naive algorithms like using  a for loop within a  for loop with O(n^2) complexity. Let's look at more efficient solutions.

Solution 1: Store processed numbers in a set.

Here is the code

package com.java8.examples;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import javax.management.RuntimeErrorException;

public class Sum2NumsToATargetNumberTest {
 
 public static int[] findNumsThatSumToTargetNum(int[] numbers, int target) {
  Set<Integer> processedNumbers = new HashSet<>();
  boolean foundSum = false;
  int[] result = new int[2];
  for (int i = 0; i < numbers.length; i++) {
   int reqNumber = target - numbers[i]; 
   System.out.println("current number="  + numbers[i] + " , requiredNumber = " + reqNumber);
   if(processedNumbers.contains(reqNumber)){
    result[0] = numbers[i];
    result[1] = reqNumber;
    foundSum = true;
    break;
   }
   else {
    processedNumbers.add(numbers[i]);
   }
  }
  
  if(!foundSum){
   throw new RuntimeException("Sum is not found !!");
  }
  
  return result; 
 }
}

The main method to test:

        public static void main(String[] args) {
  int[] numbers = {2, 3, 8, 7, 5};
  int target = 9;
  int[] result = findNumsThatSumToTargetNum(numbers, target);
  System.out.println("Two numbers that add up to " + target + " are " + result[0] + " and " + result[1]);
 }

Output:

current number=2 , requiredNumber = 7
current number=3 , requiredNumber = 6
current number=8 , requiredNumber = 1
current number=7 , requiredNumber = 2
Two numbers that add up to 9 are 7 and 2




Solution 2: Sort the numbers and use 2 pointers.

package com.java8.examples;

import java.util.Arrays;

public class Sum2NumsToATargetNumberTest2 {
 
 public static void main(String[] args) {
  int[] numbers = {2, 3, 8, 7, 5};
  int target = 9;
  int[] result = findNumsThatSumToTargetNum(numbers, target);
  System.out.println("Two numbers that add up to " + target + " are " + result[0] + " and " + result[1]);
 }
 
 // System.out.println("current number="  + numbers[i] + " , requiredNumber = " + reqNumber);
 static int[] findNumsThatSumToTargetNum(int[] numbers, int target) {
  int pointer1 = 0;
  int pointer2 = numbers.length -1;
  
  int[] result = new int[2];
  
  Arrays.sort(numbers); // sort the numbers
  
  while(pointer2 >= pointer1) {
   int sum = numbers[pointer1] + numbers[pointer2];
   if(sum == target) {
    result[0] = numbers[pointer1] ;
    result[1] = numbers[pointer2] ;
    break;
   }
   
   //if sum is greater than the target
   if(sum > target) {
    pointer2--; //move pointer2 to the left to reduce the sum
   }
   
   //if sum is less than the target
   if(sum < target) {
    pointer1++; //move pointer1 to the right to increase the sum
   }
  }
  
  
  
  return result;
  
 }
}

Output:

Two numbers that add up to 9 are 2 and 7

Core Java coding question on palindrome

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. What is a palindrome?
A. A palindrome is a word or sentence that reads the same forward as it does backward. For example, the terms "racecar", "dad", "madam" and the name "Hannah". The longest palindromic substring of "bananas" is "anana" -- the left side of a palindrome is a mirror image of its right side.

  //loop from left to right  
    for (int i = 0; i < s.length() - 1; i++) {
  if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
   return false;
  }
 }
 
 return true;

"anana" is a palindrome.

i = 0 --> a != a : false
i = 1 --> n != n : false
i = 2 --> a != a : false
i = 3 --> n != n : false
i = 4 --> break the loop

Alternatively, the reversed string must match the original string.

      String reverse = "";

      //loop from right to left
      for ( int i = length - 1 ; i >= 0 ; i-- ) {
         reverse = reverse + s.charAt(i);
   }
 
      if (s.equals(reverse)) {
        return true;
   } 
   else {
        return false;
   }

We don't actually have to process all the characters, and can stop in the middle

package com.java8.examples;

public class PalindromeTest {

 public static void main(String[] args) {
  System.out.println("Is madam a Palindrome? " + isPalindrome("madam"));
 }

 public static boolean isPalindrome(String s) {
  boolean result = false;

  int i, begin, end, middle;

  begin = 0;
  end = s.length() - 1;
  middle = (begin + end) / 2;

  //process from left to middle
  for (i = begin; i <= middle; i++) {
   if (s.charAt(begin) == s.charAt(end)) {
    begin++;
    end--;
   } else {
    break;
   }
  }

  //if has gone past the middle
  if (i == middle + 1) {
   result = true;
  }

  return result;
 }
}

Q. How will you find the longest palindrome of a given string?
A. Algorithm: Have 2 center pointers, and move  one to the left and the other to the right. Cater for 2 scenarios where you have odd number of characters and even number of characters as shown below.

package com.java8.examples;

public class PalindromeLongestSubstring {
 
  private static String findLongestPalindrome(String s){
  if(s == null || s.length() == 1){
   return s;
  }
  
  String longest = s.substring(0,1);
  
  for (int i = 0; i < s.length(); i++) {
   //one center. odd number of characters (e.g 12321)
   String result = findPalindromeForGivenCenter(s, i, i);
   longest = result.length() > longest.length()? result : longest;
   
   //two centers. even number of characters (e.g 123321)
   result = findPalindromeForGivenCenter(s, i, i+1);
   longest = result.length() > longest.length()? result : longest;
  }
  
  return longest;
 }
 
 
 
 // Given either same left and right center (e.g.12321) or 
 // 2 left and right centers  (e.g. 123321) find the longest palindrome
 private static String findPalindromeForGivenCenter (final String s, int leftCenter, int rightCenter) {
  int length = s.length();
  
  while (leftCenter >= 0 && rightCenter <= length -1 && s.charAt(leftCenter) == s.charAt(rightCenter)) {
   leftCenter--;  //move from center to left
   rightCenter++; //move from center to right 
  }
  
  //leftCenter+1 because the index would have moved left before exiting the above loop
  return s.substring(leftCenter+1,rightCenter);
 }

}

Test the output for different inputs

        public static void main(String[] args) {
  String s1 = "12321", s2= "123321", s3 = "71233218", s4="1234", s5="88123217";
  System.out.println(s1  + " = " + findLongestPalindrome(s1));
  System.out.println(s2  + " = " + findLongestPalindrome(s2));
  System.out.println(s3  + " = " + findLongestPalindrome(s3));
  System.out.println(s4  + " = " + findLongestPalindrome(s4));
  System.out.println(s5  + " = " + findLongestPalindrome(s5));
  
  String s6 = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
  System.out.println(s6  + " = " + findLongestPalindrome(s6));
  
 }

Output:

12321 = 12321
123321 = 123321
71233218 = 123321
1234 = 1
88123217 = 12321
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE = 12345678987654321

Core Java coding interview question and answer on Reverse Polish Notation (RPN)

Q.  Can you explain Reverse Polish Notation (RPN)?
A.  You have already heard about the following from your elementary schooling:

• "Please Excuse My Dear Aunt Sally" (meaning Parentheses, Exponentiation (roots and powers), Multiplication, Division, Addition, and Subtraction
• BODMAS, tells us to attend to Brackets, Of, Division, Multiplication, Addition, and Subtraction

This means:

(1+2)*3 = 9 using BODMAS or  "Please Excuse My Dear Aunt Sally" 

Polish Notation was invented in the 1920's by Polish mathematician Jan Lukasiewicz, who showed that by writing operators in front of their operands, instead of between them, brackets were made unnecessary. 

3 2 1 + x = 9  using Reverse Polish Notion (RPN).

In programming, the RPN is evaluated using a stack, which is a LIFO (Last In First Out) data structure.

The algorithm for RPN is: 

Keep pushing the numbers into a stack, and when it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

Q. Can you write code that demonstrates RPN?
A. It can be coded in Java 7, as shown below. Java 7 supports string in switch statements.

package com.java8.examples;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class ReversePolishNotationTest {

 public static void main(String[] args) {
  
  String[] tokens = new String[] { "3", "2", "1", "+", "*" };
        System.out.println(evalRPN(tokens));
 }
 
 
 
 public static int evalRPN(String[] tokens){
  int result = 0;
  String operators = "+-*/";
  
  //Double ended queue can be used as a stack LIFO(push/pop) or queue FIFO (offer/poll).
  Deque<String> stack = new ArrayDeque<String>();
  
  for (String string : tokens) {
   //keep pushing the numbers
   if (!operators.contains(string)) {
    stack.push(string);
   } else { //for operators
    int a = Integer.valueOf(stack.pop());
    int b = Integer.valueOf(stack.pop());
    switch (string) {
    case "+":
     stack.push(String.valueOf(a + b));
     break;
    case "-":
     stack.push(String.valueOf(b - a));
     break;
    case "*":
     stack.push(String.valueOf(a * b));
     break;
    case "/":
     stack.push(String.valueOf(b / a));
     break;
    }
   }
  }
  
  //get the value left in th stack
  result = Integer.valueOf(stack.pop());
  
  return result;
 }

}

Things to remember:

1. Algorithm: Keep pushing the numbers into a stack, and when it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

2. Use a stack, which is a LIFO data structure.

3. In Java, Deque is a linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck".

Java coding questions frequently asked in technical tests and job interviews -- part 4: iteration Vs recursion

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. Can you write a sample code that will count the number of "A"s in a given text? Show both iterative and recursive approaches?

A. Let's assume the input string is "AAA rating". The iterative approach is pretty straight forward as illustrated below.

public class Iteration {

    public int countA(String input) {
        if (input == null || input.length( ) == 0) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < input.length( ); i++) {
            if(input.substring(i, i+1).equals("A")){
                count++;
            }
        }
        return count;
    }

    public static void main(String[ ] args) {
          System.out.println(new Iteration( ).countA("AAA rating"));     // Ans.3
    }
} 

Now, let's look at the recursive approach.

public class RecursiveCall {

    public int countA(String input) {
       
        // exit condition – recursive calls must have an exit condition
        if (input == null || input.length( ) == 0) {
            return 0;
        }

        int count = 0;
         
        //check first character of the input 
        if (input.substring(0, 1).equals("A")) {
            count = 1;
        }
        
        //recursive call to evaluate rest of the input 
        //(i.e.  2nd character onwards)
        return count + countA(input.substring(1)); 
    }

    public static void main(String[ ] args) {
        System.out.println(new RecursiveCall( ).countA("AAA rating"));    // Ans. 3
    }
}

Many find it harder to understand recursion, hence let's try it with a simple diagram.

Q.What concepts do you need to know to understand recursion?

A re-entrant method would be one that can safely be entered, even when the same method is being executed, further down the call stack of the same thread. A non-re-entrant method would not be safe to use in that way. For example, writing or logging to a file can potentially corrupt that file, if that method were to be re-entrant.

A function is recursive if it calls itself. Given enough stack space, recursive method calls are perfectly valid in Java though it is tough to debug. Recursive functions are useful in removing iterations from many sorts of algorithms. All recursive functions are re-entrant, but not all re-entrant functions are recursive.

Stack uses LIFO (Last In First Out), so it remembers its ‘caller’ and knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.Java is a stack based language.



What follow up question(s) to expect?

Q. When would you use recursion? 
A. Recursion might not be the efficient way to code the above example and iterative approach will do the job, but there are scenarios where recursion is preferred as recursive functions are shorter, simpler, and easier to read and understand. Recursive functions are very handy in working with tree structures and avoiding unsightly nested for loops.

Q. What is a tail recursion, and why would you need it? Can you rewrite the above code with tail recursion?
A. Regular recursive function (aka head recursion) demonstrated above grows the size of the call stack. Each time the function calls itself, another entry has to be pushed onto the stack. The thing the function has to do before returning is add count with the result of countA(input.substring(1), assuming count is greater than 1, the computer has to evaluate count + countA(input.substring(1)), and in order to do that it must evaluate countA(input.substring(1)). This alse mean that you need to wait for the call to countA(input.substring(1) to complete so that you can add the value it returns with count. So, the last thing done here is actually the addition, not the recursive call.


What is the benifit of tail recursion? 

In tail recursion, the last thing done is the recursion and the addition would have been done before. You don't have any use for the old information because there’s nothing to do after the recursive call. You can throw out all of your old information and simply run the function again with the new set of parameters. This means you run with shorter call stack leading to lower memory usage and better performance.

Here is the above rewritten with tail recursion.

public class TailRecursiveCall {

 public int countA(String input) {

  // exit condition – recursive calls must have an exit condition
  if (input == null || input.length() == 0) {
   return 0;
  }
  
  return countA(input, 0) ;
 }
 
 public int countA(String input, int count) {
  if (input.length() == 0) {
   return count;
  }
  
  // check first character of the input
  if (input.substring(0, 1).equals("A")) {
   count = count + 1;
  }

  // recursive call is the last call as the count is cumulative
  return countA(input.substring(1), count);
 }

 public static void main(String[] args) {
  System.out.println(new TailRecursiveCall().countA("AAA rating"));
 }
}

Java coding interview questions and answers

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

These Java coding questions and answers are extracted from the book " Core Java Career Essentials. Good interviewers are more interested in your ability to code rather than knowing the flavor of the month framework.


Q. Can you write an algorithm to swap two variables?
A.

package algorithms;

public class Swap {
    
    public static void main(String[ ] args) {
        int x = 5;
        int y = 6;
        
        //store 'x' in a temp variable
        int temp = x;
        x = y;
        y = temp;
        
        System.out.println("x=" + x + ",y=" + y);
   }
}

Q. Can you write  code to bubble sort { 30, 12, 18, 0, -5, 72, 424 }?
A.

package algorithms;
import java.util.Arrays;

public class BubbleSort {

    public static void main(String[ ] args) {
        Integer[ ] values = { 30, 12, 18, 0, -5, 72, 424 };
        int size = values.length;
        System.out.println("Before:" + Arrays.deepToString(values));

        for (int pass = 0; pass < size - 1; pass++) {
            for (int i = 0; i < size - pass - 1; i++) {
                // swap if i > i+1
                if (values[i] > values[i + 1])
                    swap(values, i, i + 1);
            }
        }

        System.out.println("After:" + Arrays.deepToString(values));
    }

    private static void swap(Integer[ ] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
} 

Q. Is there a more efficient sorting algorithm?
A. Although bubble-sort is one of the simplest sorting algorithms, it's also one of the slowest. It has the O(n^2) time complexity. Faster algorithms include quick-sort and heap-sort. The Arrays.sort( ) method uses the quick-sort algorithm, which on average has O(n * log n) but can go up to O(n^2) in a worst case scenario, and this happens especially with already sorted sequences.

Q. Write a program that will return whichever value is nearest to the value of 100 from two given int numbers?
A. You can firstly write the pseudo code as follows:

• Compute the difference to 100.
• Find out the absolute difference as negative numbers are valid.
• Compare the differences to find out the nearest number to 100.
• Write test cases for +ve, -ve, equal to, > than and < than values.

package chapter2.com;



public class CloseTo100 {

    

    public static int calculate(int input1, int input2) {

         //compute the difference. Negative values are allowed as well 

        int iput1Diff = Math.abs(100 - input1);

        int iput2Diff = Math.abs(100 - input2);

        

        //compare the difference

        if (iput1Diff < iput2Diff) return input1;
        else if (iput2Diff < iput1Diff) return input2;
        else return input1;          //if tie, just return one
    }
    
    public static void main(String[ ] args) {
        //+ve numbers
        System.out.println("+ve numbers=" + calculate(50,90));
        
        //-ve numbers
        System.out.println("-ve numbers=" + calculate(-50,-90));
        
        //equal numbers
        System.out.println("equal numbers=" + calculate(50,50));
        
        //greater than 100
        System.out.println(">100 numbers=" + calculate(85,105));

        System.out.println("<100 numbers=" + calculate(95,110));
    } 
}

Output:

+ve numbers=90
-ve numbers=-50
equal numbers=50
>100 numbers=105
<100 numbers=95


Q. Can you write a method that reverses a given String?
A.

public class ReverseString {

    

    public static void main(String[ ] args) {

        System.out.println(reverse("big brown fox"));

        System.out.println(reverse(""));       

    }



    public static String reverse(String input) {

        if(input == null || input.length( ) == 0){

            return input;

        }

       

        return new StringBuilder(input).reverse( ).toString( ); 

    }

}

It is always a best practice to reuse the API methods as shown above with the StringBuilder(input).reverse( ) method as it is fast, efficient (uses bitwise operations) and knows how to handle Unicode surrogate pairs, which most other solutions ignore. The above code handles null and empty strings, and a StringBuilder is used as opposed to a thread-safe StringBuffer, as the StringBuilder is locally defined, and local variables are implicitly thread-safe.

Some interviewers might probe you to write other lesser elegant code using either recursion or iterative swapping. Some developers find it very difficult to handle recursion, especially to work out the termination condition. All recursive methods need to have a condition to terminate the recursion.

public class ReverseString2 {
    
    public String reverse(String str) {
        // exit or termination condition
        if ((null == str) || (str.length( )  <= 1)) {
            return str;
        }
        
        // put the first character (i.e. charAt(0)) to the end. String indices are 0 based. 
        // and recurse with 2nd character (i.e. substring(1)) onwards  
        return reverse(str.substring(1)) + str.charAt(0);
    }
}

There are other solutions like

public class ReverseString3 {
    
    public String reverse(String str) {
        // validate
        if ((null == str) || (str.length( )  <= 1)) {
            return str;
        }
        
        char[ ] chars = str.toCharArray( );
        int rhsIdx = chars.length - 1;
        
        //iteratively swap until exit condition lhsIdx < rhsIdx is reached
        for (int lhsIdx = 0; lhsIdx < rhsIdx; lhsIdx++) {
            char temp = chars[lhsIdx];
            chars[lhsIdx] = chars[rhsIdx];
            chars[rhsIdx--] = temp;
        }
        
        return new String(chars);
    }
} 

Or

 
public class ReverseString4 {
     
    public String reverse(String str) {
        // validate
        if ((null == str) || (str.length( )  <= 1)) {
            return str;
        }
         
        
        char[ ] chars = str.toCharArray( );
        int length = chars.length;
        int last = length - 1;
         
        //iteratively swap until reached the middle
        for (int i = 0; i < length/2; i++) {
            char temp = chars[i];
            chars[i] = chars[last - i];
            chars[last - i] = temp;
        }
         
        return new String(chars);
    }
    
    
    public static void main(String[] args) {
      String result = new ReverseString4().reverse("Madam, I'm Adam");
      System.out.println(result);
   }
} 

Relevant must get it right coding questions and answers

• Core Java coding questions frequently asked in written tests and interviews - part 2 - == Vs equals()
• Core Java coding questions frequently asked in written tests and interview - part 3 - overload Vs override
• Core Java coding questions frequently asked in written tests and interview - part 4 -- iteration Vs recursion
• Reviewing a given Java code at job interviews and code review sessions
• Java coding question and answer on multi-threading
• Java OO interview questions and answers.
• Can you write code by asking the right questions?
• Handling the programming question on the popular Fibonacci number.
• More Java interview coding question and answer - beginner to intermediate level