## 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++

void FillNext(Tree *root, Tree *succ)

{

if(root != NULL)

{

FillNext(root->left, root);

if(root->right == NULL)

{

if (succ != NULL && root->data >= succ->data)

root->next = NULL;

else

root->next = succ;

}

FillNext(root->right, succ);

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int arr[] = {50,40,45};

Tree *root = NULL;

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

root = CreateTree(root, arr[i]);

FillNext(root, root->right);

return 0;

}

Tree* Count(Tree *root)

{

if(root != NULL)

{

if(root->left == NULL)

root->lCount = 0;

if(root->right == NULL)

root->rCount = 0;

if(root->left)

root->lCount = Count(root->left)->lCount + Count(root->left)->rCount + 1;

if(root->right)

root->rCount = 1 + Count(root->right)->lCount + Count(root->right)->rCount;

}

return root;

}

Does anyone have a better solution that O(n), as I can see it can be done easily in this time

Here is the algo

1) Read line by line

2) Extract the number from the line and match with the numbers given,

Take a max which contains the string and the number of matches

Everytime you compares for a match and if matches are greater than max then make max = current string

I am writing the algo for this

Take a hash which will look like this [Assuming the input given in in sorted order]

A->B->C->D

D->E->F

Y->Z

Now we can take the first element of every row

ADY

Increment last row by one and carry on like

ADZ

AEY

AEZ

Please let me know if I am doing something wrong here

Here is my code...

bool IsPresent(Tree *root, int value)

{

if(root != NULL)

{

if(root->data == value)

return true;

else return (IsPresent(root->left, value) || IsPresent(root->right, value));

}

return false;

}

void FirstCommonAncestor(Tree *root, int lValue, int RValue)

{

if(root == NULL)

{

}

else

{

if(IsPresent(root->left, lValue) && IsPresent(root->right, RValue))

{

printf("Ancestor %d", root->data);

}

else

FirstCommonAncestor(root->left, lValue, RValue);

FirstCommonAncestor(root->right, lValue,RValue);

}

}

My answer

#include "stdafx.h"

struct Tree

{

int data;

int lCount;

int rCount;

Tree *left;

Tree *right;

};

Tree * CreateTree(Tree *root, int value)

{

if(root == NULL)

{

root = new Tree();

root->data = value;

root->left = NULL;

root->right = NULL;

root->lCount = 0;

root->rCount = 0;

}

else if(value < root->data)

root->left = CreateTree(root->left, value);

else

root->right = CreateTree(root->right, value);

return root;

}

Tree * CountLR(Tree *root)

{

Tree *node = NULL;

if(root != NULL)

{

if(root->left == NULL && root->right == NULL)

{

root->lCount = 0;

root->rCount = 0;

}

else if(root->left == NULL)

{

root->lCount = 0;

node = CountLR(root->right);

root->rCount = node->rCount + node->lCount + 1;

}

else if(root->right == NULL)

{

root->rCount = 0;

node = CountLR(root->left);

root->lCount = node->lCount + node->rCount + 1;

}

else

{

node = CountLR(root->left);

root->lCount = node->lCount + node->rCount + 1;

node = CountLR(root->right);

root->rCount = node->rCount + node->lCount + 1;

}

}

return root;

}

int _tmain(int argc, _TCHAR* argv[])

{

int arr[] = {30,15,10,66,51,53,12};

Tree *root = NULL;

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

root = CreateTree(root, arr[i]);

CountLR(root);

return 0;

}

// BFSTree.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

struct Tree

{

int data;

Tree *left;

Tree *right;

};

struct linkedList

{

Tree *node;

linkedList *next;

};

Tree * CreateTree(Tree *root, int value)

{

if(root == NULL)

{

root = new Tree();

root->data = value;

root->left = NULL;

root->right = NULL;

}

else if(value < root->data)

root->left = CreateTree(root->left, value);

else

root->right = CreateTree(root->right, value);

return root;

}

void PrintTreeBFS(linkedList *current, linkedList *last)

{

if(current == NULL)

return;

else

{

//printf("\n Node Value %d" + current->node->data);

printf("\n Node Value %d", current->node->data);

if(current->node->left != NULL)

{

linkedList *onemore = new linkedList();

onemore->node = current->node->left;

onemore->next = NULL;

last->next = onemore;

last = last->next;

}

if(current->node->right != NULL)

{

linkedList *another = new linkedList();

another->node = current->node->right;

another->next = NULL;

last->next = another;

last = last->next;

}

current = current->next;

PrintTreeBFS(current, last);

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int arr[] = {30,15,10,66,51,53,12};

linkedList *list = new linkedList();

Tree *root = NULL;

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

root = CreateTree(root, arr[i]);

list->node = root;

list->next = NULL;

PrintTreeBFS(list, list);

return 0;

}

void permuteArr3(int num1, int num2, int *arr3, int posforArr3, int length3)

{

if(posforArr3 < length3)

{

printf("\n");

printf("%d, %d, %d", num1, num2, arr3[posforArr3]);

posforArr3 += 1;

permuteArr3(num1, num2, arr3, posforArr3, length3);

}

}

void permuteArr2(int num1, int *arr2, int *arr3, int posforArr2, int length2)

{

if(posforArr2 < length2)

{

permuteArr3(num1, arr2[posforArr2], arr3, 0, 4);

posforArr2 += 1;

permuteArr2(num1, arr2, arr3, posforArr2, length2);

}

}

void permuteArr1(int *arr1, int *arr2, int *arr3, int posforArr1, int length1)

{

if(posforArr1 < length1)

{

permuteArr2(arr1[posforArr1], arr2, arr3, 0, 4);

posforArr1 += 1;

permuteArr1(arr1, arr2, arr3, posforArr1, length1);

}

}

int _tmain(int argc, _TCHAR* argv[])

{

int arr1[] = {1,2,3,4};

int arr2[] = {11,22,33,44};

int arr3[] = {111,222,333,444};

permuteArr1(arr1, arr2, arr3, 0, 4);

return 0;

}

I have hardcoded the values for now on.

Lets take an example given above to explain my logic

19 17 3 2 7

Traverse in the opposite direction taking one element at a time and comparing that with its parent. If child is less swap with the parent.

Eg

19 17 3 2 1

Take 1 compare with 17 less swap

19 1 3 2 17

Now compare 1 with parent and swap if less

1 19 3 2 17

Now take 2 and compare with parent 19 and swap

1 2 3 19 17

compare 2 with 1 and do not swap

Now take 3 and compare with 1 and do not swap...

Hence min heap is

1 2 3 19 17

take 2 pointers both pointing to the starting of the array A and B respectively

Now find the difference.

Move the pointer pointing to the lesser of the 2 ahead

Let say

A = 3,10,20

B = 2,5,15

first step 3-2 = 1

Now move pointer B to 5

5-3 = 2.

Now move pointer A to 10 and so on...

The idea is move that pointer which is pointing to the lesser value of the 2 so as to reduce the diff between numbers.

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

Open Chat in New Window

Can we generate a random number between 0 to number of nodes in the tree.

- DashDash May 13, 2012Now return the node by doing /preorder, postorder or inorder traversal using the random number.

Further traversal can also be chosen randomly