Given a string s and some strings words of the same length. Find all the starting positions of the substrings in s that can be formed by concatenating all the strings in words. Note that the substrings must exactly match the strings in words, and there can be no other characters in the middle, but there is no need to consider the order of the … Continue reading Concatenation of all combinations of words

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