From wiki, Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
C++ Class Hierarchy Pointer Assigments
Implicit Conversion of Classes: The address of an object of a derived class can be assigned to a pointer declared to the base class, but the base class pointer can be used only to invoke member functions of the base class
Profit Maximization – Maximum Single-Sell Profit problem
Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized.
Reverse Linked List – single pointer – in group of K
Reverse a link list using one/single pointer.
We first try to device straightforward solution to reverse a linked list recursively. For example, given a linked list 1->2->3->4->5->null, how we can reverse this? Let’s start with straightforward solution using two temp pointers. We will basically keep a new pointer to append nodes from the list into the front of new pointer. Below is both recursive and iterative solution in O(n) time.
Merge Sort
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.
Split The Linked List
Given a linked list and a number n. Split the link list into two based on the following pattern
input: 1->2->3->4->5->6->7->8->null and n=2
output: 1-2->3->4->null and 5->6->7->8->nullinput: 2->3->1->4->6->7->7->6->null and n=4
output: 2-3->null and 1->4->6->7->7->6->nullreturn the right partition pointer.
Binary Tree All Paths, Max Sum Path, Diameter, Longest Path, Shortest Path, Closest Leaf
Given a Binary Tree T.
1. Find all paths from root to each of the leaves in T.
2. Find the longest path from root to a leaf (also called Max Depth or Height of the tree).
3. Find the path that has largest sum along the path in T.
4. Find distance (shortest) between given two nodes in T.
5. Diameter of T or Longest path between any two nodes in T.
6. Find mirror image tree of T.
7. Find min length path that sums to a given value.
8. Find the closest leaf from root.
First non-repeating or unique character in a stream of characters
Given a stream of characters, find the first non-repeating i.e. unique character occurred.
For example, in a stream [a,c,b,a,d,a,…] first unique is ‘c’ but if another ‘c’ character comes to stream [a,c,b,a,d,a c,…] then first unique would be ‘b’.
C++ vs Java
The first difference is the syntax. Other than that, the major differences are:
C++
* OOP is optional.
* Compiled: produces non-portable native code.
* Manually managed memory. Garbage collection libraries are available.
* Source can be written to be portable, so a correctly written program can be compiled for any platform where a C++ compiler is available.
* Mostly used for medium-to-high performance applications, such as games.
How database indexing works?
Why is it needed?
When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.
Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire table space must be searched at N block accesses.
Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.
Static vs Volatile in Java
Declaring a static variable in Java, means that there will be only one copy, no matter how many objects of the class are created. The variable will be accessible even with no Objects created at all. However, threads may have locally cached values of it.
When a variable is volatile and not static, there will be one variable for each Object. So, on the surface it seems there is no difference from a normal variable but totally different from static. However, even with Object fields, a thread may cache a variable value locally.
This means that if two threads update a variable of the same Object concurrently, and the variable is not declared volatile, there could be a case in which one of the thread has in cache an old value.
Even if you access a static value through multiple threads, each thread can have it’s local cached copy! To avoid this you can declare the variable as static volatile and this will force the thread to read each time the global value.
However, volatile is not a substitute for proper synchronisation! For instance:
Maximum number of overlapping intervals – Merge Overlapping Intervals – Max Task Load
Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time.
For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5).
Floor and Ceiling of a Key in Sorted Array – Search Min Diff Element
Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x.
Weighted job/interval scheduling – Activity Selection Problem
Given N jobs where every job is represented by following three elements of it.
1) Start Time
2) Finish Time.
3) Weight representing Profit or Value Associated.
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.
Contiguous subarray with sum in a range
Given an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b]
Examples:
count([1,2,3], 0, 3) = 4 ( [1], [2], [3], [1, 2])
count([-2,5,-1], -2, 2) = 3 ( [-2], [-1], [-2, 5, -1] )
Count Inversions – Count Smaller on Right
Given an integer array, count the number of inversions.
Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Max Surpasser
For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers.
For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser.
Find the single number that duplicates one or more times
Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Walls and Gates – find shortest escape paths
You are given a m x n 2D grid initialized with these three possible values.
-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.
Assign binary operators to evaluate to target value
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
For example:
“232”, 8 -> [“2*3+2”, “2+3*2”]
“00”, 0 -> [“0+0+0”, “0-0”, “0*0”]
“102”, 2 -> [“1*0+2”]
“45435”, 9191 -> []