Karat Interviews

Some students of an American university built an app and deployed in United States, and now they want to release it internationally. What should be the concerns before doing so and how should they take actions accordingly?

You have a crossword puzzle app. You have access to the hints useful for solving the puzzle, which is stored in both the application and server. What are the pros and cons of these approaches?

Efficient way to find top 100 contestants leaderboard and search contestant's progress by name.

Some inputs/numbers are given. Based on storage size and CPU/query load calculate how many servers do we need in both cases.

You are a developer for a university. Your current project is to develop a system for students to find courses they share with friends. The university has a system for querying courses students are enrolled in, returned as a list of (ID, course) pairs.

Write a function that takes in a collection of (student ID number, course name) pairs and returns, for every pair of students, a collection of all courses they share.

Sample Input:

enrollments1 = [
  ["58", "Linear Algebra"],
  ["94", "Art History"],
  ["94", "Operating Systems"],
  ["17", "Software Design"],
  ["58", "Mechanics"],
  ["58", "Economics"],
  ["17", "Linear Algebra"],
  ["17", "Political Science"],
  ["94", "Economics"],
  ["25", "Economics"],
  ["58", "Software Design"],
]

Sample Output (pseudocode, in any order):

find_pairs(enrollments1) =>
{
  "58,17": ["Software Design", "Linear Algebra"]
  "58,94": ["Economics"]
  "58,25": ["Economics"]
  "94,25": ["Economics"]
  "17,94": []
  "17,25": []
}

Additional test cases:

Sample Input:

enrollments2 = [
  ["0", "Advanced Mechanics"],
  ["0", "Art History"],
  ["1", "Course 1"],
  ["1", "Course 2"],
  ["2", "Computer Architecture"],
  ["3", "Course 1"],
  ["3", "Course 2"],
  ["4", "Algorithms"]
]

Sample output:

find_pairs(enrollments2) =>
{
  "1,0":[]
  "2,0":[]
  "2,1":[]
  "3,0":[]
  "3,1":["Course 1", "Course 2"]
  "3,2":[]
  "4,0":[]
  "4,1":[]
  "4,2":[]
  "4,3":[]
}

Sample Input:

enrollments3 = [
  ["23", "Software Design"], 
  ["3", "Advanced Mechanics"], 
  ["2", "Art History"], 
  ["33", "Another"],
]

Sample output:

find_pairs(enrollments3) =>
{
  "23,3": []
  "23,2": []
  "23,33":[]
  "3,2":  []
  "3,33": []
  "2,33": []
}

All Test Cases:

find_pairs(enrollments1)
find_pairs(enrollments2)
find_pairs(enrollments3)

Complexity analysis variables:

n: number of student,course pairs in the input
s: number of students
c: total number of courses being offered (note: The number of courses any student can take is bounded by a small constant)

As you are reading the book multiple times, you notice that you often get bad endings. You start to suspect there is no way to get to the good endings, so you decide to find out.

Good and bad endings will be separate lists of page numbers, like this:

good_endings = [10, 15, 25, 34]
bad_endings = [21, 30, 40]

Given lists of good endings, bad endings, and a list of the choices along with their options, return a collection of all the reachable good endings, if any.

Examples:

choices1 = [[3, 16, 24]]
find_good_endings(good_endings, bad_endings, choices1)
  Start: 1 -> 2 -> 3(choice) -> 16 -> 17... -> 21(bad ending)
                   |
                   -> 24 -> 25(good ending)
Thus it is possible to reach the good ending at 25 but no others, so we return [25].

choices2 = [[3, 16, 20]]
find_good_endings(good_endings, bad_endings, choices2)
  Start: 1 -> 2 -> 3(choice) -> 16 -> 17... -> 21(bad ending)
                   |
                   > 20 -> 21(bad ending)
No good ending is reachable, so return [].

choices3 = [[3, 16, 19], [20, 2, 17]]
find_good_endings(good_endings, bad_endings, choices3)
                                      +------<-------<----+
                                      v                   |
  Start: 1 -> 2 -> 3(choice) -> 16 -> 17 -> 18 -> 19 -> 20(choice)
              ^       |                           ^       |
              |       +----->------->------>------+       v
              +-------<--------<-------<----------+
No good ending is reachable, so return [].

Additional Inputs:

choices4 = [[3, 2, 19], [20, 21, 34]]
choices5 = []
choices6 = [[9, 16, 26], [14, 16, 13], [27, 29, 28], [28, 15, 34], [29, 30, 38]]
choices7 = [[9, 16, 26], [13, 31, 14], [14, 16, 13], [27, 12, 24], [32, 34, 15]]
choices8 = [[3, 9, 10]]
choices9 = [[3, 9, 10], [12, 13, 14]]

Complexity Variable:

n = number of pages
(endings and choices are bound by the number of pages)

All Test Cases:

find_good_endings(good_endings, bad_endings, choices1) => [25]
find_good_endings(good_endings, bad_endings, choices2) => []
find_good_endings(good_endings, bad_endings, choices3) => []
find_good_endings(good_endings, bad_endings, choices4) => [34]
find_good_endings(good_endings, bad_endings, choices5) => [10]
find_good_endings(good_endings, bad_endings, choices6) => [15, 34]
find_good_endings(good_endings, bad_endings, choices7) => [15, 25, 34]
find_good_endings(good_endings, bad_endings, choices8) => [10]
find_good_endings(good_endings, bad_endings, choices9) => [10]