Equal Access Robotics Competitive Programming Diagnostics Test
This is a simple Diagnostics Test that will be reviewed by the staff. Results will be emailed to you ASAP. If you still really wish to take the class, you can still sign up, no matter how you do on the test. Note that you are not expected to perfectly solve both problems to pass the test, so do not worry if your solutions are not optimal. Just do the best you can. Also, please do not spend more than an hour on this test. I just need to get a sense of what you know. Good luck!
Thoroughly describe how you would solve the following problem in the fastest way you know: You are given an array, a, of length N (2 ≤ N ≤ 100,000), filled with integers. Each integer is in the range -1,000,000,000 to 1,000,000,000. You are also given another integer, M. The problem is asking, how many pairs of distinct elements in the array a (a[i] and a[j] where i ≠ j and 0 ≤ i, j < N) sum up to M? (Sample input: N = 7, a = [-1, 0, -1, -2, 1, 0, 3], M = 0 | Sample output: 3 | Explanation: a[0] + a[4] = 0, a[2] + a[4] = 0, a[1] + a[5] = 0. There are no other pairs of distinct indices i and j such that a[i] + a[j] = M, so the total amount of pairs is 3) *
Thoroughly describe how you would solve the following problem in the fastest way you know: You are given an array, a, of length N (1 ≤ N ≤ 100,000), filled with intervals. Each interval is defined by 2 integers, a and b, such that (0 ≤ a ≤ b ≤ 1,000,000). Note that these intervals might overlap in some places and intervals are inclusive (of both endpoints). Additionally, you need to answer Q queries (1 ≤ Q ≤ 100,000) given in an array q, each query asking the number of intervals in array a that pass through point c (0 ≤ c ≤ 1,000,000), where c is given for each query. In all your output should have Q separate integers representing their respective query. (Sample input: N = 4, a = [[0, 3], [1, 5], [0, 10], [6, 6]], Q = 3, q = [2, 5, 6] | Sample output: 3 2 2 | Explanation: The first 3 intervals pass through point 2, so the answer to the first query is 3. Intervals 2 and 3 pass through point 5, so the answer to the second query is 2. Lastly, intervals 3 and 4 pass through point 6, so the answer to the third query is 2) *
Submit
Clear form