Given an n by n matrix with zeros and ones, find the largest sub-matrix full of ones in O(n2) time.
Given an array of size n+1 whose entries are integers in the range [1, n], find an integer that occurs two or more times. Use only O(1) space and treat the input as read-only. Solution.
A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n - 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.
Find an Euler tour in an undirected graph, where an Euler tour is a closed circuit using all the edges of the graph.
Given an undirected graph, identify the 'Bottleneck Spanning Tree' of an undirected graph, which is defined to be any spanning tree that minimizes the weight of the heaviest edge used in the tree. In the usual 'Minimum Spanning Tree' problem, the sum of weights is minimized.
Find a satisfying assignment to variables in a 3-SAT formula where each clause has at most two literals.
A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible. Solution.
Given the head of a linked list, identify if it contains a loop or not. Solution.
There are n persons at a party. Each person knows at most 3 other persons at the party. Split the party into two groups so that each person knows at most one other person within the group (s)he belongs to.
Given an array with integers, find the sub-array with the maximum sum.
The number of binary strings of length k such that two 1's are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.
Randomly permute an array of integers.