Anthony Mai
BAN USERYou guys missed the most efficient solution. If the remainder units (k%N) is more than than (N+1)/2, Harry can choose to hop down 1 step of time to a position which is exactly N units, then hop up N units. That is more efficient than directly hop up 1 step at a time.
For example, N is 7 and there are 5 units left. The naive way is one unit up at a time and need 5 more steps. Since 5 is more than (7+1)/2 = 4, the more efficient way is hop down 2 units, make the remaining units 7, then hop up 7 units, total remaining steps is 3.
The answer is (k/n) + (((k%n)>((k+1)/2))? (n+1 - (k%n)) : (k%n))
This is a shared resource management problem which is typically resolved using counting semaphores. Please note the difference from mutex, semaphores are shared by multiple processes, mutexes are not. And mutxes are like binary semaphore: they are either locked or unlocked and can be in no other state. But a counting semaphore can have any number of counts.
You would start the write semaphore at the count of 2, and start the read semaphore at the count of one.
Each process, when it needs to write to the file, will wait on the semaphore. If the count is less than one, the process is put in a waiting queue and wait for some other process to signal the semaphore. If the count is large then one, the count is reduced by one and the process then proceeds to access the resource. When it is done accessing the resource, it then signals the semaphore, meaning the count is increased by one, so that other processed in the waiting queue can then proceed.
Same happens to the read process. It wait on the semaphore, access the resource, and then signals the semaphore when done.
This is indeed a O(1) problem. Note the key is that the array is already sorted. So if an element repeats ceiling(N/2) times in the array, then no matter it is placed, the center element will be that element. If number of element is even so there is no precise center, then exam if the center two elements are the same or not. If they are not the same, pick up one more element on either side to compare. The element that has an identical peer is the answer.
- Anthony Mai January 19, 2016Interesting question.
Normally you declare a static array like this:
const int m = 10, n = 12;
int ar[m][n];
But that would not take malloc-ed memory. To take malloc-ed memory you have to have a pointer type. It can be done like this:
const int m=10, n=12;
int (*ar)[m][n] = (int(*)[m][n]) malloc(sizeof(*ar));
//Access elements:
(*ar)[1][2] = 3;
// Free the memory.
free(ar); ar = nullptr;
It would be extremely rare that some one would use such a code construct. But the language allows it.
None of the above answers are correct. Convert to string, reverse the characters and then convert back to value is not allowed. Repeatedly subtracting 10 is not efficient.
The correct answer is that although you are not allowed to divide by 10, you are allowed to right shift bits, which is equivalent to divide. So consider that
X / 10 = X * (1/10) = X*(2^N/10)/2^N = (X*(2^N/10))>>N
Pick a reasonable N, like N=9. The calculation becomes:
X/10 = (X*(512/10))>>9 ~= (X*51)>>9
This is only approximately but gets you pretty much close to using divide directly.
So original number is 756:
(756*51)>>9 = 38556>>9 = 75 which is the quote.
We check the remainder:
756 - 75*10 = 6, which is within expected range 0 to 9. If it is not you increment the quote and try again. In this case we successfully split 756 into 75x10 + 6.
Next (75*51)>>9 = 7, the quote,
and the remainder is:
75 - 7x10 = 5, which looks good.
This is a powerful technique to convert expensive division to merely multiplication and shift right. I use this trick a lot.
That's pretty simple. Each time you do X &= X-1 it erases the lowest non-zero bit. You repeat it and it removes one bit at a time, until all bits are gone. So that gives you the answer how many bits existed in the original integer.
For example, if the lowest bit is 1, after subtracting 1 it becomes 0. So AND the 1 bit and the 0 bit gives you 0, the bit is removed. All other bits are intact.
Next if you have the lowest bits as 100, subtracting 1 gives 011. AND them together, the lowest three bits cancel out. So that removes another lowest bit, with other bits intact.
Pretty useful trick to quickly count all bits without using if/else.
The answer is reserve specific port values to not represent an actual physical port, but represent a group of ports. For example abc.def.ghi.255 could be a reserved and non-used port to mean all ports with the lower digits going from 0 to 254. When you specify a port setting for abc.def.ghi.255 it will be applied to all ports abc.def.ghi.xxx with xxx from 0 to 254. The same principle could be applied to higher part of the port mapping, using specific reserved ports to represent even bigger groups of ports.
- Anthony Mai February 23, 2017