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#
Well, the problem really in *root = &v[mid]. You use vector<node>, so &v[mid] will return the address of node of the actual array, and when you call push_back the reallocation may occur (depending on the current size) and the old pointer will be invalid after that. I advise you to use the vector<node*> or first, calculate the length of the list, and allocate vector<node> of that size in order to avoid future reallocations.
I hope this will solve your problem :)
Thank you for remark. :)
Well, first, we calculate the length of the list (time:O(n)). Then construct an array of tree's nodes' pointers in the same sequence, without making any connections, just copying the actual data from the corresponding node (time:O(n), memory:O(n)). Now we can access the i-th element in O(1).
In order to make BST with balanced heights we need to make the middle (n/2) node as a root (elements already sorted), then do the same recursively for left and right sub-arrays and finally connect the roots of left and right sub-trees to corresponding fields (time:O(n)).
I hope this is correct. Any comments are welcome.
template <class T>
struct SListNode
{
SListNode(T d)
: data(d), next(NULL) {}
T data;
SListNode<T> * next;
};
template <class T>
struct BTreeNode
{
BTreeNode(T d)
: data(d), left(NULL), right(NULL) {}
T data;
BTreeNode<T> * left;
BTreeNode<T> * right;
};
template <class T>
BTreeNode<T> ** ConstructArray(
SListNode<T> * first, size_t & N)
{
N = 0;
SListNode * node = first;
while (node)
{
++N;
node = node->next;
}
BTreeNode<T> ** array =
new BTreeNode<T> * [N];
node = first;
for (size_t i = 0; i < N; ++i)
{
array[i] = new BTreeNode<T>(node->data);
node = node->next;
}
return array;
}
template <class T>
BTreeNode<T> * ConstructBTree(
BTreeNode<T> ** array, size_t N)
{
if (!N) return NULL;
if (N == 1) return array[0];
size_t middle = N >> 1;
BTreeNode<T> * root = array[middle];
root->left = ConstructBTree(array, middle);
root->right = ConstructBTree(
array + middle + 1, N - middle - 1);
return root;
}
template <class T>
BTreeNode<T> * ConstructBTree(
SListNode<T> * first)
{
size_t N = 0;
BTreeNode<T> ** array =
ConstructArray(first, N);
BTreeNode<T> * root =
ConstructBTree(array, N);
delete [] array;
return root;
}
Also we can use modified version of quicksort's partition operation.
Select the pivot element, then during the partitioning we can get the following:
[ left side of array < pivot ] [ pivot ] [ right side of array > pivot ]
minL = min(left side of array)
minR = min(right side of array)
So the possible elements should be (minL, pivot) or (pivot, minR).
Then recursively perform this for left and right subarrays and get the necessary result.
Time complexity O(nlong).
int FindLeastDiff(int a[], int N, int & i, int & j)
{
i = j = -1;
int ii = 0, least_diff = -1;
for (int jj = 1; jj < N; ++jj)
{
int diff = abs(a[ii] - a[jj]);
if (diff < least_diff || least_diff < 0)
{
least_diff = diff;
i = ii;
j = jj;
} else
ii = jj;
}
return least_diff;
}
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;
// swap
a[mapped_index] ^= memory ^= a[mapped_index] ^= memory;
++processed_elements;
current_index = mapped_index;
} while (current_index != loop_start_index);
++loop_start_index;
}
}
const int N = 5;
const int alphabet[N] = { 1, 2, 3, 4, 5 };
void print()
{
for (int i = 0; i < N; ++i)
std::cout << alphabet[i] << " ";
std::cout << std::endl;
}
void swap(int & x, int & y)
{
int temp = x;
x = y;
y = temp;
}
void combination(int offset = 0)
{
if (offset == N - 1)
print();
else
{
combination(offset + 1);
for (int i = offset + 1; i < N; ++i)
{
swap(alphabet[offset], alphabet[i]);
combination(offset + 1);
swap(alphabet[offset], alphabet[i]);
}
}
}
<pre lang="c++" line="1" title="CodeMonkey6989" class="run-this">// omit iostream in thre prev. post :)
#include <iostream>
using namespace std;
int findPos(int a[], int l, int r)
{
if (l == r)
return l;
int middle = (l + r) / 2;
if (a[middle] > a[middle + 1])
return middle + 1;
return a[middle] < a[l] ? findPos(a, l, middle) : findPos(a, middle, r);
}
int main()
{
int a[] = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7 };
int pos = findPos(a, 0, sizeof(a) / sizeof(a[0]));
cout << pos << endl;
return 0;
}</pre><pre title="CodeMonkey6989" input="yes">1
2
10
42
11
</pre>
<pre lang="c++" line="1" title="CodeMonkey36033" class="run-this">#include <iostream>
using namespace std;
int findPos(int a[], int l, int r)
{
if (l == r)
return l;
int middle = (l + r) / 2;
if (a[middle] > a[middle + 1])
return middle + 1;
return a[middle] < a[l] ? findPos(a, l, middle) : findPos(a, middle, r);
}
int main()
{
int a[] = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7 };
int pos = findPos(a, 0, sizeof(a) / sizeof(a[0]));
cout << pos << endl;
return 0;
}
</pre><pre title="CodeMonkey36033" input="yes">1
2
10
42
11
</pre>
Here the length of the array and exact arguments of constructors are known at compile time. Suppose that you need to read the length and each argument from console. The elements will be allocated in sequential cells (in case of using array of pointers, the actual objects allocated in different locations).
- fiddler.g June 21, 2010Here is pseudocode:
var sortedArray = new Array();
var count = 0;
foreach b in array
{
// insert b in already sorted array and get position (staring from 1)
// running time is log(sortedArray.length)
// can be implemented like binary-search
var pos = insert(sortedArray, b);
// all the elements in sortedArray located after pos are > b
// so those elements can appear in pair with b
count += sortedArray.length - pos;
}
print(count);
// total running time is about NlogN
void common(Node * list1, Node * list2, Node * result)
{
// assume that lengths of lists are M & N respectively
sort(list1); // MlogM
sort(list2); // NlogN
// max. M + N
while (list1 && list2)
{
int val1 = list1->data;
int val2 = list2->data;
if (val1 == val2)
append(result, val1);
if (val1 > val2)
list1 = list1->next;
else
list2 = list2->next;
}
// total time NlogN + MlogM + M + N
}
void sort012(int a[], int size)
{
int l = 0;
int r = size - 1;
while (l < r)
{
while (a[l] == 0 && l < size) ++l;
while (a[r] == 2 && r >= 0) --r;
if (a[l] == a[r]) // == 1
break;
std::swap(a[l], a[r]);
}
for (int i = l + 1; i < r; ++i)
if (a[i] == 0) std::swap(a[i], a[l++]);
for (int i = r - 1; i > l; --i)
if (a[i] == 2) std::swap(a[i], a[r--]);
std::swap(a[l], a[r]);
}
call by value: during this call the copy of the actual data is passed
- fiddler.g July 16, 2010call by reference: during this call passed only some reference information (in terms of C/C++: reference or pointer) about where to find the actual data (the actual data doesn't copied)