Q.1 What is an algorithm?
Q.2 What is time complexity of Binary Search?
Answer: Time complexity of binary search is O(Logn).
Q.3 How to find if two given rectangles overlap?
Answer: Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. An algorithm is a step by step procedure to solve logical and mathematical problems. A recipe is a good example of an algorithm because says what must be done, step by step. It takes inputs (ingredients) and produces an output (the completed dish). Informally, an algorithm can be called a "list of steps".
Answer: Time complexity of binary search is O(Logn).
Q.3 How to find if two given rectangles overlap?
Answer: Two rectangles do not overlap if one of the following conditions is true.
- One rectangle is above top edge of other rectangle.
- One rectangle is on left side of left edge of other rectangle.
Q.4 Can Binary Search be used for linked lists?
Answer: Since random access is not allowed in linked list, we cannot reach the middle element in O(1) time. Therefore Binary Search is not possible for linked lists. There are other ways though, refer Skip List for example.
Q.5 When does the worst case of QuickSort occur?
Answer: In quickSort, we select a pivot element, then partition the given array around the pivot element by placing pivot element at its correct position in sorted array. the worst case of quickSort occurs when one part after partition contains all elements and other part is empty. For example, if the input array is sorted and if last or first element is chosen as a pivot, then the worst occurs.
Q.6 Given a big string of characters, how to efficiently find the first unique character in it?
Answer: The efficient solution is to use character as an index in a count array. Traverse the given string and store index of first occurrence of every character, also store count of occurrences. Then traverse the count array and find the smallest index with count as 1.
Q.7 A sorted array is rotated at some unknown point, how to efficiently search an element in it.
Answer: A simple approach is linear search, but we can search in O(Logn) time using Binary Search. See Search an element in a sorted and pivoted array for more details. Other variations of this problem like find the minimum element or maximum element in a sorted and rotated array.
Q.8 How to count inversions in a sorted array?
Answer: Two elements arr[i] and arr[j] in an array arr[] form an inversion if a[i] > a[j] and i < j. How to count all inversions in an unsorted array. See Count Inversions in an array for all approaches.
Q.9 Given an array of size n with range of numbers from 1 to n+1. The array doesn’t contain any duplicate, one number is missing, find the missing number.
Answer: There can be many ways to solve it. The best among is to use XOR. See Find the missing number for details. There are many variations of this problem like find the two repeating numbers, find a missing and a repeating number.
