路公平店面redo过经

karat，面试官比较冷漠。。
开始是设计五小题，地里都有。

代码题我感觉还是有点难度对于我（lc只刷了100来道题），还好最后做出来了。
编程题如下：
/**
You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program.

Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

Sample output 1:
"Data Structures"


Sample input 2:
prereqs_courses2 = [
    ["Algorithms", "Foundations of Computer Science"],
    ["Data Structures", "Algorithms"],
    ["Foundations of Computer Science", "Logic"],
    ["Logic", "Compilers"],
    ["Compilers", "Distributed Systems"],
]


Sample output 2:
"Foundations of Computer Science"

Sample input 3:
prereqs_courses3 = [
["Data Structures", "Algorithms"],
]


Sample output 3:
"Data Structures"

Complexity analysis variables:

n: number of pairs in the input

*/

import java.io.*;
import java.util.*;

public class Solution {
  public static void main(String[] argv) {
    String[][] prereqsCourses1 = {
        {"Foundations of Computer Science", "Operating Systems"},
        {"Data Structures", "Algorithms"},
        {"Computer Networks", "Computer Architecture"},
        {"Algorithms", "Foundations of Computer Science"},
        {"Computer Architecture", "Data Structures"},
        {"Software Design", "Computer Networks"}
    };

    String[][] prereqsCourses2 = {
        {"Algorithms", "Foundations of Computer Science"},
        {"Data Structures", "Algorithms"},
        {"Foundations of Computer Science", "Logic"},
        {"Logic", "Compilers"},
        {"Compilers", "Distributed Systems"},
    };


    String[][] prereqsCourses3 = {
        {"Data Structures", "Algorithms"}
    };

    System.out.println(findHalfway(prereqsCourses3));

  }

  public static String findHalfway (String[][] courses) {
  }
}

答案：（recruiter反馈我的解法是optimal solution）

1. </blockquote></div><div class="blockcode"><blockquote>public static String findHalfway (String[][] courses) {
   
2.       LinkedList<String> lst = new LinkedList<>();
   
3.       int x = courses.length;
   
4.       // assume there is always records.
   
5. 
   
6.       //"Data Structures" -> "Algorithms" -> "Foundations of Computer Science" -> "Operating Systems"
   
7. 
   
8.       Map<String, String> ba = new HashMap<>();
   
9.       Map<String, String> ab = new HashMap<>();
   
10.       for(int i=0; i<x; i++) {
    
11.         String before = courses[i][0];
    
12.         String after = courses[i][1];
    
13.         ba.put(before, after);
    
14.         ab.put(after, before);
    
15.       }
    
16. 
    
17.       lst.add(courses[0][0]);
    
18.       lst.add(courses[0][1]);
    
19. 
    
20.       for(int j=1; j<x; j++){
    
21.         String head = lst.getFirst();
    
22.         String tail = lst.getLast();
    
23.         if(ab.get(head) != null) {
    
24.           lst.addFirst(ab.get(head));
    
25.         }
    
26.         if(ba.get(tail) != null) {
    
27.           lst.addLast(ba.get(tail));
    
28.         }
    
29.       }
    
30.       return lst.get(x/2);
    
31.   }

复制代码

求求求大米！～～

谢谢分享！！