Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth. Algorithms power the biggest web companies and the most promising startups. Interviews at tech companies start with questions that probe for good algorithm thinking.
Flashback: Write A Java Program | 5 Commonly Asked Java-Program In Selenium Interview
Algorithms are the heart of computer science
“An algorithm is a well-defined procedure that allows a computer to solve a problem. Another way to describe an algorithm is a sequence of unambiguous instructions. The use of the term ‘unambiguous’ indicates that there is no room for subjective interpretation. Every time you ask your computer to carry out the same algorithm, it will do it in exactly the same manner with the exact same result.”
6. Binary Search in an Array
Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful or the remaining half is empty.
The logic: Define three variables denoting lower index, highest index and middle index. Check for the element at middle index and then shift either the lower index or the highest index accordingly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
<span style="font-size: 12pt; font-family: helvetica, arial, sans-serif;">package Java; public class BinarySearch { // Complexity | O(LogN) public int BS(int item, int[] list) { int index = -1; int l = 0,h = list.length-1,mid; while (h >= l) { mid = (h + l)/2; if (item < list[mid]) { h = mid - 1; } else if (item > list[mid]) { l = mid + 1; } else { index = mid; break; } } return index; } } </span> |
Binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm.
7. Find out duplicate number between 1 to N numbers.
An array is given with a range of numbers between 1 to N, where one of the numbers is repeated. You need to write a program to find out the duplicate number.
The logic: Ideally the sum of 1 to N numbers is n*(n+1)/2. Since one of the number is repeated, calculate the actual sum and minus it from the ideal sum to get the duplicate number.
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 |
<span style="font-size: 12pt; font-family: helvetica, arial, sans-serif;">package Java; import java.util.ArrayList; import java.util.List; public class DuplicateNumber { public int Duplicate(List numbers){ int n = numbers.size() - 1; System.out.println(n); int total = getSum(numbers); int dup = total - (n*(n+1)/2); return dup; } public int getSum(List numbers){ int sum = 0; for(int num:numbers){ sum += num; } return sum; } public static void main(String a[]){ List numbers = new ArrayList(); for(int i=1;i<30;i++){ numbers.add(i); } //add duplicate number into the list numbers.add(22); DuplicateNumber dn = new DuplicateNumber(); System.out.println("Duplicate Number: "+dn.Duplicate(numbers)); } } </span> |
8. Linear Search
Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
The logic: Run a loop from 0 till array length searching for the element.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
<span style="font-size: 12pt; font-family: helvetica, arial, sans-serif;">package Java; public class LinearSearch { public static void Search(int[] a,int num){ for(int i=0;i<a.length;i++){ if(a[i]==num) System.out.println("The given number found at index: "+i); } } public static void main(String[] args){ int[] a = {1,12,65,34,8,54,23}; Search(a,34); } } </span> |
Linear search runs in at worst linear time O(n) and makes at most n comparisons, where n is the length of the list.
9. Identify Odd Even
Any integer that can be divided exactly by 2 is an even number.
The logic: Check for the remainder when number is divided by 2. If the remainder is 0, the number is even – else odd.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
<span style="font-size: 12pt; font-family: helvetica, arial, sans-serif;">package Java; import java.util.Scanner; public class OddEven { public static void main(String args[]) { Scanner in= new Scanner(System.in); System.out.println("Please enter number to check even or odd"); int n=in.nextInt(); if(n%2==0){ System.out.println(+n+" is even number"); } else{ System.out.println(+n+" is odd number"); } in.close(); } } </span> |
10. Check for Prime number
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6.
The logic: Run a loop from 2 till n/2 and return false in case the input is divisible by any of the iterator.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
<span style="font-size: 12pt; font-family: helvetica, arial, sans-serif;">package Java; public class CheckPrime { public static boolean PrimeNumber(int number){ for(int i=2; i<=number/2; i++){ if(number % i == 0){ return false; } } return true; } public static void main(String a[]){ System.out.println("Is 17 prime number? "+PrimeNumber(17)); System.out.println("Is 19 prime number? "+PrimeNumber(19)); System.out.println("Is 15 prime number? "+PrimeNumber(15)); } } </span> |
Hope these initial algorithms will help you get started with Java programming. In subsequent articles we will try to cover as many popular Java algorithms as we can – so that you are prepared for basic Selenium automation interview. If you know of other popular algorithms, do let us know in the comments section below.
By the way, don’t forget to share it with your friends & colleagues!