## Vijay Rajanna

BAN USERInternet Explorer

-> Addons

-> Java Script Engine & Performance.

-> UX

-> Security

-> Bookmarks.

I hope the question is like this.

Given a Binary Tree ( Not a binary search tree), and values/data of two nodes, find all the common ancestors.

Algorith.

1) Write a recursive function to get reference to two given nodes traversing from root node.

2) Now consider one of the node, and traverse up the tree till node, and pushing all the parent reference to a vector.

3) Now consider the other node, and up up the tree, at each step search for its parent in the vector created in step 2.

4) At a given point if search of step 3 matches, return all the elements in the rest of vector from the point the reference found, as common ancestor.

Hi Netesh,

Your algorithm was little obfuscating.

But, however this will not work, if there are duplicate items.

Consider the below sorted matrix.

1 2 3 4

2 3 4 5

6 7 8 9

Rdo, you are right, the above solution works for even distribution of points. without any distant point from a cluster.

- Vijay Rajanna April 24, 2012My approach would be.

Given all the co-ordinates..

1) Pick minimum absolute values of X call it X1

2) Pick Maximum absolute values of X call it X2

3) Pick minimum absolute values of Y call it Y1

4) Pick Maximum absolute values of Y call it Y2

The source P should be very close to (X1 + X2)/2 , (Y1 + Y2)/2

In the above solution, The concept is right, but it doesn't always work.

Consider a GRID with both +ve and -ve points . and the above formula fails to work for such inputs.

Maze is nothing but a graph, Hence to be very simply Maze can be represented as 2D matrix, if there is single connecting edge between two nodes, the corresponding cell entry will have value 1 else 0 .

Next , simply you can use DFS to find out the way to reach destination from source.

similar questions on matrix reading, is on my blog.

vijaysringeri.blogspot.in/2011/06/matrix-is-back-but-this-time-instead-of.html

I have two inputs here for optimization

1) sizeof(unsigned int) , is the culprit, assign the value to an integer and use it.

don't call function in a loop.

2) instead of reinterpret_cast<char*> , if you know that all data read is going to be char*.. just use an explicit cast as (char*)&i.. This saves lot of time as well.

This is more of a database schema question, wherein subordinates of a employee is represented as foreign key in the employee table.

Representing in OOP model,

Every employee can have a vector to store references of his subordinates, the only issue with this, to store references of all the subordinates in a vector of employee class it needs all subordinate objects must have been instantiated.

You need to consider whether the bits are counted from 0 or 1.

The above approaches wroks if the bits are counted from 0, but if counted from 1, below is the solution.

bool bitset(int number, int pos)

{

return (number & pow(2,(pos-1)) ;

}

Find the predecessor for both the nodes, considering that the left subtree for both of these nodes is null.

The first common predecessor of both of these nodes will be the common ancestor.

We can simply use an equation...

ax^n + b x^n-1 + C x^n-2 +..............+ Z X^0

a, b, c represents ascii value for each char in the linked list..

Take any arbitrary value for X,

N represents LinkedList lenght -1

Traverse the list from left to right , and right to left and if the sum is same in both the cases.

They are palindrome.

In the inorder traversal for a given node, the successor will be the very next node...

Since all the nodes are arranged in increasing order...

Eg : 1 , 2, 5, 6,7,9,10,15.. (Inorder of a BStree)

Successor of 7 is 9..

This works when right subtree of the node for which successor needs to be found is not null.

Scan the file/line character by character.. and if there is successive redundant space characters... Remove those.

- Vijay Rajanna February 27, 2012If I name each interval as A, B, C.. and if there are N intervals...

for eg : A = { 7,8,9,10 } B= { 9,10, 11} C = { 1, 2, 3, 4}.........

By intersection, I would get nC2 combinations...

Each combination is of the form .. |A^B|, | A^B|.. etc...

For each interval , sum up the total number of intersection... as below.

|A^B| + | A^B| + | A^C |..... Etc..

The one which has maximum sum is the answer.

This is my understanding.

Perspective - 1

Sort all those fifty Students/Ranks then the index of the student picked would tell you his relative position.

Perspective - 2

I am not sure, but is the question based on " Counting Sort " where you have a fixed range ( in this case 50 ) for a huge numbers of items to sort with ( in this case 100 students )

Below are my findings.

1) Here the assignment operator need to overloaded to implement deep copy.

2) The whole solution could have been simply implemented using Vectors.

This is basically a permutation problem. Hence the total number of possible words is found by..

16p1 + 16p2 + 16p3 +................................................ + 16p15 + 16!

However this solution results in many combinations which are not possible by joining characters in the adjoining cells.

First Merge two sorted arrays to get a single sorted array.

Time = ( n + m ) -> Consider it as n.. Hence merging takes O(n) time.

Find Median.

Index of the median element = (int) ((n+m)/2) -> Which can be achieved in constant time..

Hence Solution is of the order O(n) ->

The program still works fine.. For number 10 and pos 2.. The answer should be 1.

1010

0010

______

0010 != 0 hence return 1

This should do.

boolean getBit(int num, int i)

{

if ((num&(1<<(i-1)))!=0) return 1 ;

else 0 ;

}

We should look for optimum solutions here. It is not enough if we just parse the elements from left to right or right to left. we must find out proper combinations to achieve maximum compression.

EG : cabb

Parsing from left to right yields -> cabb -> bbb -> String of lenght 3

Parsing from right to left yields -> cabb -> ccb -> ca-> b -> string of length 1.

Hence we must check when we combine two adjacent chars to produce the resultant char, if the resultant char is same as the next char. If so, skip this pair for that round and continue.

The optimization should happen during compile time, with respect to the above chunk of code.

This is because

1) Other than " abc = 3 " the code is not being altered anywhere

2) Also you don't see any statement like " abc = RHS " where you are trying to assign a new value at run time.

Hece the compiler is very sure that " Else " part never gets executed. Hence code optimization should happen @ compile time.

It is possible...

codeproject.com/Articles/10900/Polymorphism-in-C

It should be possible. But the module/program for both the processes should be coded by in such a way that, altering a variable of a process by the other shouldn't cause any data loss, or alternation.

So basically such programs are coded by a single team who knows behavior of both the processed.

And, if the processes/code are developed by different teams having no knowledge on the other process. In such cases above operations may lead to crashes.

My solution is this.

Sort the array , using any Nlog(N ) algorithm.

After sorting, If the array has N elements, pick the

first element, and the last,

Second element and the last but one th element

and so on.. Until you pick N/2 element this will for subset -1

The remaining N/2 elements will form subset 2

To be very specific as @numbus said, All door numbers which are perfect squares will be closed.

And rest of the doors will remain open, The reason is, There is always a pair of devisors.

EG : take number 12.

2*6

6*2

3*4

4*3

12*1

1*12

Doors with " Even Number of Factors " remains opened.

and Doors with " ODD " number of factors remains closed.

Considering that the hour format is in 24 Hrs a day.

Angle = ((MinuteHandReading/5)*30) - ((HourHandReading % 12)*30)

This turns out to be a combination problem.

In general given "N" elements and asked to find a subset of "R" elements, it is required to find all the combinations of ( R-1) size from (n-1) elements, and compare with "N" element which is taken as reference and this happens "N" times.

Hence for any give problem to find out the subset of " R " elements it takes O( N^r+1) time complexity.

@Manan, I doubt that the above solution works.

Because " TreeNode p = (TreeNode) list.remove(); " statement wouldn't ensure that you always referring to internal nodes.

Also this isn't a linear list. It is a tree.

So , if you can elaborate on this solution , it will be good.

The solution by @Harty, is a brute force approach..

Start from each node, and traverse hence you would end up in O(n2) algorithm.

Also we need to consider that one must traverse in both clockwise and anticlockwise directions.

which is n2+n2 Algo.. which still runs in O(n2) algorithm.

@Harty : You are right, I misunderstood it.

- Vijay Rajanna January 12, 2012The problem seems to be pretty simple.. But I doubt.

From the problem definition it can be noticed that the track is circular.. and user is has only 2 options, moving in clockwise and counterclockwise directions.

Calculate total perimeter of the track, divide it into segments , and joining two segments is a fuel pit.

Check travelling in a particular direction consuming fuel at pits is enough to reach next pit or ahead of it.

And this should work.

Each and every process running on windows (or any other OS) is provided with a predefined amount of virtual memory in case of vc++ apps I think it is 4 GB.

Though the RAM size is say 512 MB or 1GB , OS will ensure such a huge memory for processes using "Paging" mechanism.

Use observer pattern, whenever the particular value is encountered trigger the event to intimate.

- Vijay Rajanna May 05, 2011A warning is expected but not a compiler error.

- Vijay Rajanna May 03, 2011This would be parent of left most node.

- Vijay Rajanna May 03, 2011This would be parent of left most node.

- Vijay Rajanna May 03, 2011Agree with Mersulo, traverse till the left most node in BST and return the value, this will run in 0(log n) complexity.

if the BST is stored in an array... using the property

"if a node has an index i, its children are found at indices 2i + 1(for the left child) and 2i + 2(for the right)"

The least value can be found in o(1) time.

I think VIV is 11 , and not 54 or 65...

Basically here we do the addition, and place value is not considered.

Rep**LisaNoto**, Android Engineer at ADPAnnie has nearly 10 years of experience working on anadromous and estuarine fishery issues in California. She serves as a ...

Rep**marilyannrandall**, Backend Developer at ABC TECH SUPPORTAs a Data input clerk, I deal with customers on a daily basis. Entering customer and account data from source ...

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

Create a binary search tree, and each time when you find a duplicate element while inserting a new element, reject it.

- Vijay Rajanna June 20, 2013Time Complexity O(nlogn)