Given an array v of n numbers, where n=2k, k>0 be a natural number, find the minimum and maximum element in v. There are no assumptions regarding the orders of the elements of v. A basic iterative approach would require 2(n-1) comparisons (n-1 comparisons to find the minimum and n-1 comparisons to find the maximum). However, your program MUST perform at most 3/2n-1 comparisons. Difficulty: … Continue reading Min-max in array

Given an array v of distinct numbers, and a number k where k is smaller than the size of v, find the k-th smallest element in the array. A simple solution would be first sorting the array in growing order and than selecting the k-th element which can be done in θ(n logn). However, your program MUST run in θ(n) on average. Difficulty: Medium. Input There … Continue reading K-th smallest element in unsorted array

Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n words of lengths l1, l2,…,ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line … Continue reading Printing Neatly

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive. A naïve algorithm of O(n2) is trivial. You MUST do better than that. Difficulty: Very hard. Input The first line contains 3 integers separated by spaces: n, representing the length of the integer array nums. lower. upper. The second line is the integer … Continue reading Count of Range Sums

Merge Sort is a “Divide and Conquer” algorithm which first divides an input array in two sub-arrays, then it calls itself for those two sub-arrays, orders them and finally merges them into the original array. Write a merge sort program to sort an integer array in ascending order. Difficulty: Easy. Input One integer representing the length of the integer array. n integers with neighboring elements separated by a space representing the … Continue reading Merge Sort

A partition of a positive integer n is a multiset of positive integers such that their sum is equal to n. We denote the number of partitions of n by p(n). What is the number of ways to partition n into no more than k positive integers? Difficulty: Very hard. Input There are two integers, n and k. Output Output the number of ways modulo 10^9+7 to split n into no more than k positive integers. Example Given n=5 … Continue reading Integer Partition

Going from the point (x1,y1) to the point (x2,y2) in the Cartesian graph takes at least |x1−x2|+|y1−y2| steps moving unit length along the x-axis or the y-axis at a time (taxicab geometry). We now wonder, how many ways are there, to go from (x1,y1) to (x2,y2) using least steps, and without crossing or touching the line y=x? Difficulty: Medium. Input Four integers, representing x1, y1, x2, y2, respectively. Output The number of ways modulo 10^9+7 to go from (x1,y1) to (x2,y2) using least steps, … Continue reading Lattice Paths