Abhishek
BAN USERA node in a linked list is an object. So what is meant in this question is that one is given the object depicting the node to be deleted. And the object will have the data (key) and the pointer to the next node (object) in the linked list. So the solution given by syrus is correct if the current node is not the last node.
One modification that I can think of to go around this problem is to attach a dummy node at the end of the linked list. This way the node to be deleted can never be the last node. We just make the node to be deleted (if it's second last) the dummy node.
<pre lang="" line="1" title="CodeMonkey4296" class="run-this">#include <iostream>
#include <cstdlib>
using namespace std;
void sort_stream(char* stream, int length) {
if(!stream || length <=0)
throw("invalid input");
int char_array[256] = {0};
int int_array[10] = {0};
for(int i=0;i<length;++i) {
int index = (int) stream[i];
if(stream[i] >= '0' && stream [i] <= '9') {
index-=(int) '0';
++int_array[index];
}
else
++char_array[index];
}
int j=1, k=0;
for(int i=0;i<length;++i) {
while(!int_array[k]) ++k;
while(!char_array[j]) ++j;
if(stream[i] >= '0' && stream [i] <= '9') {
stream[i] = (char) k + '0';
--int_array[k];
}
else {
stream[i] = (char) j;
--char_array[j];
}
}
}
int main(int charc, char* charv[]) {
try {
int length = atoi(charv[2]);
cout<<"input stream is \n"<<charv[1]<<"\n\n";
sort_stream(charv[1], length);
cout<<"output stream is \n"<<charv[1]<<"\n";
}
catch(...) {
cout<<"exception catched\n";
}
return 0;
}</pre><pre title="CodeMonkey4296" input="yes">I am using counting sort for this problem.
The first for loop count the occurrences of each digit and character encountered in the input stream.
In the second loop, I recreate the stream in sorted order with indexes of digit or characters kept intact.
The solution is simple enough, so I don't think much explanation is required.</pre>
one obvious solution is to find the pair of points of persons with max distance and min distance between them on square grid and join them. find the intersection point of the line connecting points in the pairs. this point is where everyone shall meet. if the two lines overlap, take the center point of any of these lines.
- Abhishek June 07, 2011I have an idea and am pretty confident that it shall work. Since we have to calculate power of a single digit number, we have 8 numbers (excluding 0 and 1) worth consideration.
Here's a general idea of what I intend to do.
1. find nearest power of two less than the number, e.g. if number is 7 then 4 is the nearest power of 2 less than 7.
2. represent original pow(7,100) as now pow(4+3,100).
3. we can now recursively call binomial theorem on this.
4. while doing so, 3 can itself be divided into (2+1) and binomial theorem can be recursively called on this.
5. Each part of binomial theorem is product of two numbers now. 1 number is a power of 2. So we will now by how much the second number will be shifted to its left.
6. Using this information we can know how many 4 byte integers will be required to stored the new number.
7. Adding each part of binomial theorem won't be much of a problem as we will only require 1 extra bit than the largest part of binomial theorem to store the final result.
I am not sure of the complexity of this solution yet. Will post as soon as I come up with this. I also hope I have been able to clearly state the solution.
Here's O(n) working solution
1. Declare two variables a) count variable to keep track of count of majority element.
2. Majority element.
3. Do a for loop and repeat following steps 4-6 until end of array is reached.
4. if current array element equals majority element, increment count
5. else, if count is 0, update majority element with current array element and increment count.
6. else if count is not 0 then decrement count.
7. Do another for loop and count the number of occurrences of majority element in the array, if it's half the array size then we have found the majority element, else there's no majority element.
Time complexity - O(n)
Space complexity - O(1)
you missed to see the if statement before return statement.
- Abhishek August 10, 2011