## ediston

BAN USERint * it;

&it = impossible;

-----------------------------

(I can do it)

- 0of 0 votes

AnswersHi all genius minds.

- ediston in United States

I have a small algorithm question. Any help will be appreciated.

Suppose there is a lake (some height lh) and then there are hills/mountains (with height from 0 to 9).

And finally there is Dam. All the hills and the lake and the dam are on a n*m matrix.

given the height of all points on matrix (lake and dam are also on one such point). find the minimum cost required to create a path from lake to dam so that dam can be filled with water.

Now height of each point can be increased or decreased except the lake.

water can flow only along the adjacent points not along the diagonals. Water can flow from point A to adjacent point B iff heightA >=heightB

-----------------------------------------------------------------------------------------

If we could only decrease the heights, this was a very easy question. but in current case heights can be decreased as well.

How do we solve this.?

Please revert for any clearifiactions| Report Duplicate | Flag | PURGE

Software Engineer / Developer Algorithm - 0of 0 votes

AnswersSuppose you have a graph G(V,E).

- ediston in United States

You are supposed to find the shortest path from a vertex 's' to vertex 'e' for 'n' different cases.

In each case one of the edges 'Ei' (any one edge) of the graph will be blocked/deleted only for that case and we have to find the shortest path in the graph with that edge removed.

Guys finding the shortest path is easy. But how can I make the algo so fast that even if I remove one of the edges my algo should still be very fast. O(n log n) or faster.

Remember we are not deleting the edges permanently. We are just temporary removing one edge per case.

In each case only one edge is removed.

Suppose we blocked one edge E in one case. We have to find the shortest path for the graph.

In next case, we will reconnect the last edge and we will block/remove a new edge. And again for this new case we have to find the shortest path.

Another way of understanding the problem is suppose there are cities connected to each other.

And every day one of the roads gets blocked because of heavy rain. what is the shortest path every day from city s to e.

Also one more important thing to note that each road can be used only once.

But there could be more than 1 direct road from city a to city b.

FInd the shortest path distance from city s to e on a day when all direct roads from city f to city h are blocked. If there is no connecting path return -1| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer - -1of 1 vote

AnswersHow can I do arrangements. of numbers... such that each new number formed out of arrangement has at max a difference of 1 from prev maxima.

- ediston in India

e.g.

if input is k=1 output will be 1

if k =2 outputs are : 11, 12

2,1 is wrong as left most has to be 1 always.

if k = 3 outputs are: 111,112, 121, 122, 123

if k = 4 : 1111,1112,1121,1122,1123,1212,1211,1213,1223,1221, 1222, 1233, 1234

1423 is wrong diff b/w 1 and 4 is 3.

1243 is wrong diff b/w 2 and 4 is 2....

How I do this using DP? if possible ?| Report Duplicate | Flag | PURGE

Qualcomm Software Engineer / Developer Algorithm

No

I meant .. while taversing.. just check current value is bigger than previous or not.

so code will be something like this:

int last;

isBST (tree * node)

{

if(node==null) return true;

if(node->left)

{

if (!isBST(node->left))

return false;

if (node->value < node->left->value) return false;

}

if( node->right) if (node->value > node->rightt->value) return false;

if(!LeftSmaller || !RightBigger )

return false;

if (!isBST(node->right))

return false;

return true;

}

char replace(char char1, char char2)

{

if((char1=='a' && char2=='b') || (char1=='b' && char2=='a')) return 'c';

else if((char1=='a' && char2=='c') || (char1=='c' && char2=='a')) return 'b';

else return 'a';

}

int main()

{

string a = "bcabccc";

for(int i=0 ;i+1<a.length(); i++)

{

if(a[i]!=a[i+1])

{

a[i] = replace(a[i],a[i+1]);

a.erase(i+1,1);

i= (i-2<-1)?-1:i-2;

}

cout << a <<" ";

}

cout <<a.length();

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <string>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

//---------- macros ----------

#define fp(i,a,b) for(int i=a; i<b; i++)

#define fm(i,a,b) for(int i=a; i>b; i--)

using namespace std;

string reduce(string s)

{

int n = s.length();

for(int i=0; i < n; i++)

if (s[i]=='*')

{

if(i>=2 && s[i-1]=='x' && s[i-2]=='x'){ s.erase(i-1,2);

i=i-2; }

}

return s;

}

int main()

{

int n;

cin >> n;

while(n--)

{

string s;

cin >> s;

int c = 0;

s=reduce(s);

while(s!="x")

{

int firstStar = (int)s.find('*');

if(s.size()==2)

{

if(s=="**")

c = c+2;

else // "x*", "*x", "xx"

c++;

s = "x";

}

else

{

if(firstStar>=0)

{

if((int)s.find('x')<0) // all *'s

{

c = c+s.size()/2+1;

s = "x";

}

else

{

c++;

s[firstStar]= 'x';

}

}

else // all x's replace 1/2 by *.. if odd replace delete last one

{

c = c+s.size()/2;

s = "x";

}

if(s!="x")

s=reduce(s);

}

}

cout << c << endl;

}

//-----------------------------

cout << endl;

// system("pause");

return 0;

}

Question says "perform in linear time complexity" .. I have a doubt cant we use two for loops?

By the way.. Can some one review this solution:

int a[4] = {2,3,1,4,5,1,6,2,3,4};

int n=10;

int ti, tj, maxj, mini, i, j;

i=n-1;j=n-1;

mini=0; maxj=n-1; ti=0;tj=0;

for(int k=0, l=n-1; k<n; k++,l--)

{

if(a[k]>=a[tj])

{

tj=k; ti=mini;

}

else if(a[k]<a[mini]) mini=k;

if(a[l]<=a[i])

{

i=l; j=maxj;

}

else if(a[l]>a[maxj]) maxj=l;

}

if (a[tj]-a[ti] > a[j]-a[i]){ i = ti; j=tj;}

//- -- - -- -- here we re traversing from left to right...

finding the largest a[k] and replacing j=k; if current a[i] > some k which we have already passed through then i== that minimum;

at the same time we are going right to left..

finding smallest a[k] and making i=k; if current a[j] < some k which we have already passed through then j== that max;

then we compare the two differences.. and assign i and j

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

yes this is an NP problem... so how do u solve it for limited input sizes ?

- ediston May 22, 2012