Johnie
BAN USERWe can keep a max heap of size k where we check each incoming element vs the top and if it's smaller we replace it. After we've gone through the list of N points we pop our heap into a list and reverse that list. Running time O(N*log(K)) extra space O(K).
List<Point> findClosestToOrigin(List<Point> points, int numToFind) {
PriorityQueue<Point> closestPoints = new PriorityQueue<>(Collections.reverseOrder());
for (Point point : points) {
if (closestPoints.size() < numToFind) {
closestPoints.add(point);
} else if (point.compareTo(closestPoints.peek()) < 0) {
closestPoints.poll();
closestPoints.add(point);
}
}
List<Point> closeList = new ArrayList<>();
while (!closestPoints.isEmpty()) {
closeList.add(closestPoints.poll());
}
Collections.reverse(closeList);
return closeList;
}
class Point implements Comparable {
double x, y;
double distanceFromOrigin() {
return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
}
@Override
public int compareTo(Object other) {
if (!(other instanceof Point)) {
throw new IllegalArgumentException("Points can only be compared with other points.");
}
double diff = (distanceFromOrigin() - ((Point) other).distanceFromOrigin());
if (diff == 0) {
return 0;
} else {
return diff > 0 ? 1 : -1;
}
}
}
Since the numbers are a positive we should be able to do this with a window function. We move the right side as long as we don't make the sum too large, otherwise we move the left one. Complexity O(N) time, O(1) space.
private boolean sumsToX(int[] arr, int target) {
int start = 0, end = 0, sum = 0;
while (end < arr.length) {
if (sum + arr[end] <= target) {
sum += arr[end++];
} else {
sum -= arr[start++];
}
if (sum == target) {
return true;
}
if (end < start) {
end = start;
sum = 0;
}
}
return false;
}
Here is an approach walking along the diagonal. General approach:
1. Start in the bottom left corner.
2. Subtract row index until you find a 0.
3. Add the row index + 1 to you total and move one column right.
4. Repeat from step 2 until you find the top or right edge of the matrix.
This is worst case O(N) since the length of the diagonal is proportional to N.
Code:
private int countNumZeroes(int[][] matrix) {
int row = matrix.length - 1, col = 0, numZeroes = 0;
while (col < matrix[0].length) {
while (matrix[row][col] != 0) {
if (--row < 0) {
return numZeroes;
}
}
// Add one since matrix index is 0 based
numZeroes += row + 1;
col++;
}
return numZeroes;
}
We can count up from 0 and reverse and add every number to itself which will give us the correct ordering. The important trick is to hold off with the odd length palindromes until we hit a new power of two.
private List<String> getBitPalindromes(int count) {
List<String> palindromes = new ArrayList<>(), oddLengths = new ArrayList<>();
palindromes.add("1");
int current = 1, powOfTwo = 0;
while (palindromes.size() < count) {
if (powOfTwo != Integer.numberOfLeadingZeros(current)) {
palindromes.addAll(oddLengths);
oddLengths.clear();
powOfTwo = Integer.numberOfLeadingZeros(current);
}
String left = Integer.toBinaryString(current);
String right = new StringBuilder(left).reverse().toString();
palindromes.add(left + right);
oddLengths.add(left + "0" + right);
oddLengths.add(left + "1" + right);
current++;
}
return palindromes.subList(0, count);
}
Start iterating over the possible substrings, continue to next substring immediately if the first char isn't a vowel or the last one is.
private void printFirstAndLast(String base) {
Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
String first = null, last = null;
for (int i = 0; i < base.length(); i++) {
if (!vowels.contains(base.charAt(i))) continue;
for (int j = i + 1; j < base.length(); j++) {
if (vowels.contains(base.charAt(j))) continue;
String substring = base.substring(i, j + 1);
if (first == null || substring.compareTo(first) < 0) {
first = substring;
}
if (last == null || substring.compareTo(last) > 0) {
last = substring;
}
}
}
System.out.println(first);
System.out.println(last);
}
On a theoretical level the problem is quite simple.
Take the list of commands. When repeated over and over the list can be simplified to a single translation t followed by a single rotation r.
The only way we can't build a wall that contains the robot is if it will travel in a single direction infinitely, e.g. r == 0 && t > 0.
So run through the list of commands updating the robots position and as long as it faces in a different direction than it started OR ends its travel in the start position the wall is possible.
If this problem is about how to do accurate 2d plane traversal using integer coordinates and angles that is a much harder problem to solve and I would be interested to see solutions.
One can make the following observation:
printing for k
is equivalent to
print all combinations of length k with 0 ones
print all combinations of length k with 1 ones
...
print all combinations of length k with k ones
A second observation is:
print all combinations of length k with n ones
is equivalent to
print (prepend 0 to all combinations of length k-1 with n ones)
print (prepend 1 to all combinations of length k-1 with n-1 ones)
This way we get a recursive function where we can cache intermediary results.
This is obviously more space inefficient than just generating all bit combinations and sorting them in place. Can anyone help me out with runtime analysis and tell me if it's faster?
Python class:
class KBitGenerator:
cache = {}
def generate(self, k):
result = []
for i in range(k + 1):
result += self.generate_for_num(k, i)
return result
def generate_for_num(self, length, num_ones):
if (length, num_ones) in self.cache:
return self.cache[(length, num_ones)]
result = []
if num_ones == 0:
result = [[0] * length]
elif length == num_ones:
result = [[1] * length]
else:
for pattern in self.generate_for_num(length - 1, num_ones):
result.append([0] + pattern)
for pattern in self.generate_for_num(length - 1, num_ones - 1):
result.append([1] + pattern)
self.cache[(length, num_ones)] = result
return result
I feel like people are making the logic more complicated than it needs to be. If MAX1 is the number furthest to the right on the natural number line and MIN1 is the number furthest to the left then there are only two possible candidates for largest triplet:
Candidate 1: MAX1 * MAX2 * MAX3
Candidate 2: MAX1 * MIN1 * MIN2
This is true for all natural numbers. To optimize we can exclude candidate 2 if MAX1 <= 0.
Find these and compare, time: O(n), space O(1).
One approach, if we're assuming multiple accesses to the data (otherwise linear find is best) is to set up a Trie where the node is the start of each subsequent word. In the trie we store indexes that match the current pattern.
That way, for any given pattern we can quickly get the indexes that can match the pattern based on the start of the camelcased words and we perform an individual match on those.
- Johnie July 08, 2016