Questions with a spec which requires all answers to meet certain time complexity restrictions. This could be specific ("Your answer must be O(n^2) where n is the number of items in the input"), or at the level of complexity classes ("Your answer must be polynomial in the number of items in the ...
11
votes
9answers
998 views
A classic sorting code-golf question
This is a code-golf question.
Input
A list of non-negative integers in whatever format is the most convenient.
Output
The same list in sorted order in whatever format is the most convenient.
...
11
votes
11answers
2k views
Solve the Secretary Problem
The Secretary Problem is a famous problem described as thus:
You need a new secretary
You have N applicants that you can interview one at a time
You are able to score each applicant after the ...
19
votes
3answers
302 views
Permutation Square Root
In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list:
2 1 4 3
represents the permutation σ such that σ(1) = 2, σ(2) = 1, σ(3) = 4, and σ(4) = 3.
...
17
votes
11answers
470 views
Maximise the squared difference
Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4:
[1, 3, 4, 2]
We'll consider this list to be cyclic, such that 1 and 2 are treated as adjacent. One quantity we ...
5
votes
2answers
181 views
Convolve integers in subquadratic time
An linear discrete convolution is an operation that turns two vectors of numbers into a third vector of numbers by multiplying elements inside-out. Formally, for two vectors a and b with elements 0 to ...
6
votes
3answers
285 views
Symmetric boolean functions as Zhegalkin polynomials
Let 𝔹 = ℤ2 = {0, 1} be the set of booleans. A symmetric boolean function in n arguments is a function fS : 𝔹n ↦ 𝔹 that checks if the number of its true arguments is in S, i. e. a ...
19
votes
1answer
195 views
One goes up, the other comes down
Introduction
In this challenge, your task is to decide whether a given sequence of numbers can be separated into two subsequences, one of which is increasing, and the other decreasing.
As an example, ...
7
votes
2answers
314 views
Crack a Vigenère Cipher
A Vigenère Cipher is encrypted by repeating a keyword to be the length of the plaintext, and summing each character in that text with the corresponding letter in the plaintext modulo 26. (using ...
11
votes
2answers
395 views
Pair Capacitors
Capacitors are notorious for being manufactured with high tolerances. This is acceptable in many cases, but some times a capacity with tight tolerances is required. A common strategy to get a capacity ...
12
votes
3answers
284 views
Books on a Shelf
I have some books and a bookshelf. I would like to put as many books on the shelf as possible but I have a rule. All dimensions of the books (height, width and depth) should form a non-increasing ...
14
votes
5answers
676 views
Real-time string matching
Task
The task is to golf a real-time exact string matching algorithm of your choice.
Input
Two lines of text supplied on standard input, separated by a new line. The first line contains the ...
13
votes
4answers
885 views
Find the maximum of ax+b
You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.
Your program or function must run in expected (to the ...
14
votes
0answers
1k views
Longest common substring
This challenge is about writing code to solve the following problem.
Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.
...
21
votes
2answers
1k views
Book Stack Sort
When stacking books you usually want to put the largest ones at the bottom and the smallest ones at the top. However, my latent OCD makes me feel very uneasy if I've got two books where one is shorter ...
12
votes
15answers
3k views
Pick the longest stick
You are a young programming geek living with your 2 other best friends. Every week, one of you has to do all the chores of the house and you decide whose turn it is by picking a stick. The one who ...
7
votes
1answer
580 views
Approximate square root from algorithm time complexity
There have been a few square root challenges lately, but I think this one is different.
Challenge
Find an algorithm such that the worst case time complexity is proportional to n^2 and the best case ...
