Given 5 boxes with different weight
[24, 27, 17, 15, 17], distribute the weight as even as possible among 3 trucks of the same size. The trucks can fit unlimited number of boxes. The weight of the boxes can’t be transferred, for example move
4 from box 1 (originally weight
24) and transfer to box 2.
What if we have more boxes with different weight, let’s say 6 boxes with weight of
[1, 2, 17, 21, 7, 6].
What if the number of truck change to 5 trucks?
What’s the most effective algorithm to distribute the boxes evenly (in weight) within all the trucks?
A simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
A comparison-based sorting algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the smallest element and moving that to the sorted region.
Larger nodes don’t stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
The steps are:
- Pick an element, called a pivot, from the array.
- Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called thepartition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It uses information about variations and inconsistencies in English spelling and pronunciation to produce a more accurate encoding, which does a better job of matching words and names which sound similar.
Source: Wikipedia: Metaphone
Why does this matter?
In real life, this algorithm can be used for voice translation as well as similar sounding names search.
a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.
Source: Wikipedia: Levenshtein Distance
Why does this matter?
Levenshtein distance is a form of approximate string matching. In real life application, Levenshtein distance can be used in spell checking, correction in OCR system (Optical Character Recognition), record linkage, auto suggest words in smart phone and many more.