Massive Algorithms: Interview Misc Part 3

Interview Misc Part 3

http://ninefu.github.io/blog/RelationCosts/

 public List<Node> findShortestPath(List<List<Integer>> relations, int start, int target) {
  if (relations == null || relations.size() < 0) {
   return null;
  }
  HashMap<Integer, Node> map = new HashMap<>();
  for (int i = 0; i < relations.size(); i++) {
   Node person;
   if (map.containsKey(i)) {
    person = map.get(i);
   } else {
    person = new Node(i);
    map.put(i, person);
   }
   if (i == start) {
    person.minCost = 0;
    person.minPath.add(person);
   }
   for (Integer integer : relations.get(i)) {
    Node after = map.getOrDefault(integer, new Node(integer));
    map.put(integer, after);
    person.frontier.add(after);
   }
  }
  
  dijkstra(map, start, target);
  return map.get(target).minPath;
 }
 
 public void dijkstra(HashMap<Integer, Node> map, int start, int target) {
  PriorityQueue<Node> frontiers = new PriorityQueue<>((a,b) -> (a.minCost - b.minCost));
  Node startNode = map.get(start);
  for (Node next : startNode.frontier) {
   next.minCost = (next.person - startNode.person) * (next.person - startNode.person);
   next.minPath = new LinkedList<>(startNode.minPath);
   next.minPath.add(next);
   frontiers.add(next);
  }
  while (!frontiers.isEmpty()) {
   Node cur = frontiers.poll();
   for (Node next : cur.frontier) {
    int oldCost = next.minCost;
    int cost = cur.minCost + (next.person - cur.person) * (next.person - cur.person);
    if (cost < next.minCost) {
     next.minCost = cost;
     next.minPath = new LinkedList<>(cur.minPath);
     next.minPath.add(next);
    }
    if (oldCost == Integer.MAX_VALUE) {
     frontiers.add(next);
    }
   }
  }
 }
 
 public class Node {
  int person;
  int minCost;
  List<Node> minPath;
  List<Node> frontier;
  
  public Node(int person) {
   this.person = person;
   minCost = Integer.MAX_VALUE;
   minPath = new LinkedList<>();
   frontier = new LinkedList<>();
  }
 }

http://ninefu.github.io/blog/PageDisplay/

Each page has 12 listings
Try to avoid listings with the same host ID in the same page
If the number of remaining listings is less than 12, allow duplicated host ID in the same page// not implemented?

 public static List<List<String>> displayPages(List<String> input) {
  LinkedList<List<String>> result = new LinkedList<>();
  if (input == null || input.size() == 0) return result;
  
  HashSet<String> visited = new HashSet<>();
  LinkedList<String> page = new LinkedList<>();
  Iterator<String> iter = input.iterator();
  
  while (iter.hasNext()) {
   String entry = iter.next();
   String host = entry.split(",")[0];
   if (visited.add(host)) {
    page.add(entry);
    iter.remove();
   }
   if (page.size() == 12 || !iter.hasNext()) {
    visited.clear();
    iter = input.iterator();
    if (page.size() == 12) {
     // sort the list
     result.add(new LinkedList<>(page));
     page = new LinkedList<>();
    }
   }
  }
  if (page.size() != 0) {
   result.add(page);
  }
  return result;
 }
 
 public static List<List<String>> displayFast(List<String> input) {
  List<List<String>> result = new LinkedList<>();
  if (input == null || input.size() == 0) return result;
  
  int notFullPageNumber = 0;
  HashMap<String, Integer> map = new HashMap<>(); // <host id, last inserted page index>
  for (int i = 0; i < input.size(); i++) {
   String entry = input.get(i);
   String host = entry.split(",")[0];
   int page = map.getOrDefault(host, -1);
   // never seen host id, insert into the first page that is not full
   if (page == -1) {
    if (result.size() <= notFullPageNumber) {
     result.add(new LinkedList<>());
    }
    result.get(notFullPageNumber).add(entry);
    map.put(host, notFullPageNumber);
    if (result.get(notFullPageNumber).size() == 12) {
     notFullPageNumber = findNextNotFullPage(notFullPageNumber, result);
    }
   } else {
    // duplicate id, insert into the first not-full page after the last inserted index
    int nextInsertPageNumber = findNextNotFullPage(page, result);
    if (nextInsertPageNumber == result.size() && 
      result.get(nextInsertPageNumber - 1).size() + input.size() - i > 12) {
     result.add(new LinkedList<>());
    } else if (nextInsertPageNumber == result.size()){
     nextInsertPageNumber--;
    }
    result.get(nextInsertPageNumber).add(entry);
    map.put(host, nextInsertPageNumber);
   }
  }
  return result;
 }
 
 public static int findNextNotFullPage(int currentPageNumber, List<List<String>> result) {
  int res = currentPageNumber + 1;
  while (res < result.size() && result.get(res).size() == 12) {
   res++;
  }
  return res;
 }

http://ninefu.github.io/blog/MeetingIntervals/

 * 每个subarray都已经sort好
举例：
[
  [[1, 3], [6, 7]],
  [[2, 4]],
  [[2, 3], [9, 12]].
]
返回
[[4, 6], [7, 9]]
N个员工，每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals
解法：这题最简单的方法就是把所有区间都拆成两个点，然后排序，然后扫描，每次碰到一个点如果
是左端点就把busy_employees加1，否则减1，等到每次busy_employees为0时就是一个新的区间。
这样复杂度O(MlogM)，M是总共区间数。但是我当时也不知道是脑抽了还是脑子太好用了，弄了个堆的，
堆里N个元素，存每个员工的下一个端点，如果堆顶是某个员工的左端点就busy_employees加1，否则减1。
这样好处是时间复杂度低了一点点，坏处是给面试官讲了半天而且代码不是太好写……不建议这么做.
 * @author yihuifu
 *
 */
public class MeetingIntervals {

 public static void main(String[] args) {
  MeetingIntervals meetingIntervals = new MeetingIntervals();
  List<List<Interval>> intervals = new LinkedList<>();
  for (int i = 0; i < 3; i++) {
   intervals.add(new LinkedList<>());
   switch (i) {
    case 0: 
     intervals.get(i).add(meetingIntervals.new Interval(1,3));
     intervals.get(i).add(meetingIntervals.new Interval(6,7));
     break;
    case 1:
     intervals.get(i).add(meetingIntervals.new Interval(2,8));
     break;
    case 2:
     intervals.get(i).add(meetingIntervals.new Interval(2,3));
     intervals.get(i).add(meetingIntervals.new Interval(9,12));
     break;
   }
  }
  List<Interval> freeIntervals = meetingIntervals.findFreeIntervals(intervals);
  for (Interval interval : freeIntervals) {
   System.out.println(interval.toString());
  }
 }
 
 public List<Interval> findFreeIntervals(List<List<Interval>> intervals) {
  List<Interval> result = new LinkedList<>();
  if (intervals == null || intervals.size() == 0) {
   return result;
  }
  LinkedList<Interval> all = new LinkedList<>();
  for (int i = 0; i < intervals.size(); i++) {
   for (int j = 0; j < intervals.get(i).size(); j++) {
    all.add(intervals.get(i).get(j));
   }
  }
  Collections.sort(all, (a,b) -> (a.startTime - b.startTime));
  PriorityQueue<Interval> pq = new PriorityQueue<>((a,b) -> a.endTime - b.endTime);
  pq.offer(all.get(0));
  for (int i = 1; i < all.size(); i++) {
   Interval prev = pq.poll();
   Interval cur = all.get(i);
   if (cur.startTime <= prev.endTime) {
    prev.endTime = Math.max(prev.endTime, cur.endTime);
   } else {
    pq.offer(cur);
   }
   pq.offer(prev);
  }
  Interval prev = pq.poll();
  while (!pq.isEmpty()) {
   Interval cur = pq.poll();
   result.add(new Interval(prev.endTime, cur.startTime));
   prev = cur;
  }
  return result;
 }
 
 public class Interval {
  int startTime;
  int endTime;
  
  public Interval(int start, int end) {
   startTime = start;
   endTime = end;
  }
  
  @Override
  public String toString() {
   return "" + startTime + " " + endTime;
  }
 }

http://ninefu.github.io/blog/CIDR/

 * 输入一个ip，和一个count来表示一组ip, e.g.   7.7.7.7和3表示 7.7.7.7, 7.7.7.8, 7.7.7.9, 
 * 输出这组ip的CIDR形式.CIDR表达是： ip地址/掩码位数 表示一个区间
 * 比如 0.0.0.8 / 30 就是以0.0.0.8为准，前30位不能变--》0.0.0.(0000 10 00)--0.0.0.(0000 10 11) 
 * 然后给你一个起始ip，和数量。用最少的cidr表示这个区间
 * @author yihuifu
 
 public void getCIDRS(String binaryIP, int count, List<String> res) {
  while (count > 0) {
   int zero = 0, last = binaryIP.length() - 1;
   while (last >= 0 && binaryIP.charAt(last) == '0') {
    if (count - (int) Math.pow(2, zero + 1) >= 0) {
     zero++;
     last--;
    } else {
     break;
    }
   }
   String cidrIP = binaryToDecimal(binaryIP) + "/" + (32 - zero);
   System.out.println("Found one CIDR " + cidrIP);
   res.add(cidrIP);
   count -= (int) Math.pow(2, zero);
   binaryIP = getNextBinaryIP(binaryIP, zero);
  }
  
 }
 
 public String getNextBinaryIP(String prevIp, int lastZero) {
  System.out.println("prevIP " + prevIp);
  int one = 32 - 1 - lastZero;
  while (one >= 0 && prevIp.charAt(one) == '1') {
   one--;
  }
  StringBuilder res = new StringBuilder(prevIp.substring(0, one));
  res.append("1");
  while (res.length() < 32) {
   res.append("0");
  }
  return res.toString();
 }
 
 public String binaryToDecimal(String binaryIP) {
  StringBuilder sb = new StringBuilder();
  for (int i = 0; i < binaryIP.length(); i += 8) {
   String subBinary;
   if (i < 24) {
    subBinary = binaryIP.substring(i, i + 8);
   } else {
    subBinary = binaryIP.substring(i);
   }
    
   Integer sub = Integer.parseInt(subBinary, 2);
   sb.append(sub);
   if (i < 24) {
    sb.append(".");
   }
  }
  System.out.println("convert " + binaryIP + " to " + sb.toString());
  return sb.toString();
 }
 
 public String decimalToBinary(String decimalIP) {
  StringBuilder sb = new StringBuilder();
  String[] ips = decimalIP.split("\\.");
  for (int i = 0; i < ips.length; i++) {
   Integer sub = Integer.parseInt(ips[i]);
   String binarySub = Integer.toBinaryString(sub);
   int missingDigit = 8 - binarySub.length();
   String zeros = "";
   while (missingDigit > 0) {
    zeros += "0";
    missingDigit--;
   }
   sb.append(zeros + binarySub);
  }
  System.out.println("convert " + decimalIP + " to " + sb.toString());
  return sb.toString();
 }

Interview Misc Part 3

Labels

Popular Posts