~amit
BAN USERWe might want to use DP for this problem because of its subproblem nature for maximum profit.
#include <iostream>
#include <stdlib.h>
using namespace std;
int maxProfitRec(int a[],int i,int n) {
if(i >= n) return 0;
int mx1 = maxProfitRec(a,i+1,n);
return max(mx1, a[i]+maxProfitRec(a,i+2,n));
}
int maxProfit(int a[],int n) {
int table[n+1];
table[0] = table[1] = 0;
for(int i=2;i<=n;i++) {
int mx = table[i-1];
for(int j=i-2;j>=0;j--) {
mx = max(table[j]+a[i-1],mx);
}
table[i] = mx;
}
return table[n];
}
int main() {
int a[] = {3,5,2,5,60,12,5,234,5,223,123};
int n = sizeof(a)/sizeof(a[0]);
cout<< "DP Algo :"<<maxProfit(a,n) <<endl;
cout<< "Rec Algo:"<<maxProfitRec(a,0,n) <<endl;
return 0;
}
find the next smaller and next greater number with same set of bits.
Find the one with minimum difference and return the same.
finding next greater -
1) find the first one from right;
2) find the first zero from right and first one.
3) set the first zero as One and right next to it as Zero.
4) Set all remaining zeros first and then Ones.
Same for other also...
The actual run time depends upon the type of tree. If it is skew tree, then it will be O(n2), otherwise if it is balanced tree, then O(nlgn).
#include <iostream>
#include <unordered_map>
using namespace std;
struct tree{
int data;
struct tree *left,*right;
tree(int data) {
this->data = data;
left = right = NULL;
}
};
void find(tree *root,unordered_map<tree *,pair<int,int> > &m)
{
if(!root) return;
for(auto i : m)
if(root->data < i.second.first)
m[i.first].second += root->data;
m[root] = make_pair(root->data,0);
find(root->left,m);
find(root->right,m);
cout<<m[root].second<<" ";
}
int main()
{
tree *root = new tree(6);
root->left = new tree(3);
root->right = new tree(5);
root->right->left = new tree(18);
root->right->right = new tree(5);
root->left->left = new tree(4);
root->left->right = new tree(2);
unordered_map<tree *,pair<int,int> > m;
find(root,m);
return 0;
}
Just another solution -
1) For every element in matrix(at pos1), find smallest(pos2) in its surroundings and record its position in format (row*ROWS+col);
2) union the original position to this position. union1(pos1,pos2);
3)store in map and sort by frequency
4)print it
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <vector>
#define NEIGHBOURS 4
using namespace std;
typedef vector< vector<int> > matrix;
int neighbour[NEIGHBOURS][2] = { {0,-1}, {-1,0},{0,1},{1,0} };
int find(int id[],int p) {
while(p != id[p])
p = id[p];
return p;
}
void union1(int id[],int p,int q) {
int proot = find(id,p);
int qroot = find(id,q);
if(proot != qroot)
id[proot] = qroot;
}
bool issafe(int p,int S) {
return (p>=0 && p < S);
}
int small(matrix m,int i,int j,int S) {
int sm = m[i][j];
int pos = i*S+j;
for(int k=0;k<NEIGHBOURS;k++) {
if( issafe(neighbour[k][0]+i,S) && issafe(neighbour[k][1]+j,S) ) {
int tmp = min(sm, m[ neighbour[k][0]+i ] [ neighbour[k][1]+j ]);
if(sm != tmp)
pos = S*(neighbour[k][0]+i) + neighbour[k][1]+j;
sm = tmp;
}
}
return pos;
}
int main()
{
/*matrix mat = {
{1, 5, 2},
{2, 4, 7},
{3, 6, 9}
};*/
matrix mat = {
{1, 0, 2, 5, 8},
{2, 3, 4, 7, 9 },
{3, 5, 7, 8, 9},
{1, 2, 5, 4, 2},
{3, 3, 5, 2, 1}
};
int S = 5;
unordered_map<int,int> m;
vector<int> v;
int id[S*S];
for(int i=0;i<S*S;i++) {
id[i] = i;
}
for(int i=0;i<S;i++) {
for(int j=0;j<S;j++) {
int s = small(mat,i,j,S);
if( s != i*S +j)
union1(id,i*S+j,s);
}
}
for(int i=0;i<S*S;i++) {
m[ find(id,id[i]) ]++;
}
for(auto i:m) {
v.push_back(i.second);
}
sort(v.rbegin(),v.rend());
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
void find(int a[],int n,int &s,int &l)
{
unordered_map<int,int> m;
for(int i=0;i<n;i++) {
m[ a[i] ]++;
}
int max1 = 0;
int cur = 0;
int first;
for(auto i : m) {
cur = i.second + m[i.first+1];
if(cur > max1) {
s = i.first;
max1 = cur;
}
}
l = max1;
}
int main()
{
//int a[] = { 2, 6, 7, 9, 1, 0, 1, 2, 3, 6 };
//int a[] = {1,5,1,0,2,6,2,1};
int a[] = {6,6,5,5,4,4,3,3,2,2,2,1,0,7,7,7,7};
//int a[]= {0,0,-1,-1,-9,9,-9,9,-9,9,-9,-10,9};
int n = sizeof(a)/sizeof(a[0]);
int s,l;
find(a,n,s,l);
cout<<"from "<<s<<" to "<<(s+1)<<" : "<<l<<endl;
cout<<endl;
return 0;
}
As the array is very large so we can assume that array has more space than range of its charset i.e [a-z] or [A-Z] or both
1) for only printing the non-repeating elements -
/*for simplicity consider only chars in set [A-Z]*/
void print(char in[],int n)
{
for(int i=0;i<n;i++) {
int pos = (abs(in[i])-'A')%26;
if(in[pos] > 0 ) {
cout<<(char)(abs(in[i]))<<" ";
in[pos] *= -1;
}
}
}
2) For actually removing duplicates from array and return array with non-duplicate elements -
Can somebody point out how can we do in place replacement to remove duplicates?
As the first array is sorted, so we don't need to binary search all elements of b in a. We can just (modified)bsearch first element of array b in array a and then can check if it continuously matches or not. Please point out if i am wrong or missing something important.
int bsearch(int a[],int l,int r,int e) {
if( (r-l) > 1 ){
int m = (l+r)/2;
if ( e < a[m] )
return bsearch(a,l,m-1,e);
return bsearch(a,m,r,e);
}
return ( (a[r] == e ) ? r : ( (a[l] == e) ? l : -1 ) );
}
bool check(int a[],int n,int b[],int m,int &f,int &l) {
int firstRightIndex = bsearch(a,0,n-1,b[0]);
if( firstRightIndex == -1 ) {
cout <<" Err : first index not found "<<endl;
return false;
}
int prev = b[0];
int i = 0,j;
while(b[i] == prev) i++;
if(firstRightIndex - i + 1 < 0 || a[ firstRightIndex - i + 1] != b[0] ) {
cout << "out of Index "<<endl;
return false;
}
f = firstRightIndex - i + 1;
for(i=f,j=0;i<n && j<m;i++,j++) {
if( b[j] != a[i] ) {
cout << "Not proper subarray"<<endl;
return false;
}
}
l = i;
return true;
}
int main()
{
int a[] = {1,2,2,3,3,3,3,4,4,5,5,5,6,6,7,8};
int sz_a = sizeof(a)/sizeof(a[0]);
int b[] = {1,2,4,5,5,5,6,6,7};
int sz_b = sizeof(b) / sizeof(b[0]);
int f =-1,l = -1;
cout << "Result : "<< ( check( a, sz_a, b , sz_b , f ,l) ? "True" : "False")<<endl;
cout<<"Matched from "<<f<<" to "<<l<<endl;
cout<<"Matched array : ";
if( f != -1 && l != -1) {
for(int i=f;i<l;i++)
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
1) If we can keep the hashes of entire array in memory then simple hashing technique would be fast enough for this problem. But to avoid the collision, we might need sufficiently large hash function ( 160 -256 bits ), which may again result in memory issue.
2) We can use the distributed hash table ( is possible ) to solve the memory problem.
3) We can use the Bloom filters -
a) We may use 10 bits bloom filter to keep false positive rate under 1% ( source : wiki)
b) While inserting any element into bloom filter, we can check if it is "definitely not in set". We can write these strings to "resultset" file.
c) If it "can be in set", keep track if it - Either writing to file or keep in memory using hashes (depending upon memory)
d) After we have consumed available memory space or all elements, we have definitely unique elements in "resultset". We repeat this step until, we consume all elements in source file.
e) Then, we can discard/keep elements "can be in set" using simple comparison or comparing hashed in group.
My Algorithm:
1) Keep pointer to start and end of array.
2) keep on counting number from start if ( cur_num == prev_num) count++; and do start++.
3) if (count > k), then swap(cur_elem, last_elem) and decrement last pointer (last--); but don't do start++ at this step.
4) Now check the (2) condition for swapped element and (cur_elem != prev_elem) then, do start++, and last = n-1;
5) keep on doing same thing until (start == last)
Other than design pattern, i can think of this problem as (undirected) graphical representation of different components. Such as "Motherboard" has edges to all CPUs it supports and then CPUs can have edges to all RAMs in turns that it supports and it goes on.
So when user first select "Motherboard", it display all CPUs in its adjacency list ( and can even filter down as other components along their children if needed).
Now User select particular CPU, then display all supported RAMs i.e all adjacent vertices.
Same way for reverse filtering..
-> Just keep in counting all the substrings that are palindromic, Use table to keep tack of which all substring are palindromic.
int dp(char a[],int n) {
bool table[n][n];
memset(table,0,n*n);
for(int i=0;i<n;i++) table[i][i] = true;
int count = n; // all one length are palindromic
for(int len = 2;len <= n;len++) {
for(int i=0;i<n-len+1;i++) {
int j = i+len-1;
if(j == i+1 && a[i] == a[j]) table[i][j] = true;
else {
if(a[i] == a[j]) table[i][j] = table[i+1][j-1]; //mark all palin substring
//else table[i][j] = table[i+1][j] || table[i][j-1];
}
if(table[i][j]) count++;
}
}
/*
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++)
cout<<table[i][j]<<" ";
cout<<endl;
}
*/
return count;
}
As the storage size will be limited, we don't want to keep on storing entire browsing history.
1) We can use circular array of limited size (say 1000) and then keep on updating the queue, so the final 1000 will contain latest browsed pages-in order of browsed date and time.
2) For displaying history, process the array from end -> start ( in reverse order) , so printing recently browsed page first.
3) We may like to write the older history record to file. So, don't discard the updated urls at the end of queue, but keep on inserting them on fixed size queue.
4) Once the queue is full, create new queue to push the pages.Write the entire old queue data to file and destroy it. [ using queue to do bulk IO instead of small writes ]
5) When user want to load older pages, read the data from file.
6) Here, to maintain the order, we have to read the entire file and print it in reverse order to display by access time.
psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced
int median(tree *root,int n, int orgN,int suc)
{
if(!root) return 0;
if(n == 0) {
if(orgN & 1) return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);
{{
- ~amit March 11, 2017* 1. Start from first element, if zero then we can't move forward.
* 2. Record the current index in bitset : store.set(i, true);
* 3. If not zero, the nextIndex = (curIndex+a[i])%size
* 4. Move to next index and follow same step.
* 5. If bitset.size() == size , that means we have covered all elements of array.
* 5. If we find bitset.get(index) == true, break the loop and return true;
}}