DashDash
BAN USER- -2of 2 votes
AnswersHow to print a variable 1000 times without using loops and recurssion
- DashDash in India| Report Duplicate | Flag | PURGE
Software Engineer / Developer - 0of 0 votes
AnswersWe have
- DashDash in India for Development
char *p = "abc";
I know we cant do p[0] = 'a'. What is the reason behind it?| Report Duplicate | Flag | PURGE
Software Engineer / Developer C++ - 0of 0 votes
AnswersWhat is the next number in the series
- DashDash in India
2,4,8,16,24...| Report Duplicate | Flag | PURGE
Goldman Sachs Applications Developer Brain Teasers - 0of 0 votes
Answersvoid copystring(char* dest, char *source)
- DashDash
{
while(*source != NULL)
{
*dest = *source;
dest++;
source++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char input[10] = "hello";
char *dest;
dest = &input[1];
copystring(dest, input);
return 0;
}
What is the output of the program...| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++
Here is my approach
1) Create a min heap tree of first k elements and keeping track of the max element in the tree
2) Now scanning the other elements from left to right, if any elements is greater than the max number in the tree, remove the min elements from the tree and insert that one and reheapify.
Time Complexity = nlog(k)
struct Tree
{
int data;
int freq;
Tree *left;
Tree *right;
};
Tree* AddNodes(Tree *node, int value, int *arr, int index, int count)
{
if(node == NULL)
{
node = new Tree();
node->data = value;
node->freq++;
node->left = NULL;
node->right = NULL;
arr[index] = count;
return node;
}
else
{
if(value == node->data)
{
arr[index] = count + node->freq;
node->freq++;
}
else if(value < node->data)
{
node->left = AddNodes(node->left, value, arr, index, count);
}
else
{
node->right = AddNodes(node->right, value, arr, index, (count + node->freq));
}
}
return node;
}
int _tmain(int argc, _TCHAR* argv[])
{
Tree *root = NULL;
int arr[] = {1,3,2,4,5,4,2};
int arrCount[7];
for(int i=6;i>=0;i--)
{
root = AddNodes(root, arr[i], arrCount, i, 0);
}
return 0;
}
We can reverse the once which are monotonically decreasing
Now after reversing all them we have k sorted arrays.
Reversing will be done in O(x) time therefore total time O(k/2x) where x is the maximum number of elements in the subarray
If we can solve the algo given 3407664 in O(n) time then total time will be O(k/2n) time.
I take up the example to describe how it works
Let say we have the array as {1,3,2,4,5,4,2}
Scan from right to left
1) insert 2 with freq as 1, since parent therefore count = 0 for it where count is the number of elements lower than or equal to it.
2) Insert 4, right of 2, its count will be freq of 2 and its own freq will be 1
Uptil now resulting array = {1,0}
3) Insert 5, which is right of 2 and right of 4, therefore count = freq(4) + freq(2) = 2, its freq = 1
4) Insert 4 again, right of 2 but exists, therefore
count = freq(2) + freq(4) = 2, node with value 4 freq = 2
5) Insert 2, parent count = 1 and freq = 2
6) insert 3, right of 2 and left of 4, count = freq(2) , its own freq = 1
7) Insert 1, left of 2 therefore count = 0, freq = 1
int Swapbits(int num, int pos1, int pos2)
{
int temp1 = num>>(pos1-1) & 1;
int temp2 = num>>(pos2-1) &1;
int swapnum = num;
//int temp3 = 0;
if(temp1 ^ temp2)
{
//bits are different
int temp3 = 1<<(pos1-1);
int temp4 = 1<<(pos2-1);
swapnum = num ^(temp3 | temp4);
}
return swapnum;
}
int _tmain(int argc, _TCHAR* argv[])
{
int num = 102;
int newnum = Swapbits(num, 3,6);
return 0;
}
Instead of creating a heap of all elements create a max heap of first three points
Now as you scan next point check whether it is less than max and if it is then remove the max elements and insert this one and reheapify.
Go on doing this....
Time complexity : klogk + (n-k)logk => nlogk
where k is the number of points to be find out, here it is = 3
Scan from right to left of the array
Tree structure
Struct tree
{
int data;
int freq;
tree *left;
tree *right;
}
Now as you create the tree if the new element is to the right of the node then add the freq of that node until that element find place in the tree
The total freq = no of elements small or equal to it.
If element is already their in the tree then increase its freq.
Time complexity : T(nlogn)
Tree* ClosestAnscestor(int Rdata, int lData, Tree *node)
{
if(node != NULL)
{
if(findnode(node->left, lData) && findnode(node->right, Rdata))
return node;
else
{
ClosestAnscestor(Rdata,lData,node->left);
ClosestAnscestor(Rdata,lData,node->right);
}
}
else
return NULL;
}
bool findnode(Tree *node, int data)
{
if(node != NULL)
{
if(node->data == data)
return true;
else if(data < node->data)
findnode(node->left, data);
else
findnode(node->right, data);
}
else
return false;
}
bool binsearch(int *arr, int l, int h, int searchElement)
{
int mid = (h-l)/2;
if(l>= h)
return false;
if(arr[mid] == searchElement)
return true;
else if(searchElement > arr[mid])
binsearch(arr, mid+1,h,searchElement);
else
binsearch(arr,l,mid-1,searchElement);
}
bool FindElement(int *arr, int circShifted, int SearchElement,int length)
{
if(arr[circShifted] == SearchElement)
return true;
else
return (binsearch(arr,0,circShifted-1,SearchElement) || binsearch(arr,circShifted+1,length,SearchElement));
}
kulang u r rite.
- DashDash July 25, 2010from my algo its 2,10,12
I think I have made a mistake here...