Posts

Showing posts from July, 2017

TinyURL, by LeetCode

Fun beginner's problem by LeetCode, here it is  https://leetcode.com/problems/encode-and-decode-tinyurl/#/description : TinyURL is a URL shortening service where you enter a URL such as  https://leetcode.com/problems/design-tinyurl  and it returns a short URL such as  http://tinyurl.com/4e9iAk . Design the  encode  and  decode  methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. Simple solution: keep two hash-tables, one mapping long URLs to short URLs, and another one the other way around (short to long). Use a random number generator to generate the short version. Mix that all up, and voila! public class Codec { private Hashtable longToShort = new Hashtable(); private Hashtable shortToLong= new Hashtable(); // Encodes a URL to a shortened URL public string encode(string longUrl)

Solve the Equation (LeetCode)

Image
Problem is here:  https://leetcode.com/problems/solve-the-equation/#/description , or copied/pasted: Solve a given equation and return the value of  x  in the form of string "x=#value". The equation contains only '+', '-' operation, the variable  x  and its coefficient. If there is no solution for the equation, return "No solution". If there are infinite solutions for the equation, return "Infinite solutions". If there is exactly one solution for the equation, we ensure that the value of  x  is an integer. Example 1: Input: "x+5-3+x=6+x-2" Output: "x=2" Example 2: Input: "x=x" Output: "Infinite solutions" Example 3: Input: "2x=x" Output: "x=0" Example 4: Input: "2x+3x-6x=x+2" Output: "x=-1" Example 5: Input: "x=x+2" Output: "No solution" This is a problem of attention to details  and modularization

Average of Levels in Binary Tree (LeetCode)

Here is the problem (link: https://leetcode.com/problems/average-of-levels-in-binary-tree/#/description ): Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Example 1: Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. Note: The range of node's value is in the range of 32-bit signed integer. One way to solve it is the following: a) First get the number of levels in the tree (one-line function) b) After that do a DFS where you pass along an array to keep track of the sum and count per level, and an index indicating in which level you're at c) At the end transform the array into an IList while calculating the avg per level Cheers, Marcelo. public class Solution { public IList<double> AverageOfLevels(TreeNode root) { if (root