amit
BAN USERI think of two approaches here -
1. Using directed Graph (Not necessary that all comes under one manager)
For each entry in hashmap :
addEdge(entry.key, entry.val); //directed edge
//When printing employee under it or count just bfs/dfs starting from that node.
2. Use Hashmap :
Map <String, List<String>> map;
//iterate first time to store the relationship between manager and immediate employees
for each entry in hierarchy:
if entry.key != entry.val :
List<String> l = map.containsKey(entry.val) ? map.get(entry.val) : new ArrayList();
l.add(entry.key);
map.put( entry.val, l);
//insert key for leaf node employees
if map.containsKey(entry.key) :
map.put(entry.key, new ArrayList());
//Now, we need to put all employees under a manager from hierarchy
for each entry in map :
List<String> l = entry.val;
List<String> nl = new ArrayList(l);
for each key in l :
nl.addAll(map.get(key));
map.put(entry.key, nl);
//Print map directly and get size
I would suggest two approaches for linear time.
1. Use first loop to places all non-zeros at position counter <index> and keep count for zeros also. In second loop, iterate over only zeros to places zeros at the end. The time complexity will be O(n) still in this case.
2. Do only in one loop -
void placeZeros(int a[],int n) {
int j = 0;
int i = 0;
while(j<n) {
if(a[i] != 0) i++, j++;
else {
if(a[j] == 0)
j++;
else {
swap(a[i++],a[j++]);
}
}
}
}
int main() {
int a[] = {30,30,15,18,20,25,80};
int n = sizeof(a)/sizeof(a[0]);
int profit[n];
int mn[n];
mn[n-1] = a[n-1];
int minVal = a[0];
profit[0] = 0;
for(int i=1;i<n;i++) {
profit[i] = max(profit[i-1],a[i]-minVal);
minVal = min(minVal,a[i]);
}
for(int i=n-2;i>=0;i--) {
mn[i] = min(mn[i+1],a[i]);
}
for(int i=4;i<n;i++) {
profit[i] = max(profit[i],profit[i-1]);
for(int j=i-3;j>=1;j--) {
profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
}
}
for(int i=0;i<n;i++)
cout<<profit[i]<<" ";
cout<<profit[n-1]<<endl;
return 0;
}
A prime number could be in format of 6n+-1 so check for numbers in this format if they are prime or not upto the given count.
int c = 0;
int n = 1;
int lastPrime=-1;
while( c < N ) {
int k1 = 6*n-1;
int k2 = 6*n +1;
if( isPrime(k1) ) { lastPrime = k1; c++; }
if(c == N) break;
if(isPrime(k2) ) { lastPrime = k2; c++; }
n++;
}
return lastPrime;
If i am not wrong, it can be solved much easier -
Record < string,string_len> for each word;
Sort the container according to string_len in non-decreasing order.
starting from beginning, search for longest increasing subarray and keep track or maximum length subarray.
return maxlen subarray.
I think the maximum number of collected diamonds can be the best two paths to reach the last cell. Probably, the following logic can work.
int fun(int mat[][N] ) {
int table[N][N];
table[0][0] = mat[0][0];
for(int i=1;i<n;i++) {
if(mat[i][i] != -1)
table[i][0] = table[i-1][0] + mat[i][0];
else
table[i][0] = -1;
}
for(int j=1;j<n;j++) {
if(mat[[0][j] != -1)
table[0][j] = table[0][j-1] + mat[0][j];
else
table[0][j] = -1;
}
for(int i=1;i<n;i++) {
for(int j=0;j<n;j++) {
if(mat[i][j] != -1)
table[i][j] = max(table[i][j-1],table[i-1][j]) + mat[i][j];
else
table[i][j] = -1;
}
}
if(table[n-1][n-2] < 0 || table[n-2][n-1] < 0) {
cout<<"No Roundtrip path possible";
return -1;
}
return table[n-2][n-1] + table[n-1][n-2] + mat[n-1][n-1] - mat[0][0];
}
I think the logic should be same as finding the second maximum.
int findRange(int a[],int n) {
int maximum = INT_MIN;
int f = 0, s = 0;
for(int i=1;i<n;i++) {
if(a[i] > a[f] ) {
s = f;
f = i;
} else
s = (a[i] > a[s])?i:s;
if(b > maximum ) {
range = abs(a-b)+1;
maximum = b;
}
}
return range;
}
* This solution assumes extra iteration to calculate the array product first time.
1. Iterate over array.
2. Calculate the prod to the left of current element or right of current element.
3. Update the result with max.
- amit March 25, 2017