## inevitablekris

BAN USER- 0of 0 votes

AnswersBy saying that an algorithm runs in O(n) time in the worst case, what does we really mean?

- inevitablekris in United States| Report Duplicate | Flag | PURGE

Algorithm - 0of 0 votes

AnswersSuppose S and T are two ordered dictionaries each containing n items. Both are implemented via sorted arrays and do not have any keys in common. Describe

- inevitablekris in United States

an O(log n)-time algorithm that outputs the item whose key is the lower median in the union of S and T. For example, when the keys stored in S and T are

S = [3, 6, 7, 9] and T = [−1, 1, 2, 8], the lower median key is 3.| Report Duplicate | Flag | PURGE

Algorithm - 0of 0 votes

AnswerAssume the numbers 1 through n are stored in a binary tree T. For the pre-

- inevitablekris in United States

order, postorder and inorder traversals the output of a preorder

traversal of T with 5 nodes can be something like 2; 3; 1; 5; 4. We can think of

this output as the \preorder traversal signature" of the tree. Clearly, we can do

the same for both the postorder and inorder traversals.

a. Is the preorder traversal signature of a tree T unique? That is, are there

two trees storing the numbers 1 through n with the same preorder traversal

signature? How about the postorder traversal signature? the inorder traversal

signature? If your answer is yes to any of these questions, provide an expla-

nation.| Report Duplicate | Flag | PURGE

Algorithm - 3of 3 votes

AnswersSuppose that each row of an n x n array A consists of 1's and D's such that, in any

- inevitablekris in United States

row i of A, all the 1's come before any D's in that row. Suppose further that the

number of 1's in row i is at least the number in row i+ 1, for i= 0, 1, ... .n - 2.

Assuming A is already in memory, describe a method running in O(n) time (not

O(n2) time) for counting the number of 1's in the array A.| Report Duplicate | Flag | PURGE

Arrays

This is o(n).

- inevitablekris September 23, 2014int count = 0;

int column = 0;

for (int row = arr.length - 1; row > 0; row--) {

while (column <= arr.length - 1 && arr[row][column] == 1) {

count = count + row + 1;

column = column + 1;

}

}

Thank you. Can you write the pseudocode if possible.

- inevitablekris September 22, 2014This will give O(n^2) i want it in O(n)

- inevitablekris September 22, 2014This will give O(n^2) i want it in O(n)

- inevitablekris September 22, 2014

RepI'm from India, 26 years old. I want to travel, I want a job where I can earn money ...

Rep**danielhlee542**, Associate at ASAPInfosystemsPvtLtdHi i am an health information technician at Seamans Furniture.Expertise in medical assistance, staff development and training, and implementing ...

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

Open Chat in New Window

GeeksForGeeks

- inevitablekris October 15, 2014Perfect O(log(n))

public class GetMedianRec {

/*

* This function returns median of ar1[] and ar2[]. Assumptions in this

* function: Both ar1[] and ar2[] are sorted arrays Both have n elements

*/

static int getMedian(int ar1[], int ar2[], int n) {

return getMedianRec(ar1, ar2, 0, n - 1, n);

}

/*

* A recursive function to get the median of ar1[] and ar2[] using binary

* search

*/

static int getMedianRec(int ar1[], int ar2[], int left, int right, int n) {

int i, j;

/* We have reached at the end (left or right) of ar1[] */

if (left > right)

return getMedianRec(ar2, ar1, 0, n - 1, n);

i = ((left + right) / 2);

j = n - i - 1; /* Index of ar2[] */

/* Recursion terminates here. */

if (ar1[i] > ar2[j] && (j == n - 1 || ar1[i] <= ar2[j + 1])) {

/*

* ar1[i] is decided as median 2, now select the median 1 (element

* just before ar1[i] in merged array) to get the average of both

*/

if (i == 0 || ar2[j] > ar1[i - 1])

return Math.min(ar1[i], ar2[j]);

else

return Math.min(ar1[i], ar1[i - 1]);

}

/* Search in left half of ar1[] */

else if (ar1[i] > ar2[j] && j != n - 1 && ar1[i] > ar2[j + 1])

return getMedianRec(ar1, ar2, left, i - 1, n);

/* Search in right half of ar1[] */

else

/* ar1[i] is smaller than both ar2[j] and ar2[j+1] */

return getMedianRec(ar1, ar2, i + 1, right, n);

}

public static void main(String[] args) {

int ar1[] = { 1, 2 };

int ar2[] = { 4, -2 };

System.out.println(getMedian(ar1, ar2, ar1.length));

}

}