Praveen
BAN USERThe number of distinct integers can be 2^32, which is 4billion. Since 1GB(8billion bits) memory is given, we can declare
bit map array of size 4billion and initialize it to zero. Scan through the file. As and when you get an integer, set the bit to 1. If you encounter the same number again, check the bitmap's value is set. If it is set to 1, don't change.
Once you finish reading the file, scan the bit map. If any bit is not set, it is the number that is missing from the 4billion integer list.
Interrupt Handler: Is a routine that gets executed by kernel for every interrupt. It can be called Interrupt Service Routine(ISR). Each device that generates interrupts will have a associated interrupt handler. For example, one routine handles the interrupts from keyboard, and other routine handles interrupts from the system timer.
- Praveen April 05, 2008MSI Protocol: This is a cache coherency model where every cache block can be in either state Modified or Shared or Invalid.
If the cache block is modified, it can't be evicted with writing the data to the backing store(Memory Resource).
If the cache block is Shared, it is not modified and can be evicted without writing the block to the backing store.
If the cache is in invalid state, it must be fetched from the backing store to cache.
This problem occurs, if you have a shared memory resource and multiple CPUs each having a separate cache. Let us say the two CPUs, X and Y, having caches Xx and Yy. If X has same block of memory in its cache Xx and updates it. Y's cache would be containing stale data.
Cache coherency is used to maintain the integrity of data between cache and memory resources.
There is a flaw in Anonymous's algorithm. If you set the value of a[i] = -1 as and when you see an element i, you replace the element in a[i] which you should verify later.
- Praveen April 08, 2008My Algorithm:
1. Declare another array A with size = size(given_array) + 2. Initialize all elements to 0
2. Scan the given array S. If you see an element i, set array[i] = -1 if array[i] > 0
3. Scan the A, check if there is any element whose value is == 0.
4. You will find two elements. Those two are missing elements
The problem with it is, it uses space.