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] )
Daily Archives: October 3, 2015
Count Inversions – Count Smaller on Right
Given an integer array, count the number of inversions.
Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Max Surpasser
For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers.
For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser.
Find the single number that duplicates one or more times
Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
Walls and Gates – find shortest escape paths
You are given a m x n 2D grid initialized with these three possible values.
-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.
Assign binary operators to evaluate to target value
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 -> []
Add two number represented by Linked Lists
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 -> 3
Longest sub-string with no duplicate chars
Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Dutch National Flag (DNF) problem (3-way partitioning)
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Container With Most Water
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. Note: You may not slant the container.