Convert String to ZigZag Bottom Up

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/zigzag-conversion/. Problem The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Example P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string...

Read More

Growth Rate - The Importance of Asymptotics

It really is true that if algorithm A is o(algorithm B) then for large problems A will take much less time than B. Definition: If (the number of operations in) algorithm A is o(algorithm B), we call A asymptotically faster than B. Example:: The following sequence of functions are ordered by growth rate, i.e., each function is little-oh of the subsequent function. log(log(n)), log(n), (log(n))2, n1/3, n1/2, n, nlog(n), n2/(log(n)), n2, n3, 2n, 4n, n! One way to compare 2 functions, is using L'Hospital rule. Here is good explanation: Growth...

Read More

Asymptotic Notation

Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course. Now we are going to be less precise and worry only about approximate answers for large inputs. The Big-Oh Notation Definition: Let f(n) and g(n) be real-valued functions of a single non-negative integer argument. We write f(n) is O(g(n)) if there is a positive real number c and a positive integer n0 such that f(n)≤cg(n) for all n≥n0. What does this mean? For large inputs (n≤n0), f is...

Read More

Given a BST with 2 nodes swapped, fix it

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/recover-binary-search-tree-problem/. Problem Given a BST with 2 nodes swapped fix it. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8 and 20, and BST is changed. Input Tree: 10 / \ 5 8 / \ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree....

Read More

Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/given-a-binary-search-tree-with-2-nodes-swapped-find-number-of-pairs-not-following-bst-properties/. Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8...

Read More

For a Given node of a binary tree, print the K distance nodes.

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/all-nodes-distance-k-in-binary-tree/. Problem You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted...

Read More

Print all nodes that are at distance k from a leaf node

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/nodes-at-distance-k-from-leaf-nodes-in-binary-tree/. Problem Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For...

Read More