 |
.. (לתיקייה המכילה) | |
Can we assume we have only one array? | |
| Yes. |
Is all allocated memory must be released | |
| Yes |
In Init function, can addtional memory be used ? | |
|
Only O(1) additional memory can be used. There must be only one array of type arrayType of size N. No additional data structures should be allocated. However, for the other operations (like Sort, NumInRange, etc.) you can allocate additional memory according to the restrictions posed by the operations. |
Can we assume that arraySizeType and arrayMembersType are of the same size (e.g. 32bit) | |
| Yes, you can also assume that the size of the array will not be greater than MAX arraySizeType (e.g. for 16 bit array size will be < 2^15-1 = 32767). |
In the MaxSumRange function, if we get several ranges with maximum sum which one should we return? | |
|
The shortest range you encounter e.g. for a 1 2 -100 3 array from = 3 to = 3 should be returned |
In the MaxSumRange function, | |
|
MaxSumRange should return the shortest range with the maximum sum. If there are several ranges with same sum and same length, then first one should be returned. For example: 1 2 -3 5 6 7 -8 +8 -20 9 9 -10 will return from=9, to=10. In other words there is no need in prefix and suffix of zero sum (1+2-3 and -8+8). Also 5+6+7 gives same maximum sum, but it's not the shortest. With this new definition, only one range can be returned correctly. More examples: a) 1 2 -1 -2 5 There are two possible ranges [0,4] and [4,4] we choose the shortest one - [4,4] b) 3 -1 -2 3 There are three possible ranges [0,3], [0,0] and [3,3] there are two shortest ranges [0,0] and [3,3] but [0,0] is the first. so [0,0] should be returned. |
Can we create a dynamicly allocated linked list that will hold only the "alive" elements ? | |
|
NO!!!!!! Since you have to free all allocated memory in the Quit function, which requires O(1) time and space complexity. |
In NumInRange function, what exactly is the r?? | |
|
If you call NumInRange r consecutive times, the complexity should be O( M+ |k| +r) e.g. NumInRange NumInRange NumInRange ..... NumInRange ---------------- r times the complexity should be O( M+ |k| +r) Note that there are no insert and no delete between the calls ! |
In SumMaxRange, do empty spaces affect the length of the range? | |
|
Yes The range length is defined by to-from thus empty space do affect the length of the range e.g. 5 6 7 -100 9 blank blank 9 should return [0,2] and NOT [4,7]. |
Can we allocate the array with N+1,N+2,N+3 size? | |
|
No, the array size must be exactly N !. You can store additional information in static global variables. |
Can SumMaxRange include range with empty elements? | |
|
Yes e.g. A = 1 2 blank 3 from = 0 to = 3 |
In the Sort function, who needs to allocate the sorted_array | |
|
You should allocate the array your self (O(m) space complexity) you should not use it in any of the other function. Once sort is called again the old array can ( and should ) be freed, and a new one should be allocated. After the array is printed in parser function it is not used by OUR main again. In the Quit function don't forget to free everything that was not freed. |