Data Structure & Algorithms
Basic Process to Solve any Problem1. Read the Problem twice or thrice
2. Solve the Problem manually on Paper with 3 or 4 sets of data.
3. Optimize the Manual Steps
4. Write the Manual Steps as comments or pseudo code
5. Replace the comments or pseudo code with real code.
6. Optimize the real code.
Must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/
Families of Sorting Algo -
1. Linear -treat the problem of sorting as a single large operation.
2. Divide and Conquer - partition the data in smaller sets that can be independently sorted.
Measuring performance - depends on 1. Comparisons 2. Swaps.
1. Bubble Sort -
On Each Pass -
1. compare each array item to it's right neighbor
2. if the right neighbor is smaller then swap right and left
3. repeat for the remaining array items
Perform subsequent passes until no swaps are performed.
Performance - worst case O(n^2)
Average - O(n^2)
Best - O(n) - for small and nearly sorted data sets.
Not appropriate for larger unsorted data sets.
Space required : O(n) - as directly operates on array meaning it is a candidate algo when minimizing space is paramount.
Average and Worst case - O(N^2) - Not appropriate for large unsorted data sets.
This algo directly operates on input array so it's best candidate algo when space is paramount.
3. Selection Sort - Sorts the data by finding smallest item in array and swap it into array with first unsorted location. opposite to bubble sort as bubble sort find large item and swap to right but this algo find smallest and swap to left. It's similar to insertion sort.
1. Enumerate array from first unsorted item to end.
2. Find smallest element from unsorted array.
3. Swap the Item with First Unsorted Item.
static void SelectionSort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
int j = i + 1;
int minIndex = i;
while (j < arr.Length)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
j++;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
For More Selection-sort/
1. The Array is recursively split in half.
2. when Array is in group of One (1), it is reconstructed in sort order.
3. Each reconstructed array is merged with other half.
2. Pick a Pivot and partition the Array
3. Put All values smaller than pivot to left and larger to right - Pivot value is sorted now (Relative sort) as left side all smaller values and right side all larger values.
4. Perform pivot and partition algorithm on left and right partitions.
5. Repeat the steps until array is sorted
static void QuickSort(int[] arr)
{
int low = arr.GetLowerBound(0), high = arr.GetUpperBound(0);
Sort(arr, low, high);
}
static void QuickSort(int[] arr, int low, int high)
{
int pivot = Partition(arr, low, high);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, high);
}
static int Partition(int[] arr, int low, int high)
{
int i = low - 1;
int pivot = arr[high];
for (int j = low; j < high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
var temp1 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp1;
return i + 1;
}
Heaps-and-Priority-queues/
Common Computer Science Questions for Interview
Bit Manipulation
Data Structures
Array,
LinkedList - Reverse a LinkedList and detect a cycles Loops
Trees, Tree traversal - BFS, DFS , Searching, Creating Tree, Find Depth, Find Number of Elements
Stacks & Queues - Implement using Array or Linked List, build a queue from Stack - use 2 stacks -1 to hold queued items and 1 to dispense de-queued items
Algorithms
Searching - Linear, Binary
Tree Search - Sorted Binary Tree, Unsorted Tree - same as tree traversal
Sorting - Bubble, Insertion, Selection, Merge , Quick - Sorting Array , list (Sometimes Trees), insert into sorted list
Concurrency
Big O Notation
Bit Manipulation
Binary Conversion
Bit wise Operator
Bit Problems
Concurrency
Locks, Deadlocks, Race Conditions
Must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/
Sorting -
Sorting - arranging data in a collection based on comparison algorithm.Families of Sorting Algo -
1. Linear -treat the problem of sorting as a single large operation.
2. Divide and Conquer - partition the data in smaller sets that can be independently sorted.
Measuring performance - depends on 1. Comparisons 2. Swaps.
1. Bubble Sort -
1. compare each array item to it's right neighbor
2. if the right neighbor is smaller then swap right and left
3. repeat for the remaining array items
Perform subsequent passes until no swaps are performed.
Performance - worst case O(n^2)
Average - O(n^2)
Best - O(n) - for small and nearly sorted data sets.
Not appropriate for larger unsorted data sets.
Space required : O(n) - as directly operates on array meaning it is a candidate algo when minimizing space is paramount.
static void BubbleSort(int[]arr)
{
int j = 0;
while ( j< arr.Length)
{
for (int i =0; i < arr.Length-1; i++)
{
if (arr[i] > arr[i+1])
{
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
j++;
}
}
2. Insertion Sort -
1. Sort each item in array as they are encountered.
2. As the current items works from Left to right -
a. Everything to left of item is sorted.
b. Everything to right of item is unsorted.
3. The current Item is placed witin sorted selection.
For More - Insertion-sort/
static void InsertSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
var key = arr[i];
var j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key,
// to one position ahead of
// their current position
while (j >= 0 && key <arr[j])
{
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
Average and Worst case - O(N^2) - Not appropriate for large unsorted data sets.
Best Case Performance - O(N) - very good best case performance and can sort effectively very small or nearly sorted data sets.
This algo directly operates on input array so it's best candidate algo when space is paramount.
1. Enumerate array from first unsorted item to end.
2. Find smallest element from unsorted array.
3. Swap the Item with First Unsorted Item.
static void SelectionSort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
int j = i + 1;
int minIndex = i;
while (j < arr.Length)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
j++;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
Average and Worst case - O(N^2) - Not appropriate for large unsorted data sets.
Best Case Performance - O(N^2) - Not appropriate for large unsorted data sets. Better than bubble worse than Insertion.
This algo directly operates on input array so it's candidate algo when space is paramount.
Stable Algorithms - A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Background: a "stable" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:
peach
straw
apple
spork
If we sort the list by just the first letter of each word then a stable-sort would produce:
apple
peach
straw
spork
In an unstable sort algorithm,
straw or spork may be interchanged, but in a stable one, they stay in the same relative positions (that is, since straw appears before spork in the input, it also appears before spork in the output).
4. Merge Sort -
2. when Array is in group of One (1), it is reconstructed in sort order.
3. Each reconstructed array is merged with other half.
static void MergeSort(int[] arr)
{
Sort(arr, arr.GetLowerBound(0), arr.GetUpperBound(0));
}
static void Sort(int[] arr, int l, int r)
{
if (l < r)
{
int m = (l + r)/ 2;
Sort(arr, l, m);
Sort(arr, m + 1, r);
Merge(arr, l, m, r);
}
}
static void Merge(int[] arr, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
Time Complexity - O(N log N) in All Cases
Appropriate for Large data sets.
It's Stable Sort.
Auxiliary Space: O(n)
Algorithmic Paradigm: Divide and Conquer
5. Quick Sort
1. Divide and Conquer Algorithm2. Pick a Pivot and partition the Array
3. Put All values smaller than pivot to left and larger to right - Pivot value is sorted now (Relative sort) as left side all smaller values and right side all larger values.
4. Perform pivot and partition algorithm on left and right partitions.
5. Repeat the steps until array is sorted
static void QuickSort(int[] arr)
{
int low = arr.GetLowerBound(0), high = arr.GetUpperBound(0);
Sort(arr, low, high);
}
static void QuickSort(int[] arr, int low, int high)
{
int pivot = Partition(arr, low, high);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, high);
}
static int Partition(int[] arr, int low, int high)
{
int i = low - 1;
int pivot = arr[high];
for (int j = low; j < high - 1; j++)
{
if (arr[j] <= pivot)
{
i++;
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
var temp1 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp1;
return i + 1;
}
Worst Case Analysis - O(N^2) - Not appropriate for large sorted (inverse sort) data sets.
Average Case - O(N logN) - appropriate for large data sets.
Best Case Performance - O(N logN) - very good best case performance and can efficiently sort small and nearly sorted data sets
Space Required - O(N)
Heaps-and-Priority-queues/
Common Computer Science Questions for Interview
Bit Manipulation
Data Structures
Array,
LinkedList - Reverse a LinkedList and detect a cycles Loops
Trees, Tree traversal - BFS, DFS , Searching, Creating Tree, Find Depth, Find Number of Elements
Stacks & Queues - Implement using Array or Linked List, build a queue from Stack - use 2 stacks -1 to hold queued items and 1 to dispense de-queued items
Algorithms
Searching - Linear, Binary
Tree Search - Sorted Binary Tree, Unsorted Tree - same as tree traversal
Sorting - Bubble, Insertion, Selection, Merge , Quick - Sorting Array , list (Sometimes Trees), insert into sorted list
Concurrency
Big O Notation
Bit Manipulation
Binary Conversion
Bit wise Operator
Bit Problems
Concurrency
Locks, Deadlocks, Race Conditions
No comments:
Post a Comment