fiddler.g
BAN USER- 0of 0 votes
Answerspublic string impossible()
- fiddler.g
{
try
{
// Person is a reference type
Person person = null;
return person.FullName;
}
catch (NullReferenceException)
{
return string.Empty;
}
}
Could method `impossible` ever return a non-empty string? If yes, in which cases.| Report Duplicate | Flag | PURGE
Software Engineer / Developer C#
The above algorithms have O(N*N) time complexity in all cases. I'll try to describe my approach with O(N*N) in the worst case.
Well, the idea is to analyse each column and group current identical rows.
First, we analyse the first column. All 0-s will be moved to group G0 and the 1-s to G1. The algorithm continues until there are no groups with more than one row in it or we reach the N-th column. On the k-th step we analyse the k-th column and only groups with more than one row in it. For such a group we will replace it with a two new ones. At any time empty groups must be removed. Getting one row from each group we will get the resultant unique rows. Here is an example:
N=5.
columns: 1 2 3 4 5
---------
row 1: | 0 1 0 0 1
row 2: | 1 0 1 1 0
row 3: | 0 1 0 0 1
row 4: | 1 1 1 0 0
row 5: | 1 1 0 1 1
step 1: G0={1,3}; G1={2,4,5}.
step 2: G0 => (G00={empty}, G01={1,3}); G1 => (G10={2}, G11={4,5}).
step 3: G01 => (G010={1,3}, G011={empty}); G10={2}; G11 => (G110={5}, G111={4}).
step 4: G010 => (G0100={1,3}, G0101={empty}); G10={2}; G110={5}; G111={4}.
step 5: G0100 => (G01000={empty}, G01001={1,3}); G10={2}; G110={5}; G111={4}.
Result groups: G01001={1,3}; G10={2}; G110={5}; G111={4}.
Unique rows: 1 (or 3), 2, 5, 4.
Lets denote by A and B the given sorted arrays of size N. Suppose that the median value is A[m]. Therefore there are m elements from A which are less that or equal to A[m], so array B must contain N-m such elements. In this case we can say that B[N-m] <= A[m] < B[N-m+1] (of course, taking into account the array boundaries). Denote this condition as C(m). Here is the algorithm. First check the m=[N/2] element. If C(m) is true, then the median is A[m], otherwise compare the B[N-m] and A[m]. If it <= then do the same for [N/2] to N range, else for 0 to [N/2]. Overall time complexity is O(log(N)).
- fiddler.g January 29, 2011Instead of finding K-th largest element we can find the (N*N - K + 1)-th smallest element, so I will describe my approach how to find the K-th smallest element of matrix A.
Suppose 1 <= M <= N. It is easy to see that sub-matrix ([1,1] - [M,M]) contains the first smallest M*M elements. So, suppose that the sought K-th smallest element is located at [I,J]. Then we can say that all elements of sub-matrix ([1,1] - [M,M]), where M = max(I,J) - 1, are less than the sought element. the number M could be found by the following formula: M = [sqrt(K)]. In case when K = M*M, then the sought element is A[M,M]. Otherwise, it will be one of Line={A[M+1,1], A[M+1,2], ..., A[M+1,M+1]} or Column={A[1,M+1], A[2,M+1], ..., A[M,M+1]}. As we can see here are only (2*M + 1) elements and we must find the (L = K - M*M)-th element. Taking into account that Line and Column are sorted we can do it just using two pointers with L comparisons.
The overall time complexity is O(N) (exactly K-[sqrt(K)]*[sqrt(K)] comparisons, 2*N-2 in worst case when K=N*N-1) and O(1) memory.
Any comments are welcome :).
Lets decompose the number N as follows: (A)(B) (even digits) or (A)(x)(B) (odd digits). For example if N=12345 then A=12, B=45 and x=3. Lets denote by rev(A) the reverse of A. In our example it will be rev(A)=21.
1) N=(A)(B), In case when N contains even number of digits, then
if rev(A) > B, the sought number will be (A)(rev(A)),
otherwise, (A+1)(rev(A+1)).
2) N=(A)(x)(B), In case when N contains odd number of digits, then
if rev(A) > B, the sought number will be (A)(x)(rev(A)),
otherwise, if x < 9, then the sought number will be (A)(x+1)(rev(A)),
else (x = 9), (A+1)(0)(rev(A+1)).
OK, one mistake, it should be 2^(n+1). To solve this, just shift right by 1 bit.
We have equation like this: 2^(n+1) = (x xor (x-1)) + 1,
where n is the number of last consequent 0-s of x written
in binary format.
x = [binary data][1][n 0-s]
x-1 = [binary data][0][n 1-s]
x xor (x-1) = [ 0-s ][1][n 1-s]
(x xor (x-1)) + 1 = [ 0-s and 1 ][n+1 0-s] = 2^(n+1).
node * restore(int pre[], int in[], int N)
{
if (!N) return NULL;
int * it = std::lower_bound(in, in + N, *pre);
assert(it != in + N && !(*pre < *it));
int index = it - in;
node * root = new node(*pre);
root->left = restore(pre + 1, in, index);
root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
return root;
}
template <typename Iterator, typename Function>
typename std::iterator_traits<Iterator>::value_type
Reduce(const Iterator begin, const Iterator end, Function fn)
throw (NotEnoughElements)
{
if (begin == end) throw NotEnoughElements();
Iterator it = begin;
typename std::iterator_traits<const Iterator>::value_type result = *it++;
if (it == end) throw NotEnoughElements();
for (; it != end; ++it) result = fn(result, *it);
return result;
}
a) It is safe, because nothing will be changed in the object structure. The libraries will not be aware that new constructor is available.
b) This will change the structure of the object. So, it will be problem if the size of this class used anywhere in the library. Or if the member added before any other member.
c) If the previous version of the class was not polymorphic, this will change the structure (vptr), so it is not safe, otherwise you will decrease the number of possible bugs in libraries :)
d) It is safe if this argument appended at the end of the argument list.
template <typename Container, typename Function>
typename Container::value_type
Reduce(const Container& c, Function fn) throw (NotEnoughElements)
{
if (c.size() < 2) throw NotEnoughElements();
typename Container::const_iterator it = c.begin();
typename Container::value_type result = *it++;
for (; it != c.end(); ++it) result = fn(result, *it);
return result;
}
bool isBST(TreeNode * root, int * pMin=NULL, int * pMax=NULL)
{
if (!root) return true;
if (pMin && root->data <= *pMin) return false;
if (pMax && root->data > *pMax) return false;
return isBST(root->left, pMin, &root->data) &&
isBST(root->right, &root->data, pMax);
}
2)
void MakeMagic(int src[], int dst[], int N)
{
if (!N) return;
int * p = new int [N];
int index = N-1;
p[index] = 1;
p[index-1] = src[index];
for (--index; index > 0; --index)
p[index-1] = src[index] * p[index];
int q = 1;
for (index = 0; index < N; q *= src[index++])
dst[index] = q * p[index];
delete [] p;
}
node * findMaxBST(node * root, int & N)
{
if (!root) return N=0, NULL;
if (!root->left && !root->right) return N=1, root;
int n1=0;
node * rootL=findMaxBST(root->left, n1);
int n2=0;
node * rootR=findMaxBST(root->right, n2);
if (!n1 && !n2) return N=1, root;
bool left = rootL==root->left && rootL->data<root->data;
bool right = rootR==root->right && rootR->data>=root->data;
if (left && right) return N=n1+n2+1, root;\
if (left)
if (n1+1>n2) return N=n1+1, root;
else return N=n2, rootR;
if (right)
if (n2+1>n1) return N=n2+1, root;
else return N=n1, rootL;
if (n1>n2) return N=n1, rootL;
return N=n2, rootR;
}
Use 2 min-heaps. Scan the array's elements. Keep track of the max element for each heap and the current number of elements. Current heap should be the heap with the maximum. If the next element is greater than the max, then if the number of elements in the current heap is < k, add it to the heap, otherwise replace it with the minimum. If the next element is less than the max of current heap add it to the second heap. If the next element is less than the both maximums, overwrite the heap with the minimum sum. Change the current heap, when another becomes greater.
- fiddler.g July 25, 2010I suppose that the BST is a complete tree and the indices are 0-based.
Say the given number is at index i. There are several cases we need to check:
1) If this node has a right child, so the sought node should be the leftmost node of the right subtree.
2) If this node hasn't a right child and it is a left child, so the parent node is the sought node.
3) If this node hasn't a right child and it is a right child, so we need to find the first parent which is a left child, and it's parent should be the sought node.
In all cases we can do some calculations (O(1)) in order to find the sought node.
1) The existence of the right child could be done with the following condition:
bool isRightChildExists = (2*i+2 < N), where N is the number of node in the tree. Now we must find the leftmost nodes index. this node should be located on the last or previous level. The hight of the tree is [log(N+1)] (say root is located on the 0 level) and the i-th node's level is [log(i+1)]. The root of the right subtree is 2*i+2 so we need to find the (d = [log(N+1)]-[log(i+1)]-1) d-th left child. It is also easy to see that the n-th left node's index could be found as follows: (2^(n+1))*(i+1)-1. So the sought node's index should be (2^(d+1))*((2*i+2)+1)-1. If this value is > N, so the sought node is located on the previous level and it's index is calculated in the same way, just by replacing d with d-1.
2) All left child's indices are odd, so if (i&1 != 0) then the sought node's index is [(i-1)/2].
3) The n-th (n>1) right child of the i-th node could be found as follows: (2^n)*(i+2)-2. So we need to find the maximum n for which there is some x (the first left child parent of i-th node) when (2^n)*(x+2)-2=i. That is i-th node is the n-th right child.
Therefore x=(i+2)/(2^n)-2. Easy to see that n is the greatest for which i+2 could be divided to 2^n. If we write the i+2 in the binary format, then the number of the last 0-s should the n. So 2^n=((i+2)xor(i+1))+1. Then x=(i+2)/(((i+2)xor(i+1))-1). The sought node is the parent of x: [(x-1)/2].
Any comments are welcome.
Lets group all pairs in the following way:
(suppose elements are sorted in descending order)
G(k) = { (a,b) | (a=A[k] and b in B[k..n]) or
(b=B[k] and a in A[k..n]), 1<=k<=n }.
Each G(k) will contain 2(n-k)+1 pairs and the union of all this groups will cover whole possible pairs.
Now we need to store next candidate pair from the corresponding group. It could be done by storing current index i and j for A and B arrays correspondingly. This will mean that the next candidate pair from this group is (A[i], B[j]). If we pick this pair, the text one (for that group) will be (A[i+1], B[j]) or (A[i], B[j+1]) (just compare them and get the largest). Now we need to store all n candidates from each group in the max-heap (O(n*log(n))). Then pick up the top element (O(1)), this will be the next largest pair, then remove it from the heap (O(log(n))), change the candidate for the corresponding group (O(1)) and add this one to the heap (O(log(n))). Continuing this operation n times we will get the n largest pairs (O(n*log(n))).
Additional optimization could be done and in the best case we will get O(n) (in the mentioned version we will ALWAYS get O(n*log(n))).
Any comments are welcome.
void PrintMaxSumPairs(int a[], int b[], int N, int total)
{
if (total > N*N) return;
int i = N - 1, j = N - 1;
for (int k = 0; k < total; ++k) {
std::cout << '(' << a[i] << ',' << b[j] << ')' << std::endl;
if (!i) --j; else
if (!j) --i; else
if (a[i] - a[i-1] < b[j] - b[j-1]) --i; else --j;
}
}
void CyclicShift(int a[], int N, int K)
{
if (K > N) K %= N;
if (!K) return;
int processed_elements = 0,
loop_start_index = 0;
while (processed_elements < N) {
int current_index = loop_start_index;
int memory = a[current_index];
do {
int mapped_index = (current_index + K) % N;
a[mapped_index] ^= memory ^=
a[mapped_index] ^= memory;
++processed_elements;
current_index = mapped_index;
} while (current_index != loop_start_index
&& processed_elements < N);
++loop_start_index;
}
}
void Merge(int a[], int N, int offset)
{
int i = 0, j = offset;
while (i < j && j < N)
if (a[i] > a[j]) {
int k = j;
while (a[k] < a[i] && k < N) ++k;
CyclicShift(a + i, k - i, k - j);
i += k - j;
j = k;
} else ++i;
}
#include <hash_set>
void PrintAnagrams(char * str,
size_t offset = 0, size_t * pLen = NULL)
{
if (!offset) pLen = new size_t(strlen(str));
if (offset == *pLen - 1)
std::cout << str << std::endl;
else {
stdext::hash_set<char> distinct;
distinct.insert(str[offset]);
PrintAnagrams(str, offset + 1, pLen);
for (int i = offset + 1; i < *pLen; ++i)
if (distinct.find(str[i]) == distinct.end()) {
distinct.insert(str[i]);
std::swap(str[offset], str[i]);
PrintAnagrams(str, offset + 1, pLen);
std::swap(str[offset], str[i]);
}
}
if (!offset) delete pLen;
}
// Try this code and look at the generated assembler ;)
- fiddler.g January 13, 2012void test() { }
void main()
{
void (*testFunc)() = test;
testFunc();
}