SK
BAN USER
- 1of 1 vote
AnswersGiven row on N house, each is marked either R or B. And each house having some gems. You have to collect gems from these house with some constraint:
- SK in India
You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)
each time you take gem from one house, you will multiply gems received with gems currently, you have.
You have to choose continuous houses.
You have to return start point and end point of house (remember this should be continuous )| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm - 5of 5 votes
Answersyou have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.
- SK in India
You have to return sum of max M subarray of size K (non-overlapping)
N = 7, M = 3 , K = 1
A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)
M=2,K=2
{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm Dynamic Programming - 0of 0 votes
AnswerDesign a notification framework which notifies for birthdays, movie release, book release whenever one occurs.
- SK in India
Things kept on adding based on user subscription?
How all object, classes related/talk to each other?
There on, move on how to store them in tables?| Report Duplicate | Flag | PURGE
iLabs Senior Software Development Engineer Object Oriented Design - 0of 0 votes
AnswersGiven a Binary tree find out if it a BST or not?
- SK in India| Report Duplicate | Flag | PURGE
iLabs Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersGiven a N * M matrix, you have to rotate it by 90 degree.
- SK in India for Bing
I gave him solution with transpose matrix & then reverse each row.
He was satisfied but after asked that this required each element to be touched twice. Can you do it like all elements will be touched once only.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersYou given an array:
- SK in India
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer Algorithm - 2of 2 votes
AnswersFollowing sequence is given:
- SK in India
1,2,3,4,5,6,8,9,10,12,15,16,18,20,24
In this sequence, each number is multiple of 2,3 or 5 only.
This sequence does not contain 7 & 14 as these number has sequence 7 as multiple.
So, if you are given N find the Nth number of this sequence.| Report Duplicate | Flag | PURGE
Flipkart Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersThere is a server when a user can login.
- SK in India
A used can login multiple times.
you have to return number of unique users in last 10 minutes.
Retrieve unique user count operation should be as fast as possible.
Note:
A user who has done login in last 10 minutes more than once should be counted only 1.
It is possible that in a particular duration no user has logged in.| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 5of 5 votes
AnswersGiven a binary tree.
Print nodes of extreme corners of each level but in alternate order.10 5 11 9 20 - 15 14 - - - 25 30
then output should be 10,11,9,25,30
- SK in India
left most of 0th level
right most of 1st level
left most of 2nd level
& like this| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm Trees and Graphs
1) Each node will receive some values from left subtree and from right subtree.
2) That node will change its value with : selfvalue + sum of value received from right subtree
3) That node will return new pair of values to its parent: < sum of left subtree value, node's new value >
I can explain algo with an example:
left assume following BST:
41
40 50
39 45 55
node 40 will return <39, 40>
node 50 will return <45, (50+55)> -- <45, 105>
node 41 will receive left pair<39, 40> and right pair <45, 105>
node 41 will change -- 41 + right pair --> 41 + 45 + 105 -->191
node 41 will return <sumofleftpairvalue + newsumeofcurrentnode> -- <(39+40), 192> -- <79,192>
this will continue
sudo code:
pair<int, int> updateBst (tree *root)
{
if (!root) return <0,0>
if (leafnode) return <0, root->key>
leftpair = updateBst (root->left)
rightpair = updateBst (root->right)
root->key += rightpair.first + rightpair.second;
return < (leftpair.first+leftpair.second) , root->key>
}
take var=1. then multiply var with 5 each time as long as number is less than given number.
Take remainder of number and again apply same above step.
int remainder (int a)
{
int mask = 1;
while ( (mask * 5) <= a )
{
mask *= 5;
}
return (a - mask);
}
void remainderOfFive (int a)
{
int rem = a;
while (rem >= 5)
{
rem = remainder (rem);
}
if (rem == 0)
cout << a << " is Multiple of 5" << endl;
else
cout << a << " Not Multiple of 5" << endl;
}
This problem can be divided into two parts:
1) All nodes K distance away from arbitrary node in arbitrary node's subtree.
2) All nodes K distance away from arbitrary node above to this arbitrary node.
First part is quite easy.
void kdistanceNodes (tree *root, int K)
{
if (root)
{
if (K == 0)
{
print << root->key;
}
kdistanceNodes (root->left, K-1);
kdistanceNodes (root->right, K-1);
}
}
when arbitrary node is found
1) process all K distance node in its subtree
for second part,
2) if arbitrary node is not found, at every node, keep distance from leaf node in left subtree and from leaf node in right subtree
3) if arbitrary node is found, at every node, keep distance from arbitrary node from either of subtree and then search for remaining other subtree (K - distance from arbitrary node)
pair<bool, int> printKNodes (tree *root, int depth, int node, int K)
{
if (!root) return make_pair(false, 0);
if (K < 0) return make_pair(false, 0);
/*If Node found, then print all nodes at K distance in subtree*/
if (node == root->key)
{
if (K == 0) {print node, return <true, 1>}
kdistanceNodes (root->left, K-1)
kdistanceNodes (root->right, K-1)
return <true, 1>
}
else
{
pair<bool, int> left = printKNodes (root->left, depth+1, node, K)
/*If node is found in left subtree and current node is still <=K nodes away from arbitrary node */
if (left.first == true && left.second <= K)
{
if (K - left.second == 0)
{
print root->key
}
else if ( (K - left.second) > 0)
{
/*remaining distance from arbitrary node to right subtree via this root*/
kdistanceNodes (root->right, (K - left.second - 1) )
}
return <true, left.second+1> //pair
}
pair<bool, int> right = printKNodes (root->right, depth+1, node, K)
/*If node is found in right subtree and current node is still <=K nodes away from arbitrary node */
if (right.first == true && right.second <= K)
{
if (K - right.second == 0)
{
print root->key
}
else if ( (K - right.second) > 0)
{
/*remaining distance from arbitrary node to left subtree via this root*/
kdistanceNodes (root->left, (K - right.second - 1) )
}
return <true, right.second+1> //pair
}
/*If arbitrary node has not been found return total depth from leaf node*/
int biggerSubtree = (left.second > right.second) ? left.second : right.second;
return <false, biggerSubtree+1>
}
}
Copied from reply section in this post itself
We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data
QueueSort (queue Q1, queue Q2)
{
Q1 end marker: q1_end
Q2 end marker: q2_end
Q2.enqueue (q2_end);
//Push all data from Q1 to Q2
while ( !Q1.empty() )
{
Q2.enqueue (Q1.dequeue() );
}
//put end marker for Q1's data
Q2.enqueue (q1_end);
//sort Q2's data into Q1
while (1)
{
small = e = Q2.dequeue ();
//process till Q2's end marker is not reached
while (e != q2endmarker() )
{
//remember smallest element and keep enqueuing rest of Q2 element in Q2 itself
e = Q2.dequeue();
if (e < small)
{
Q2.enqueue (small)
small = e
}
else
Q2.enqueue (e)
}
//again mark queue end
Q2.enqueue (q2_end)
//put smallest Q2's element in Q1
Q1.enqueue (small)
//Simply Dequeue and enqueue back Q1's all element into Q2
e = Q2.dequeue()
while (e != q1endmarker()) )
{
Q2.enqueue (e)
e = Q2.dequeue ()
}
//again mark queue end
Q2.enqueue (q1_end)
}
remove q1_end and q2_end from Q2
}
//after this function, Q2 is sorted in Q1
Function (Queue Q1, Queue Q2)
{
QueueSort (Q1, Q2);
QueueSort (Q2, Q1);
//Swap elements of both queue's. Function not implemented
swapQueue (Q1, Q2);
}
this will sort data of 2 queues into single queue.
I guess question says to sort queues data in that queue itself...
We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data
Algo below
create and array of structure of Months of size 30.
parse the table, according to product & month update corresponding entry
after complete parsing, print the result for all non-zero entries from 1st product to 30th product.
Make sure to keep entry in lexicographic order
first largest height tree will mask tree of similar height or smaller height.
Iterate array
1) 1st tree will always be visible. Print it. Make it largest height
2) Find next largest height in the input. Print it. Now make it largest height
repeat step 1 & 2 until array ends
Modification of binary search
int checkKey (int s, int e, int mid, int a[], int key)
{
if (a[s] == key)
return s;
if (a[e] == key)
return e;
if (a[mid] == key)
return mid;
return -1;
}
int find (int a[], int s, int e, int k)
{
if (s > e)
return -1;
int mid = s + (e -s)/2;
int i = checkKey (s, e, mid, a, k);
if (i != -1)
return i;
if (s == e || mid == s)
return -1;
if (k > a[mid])
s = mid+1;
else
e = mid-1;
return find (a,s,e,k);
}
Algo
Post order traversal
1) if null node, return (0, true)
2) if leaf node, then return (level, true)
3) call each subtree with level+1;
4) at any node, if level return by either subtree is non-zero and not equal , then return false.
5) at any node, if either subtree level is zero, return (non-zero level, true)
pair<int, bool> leafLevel (tree *root, int level)
{
if (!root)
{
return make_pair(0, true);
}
if (leaf_node)
{
return make_pair(level, true);
}
pair<int, bool> leftT, rightT;
leftT = leafLevel (root->left, level+1);
if (leftT.second == false)
return make_pair (-1, false);
rightT = leafLevel (root->right, level+1);
if (rightT.second == false)
return make_pair (-1, false);
if (leftT.first == 0 || rightT.first == 0)
{
int level = (leftT.first != 0) ? (leftT.first):(rightT.first);
return make_pair (level, true);
}
if (leftT.first == rightT.first)
{
return make_pair (level, true);
}
else
{
return make_pair (-1, false);
}
}
tree* searchLeftmostnodeInRightSubtree (tree* root)
{
while (root->left)
{
root = root->left;
}
return root;
}
tree* inorderSuccessor (tree *root, int key)
{
if (root)
{
if (root->key == key)
{
/*inorder successor will be in right subtree of node if right subtree exist*/
if (root->right)
{
tree *subtree = searchLeftmostnodeInRightSubtree(root->right);
return subtree;
}
/*If right subtree of this node doesnot exist, then parent node for which leftsubtree consist this node*/
else
{
return root;
}
}
tree *left = inorderSuccessor (root->left, key);
if (left)
{
/*if immediate child is key*/
if (left->key == key)
{
return root;
}
/*tree is returning correct value*/
return left;
}
tree *right = inorderSuccessor (root->right, key);
return right;
}
return NULL;
}
Code according to above algorithm
typedef struct doubly_link_list dll;
struct doubly_link_list
{
char key;
dll *prev;
dll *next;
};
class DLL
{
dll *head;
dll *tail;
public:
DLL ()
{
head = tail = NULL;
}
dll *append (char c)
{
dll *node = new dll;
memset (node, 0, sizeof(dll));
node->key = c;
node->next = NULL;
node->prev = NULL;
if (!head)
{
head = tail = node;
}
else
{
tail->next = node;
node->prev = tail;
tail = node;
}
return tail;
}
void remove (dll *node)
{
if (!node)
{
cout << "Bluffff" << endl;
return;
}
if (head == node)
{
head = head->next;
}
else
{
node->prev->next = node->next;
if (node->next)
{
node->next->prev = node->prev;
}
}
delete node;
}
dll *top()
{
return head;
}
};
void first_non_repeating_char (char input[], size_t size)
{
DLL d_list;
vector< pair<bool, dll*> >hash;
hash.reserve(256);
pair<bool, dll*> vectorInit(false, NULL);
hash.insert(hash.begin(), 256, vectorInit);
for (int i = 0; i < size; i++)
{
if (hash[ input[i] ].first == false )
{
hash[ input[i] ].first = true;
hash[ input[i] ].second = d_list.append(input[i]);
}
else
{
if (hash[ input[i] ].second)
{
d_list.remove (hash[ input[i] ].second);
hash[ input[i] ].second = NULL;
}
}
}
dll *result = d_list.top();
if (result)
{
cout << "First Non_repeating character in array:" << input << " is: " << result->key << endl << endl;
}
else
{
cout << "No Non_repeating character in array: " << input << endl << endl;
}
}
this code can be trimmed more but with loss of clarity:
void modify_subtree (tree *root, tree *new_ptr_addr)
{
tree *right = root->r_child;
root->r_child = root->l_child;
new_ptr_addr->r_child = right;
}
tree *convert_to_preorder(tree *root)
{
if (root)
{
tree *left = convert_to_preorder(root->l_child);
tree *right = convert_to_preorder(root->r_child);
if (left)
{
modify_subtree (root, left);
}
if (right)
{
return right;
}
}
return root;
}
void modify_subtree (tree *root, tree **new_ptr_addr)
{
tree *right = root->r_child;
root->r_child = root->l_child;
*new_ptr_addr = right;
}
tree **convert_to_preorder(tree *root)
{
if (root)
{
tree **left = convert_to_preorder(root->l_child);
tree **right = convert_to_preorder(root->r_child);
if (!left && !right)
{
return &(root->r_child);
}
if (left)
{
modify_subtree (root, left);
}
if (right)
{
return right;
}
else
{
return &(root->r_child);
}
}
return NULL;
}
idea is like:
for leaf node, address of right child is returned
for non-leaf node, if left subtree exist then it has returned a address that address should not point to right of this node & node's right should point to node's left.
if for non-leaf node, left subtree doesnot exist, do nothing/
for non-leaf node, if right subtree exist then this right subtree must have returned a address that address should be returned
for non-leaf node, if right subtree does not exist, then address of right child should be returned
void perfectmatch (vector<int> V, vector< pair<int,int> > E)
{
vector<int>::iterator vit;
map<int, bool> vmap;
for (vit=V.begin(); vit!=V.end(); vit++)
{
vmap[*vit] = false;
}
vector< pair<int,int> >::iterator pairit;
for (pairit=E.begin(); pairit!=E.end(); pairit++)
{
int first = pairit->first;
int second = pairit->second;
cout << "pair: " << first << " " << second << endl;
if (vmap[first] == false)
{
vmap[first] = true;
}
else
{
cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
vmap.clear();
return;
}
if (vmap[second] == false)
{
vmap[second] = true;
}
else
{
cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
vmap.clear();
return;
}
}
map<int, bool>::iterator mapit;
for (mapit=vmap.begin(); mapit!=vmap.end(); mapit++)
{
if (mapit->second == false)
{
cout << "Not A Perfect Match: Culprit Vetex:" << mapit->first << endl;
return;
}
}
cout << "Perfect Match" << endl;
}
@justhack4fun688
If you say that degree of node is 1, it means that there will be only 1 edge on that node, but in your example, there will be 3 edges on each node.
By your given definition of perfect matching, there should be 1 edge only.
glebstepanov1992 is right. But @glebstepanov1992: graph is not given in form of adjacency matrix and we dont need to create a adjacency matrix.
perfectMatch(vector<int>V, vector< pair<int,int> E>)
1) create map<int, bool>
2) For each vector element, add entry into map and make is false.
3) for each edge, check if incident node of edge are marked false in map if yes then mark them true. If any of them is marked true, then there is no perfect match.
4) If all edges pass successfully, then we will check map, if there is any node which is false, if yes then again there is no perfect match. As this node has 0 incident edge.
5) If we reach here there is a perfect match
If given list is:
(1, 2), (1, 3)
(2, 4), (2, 5)
(3, 6), (3, 7)
Given list can be converted into adjacency list:
1 --> 2, 3
2 --> 4, 5
3 --> 6, 7
4 -->
5 -->
6 -->
7 -->
On this list, we can run DFS / BFS to find we there is any revisit on a node. If a node is revisited then there is a loop else no loop.
- SK December 29, 20131) Find the depth of the node, say h
2) Now, take a pointer nodePtr. Start doing DFS upto that level. Initialize nodePtr will NULL.
3) We get a node, Nh at level h, store it into nodePtr
4) get another node on level h, but this is not given node, then store this new node in nodePtr.
5) While repeating step 4, we will come to a point where we have a node N which is stored in nodePtr and just next node in the DFS on that hight h is given node, print this nodePtr node. This is left node of given node.
6) in next iteration, we will get right node of given node.
int minIndex (int *arr, int size)
{
int low = 0;
int mid = (size/2);
int high = size-1;
while (low<high)
{
if (arr[mid] > arr[mid+1])
return mid+1;
if (arr[mid-1] > arr[mid])
return mid;
if (arr[low] < arr[high])
return low;
if (arr[low] < arr[mid])
{
low = mid+1;
}
else if (arr[low] > arr[mid])
{
high = mid-1;
}
mid = low + (high-low)/2;
}
}
This seems the best :)
Pre process dictionary:
While inserting each word, sort the word & add it to trie according to this sorted word. & store the actual word.
When anagram for a word is to be find, just sort the word & lookup into trie. You will find list of words there.
Complexity will be O(nlogn) in worst case which will be of sorting word to be searched but as the words can't be too long, this should not be the issue.
int a[4][5] = {
{1, 2, 3, 4, 5},
{14, 15, 16, 17, 6},
{13, 20, 19, 18, 7},
{12, 11, 10, 9, 8},
};
void print_spiral (int r, int c)
{
int i = 0;
int j = -1;
int right_max = c;
int down_max = r;
int left_min = -1;
int up_min = 0;
int total_count = r * c;
while (total_count > 0)
{
i = up_min;
j++;
while (j < right_max && total_count > 0)
{
printf ("%d \n", a[i][j]);
j++;
total_count--;
}
right_max--;
j = right_max;
i++;
while (i < down_max && total_count > 0)
{
printf ("%d \n", a[i][j]);
i++;
total_count--;
}
down_max--;
i = down_max;
j--;
while (j > left_min && total_count > 0)
{
printf ("%d \n", a[i][j]);
j--;
total_count--;
}
left_min++;
j = left_min;
i--;
while (i > up_min && total_count > 0)
{
printf ("%d \n", a[i][j]);
i--;
total_count--;
}
up_min++;
}
}
int main ()
{
print_spiral(4, 5);
}
This can be done but with recursion.
I hope doing it recursion will count it as one iteration :)
I have used _ in place of space( ) for clarity.
Point me out for any wrong assumptions.
#include "stdio.h"
#include "string.h"
void swap (char *a, char*b)
{
char t;
t = *a;
*a = *b;
*b = t;
}
void moveSpace (char *str, char **lastSpace)
{
if (*str == '\0')
{
return;
}
moveSpace(str+1, lastSpace);
if (*lastSpace != NULL)
{
if (*str != '_')
{
swap (str, *lastSpace);
(*lastSpace)--;
}
}
if (*lastSpace == NULL)
{
if (*str == '_')
*lastSpace = str;
}
}
void printResult (char *tar, const char *src)
{
char *last = NULL;
strcpy (tar, src);
printf ("Original String: \"%s\"\n", tar);
moveSpace (tar, &last);
printf ("New String: \"%s\"\n\n", tar);
}
int main ()
{
char str[20] = {0};
printResult (str, "abc_dce__fg__");
printResult (str, "abc_dce_fg");
}
Problem statement says that query can be for last second, last minute or last hour. We have to maintain list for each window.
My Solution:
--> Maintain a list of seconds, minutes, hour of size 60, 60 & 1 respectively.
Now, basically we have to run two operations:
1) Update all three array when user logs in.
2) Update all three array after each second. (All three array need not to be updated per second)
So array will be like:
second[60] = {0,0,0,0...0}
minute[60] = {0,0,0,0...0}
hour[24] = {0}
Now 1st operation: (Simple)
Whenever any user logs in, increment each arrays' 0th index. 0th index will always point to the last second, minute, hour.
Now 2nd operation:
Keep updating newest & keep outdating oldest index values. This can be done by timeout operation. Timeout value is 1 sec:
1) At each second:
i) 60th node of array is removed & 0th node is added to second's array. (Not for initial 60 second when only insertion operation required)
ii) value of 60th node of second array is subtracted from 0th node of minutes array.(Not for initial 60 second)
2) At each 60th second, a new node with value of current node is inserted at the start of minute array. Now, minute array has 2 node
i) 1st node will have value of 0th minute. (initial value of this node is same as old 0th node)
ii) 2nd node will have value of 1st minute.
3) At each 60th min,
i ) 60th node of minute array is removed & 0th node is inserted
ii) hour index will be subtracted with 60th minute index value.
In above solution, I have taken array but all operation has been described as link link operation (insert & remove) for sake of simplicity.
So either we can take array of link list or these operation can be done like rotating array. We need to keep start & end index for each array.
@prashanthreddy: question clearly states that characters will be of english alphabet, so we can assume, you wont get special characters.
@sgarg: this solution should be extended to resolve this issue.
1) We prepare a new ordering list of alphabets based on 1st character of new dictionary. Also will keep count for number of characters found.
2) If number of characters are less than 25, then we should continue the same process for second alphabet. This time for only those string which has same matching first character.
3) During step 2, we may found new characters which must be in between of existing list, so list should be updated accordingly.
4) If after 2 & 3 steps, we still lacks required number of characters, then same 2 & 3 steps should be repeated but this time for 3 character of strings whose 1st two characters are same.
Repeatedly doing this until we get all characters.
simply we can also keep on summing all odd numbers till we get desired num. If sum ends up with given number then it is perfectly square number otherwise if sum exceeds given number, number is not perfectly square and will return false.
all Square numbers are:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289
If we see the difference among these numbers, following figure we get:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21
So, you see, every consecutive square number is Arithmetic progression. So if we can add number of this series to get desired result.
Complexity will be O(sqrt(n))
As in case of square root of 25, we need 5 iteration of addition.
bool perfectSqr (int value)
{
int odd = 1;
int a = 0;
while (a < value)
{
a += odd;
if (a == value)
return true;
odd += 2;
}
return false;
}
I have run it for the following test cases:
int a[] = {-1,-2,1,3,11,-10,-3,1,-9,2,11,13,-11,25};
int a[] = {10,11,-15,-20,2,3,-7,15,30,-1,10,-1,30};
int a[] = {-20,-30,-40,-2,-9,-13};
int a[] = {-20,-30,-40,-1,0,-9,-13};
int a[] = {3,4,-3,1,-2,1,-1,-1,-1,-1,-1};
int a[] = {3,4,-3,1,-2,25,-1,-1,-1,-1,-1};
Update me for other tricky cases :)
- SK June 08, 2013Divided algo in few parts:
part 1:
1) get minimum negative value
2) get first positive sum of array
3) get start & end index of first positive sum
this will be current running sum
part 2:
1) get sum of all negative values
2) get sum of all positive values
3) compare current_sum with curr_sum + positive_sum + negative_sum
if max_sum < (curr_sum + positive_sum + negative_sum)
update max_sum
else
update curr_sum
if max_sum < positive sum
update max_sum with positive sum
4) also keep on updating indexes
I have written code, due to keep track of index, code has become little messy
please update me with compact code, if u have
void maxSubSeq (int *a, int n)
{
int max = -1;
int i = 0;
int max_e_i = 0;
int cur_s_i = 0;
int cur_e_i = 0;
int pos = 0;
int neg = 0;
int cur = -1;
int max_s_i = -1;
int l_n_v = -10000;
int next_p_index = 0;
int neg_i = 0;
while (i < n)
{
if (a[i] < 0 && a[i] > l_n_v && cur < 0)
{
l_n_v = a[i];
neg_i = i;
i++;
continue;
}
if (cur > 0 && a[i] < 0)
break;
if (a[i] >= 0)
{
cur = 0;
while (i < n && a[i] >= 0)
{
if (max_s_i < 0)
max_s_i = i;
cur += a[i];
i++;
}
break;
}
i++;
}
if (cur >= 0)
{
max = cur;
max_e_i = i-1;
}
while (i < n)
{
neg = 0;
pos = 0;
while (i < n && a[i] < 0)
{
neg += a[i];
i++;
}
if (i < n)
next_p_index = i;
while (i < n && a[i] > 0)
{
pos += a[i];
i++;
}
if ((cur + neg + pos) > max)
{
cur = max = cur+neg+pos;
cur_e_i = max_e_i = i-1;
}
else
{
cur = cur+pos+neg;
cur_e_i = i-1;
}
if (max < pos)
{
cur = max = pos;
cur_s_i = max_s_i = next_p_index;
}
}
if (max == -1)
{
printf ("no Positive sum. Least negative value is: %d at index: %d\n", l_n_v, neg_i);
}
else
{
printf ("Max sum is: %d\n", max);
printf ("Max SubSequence is: \n", max);
for (i = max_s_i; i <= max_e_i; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
Both iterative & recursive version :
int node_ceiling_iterative (tree *root, int value)
{
if (!root)
{
return -1;
}
int result = -1;
while (root)
{
if (value < root->key)
{
result = root->key;
root = root->l_child;
}
else if (value > root->key)
{
root = root->r_child;
}
else
{
result = root->key;
break;
}
}
return result;
}
void node_ceiling (tree *root, int value, int *result)
{
if (!root)
{
return;
}
if (root->key > value)
{
*result = root->key;
node_ceiling (root->l_child, value, result);
}
else if (root->key < value)
{
node_ceiling (root->r_child, value, result);
}
else
{
*result = root->key;
return;
}
}
Algo:
At any node, check if either of its children or both of its children has return true (got keys)
i) if both elements are found, then this current node is common ancestor. return current node
ii) if either of children has return true and this current node is another key then return this current node
iii) if either of children has return true & this current node is not another key, return NULL but update found pointer with true.
Function is called :
found = 0;
tree* node = commonAncestor (root, &found, f, s)
tree *commonAncestor (tree *root, int *found, int f, int s)
{
if (!root)
return NULL;
if (root->key == f && root->key == s)
{
*found = 1;
return root;
}
if (root->key == f || root->key == s)
{
*found = 1;
}
int left = 0;
int right = 0;
tree *ret = common (root->left, &left, f, s);
if (ret != NULL)
return ret;
ret = common (root->right, &right, f, s);
if (ret != NULL)
return ret;
if (left == 1 && right == 1)
{
*found = 1;
return root;
}
else if (left == 1 || right == 1)
{
if (*found == 1)
return root;
*found = 1;
return NULL;
}
return NULL;
}
Modify version of your code which will take care of border cases also
void printParameter (tree *root, bool left, bool right)
{
if (root)
{
if (left && !(!root->l_child && !root->r_child))
printf ("%d ", root->key);
printParameter (root->l_child, left, false);
if (!root->l_child && !root->r_child)
{
printf ("%d ", root->key);
return;
}
printParameter (root->r_child, false, right);
/*For satisfying condition that root should not be printed twice*/
if (right && !left)
printf ("%d ", root->key);
}
}
psuedocode:
1) preorder of left subtree only (including root but excluding leafs)
2) leafs of left subtree
3) leafs of right subtree
4) postorder of right subtree only (excluding leafs)
Code:
void specialPreorder (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
return;
}
printf ("%d ", root->key);
specialPreorder (root->l_child);
}
}
void leaf (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
printf ("%d ", root->key);
return;
}
leaf (root->l_child);
leaf (root->r_child);
}
}
void specialPostorder (tree *root)
{
if (root)
{
if (! root->l_child && ! root->r_child)
{
return;
}
specialPostorder (root->r_child);
printf ("%d ", root->key);
}
}
void perimeter (tree *root)
{
if (!root)
return;
printf ("\n");
specialPreorder (root);
leaf(root->l_child);
leaf(root->r_child);
specialPostorder (root->r_child);
printf ("\n");
}
1) pass sum of root to its children
2) compare at each level wether we have got desired sum
{
i) if yes, return true from that node
ii) else check if node is leaf node
{
a) if its a leaf node & sum is not desired one return false
}
pass sum upto this node to left subtree
if left subtree return false
remove left subtree node
pass sum upto this node to right subtree
if right subtree return false
remove right subtree node
if either of subtree has return tree
return true
else
return false
Code:
bool prunTree (tree *root, int sum, int K)
{
if (!root)
return false;
if (root->key + sum >= K)
{
return true;
}
if (!root->left && !root->right && ((root->key + sum) < K))
{
return false;
}
bool l_ret = prunTree (root->left, (root->key + sum), K);
if (l_ret == false)
{
if (root->left)
free (root->left);
root->left = NULL;
}
bool r_ret = prunTree (root->right, (root->key + sum), K);
if (r_ret == false)
{
if (root->right)
free (root->right);
root->right = NULL;
}
if (l_ret == true || r_ret == true)
return true;
else
return false;
}
void pruning (tree **root, int K)
{
if (!*root)
return;
if ((*root)->key >= K)
return;
bool ret = prunTree (*root, 0, K);
if (ret == false)
{
free (*root);
*root = NULL;
}
}
I agree with mike. Hash table + doubly link link will do all. Plus bit modification that we dont have to traverse whole DLL to get unique users as retrieval should be as fast as possible.
Here is my approach
1) At each node, there will be total unique visitors till that time since start of server
2) At time of user addition, check if user exists in hash map, and if exist then update its time to current time. and based on difference between lasttimeaccess of user and current time, node's counter will be updated.
3) At time of retrieval, count will be : (count at head - count in last 11th min node).
Update of list will be at time of addition and at time of retrieval.
Update can be done on 1 min timer also.
- SK January 25, 2014