Given an array int32 arr[] of size n, return the number of non-empty contigious subarrays whose sum lies in range [a, b] Examples: count([1,2,3], 0, 3) = 4 ( [1], [2], [3], [1, 2]) count([-2,5,-1], -2, 2) = 3 ( [-2], [-1], [-2, 5, -1] ) Naive O(n^2) solution – def naive_algorithm(lst, a, b): result […]
Category Archives: Algorithms
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. […]
Given a value n cents and m type of coins with values { c1, c2, .. , cm} cents each. How many ways can we make the n cents by using the coins as many times as you want? For example, for n = 5 and C = {1, 2, 5}, there are 4 solutions […]
Given an array that contains a Post order traversal of a Binary Tree. Check if a possible Binary Tree formed from the postorder traversal is a Binary Search Tree. For example, a1=[1, 3, 4, 2, 7, 6, 5] is a BST but a2=[1, 3, 4, 6, 7, 2, 5] is not a BST. 5 5 […]
Given a Binary Tree T. 1. Find all paths from root to each of the leaves in T. 2. Find the longest path from root to a leaf (also called Max Depth or Height of the tree). 3. Find the path that has largest sum along the path in T. 4. Find distance (shortest) between […]
From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all […]
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value. For example: “232”, 8 -> [“2*3+2”, “2+3*2”] “00”, 0 -> [“0+0+0”, “0-0”, “0*0”] “102”, 2 -> [“1*0+2”] “45435”, 9191 -> […]
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (9 -> 9 -> 7) + (4 -> 3 -> 7) Output: 1 -> 5 -> 3 […]
Give a list of unsorted number, find the min window or min sublist or min subarray of the input, such as if sublist is sorted, the whole list is sorted too. For example, given array a={1,2,3,5,4,4,3,3,7,8,9} then min subarray to sort the complete array sorted is {5,4,3,3}. More example : for a={1,2,3,5,6,4,2,3,3,7,8,9} then min subarray […]