Retrieve data from a Map reverse-ordered by value and then ordered by key

Problem

Given a Map of strings to their frequencies. Find top N-most frequent strings. If there is a tie get lexicographically smallest names first.

Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

List<String> findTopNNames(Map<String, Integer> data, int n) { Comparator<Map.Entry<String, Integer>> cmpByValueDesc = Map.Entry.comparingByValue(Comparator.reverseOrder()); Comparator<Map.Entry<String, Integer>> cmpByKey = Map.Entry.comparingByKey(); Comparator<Map.Entry<String, Integer>> cmp = cmpByValueDesc.thenComparing(cmpByKey); return data.entrySet().stream() .sorted(cmp) .map(Map.Entry::getKey) .limit(n) .collect(Collectors.toList()); }

Triangle rasterization under the hood (the old-school approach)

I didn't find a single source which would gave me a complete and clear picture of how to rasterize a triangle in a simplest way.

So, here's my attempt to put everything in order.

Consider, that we know how to draw a line and nothing more. Here's the corresponding method declaration for it:

void drawLine(int x0, int y0, int x1, int y1, Color color);

We need to implement a method which will draw a triangle and fill it with a specified color. Here's the corresponding method declaration:

void drawTriangle(Vec2 v0, Vec2 v1, Vec2 v2, Color color);

Here's the visual representation of what this method should do:

Initial vertices

Rasterized triangle

drawTriangle(v0, v1, v2, Color.BLACK)

============================>

How many numbers in the given interval with a bit set

Problem: given two numbers a and b find how many numbers with a bit x set are there in the interval [a,b].

Example:

Input: 5 8 2

Output: 3

Explanation:

5 = 0101
6 = 0110
7 = 0111
8 = 1000

The second bit (starting from the least significant bit with index 0) is set only in numbers 5, 6 and 7, so there are 3 numbers in the interval [5, 8] with the second bit set.

Solution:

A fast way to find out whether two elements in matrix share the same diagonal

Let's have the following matrix:

     1 2 3 4 5
     -----------
1 | 0 0 0 0 0
2 | 0 0 1 0 0
3 | 0 0 0 0 0
4 | 1 0 0 0 0
5 | 0 0 0 0 0

with two points: (x1, y1) = (2, 3) and (x2, y2) = (4, 1).

The fastest way to find out whether these two points share the same diagonal is the result of this expression:

bool result = (x1 + y1 == x2 + y2) or (x1 - y1 == x2 - y2)

Now let's complicate the task. Given matrix n x n with m points, find the minimum number of diagonals which contain at least two points. The first line of the input contains: n m. The next m lines contain points with coordinates (xi, yi).