I’ve released NDataStructure 1.0.1 !
Grab it from codeplex: NDataStructure.codeplex.com
Or install the NuGet package: NDataStructure on NuGet.org
I also generated complete documentation here: NDataStructure Documentation
Release notes:
- XML documentation for sandcastle.
- Refactored WeightedGraph away from eventing traversal to IEnumerable
- Incremented version 1.0.0.0 to 1.0.1.0
- NuGet manifest for 1.0.1
- Improved DoublyLinkedList to support ICollection
- Minor rearrangement of a few files
Posted: March 13th, 2011 | Author: benlakey | Filed under: benlakey.com | Tags: C#, codeplex, data structures, ndatastructure, NuGet | No Comments »
As I tend to do from time to time; Here is another good set of interview questions to toy with (These particular ones are in C#):
private static char FindLongestRun(string str)
{
Dictionary<char, int> runs = new Dictionary<char, int>();
char last = str[0];
runs.Add(last, 1);
for(int i = 1; i < str.Length; i++)
{
if (last == str[i])
{
int oldCount = runs[last];
runs.Remove(last);
runs.Add(last, oldCount + 1);
}
else
{
runs.Remove(str[i]);
runs.Add(str[i], 1);
}
}
char longest = last;
foreach (char c in runs.Keys)
{
if (runs[c] >= runs[longest])
longest = c;
}
return longest;
}
private static int BinSearch(int[] arr, int seek)
{
return BinSearch(arr, 0, arr.Length - 1, seek);
}
private static int BinSearch(int[] arr, int min, int max, int seek)
{
if (min > max)
return -1;
else if (min == max)
return (arr[min] == seek ? min : -1);
else
{
int partIdx = min + ((max - min) / 2);
int left = BinSearch(arr, min, partIdx, seek);
int right = BinSearch(arr, partIdx + 1, max, seek);
if (left != -1)
return left;
if (right != -1)
return right;
return -1;
}
}
private static int Atoi(string number)
{
int result = 0;
int multiplier = 1;
for (int idx = number.Length - 1; idx >= 0; idx--)
{
char digitChar = number[idx];
int digitValue = digitChar - '0';
result += (digitValue * multiplier);
multiplier *= 10;
}
return result;
}
private static string ReverseString(string str)
{
char[] strChars = str.ToCharArray();
for (int idx = 0; idx < strChars.Length / 2; idx++)
{
char tmp = strChars[str.Length - 1 - idx];
strChars[str.Length - 1 - idx] = strChars[idx];
strChars[idx] = tmp;
}
return new String(strChars);
}
private static int BitCount(int number)
{
int bits = 0;
while (number > 0)
{
bits += (number % 2);
number /= 2;
}
return bits;
}
This week I completed a BTree implementation which I’ve been working on. As verification of its efficiency over a standard data structure like List, I ran some numbers and plugged them into Google’s Graph API. The results illustrate a BTree order 4 attempting to find a span of 9000 keys over 50000 possibilities (as compared to List). The left (Y) axis represents time in milliseconds, and the bottom (X) axis represents number of keys searched.
Posted: April 4th, 2010 | Author: benlakey | Filed under: benlakey.com | Tags: big o, C#, data structures | No Comments »
Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:
- Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
- Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
- ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.
Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ‘smart’ pointer.):
void LinkedList::reverse()
{
if((_head == NULL) || (_length == 1))
{
return;
}
else
{
NodePtr previous = NodePtr();
NodePtr current = _head;
NodePtr next = NodePtr();
while(current)
{
next = current->next;
current->next = previous;
previous = current;
current = next;
}
_head = previous;
}
}
