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 nonempty 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 0s will be moved to group G0 and the 1s to G1. The algorithm continues until there are no groups with more than one row in it or we reach the Nth column. On the kth step we analyse the kth 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.

fiddler.g
February 01, 2011 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 Nm such elements. In this case we can say that B[Nm] <= A[m] < B[Nm+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[Nm] 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 Kth largest element we can find the (N*N  K + 1)th smallest element, so I will describe my approach how to find the Kth smallest element of matrix A.
Suppose 1 <= M <= N. It is easy to see that submatrix ([1,1]  [M,M]) contains the first smallest M*M elements. So, suppose that the sought Kth smallest element is located at [I,J]. Then we can say that all elements of submatrix ([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*N2 in worst case when K=N*N1) 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 (x1)) + 1,
where n is the number of last consequent 0s of x written
in binary format.
x = [binary data][1][n 0s]
x1 = [binary data][0][n 1s]
x xor (x1) = [ 0s ][1][n 1s]
(x xor (x1)) + 1 = [ 0s and 1 ][n+1 0s] = 2^(n+1).

fiddler.g
September 09, 2010 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;
}

fiddler.g
August 01, 2010 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;
}

fiddler.g
July 31, 2010 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;
}

fiddler.g
July 31, 2010 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);
}

fiddler.g
July 31, 2010 2)
void MakeMagic(int src[], int dst[], int N)
{
if (!N) return;
int * p = new int [N];
int index = N1;
p[index] = 1;
p[index1] = src[index];
for (index; index > 0; index)
p[index1] = src[index] * p[index];
int q = 1;
for (index = 0; index < N; q *= src[index++])
dst[index] = q * p[index];
delete [] p;
}

fiddler.g
July 30, 2010 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;
}

fiddler.g
July 27, 2010 Use 2 minheaps. 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 0based.
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 ith 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) dth left child. It is also easy to see that the nth 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 d1.
2) All left child's indices are odd, so if (i&1 != 0) then the sought node's index is [(i1)/2].
3) The nth (n>1) right child of the ith 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 ith node) when (2^n)*(x+2)2=i. That is ith node is the nth 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 0s 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: [(x1)/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(nk)+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 maxheap (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[i1] < b[j]  b[j1]) i; else j;
}
}

fiddler.g
July 19, 2010 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;
}

fiddler.g
July 19, 2010 #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;
}

fiddler.g
July 18, 2010
// Try this code and look at the generated assembler ;)
 fiddler.g January 13, 2012void test() { }
void main()
{
void (*testFunc)() = test;
testFunc();
}