I was asked an interesting computer science question today which left me stumped. The basic problem seems simple enough but it's more complex than at first glance. The idea is you have singly linked list that can either be standard linked list, a circular linked list (starts an ends in the same place), or a circuitous linked list (has a loop in it that doesn't necessarily go back to the start). How do you detect if a the linked list contains a loop without knowing the length of the linked list, and without being able to modify any of the data.
My initial thought was to just check and see if any of the nodes have null as their "next" value but this is an obvious pitfall because if it has a loop the code would run forever.
My next thought was to keep track of the memory location of each node and check to see if the next node's memory location has already appeared in the list, but this is not elegant, and could take a lot of memory (think of a long linked list).
After that I thought that at each position you could check the memory locations of each node up to the current one and compare them to the "next" node's memory location. This is essentially the same as my second idea but without having to store every node's memory location. This isn't a good solution either because it requires too many traversals of the list (aka SLOW!).
Next up I thought you could reverse the list and see if the the end node of the reverse list is the start node of the original list. This is good but it requires either of the two options:
a. Modifying the list (not allowed)
b. Making a copy of the list but in reverse order
Technically a could be remedied by then re-reversing the list but still then you'd have to go through the whole process twice.
Finally I had to ask for the answer and here is what I was told. Create two node objects one that is going to traverse the list quickly and one that is going to traverse the list slowly. The quick traverser moves two nodes ahead for every one node that the slow one moves. If the quick traverser ever catches the slow traverser then their must be a circuit. Why didn't I think of that? Such a simple solution.
Later I found a second answer that is pretty cool too. This one basically says always have one node to check held in memory. Basically start off with it being the second node and then check four more nodes to see if it gets selected again. If it doesn't then set the fourth node after it to the check node and check 8 nodes after that to see if any of them are the same. If they aren't set the eight node after the last check node to the new check node and then check 16 nodes after that to see if any of them are the same as the check node, and keep going until eventually one of the nodes that is traversed over is the same node as the check node, or a node with a "next" value of null is reached. I thought this solution was particularly interesting because it only requires one traverser.
I guess that's all I have on linked lists for now.
Friday, August 29, 2008
Monday, August 4, 2008
Unable to read the project file <project.csproj>. The system cannot find the path specified.
I recently received a new computer at work, after my old one blew up, and I was trying to setup my web project from SourceSafe and I kept getting the error listing in the title of this entry. I checked IIS to make sure that I had created the virtual directory correctly, and the path seemed to be fine. I also tried opening just the .csproj file instead of the entire .sln (there are several .csproj files in the solution I was working with), it opened just fine. Finally I came across an article that suggested opening Visual Studio and clicking File -> Source Control -> Open from Source Control and then selecting my solution folder. I did that and voila, my problem was fixed. I'm not sure why this was an issue, but I'd guess that it has something to do with source safe and my local project/solution files not syncing up correctly.
Friday, June 20, 2008
Access The Page Object From a Separate Class in ASP.NET
I just found this out today and thought you might want it for your notes. For awhile now I've been under the impression that the Page object was inaccessible from a class outside of the codebehind page. Today I found out that I was wrong. To access the Page object you simply need to do the following:
Page page = (Page)HttpContext.Current.Handler;It would have been alot nicer if they included a property of HttpContext that would work like this: HttpContext.Current.Page, but for some stupid reason they did not do that. Anyway, I know that I was happy to find that out so I thought you might want to know too.
Dynamically Add and Modify Server Side Buttons in an ASP.NET Datagrid or Repeater
Within the last few weeks I was asked about how to dynamically format the output of either datagrids or repeater objects in .Net. My response at the time was to do something like the following:
Where SomeMethod() is a server-side method in the code-behind which evaluates the bound-data given to it as a parameter, and returns it in the desired format. In some code that I've used this design, I send SomeMethod, which is called DateFormatter() in my code, two dates and then compare the two dates to see if they are the same. If they are the same then the method returns just the one date in MM/DD format, but if they are different then the method returns the two dates like so, MM/DD - MM/DD.
Recently I found that I had need for something a little bit more robust. I wanted to dynamically create server-side buttons in the repeater object which would have different parameters based on the data to which the item was bound. To do this I created a method and wired it to the OnItemDataBound Event of the Repeater. Here is basically what I did:
Aspx File
Code-Behind
<%# SomeMethod(DataBinder.Eval(DataItem.Container, "data_column").ToString()) %>
Where SomeMethod() is a server-side method in the code-behind which evaluates the bound-data given to it as a parameter, and returns it in the desired format. In some code that I've used this design, I send SomeMethod, which is called DateFormatter() in my code, two dates and then compare the two dates to see if they are the same. If they are the same then the method returns just the one date in MM/DD format, but if they are different then the method returns the two dates like so, MM/DD - MM/DD.
Recently I found that I had need for something a little bit more robust. I wanted to dynamically create server-side buttons in the repeater object which would have different parameters based on the data to which the item was bound. To do this I created a method and wired it to the OnItemDataBound Event of the Repeater. Here is basically what I did:
Aspx File
<asp:Repeater OnItemDataBound='ItemDataBoundMethod'>
...
<ItemTemplate>
<input type='hidden' id='parameter1' value='<%#DataItem.Container, "data_column").ToString())' runat="server" />
... Some More Hidden Fields ...
<!-- Below I create a button with no parameters and no events wired to it, so that I can set them dynamically in the OnItemDataBound Event-->
<asp:Button id='ButtonTemplate' runat='server' />
</ItemTemplate>
...
</asp:Repeater>
Code-Behind
protected void ItemDataBoundMethod(Object sender, RepeaterItemEventArgs e)
{
//Make sure that this is an item and not a header, footer, etc.
if(e.Item.ItemType == ListItemType.Item e.Item.ItemType == ListItemType.AlternatingItem)
{
//Here I access the hidden fields with the Id that I gave them
string param1 = ((HtmlInputHidden)e.Item.FindControl("parameter1")).Value.ToString().Trim();
...
Button buttonTemplate1 = ((Button).e.Item.FindControl("ButtonTemplate"));
...
...Evaluate the values in the hidden field and then set the properties of the button accordingly...
...
}
}
Thursday, April 17, 2008
COM Objects are not destroyed when using Server.CreateObject in Classic ASP (Jscript)
Recently it was discovered that, on a particular ASP page in our application, COM objects that were being created using Server.CreateObject were not being properly destroyed. Actually, I should rephrase that, they weren't being destroyed at all until the component services package was shut down. If I kept task manager open, and watched the mem usage of dllhost.exe, I could see the memory being used by the processed increased each time I hit the page in question, and never decreased. Also, if I went to Administrative Tools -> Component Services and looked at the Objects, Activated, and In Call columns for the COM objects in my package, I could see those numbers ever increasing without decreasing.
The code is written in JScript and looked something like this:
A third suggestion that I would suggest, just based on conjecture from information provided in the article, is to rewrite the code block causing the problem in vbscript, as it is not effected by this problem (no garbage collection).
As for my problem, I'm not entirely sure why the problem occurs on only one page and not the others. My only guess is that on the page that is having a problem all of the COM objects are instantiated (about 14), whereas on most others only one or two objects are created.
The following is my code, after I fixed it:
The code is written in JScript and looked something like this:
var o = Server.CreateObject("dllname");After much searching I came across this article: PRB: COM Objects Created in JScript Not Released Immediately. The article basically says that because JScript uses deferred garbage (for performance reasons), it can sometimes delay object destruction (in my case, permanently delay it). The article offers two solutions, the first suggest that a destructor be written for the dll, and the second suggests that the undocumented CollectGarbage() function be used. I chose the latter, simply because adding to the dll would be a bigger inconvenience (aka laziness).
/* do stuff... */
o = null; //<--- I thought that this line should cause this object to be destroyed, I was //wrong
A third suggestion that I would suggest, just based on conjecture from information provided in the article, is to rewrite the code block causing the problem in vbscript, as it is not effected by this problem (no garbage collection).
As for my problem, I'm not entirely sure why the problem occurs on only one page and not the others. My only guess is that on the page that is having a problem all of the COM objects are instantiated (about 14), whereas on most others only one or two objects are created.
The following is my code, after I fixed it:
var o = Server.CreateObject("dllname");
/* do stuff... */
o = null;
CollectGarbage(); // <-- This one little line fixed my problem
Wednesday, April 9, 2008
Opening Component Services In Windows Vista
I really don't hate microsoft, or Windows Vista, for that matter, but I do hate it when they move things around and don't tell you where they put them. To get to component services in Vista you should do the following.
1. Open "Run," I usually do this by typing "run" in the dynamic search embedded in the start menu.And that's that.
2. Type "comexp.msc" in the run window, and then hit enter.
Alternative:
Go to "%windir%\system32\comexp.msc" and click it, or make a shortcut to it and put it in administrative tools so it can be with all it's XP buddies.
Cause a SQL Statement to Wait (Sleep, Pause)
At work I was trying to simulate a query that took a long time to execute, in order to debug a problem that I was tasked to fix. My goal was to write it in such a way that I knew exactly how long it was going to take every time. That's when I came across code that would allow to do exactly that:
WAITFOR DELAY '000:00:20';This code will wait for 20 seconds and then and then run the code that follows it, which is exactly what I was looking for.
SELECT column_list FROM table_name;
Subscribe to:
Posts (Atom)