Balaji
BAN USER<pre lang="java" line="1" title="CodeMonkey10833" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
static void sortStackRec(Stack<Integer> s) {
if (s == null || s.size() < 2) return;
Integer i = s.pop();
sortStackRec(s);
if (s.peek().intValue() > i.intValue()) {
s.push(i);
return;
}
Integer temp = s.pop();
s.push(i);
s.push(temp);
}
static void sortStack(Stack<Integer> s) {
int l = s.size();
for (int i = 0; i < s.size(); i++) {
sortStackRec(s);
}
}
public static void main(String ... args) {
Stack<Integer> s = new Stack<Integer>();
s.push(1);
s.push(2);
s.push(3);
s.push(2);
sortStack(s);
while (s.empty() == false) {
System.out.println(s.pop());
}
}
}
</pre><pre title="CodeMonkey10833" input="yes">
</pre>
having some problems posting. ignore this if u have the proper version.
sorry for the confusion.
bool search(int a[][5], int n, int e) {
int left = 0;
int right = n * n - 1;
int mid = 0;
int val = 0;
while (left <= right) {
mid = (left + right) / 2;
val = a[mid / n][mid % n];
if (val == e) {
return true;
} else if (val < e) {
left = mid + 1;
} else {
right = mid - 1;
}
}
left = 0;
right = n * n - 1;
while (left <= right) {
mid = (left + right) / 2;
val = a[mid % n][mid / n];
if (val == e) {
return true;
} else if (val < e) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
a slightly diff. approach based on the position of the number after every iteration.
position begins with 1.
int get_log(int num, int base) {
int times = 0;
while (base <= num) {
times++;
num -= base;
}
return times;
}
bool is_blessed(int n) {
int k = 2;
while (k <= n) {
if (n % k == 0) {
return false;
}
n -= get_log(n, k);
k++;
}
return true;
}
cheers :)
- Balaji December 29, 2009We can do this by having 2 queues.
Call them A and B.
First, we push root into A
i.e.
A->enqueue(root);
while (A->isEmpty() == false) {
while ((temp = A->dequeue()) != NULL) {
printf("%d ", temp->getData());
if (temp->getLeft() != NULL) {
B->enqueue(temp->getLeft());
}
if (temp->getRight() != NULL) {
B->enqueue(temp->getRight());
}
}//end of inner while loop.
printf("\n");
//exchange the queue pointers.
tempPtr = B;
B = A;
A = tempPtr;
}
We could do the following:
1: in a hashmap, we store the node and it's position in the in-order traversal( just what KarateKamli said).
2: when we get a node as input, we check the threaded pointer by checking if it's in-order number is less than the node it points to.
3: if the order is proper, we leave the pointer as it is. If not, we make this pointer NULL and more on...
This way, there is no dependency on the sorted order of what the node contains.
A simple way to compute the sqrt is by adding the odd numbers till it becomes greater than that number.
so, 1 + 3 <= 4. So, we count the number of times we do this operation.
likewise, sqrt (9) would be 1 + 3 + 5. So, it would be 3.
Here's how this looks.
int
sqrt(unsigned int n)
{
int count = 0;
int cur_term = 1;
int next_term = 1;
if (n < 2) {
return (n);
}
while (cur_term <= n) {
cur_term += next_term;
next_term += 2;
count++;
}
return (count);
}
We can use switch-case instead of if else to make the code faster.
I don't think we can make the performance better than O(n).
int getNthNonZero(vector<int>& v, const int n)
{
int count = 0;
vector<int> :: iterator i;
for (i = v.begin(); i != v.end(); i++) {
switch (*i) {
case 0:
break;
default:
switch (++count == n) {
case false:
break;
default:
return *i;
}//switch on count
}//switch on *i
}
return ERROR;
}
Ok. Here's how I'd go.
Assuming that the level (i.e. depth, e.g: root is at level 0) is stored in each node, do the following:
Node *get_common_ancestor(Node *n1, Node *n2)
{
if (n1 == NULL)
return n2;
if (n2 == NULL)
return n2;
//if n1 was deeper in the tree.
while (n1->level > n2->level) {
n1 = n1->parent;
}
//if n2 was deeper in the tree.
while (n2->level > n1->level) {
n2 = n2->parent;
}
//now, move both of them 1 level up at a time an compare
while (n1 != NULL && n2 != NULL) {
if (n1 == n2) {
return n1; //This is the common ancestor.
}
n1 = n1->parent;
n2 = n2->parent;
}
return NULL; //No common ancestor found. Essentially, both nodes are in diff. trees
}
This will work for non-binary trees too.
- Balaji April 02, 2009That's a nice technique. It's called memoization. http://en.wikipedia.org/wiki/Memoization
We can re-use the space for keeping track of k terms. Hence, o(k) space.
The running time however is O(nk) and not O(n) since we have to traverse k locations in the array to find the current sum.
<pre lang="java" line="1" title="CodeMonkey92574" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
- Balaji August 11, 2010class Main
{
static void sortStackRec(Stack<Integer> s) {
if (s == null || s.size() < 2) return;
Integer i = s.pop();
sortStackRec(s);
if (s.peek().intValue() > i.intValue()) {
s.push(i);
return;
}
Integer temp = s.pop();
s.push(i);
s.push(temp);
}
static void sortStack(Stack<Integer> s) {
if (s == null) return;
int l = s.size();
for (int i = 0; i < l; i++) {
sortStackRec(s);
}
}
public static void main(String ... args) {
Stack<Integer> s = new Stack<Integer>();
s.push(1);
s.push(2);
s.push(3);
s.push(2);
sortStack(s);
while (s.empty() == false) {
System.out.println(s.pop());
}
}
}
</pre><pre title="CodeMonkey92574" input="yes">
</pre>