penny
BAN USERthough I think using a queue instead of vector, same idea, but seems simpler for understanding....: what do you guys think ? :)
int difference(Node* root)
{
if(!root)
return 0;
int closest = 0;
int furthest = 0;
queue<pair<Node*, int>> nodes;
nodes.push(pair<Node*, int>(root,0));
while(!nodes.empty()) {
pair<Node*, int> n=nodes.front();
nodes.pop();
if(!n.first>left&&!n.first>right) {
if(closest == 0) {
closest = n.second;
} else {
furthest = n.second;
}
} else {
if(n.first>left) {
nodes.push(pair<Node*,int>(n.first>left,n.second+1));
}
if(n.first>right) {
nodes.push(pair<Node*,int>(n.first>right,n.second+1));
}
}
}
return (furthest>closest)?(furthestclosest):0;
}

penny
October 22, 2012 O(n) solution, nonrecursion... the idea is similar as the first post above: the (i+1)th element is not included in the result if the sum till (i+1)th elem is less than the sum till ith element:
int maxSum(int* arr,int len)
{
int sum1=0;
int sum2=0;
for(int i=0;i<len1;++i) {
int temp=sum2;
sum1+=arr[i];
sum2+=arr[i+1];
if(i!=len2) {
sum2=sum1;
if(sum1>sum2) {
++i;
} else {
sum1=temp;
}
}
}
return (sum2>sum1)?sum2:sum1;
}

penny
October 21, 2012 there could be better ways but BST definitely would work. Storing each node is O(logn), printing descending order is O(n), insert and delete are both O(logn);
pseudo code for store:
initialize counter to 0;
code for Tree Node struct/class (int data, Node* left, Node* right);
store(int val) //called each time a new integer comes in
{
if(counter<=n)
{
counter++;
insert new node with value val in the bst; //O(logn)
return;
}
find the node with smallest value in the bst (the left most node); //O(logn)
if(val greater than left most node's value)
{
delete left most node; //O(logn)
insert new node with value val; //O(logn)
}
else //do nothing, the new val is not in the top n;
}
PrintDescendingOrder(node* root) //like inorder traversal, but right first, then self, then left
{
PrintDescendingOrder(root>right);
print root's value;
PrintDescendingOrder(root>left);
}
insert and delete is the same as inserting and deleting a value in bst......
Used recursive approach,
int incrementOne(int* arr, int len,int curr)
{
if(arr[len1]<9)
{
arr[len1]++;
return 0;
}
if(curr==len1)
{
arr[curr]=0;
return 1;
}
arr[curr]+=incrementOne(arr,len,curr+1);
if(arr[curr]<=9)
return 0;
arr[curr]=10;
return 1;
}
void incrementOne(int* arr, int len)
{
int c=incrementOne(arr, len,0);
if(c==1)
{
for(int i=len;i>0;i)
arr[i]=arr[i1];
arr[0]=1;
len++;
}
for(int i=0;i<=len1;++i)
cout<<arr[i];
cout<<endl;
}
#ifdef TEST_INCREONE
void main()
{
int arr[10]={2,7,8,9};
incrementOne(arr,4);
int arr1[10]={9,9,9,9};
incrementOne(arr1,4);
int arr2[10]={2,7,8,8};
incrementOne(arr2,4);
system("pause");
}
#endif

penny
June 12, 2012 time O(logn), space O(1)
use numc in Node struct to denote how many children the node has:
struct Node
{
int data;
Node* left;
Node* right;
int numc;
};
Pseudo code:
Node* func(Node* curr)
{
return curr if its numc is 0
otherwise:
1/(numc+1) possibility return the curr;
//implement this by: int r=random(1, numc+1);
//if(r==numc+1) return curr;
numc/(numc+1) possibility: //else
{
return func(curr>left) if curr>right is NULL;
return func(curr>right) if curr>left is NULL;
otherwise:
left/(left+right) possibility return func(curr>left);
right/(left+right) possibility return func(curr>right);
// left=left subtree size = curr>left>numc+1; right is similar as left
}
}
//implement left/(left+right) possibility by: int r=random(1,left+right);
if(r>=1&&r<=left) //means left/(left+right) possibility.
{ //do something}
No, not all while in a while is O(n^2).... I wouldn't post it if it was :)
If you look closely, every K elements, I put them in a stack, then in the inside while loop, I pop them out and add them to the list. It is not n^2 because I do it only when counter==k. So every node is being operated twice, not n times, so the time is O(2n)=O(n)
is temporary buffer allowed?
I was thinking of a non recursive solution:
Node* reverseK(Node* h, int k)
{
if(h==NULL)
return NULL;
if(k<=1)
return h;
stack<int> nstack;
Node* h1=NULL;
Node* curr=NULL;
int counter=0;
while(h!=NULL)
{
nstack.push(h>value);
h=h>next;
counter++;
if(counter==k)
{
while(counter>0)
{
int temp=nstack.top();
nstack.pop();
counter;
if(h1==NULL)
{
h1=new Node();
h1>value=temp;
curr=h1;
}
else
{
Node* n=new Node();
n>value=temp;
curr>next=n;
curr=n;
}
}
}
}
if(curr!=NULL)
curr>next=NULL;
return h1;
}
that works for all my test cases, and the time is O(n), just not sure if the temporary stack and new list is ok?
 penny May 31, 2012
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
Open Chat in New Window
agree with @che 's explanation (in a revert way) and @lfenjoy9 's code!!!
 penny November 20, 2012