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 ...
Repdanielhlee542, Associate at ASAPInfosystemsPvtLtd
Hi i am an health information technician at Seamans Furniture.Expertise in medical assistance, staff development and training, and implementing ...
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));
}
}