## sdm

BAN USERFrom what it looks like, it may have a worst case complexity of O(n^2)

Consider -5,2,0,-3,-1

Here -3 has to move atleast n/2-1 places and -1 has to move atleast n/2-2 places. So total movements may look something like (n/2-1) + (n/2 -2)+ ...+1 = O(n^2) in the worst case.

```
function wildCard(char[] expression,char[] text) returns boolean
boolean afterWildcard = false;
int index= 0;
begin
for(char c in expression)
loop
if(c is wildcard)
afterWildCard = true
continue
else if not afterWildCard and text[index] = c
afterWildCard = false
index++
continue
else if afterWildcard
afterWildCard = false
while(text[index++] != c OR index = text.length)
if(index = text.length)
return false
else
continue;
end loop
return true
end
```

Basically I keep track of whether a character is preceded by a wild card and handle it accordingly.

- sdm March 12, 2010I think you would need to traverse the link list and build a binary tree out of it. And while doing so, keep checking the height of right and left subtrees. If they are different, do a left/right rotation. Doing left rotation would decrease the height of right subtree by 1 and increase height of left subtree by 1 nd vice versa for left rotation.

Are you looking for binary tree creation and rotation algorithms?

Can you please elaborate the question a bit more? Max. cost of what is to be determined?

As I understand, there is a cost for moving forward in X-coordinate and moving down in Y-coordinate. But if that is that is the case, the bottom right pont of the grid would always have the highest cost.

If we keep track of the nodes which are impacted at each level while we search for the correct position of the node to be inserted/deleted, I think it will get done in O(log n), which is the tome complexity of searching for that node. Other operations of updating the impacted nodes for a particular level depending on whether the node was inserted/deleted from that level, should get done in constant time.

- sdm March 04, 2010Some suggestions, though none of them is O(1)

If the child node has reference to its parent, then traversing upto the root from a child would determine all its ancestors.

If only the parent has a references to its children, doing a DFS/BFS would tell about its offsprings.

I assume each bus stop lies on at least 1 route. So let's say we have a table like RouteTable(BusStopName,RouteNumber). So if a new bus stop lying on n number of routes is added, we add n rows to this table.

1.For finding all the bus stops on a route,

select BusStopName from RouteTable where RouteNumber=?

2.For finding all the routes between bus stops s and d

select RouteNumber from RouteTable where BusStopName = s

INTERSECTION

select RouteNumber from RouteTable where BusStopName = d

If the above query returns nothing, there is no connecting direct route. In such a case,

1.you need to find out all the bus stops which lie on the routes having s.

2.Similarly find out all the bus stops which lie on the routes having d.

3.Find the common bus stops of steps 1 and 2 above along with their routes numbers for s and d.

4.The result of 3 would give you the change bus stop and the 2 routes which you would follow one after another to reach from s to d.

The resulting matrix would be a n*n matrix. Each element of the matrix can be computed, independently of the other. So if there are n^2 computers, each has a column and a row to multiply. For e.g. computer1 has row1 and col1, computer2 has row1 and col2. Each computer takes O(n) to multiply the row and column. So the whole matrix can be multiplied in O(n) time.

- sdm February 23, 2010There 3 possible states - State0 ,State1 and State2. Here the number represents the remainder when dividing with three.

Here are the state transitions:

State0--0-->State0

State0--1-->State1

State1--0-->State2

State1--1-->State0

State2--0-->State1

State2--1-->State2

How about doing binary search for finding the first positive in a row a, say at (i,j) and then eliminating submatrix of positives (n-i,n-j). And then moving to next row and doing the same.

Worst case would still be nlogn if there are no positives at all in the matrix.

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

Here's a dynamic programming based solution sans any loops

- sdm October 21, 2014