An algorithm is a well-defined computational procedure that take some value as input and generate some value as output. In simple words, it’s a sequence of computational steps that converts input into the output.
2) Explain what is Quick Sort algorithm?
Quick Sort algorithm has the ability to sort list or queries quickly. It is based on the principle of partition exchange sort or Divide and conquer. This type of algorithm occupies less space, and it segregates the list into three main parts.
- Elements less than the Pivot element
- Pivot element
- Elements greater than the Pivot element
3) Explain what is time complexity of Algorithm?
Time complexity of an algorithm indicates the total time needed by the program to run to completion. It is usually expressed by using the big O notation.
4) Mention what are the types of Notation used for Time Complexity?
The types of Notations used for Time Complexity includes
- Big Oh: It indicates “fewer than or the same as” <expression>iterations
- Big Omega: It indicates “more than or same as” <expression>iterations
- Big Theta: It indicates “the same as”<expression>iterations
- Little Oh: It indicates “fewer than” <expression>iterations
- Little Omega: It indicates “more than” <expression>iterations
5) Explain how binary search works?
In binary search, we compare the key with the item in the middle position of the array. If the key is less than the item searched then it must lie in the lower half of the array, if the key is greater than the item searched than it should be in upper half of the array.
6) Explain whether it is possible to use binary search for linked lists?
Since random access is not acceptable in linked list, it is impossible to reach the middle element of O(1) time. Thus, binary search is not possible for linked list.
7) Explain what is heap sort?
Heap-sort can be defined as a comparison based sorting algorithm. It divides its input into the unsorted and sorted region, until it shrinks the unsorted region by eliminating the smallest element and moving that to the sorted region.
8) Explain what is Skip list?
Skip list the method for data structuring, where it allows the algorithm to search, delete and insert elements in a symbol table or dictionary. In a skip list, each element is represented by a node. The search function returns the content of the value related to key. The insert operation associates a specified key with a new value, while the delete function deletes the specified key.
9) Explain what is Space complexity of insertion sort algorithm?
Insertion sort is an in-place sorting algorithm which means that it requires no extra or little. storage. For insertion sort, it requires only single list elements to be stored out-side the initial data, making the space-complexity 0(1).
10) Explain what a “Hash Algorithm” is and what are they used for?
“Hash Algorithm” is a hash function that takes a string of any length and decreases it to a unique fixed length string. It is used for password validity, message & data integrity and for many other cryptographic systems.
11) Explain how to find whether the linked list has a loop?
To know whether the linked list has a loop, we will take two pointer approach. If we maintain two pointers, and we increase one pointer after processing two nodes and other after processing every node, we are likely to encounter a situation where both the pointer will be pointing to the same node. This will only occur if linked list has a loop.
12) Explain how encryption algorithm works?
Encryption is the process of converting plaintext into a secret code format referred as “Ciphertext”. To convert the text, algorithm uses a string of bits referred as “keys” for calculations. The larger the key, the greater the number of potential patterns for creating cipher text. Most encryption algorithm use codes fixed blocks of input that have length about 64 to 128 bits, while some uses stream method.
13) List out some of the commonly used cryptographic algorithms?
Some of the commonly used cryptographic algorithms are
- DES and Triple DES
- LOKI and so on
14) Explain what is the difference between best case scenario and worst case scenario of an algorithm?
- Best case scenario:Best case scenario for an algorithm is explained as the arrangement of data for which the algorithm performs best. For example, we take a binary search, for which the best case scenario would be if the target value is at the very center of the data you are searching. The best case time complexity would be 0 (1)
- Worst case scenario: It is referred for the worst set of input for a given algorithm. For example quicksort, which can perform worst if you select the largest or smallest element of a sublist for the pivot value. It will cause quicksort to degenerate to O (n2).
15) Explain what is Radix Sort algorithm?
Radix sort puts the element in order by comparing the digits of the numbers. It is one of the linear sorting algorithms for integers.
16) Explain what is a recursive algorithm?
Recursive algorithm is a method of solving a complicated problem by breaking a problem down into smaller and smaller sub-problems until you get the problem small enough that it can be solved easily. Usually, it involves a function calling itself.
17) Mention what are the three laws of recursion algorithm?
All recursive algorithm must follow three laws
- It should have a base case
- A recursive algorithm must call itself
- A recursive algorithm must change its state and move towards the base case
18) Explain what is bubble sort algorithm?
Bubble sort algorithm is also referred as sinking sort. In this type of sorting, the list to be sorted out compares the pair of adjacent items. If they are organized in the wrong order, it will swap the values and arrange them in the correct order.