Android programmer interview:

Android programmer interview will encounter algorithm (part 1 about binary tree that thing) attached Offer situation

Android Programmer Interview Algorithms (Part 2 Breadth-First Search)

Android Programmer Interview algorithms (Part 3 depth-first Search – Backtracking)

Android Programmer interview algorithms (Part 4 Message queue applications)

Algorithms encountered by Android Programmers (Part 5 Dictionary Tree)

Algorithms encountered by Android programmers (Part 6 PriorityQueue)

Algorithms encountered by Android Programmers (Part 7 Topological Sorting)

It took more than four months to update. I came to the United States at the end of October and started to work. There were many miscellaneous things in the middle, and I went out for several trips during Thanksgiving and Christmas holidays, which have been delayed until now.

This time I want to talk about a more classic Java data structure. PriorityQueue, some algorithms corresponding to the PriorityQueue.

A priority queue sounds like a data structure for sorting, but it encapsulates insert ->push and fetch queue headers ->poll().

In many interview algorithm rounds, the direct request of the interviewer to write the sorting algorithm has been very few, the first is that the sorting algorithm is actually not easy to write… Joy: : joy: : joy: : joy: : joy: : joy:, the second is now sorting algorithm is very mature, also asked what doorways. So in many cases the interviewer will be more inclined to ask the interviewer about the algorithm for some of the sub-scenarios in the sorting scenario. In Java, PriorityQueue already provides most of the API we need, so let’s look at some classic PriorityQueue algorithms.

1. Conference room problems

The conference room problem is arguably one of the most representative problems in sorting/priority queue applications. The problem is simply to determine, given a set of meeting data, whether a person can attend all meetings in one piece, or to put it another way, what is the minimum number of meeting rooms the organizer needs in order for all meetings to be held as usual (without meeting room conflicts).

Given a data structure,


public class Interval {
        /** Meeting start time **/
        int start;
        
        /** Meeting end time **/
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, inte) { start = s; end = e; }}Copy the code

We’re going to implement a Boolean method that returns a value

public boolean canAttendMeetings(Interval[] intervals)

Given a List of intervals, determine whether a person can participate in all meetings in the List. Such as:

Two arrow lines represent the span of a meeting. In the figure above, the two meetings do not overlap directly, as shown by the red line in the figure. Even if the red line is moving parallel from left to right, it will not cross over the arrow line of one meeting. So in the case above, one person can attend all meetings.

But as you can see below:

In these cases, one person can’t participate in all of the meetings, and obviously the red line can cross both of the arrow lines.

So what’s the way to tell?

If you think about it in your normal mind, you’re going to say, are we going to write a loop that tells you if all the meetings are at that time and if more than one is at that time, it’s going to return false?

This is certainly not possible, because you are not sure of the fine granularity of time, is it seconds? Milliseconds? Minutes? We can’t write a for loop without knowing that.

So we can think another way. Since the for loop is not possible, can we regard the beginning or end of each meeting as an Event? Each Event can be divided into two types, one is the start and the other is the end. Without the need to loop through time itself.

Such as:

In order by timeline, we would have three meetings in sequence, with the start and start of the three meetings arranged in this order. From this example, we can easily see that there are three meetings going on at the same time. But why? Student: Is it because you see the overlap of line segments? The real reason is that our first End event entered after the three start events entered.

So, after sorting all the events, every time we have a start event, the number of meetings needs to be +1, and every time we have an end event, the number of meetings needs to be -1. Because end represents the end of a meeting, the number of meeting rooms required can be reduced.

With that in mind, we can write code.

Define an event:



 public class TimeEvent {
        / * * * * / start type
        public static final int start = 0;
        / * * * * / end type
        public static final int end = 1;
        /** The event occurred **/
        public int time;
        /** The type of the event, start or end **/
        public int type;

        public TimeEvent(int type, int time) {
            this.type = type;
            this.time = time; }}Copy the code

public boolean canAttendMeetings(Interval[] intervals) {
		if (intervals.length == 0) {
			return true;
		} else {
            /** ** defines a priority queue in which events are ordered from smallest to largest **/
			PriorityQueue<TimeEvent> priorityQueue = new PriorityQueue<>(new Comparator<TimeEvent>() {
				@Override
				public int compare(TimeEvent o1, TimeEvent o2) {
					// TODO Auto-generated method stub
					if (o1.time == o2.time) {
						/** ** the two ifs here may be difficult to understand temporarily, but I will explain **/ below
						if (o1.type == TimeEvent.start && o2.type == TimeEvent.end) {
							return 1;
						}
						if (o2.type == TimeEvent.start && o1.type == TimeEvent.end) {
							return -1; }}returno1.time - o2.time; }});for (int i = 0; i < intervals.length; i++) {
                /** ** creates start and end events and places them in the priority queue **/
				priorityQueue.add(new TimeEvent(TimeEvent.start, intervals[i].start));
				priorityQueue.add(new TimeEvent(TimeEvent.end, intervals[i].end));
			}

			int max = 0;
			int current = 0;
			while(! priorityQueue.isEmpty()) { TimeEvent event = priorityQueue.poll();if (event.type == TimeEvent.start) {
                    /** Return false/current = current +1 if the number of meeting rooms is greater than or equal to 2; if (current >= 2) { return false; }} else {/** If it is a start event, the number of meeting rooms -1. By this hour, a meeting was over. Although we ** don't care which meeting ends. * * /
					current = current - 1; }}return true; }}Copy the code

The commented paragraph in the code above:


if (o1.type == TimeEvent.start && o2.type == TimeEvent.end) {
	return 1;
}
if (o2.type == TimeEvent.start && o1.type == TimeEvent.end) {
	return -1;
}


Copy the code

It actually deals with a boundary case like this:

When the start of the latter event and the end of the former event are at the same time, does this situation require two conference rooms or one?

The answer is it depends…

If the problem requires only one conference room, then if two timeEvents are start and end, and the time is the same, we must first process end, because the number of conference rooms will be -1 first.

According to the example in the figure, the number of meeting rooms will vary from 1,0,1,0.

If there are two timeEvents, respectively start and end, and the time is the same, we must deal with start first, because the number of conference rooms will be +1 first.

According to the example in the figure, the number of meeting rooms will vary as follows :1,2,1,0.

The peak of the conference room is different in both cases. So going back to the last code, I’m sure you can understand what the “if” in this code is?

2. The problem of merging line segments

Assume that given a set of line segments, the overlapping line segments are required to return into a new line segment, for example:

A situation in which

The second case

The third case, no change:

The solution here is the same as above: first sort the installation start time of each line segment. The difference is that each time the current line segment is processed, compare it with the previous line segment to see if there is overlap. If there is overlap, delete the previous line segment and generate a new line segment.

Here, a Stack works perfectly!

The steps are as follows,

1. Line segments are sorted in the priority queue

2. Extract the first line segment of the queue each time

3. Compare with the top line segment of the stack.

4. If there is overlap, pop the top line segment, generate a new line segment and put it on the top of the stack, repeat the first step

The reason we only need to deal with the top line each time is that if there is a conflict between the top line and the inner line before the top line, we dealt with it in the previous step, so there is absolutely no way that the first line in the current queue overlaps with the non-top line.

The code is as follows:

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        /** ** sort all line segments by priority queue, according to start time **/
		PriorityQueue<Interval> priorityQueue = new PriorityQueue<Interval>(new Comparator<Interval>() {
			public int compare(Interval o1, Interval o2) {
				return o1.start - o2.start;
			};
		});
		for (int i = 0; i < intervals.size(); i++) {
			priorityQueue.add(intervals.get(i));
		}
		priorityQueue.add(newInterval);

        /** ** use a stack to store processed line segments **/
		Stack<Interval> stack = new Stack<>();
		stack.push(priorityQueue.remove());
        /** **while loop processes line segment **/
		while(! stack.isEmpty() && ! priorityQueue.isEmpty()) { Interval inItem = priorityQueue.remove(); Interval originalItem = stack.pop();/** ** When line segments do not completely overlap, the minimum start time and the maximum end time are taken to generate a new line segment **/
			if (inItem.start <= originalItem.end && inItem.end > originalItem.end) {
				stack.push(new Interval(originalItem.start, inItem.end));
                /** ** When line segments overlap completely, take the line segment with the highest coverage **/
			} else if (inItem.start <= originalItem.end && originalItem.end >= inItem.end) {
				stack.push(originalItem);
			} 
               /** ** When line segments do not overlap, the two are pushed together **/
            else{ stack.push(originalItem); stack.push(inItem); }}/** ** Because the stack output is inverted, flip it once... * * /
		Stack<Interval> stack2 = new Stack<>();
		while(! stack.isEmpty()) { stack2.push(stack.pop()); } ArrayList<Interval> arrayList =new ArrayList<>();
		while(! stack2.isEmpty()) { arrayList.add(stack2.pop()); }return arrayList;

	}

Copy the code

PS: In fact, after I wrote it, I realized that it would be better to have a LinkedList instead of a stack in the code… I don’t have to flip it once. Readers can find out for themselves…

2. Urban skyline

The final question is left to the reader, the question of urban skylines:

After giving the coordinates and heights of several groups of urban buildings, return the skyline that should be drawn at last. This is also a problem that requires sorting data and processing according to events. This is a slightly more complex problem, but the principle is the same: priority queues are used.