| Sorting algorithms | Techniques for Sorting In-place vs extra memory Analyze by counting compares and exchanges(array accesses) Selection Insertion Bubble Merge Quick 1. Selection Sorting Iterative and in-place sorting algorithm that divides the data structure in two sublists: the ordered one, and the unordered one First, find the smallest item in the array, and exchange it with the first entry. Then, find the next smallest item and exchange...
read more

| Implement pow(x,n) | Implement pow(x, n), which calculates x raised to the power n (i.e., xn). Input Output x = 2.00000, n = 10     1024.00000 x = 2.10000, n = 3     9.26100 x = 2.00000, n = -2     0.25000 Notes Brute Force Approach 2^ 12 = 2 * 2^11 = 2* 2* 2^10 and so on.. This takes O(n) and could be...
read more

| Complete Binary Tree | Given the root of a binary tree, determine if it’s a complete binary tree. (Complete if u go left to right and its filled) Complete Tree Not Complete Tree Notes If you ever encounter a NULL node, you must not encounter a non NULL node after that in a Level Order Traversal, this is the definition of a complete Binary Tree. Traverse by level...
read more

| Valid Number | A valid number can be split up into these components (in order): A decimal number or an integer. (Optional) An ‘e’ or ‘E’, followed by an integer. A decimal number can be split up into these components (in order): (Optional) A sign character (either ‘+’ or ‘-‘). One of the following formats: One or more digits, followed by a dot ‘.’. One or more digits,...
read more

| Custom Sort String | You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation...
read more

| Simplify Path | Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path. “/a/./” –> means stay at the current directory ‘a’ “/a/b/..” –> means jump to the parent directory from ‘b’ to ‘a’ ”////” –> consecutive multiple ‘/’ are a valid path, they are equivalent to...
read more