![]() |
.. (לתיקייה המכילה) | |
In Q1: What should ClosestRoom(k) return if k is occupied but both k-1 and k+1 are free? | |
It can arbitrary chose between k-1 and k+1. |
In Q5: Can we assume that k=O(1)? | |
Absolutely not! Otherwise, it would be an "Intro to CS" question. |
In Q5: What do you mean “closest in absolute value”? | |
“Absolute value” simply means distance, that is closest by distance. For example consider A = {6,-10, 9, 11, 12} and k=2. The median is 9, and the answer should be either {11, 12} or {11, 6}. |
What should be the output in Q5 if A = {2,5,5,5,8} and k=2,3? | |
For k=2: the output should be {5,5} (5 two times). For k=3: the output should be either {5,5,2} or {5,5,8}. |
Are there space limitations in Q5? | |
No. |
In Q6: How is x given and what does O(log x) stand for? | |
X is given as a "normal", decimal number. (e.g 508, 49, etc..) but you have to store it in its binary representation. Think of n = log x (n is the log of x). This means O(n) (e.g. a time which is linear in n). |
Can you give an example of Q6 part b? | |
Suppose you have inserted {1,2,3,8} to the DS. Then Count(0,1) = 2. Count(0,1) counts the numbers which are 0 modulo 2, that is, all the even numbes. |