loosy.jhony
BAN USER- 0of 0 votes
AnswersGiven a binary tree with each node has count (no. of children + 1). Write an inorder traversal to find the ith node in O(lgn).
- loosy.jhony in Dubai for AzurNode * ithNode(Node *root, int i) { // return ith node in Inorder traversal. }
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test
Adjacency list: because its easy to add, delete and update data in it.
- loosy.jhony March 13, 2012QuickSelect
login2win.blogspot.com/2011/06/quick-select.html
ArrayList GetSubsets(int [] Set, int size, int sum, int index)
{
ArrayList<ArrayList<int>> allSubsets;
if( index == size ){
allSubsets = new ArrayList<ArrayList<int>>();
//allSubsets .add(new ArrayList()); // Add Empty subset
return allSubsets ;
}
else {
int first = Set[index];
ArrayList otherSets = GetSubsets(Set, size, sum, index + 1);
ArrayList<ArrayList<int>> allSets = new ArrayList<ArrayList<int>>();
allsubsets = getSubsets(set, index + 1);
int item = set.get(index);
ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> subset : allsubsets) {
if( IsValidSet( new ArrayList<Integer>(subset).add(item), sum) )
{
ArrayList<Integer> newsubset = new ArrayList<Integer>();
newsubset.addAll(subset); //
newsubset.add(item);
moresubsets.add(newsubset);
}
}
allsubsets.addAll(moresubsets);
}
return allsubsets;
}
public boolean IsValidSet(ArrayList set, int sum)
{
int tempSum= 0;
foreach(int elem : set)
tempSum +=elem;
return tempSum == sum;
}
I posted this algorithm before "@Pankaj" solution above. The only difference is that I just wrote the algo. rather than code.
- loosy.jhony February 29, 2012one solution could be:
1. Make an array of size 10 countDigitMap[10] = {0};
2. Start taking out least significant digit of number.
3. and keep wcountDigitMap[digit]++;
4. loop from end form ( 9, 8 ... 0 ) and print digits in map with count > 0.
guys if u have any better than this one please comment below.
Adjacency list: Because we are using memory for data that is stored rather than sparse matrix and because its easy to add, delete and update data in Adjacency list.
- loosy.jhony March 13, 2012