萝卜丝 karat面经

最近都没karat 面经似乎他们换题了，地里看到的都没遇到第一题， input 是一个 studentID 和 course 的二维数组 类似 [["56", "course1"], ["41", "course2"], ["56", "course3"], ["48", "course2"], ["41", "course1"]] 要求output 是 每一对 pair和他们的共同course。 比如 {["56,41", "course1"], ["56,48", ""], ["48,41", "course2"]}, 即使没用共同课程也需要输出 我用map 套 set做的

第二题
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 s

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

"Algorithms"],
]
Sample output 3:
"Data Structures"
All Test Cases:
halfway_course(pairs1) => "Data Structures"
halfway_course(pairs2) => "Foundations of Computer Science"
halfway_course(pairs3) => "Data Structures"
Complexity analysis variables:
n: number of pairs in the input
*/
时间不多没怎么想 用的map没写完但是讲了思路，可能有更好的方法。不知道有没有机会T T

求米求米求米！！！！

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题应该是topological sorting吧

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题是这个意思不

1. Class Solution{
   
2.         class Course {
   
3.                 String name,
   
4.                 Course child;
   
5.         }
   
6.         public String findMedianCourses(String[][] courses) {
   
7.                 Map<String, Course> allCourse = new HashSet<>();
   
8.                 Set<String> pendingCourse = new HashSet<>(); // courses that current have no parents
   
9.                 for (String[] course: courses) {
   
10.                         String childName = course[0];                //child course
    
11.                         String parenName = course[1];        // prereq course
    
12. 
    
13.                         boolean seenParent = allCourse.contains(parentCourseName);
    
14. 
    
15.                         Course child = allCourse.getOrDefault(childName, new Course(childName, null));
    
16.                         Course parent = allCourse.getOrDefault(parenName, new Course(parenName, null));
    
17.                         parent.child = child;
    
18. 
    
19. 
    
20.                         allCourse.put(childName, child);
    
21.                         allCourse.put(parentName, parent);
    
22. 
    
23.                         pendingCourse.remove(child); // might have child in pending, let's remove
    
24.                         if (!seenParent) {
    
25.                                 pendingCourse.add(second);
    
26.                         }
    
27.                 }
    
28. 
    
29.                 String rootName = pendingCourse.iterator().next();
    
30.                 Course ptr = allCourse.get(root);
    
31.                 int stopIndex = (allCourse.size()-1)/2;
    
32. 
    
33.                 for(int i = 1; i <= stopIndex; i++) {
    
34.                         ptr = ptr.next;
    
35.                 }
    
36.                 return ptr.name;
    
37.         }
    
38. }

复制代码

蠡口 207

第一题，如果可以assume课程数有限，比如1000个，可以用bitset，这样每个交集的计算都是常数级别的位计算。不过代价是需要多维护一个course->index以及index->course的map。