Given two sorted list, find the min distance of any 2 elements in 2 lists. For example, {1, 10, 20} and {5, 15, 21} min=21-20=1 {1, 10} and {15, 21} min=15-10=5 Solution 1 is to use merge sort. Compare abs(arr1[i]-arr[2] ) and min. Solution 2 is that it doesn’t compare in each merge. It only… Read More »
LRU can be implemented by map and doubly-linked-list. The key idea is that: 1. Maintain a head and tail, which is not null initially, 2. In Node, we store both key and value, 3. Create pickUp and setHead functions. public class LRUCache { class Node { int key; int val; Node pre; Node next; public… Read More »
Given a linked list. Use mergesort to sort this list. Time complexity is O(nlogn). package com.pli.project.algorithm.sort; import java.util.LinkedList; import java.util.List; /** * Created by lipeng on 2015/5/5. */ public class LinkedListMergeSort { public static void main(String[] args) { Node n1 = new Node(1); Node n2 = new Node(5); Node n3 = new Node(9); Node n4… Read More »
1. Delete edge. Delete the node which in-degree is 0, and the edges starting from it. In the end, there is no circle if all nodes are deleted. 2. Use DFS. It is similar to detecting cut point in a graph. Store the DFS visited sequence for each node. And find the back edge of each… Read More »