Archive for the ‘Development’ Category.

« Previous Entries

Table Layouts still win over CSS layouts in 2012

February 1, 2012, 5:29 pm

The longer I am blogging and the more often I mess with my html layout (which is done in CSS) the more I come to realize that while CSS is a solution for HTML layouts but it not a good solution and it has in my opinion completely failed to address the layout problem.

Look at any development language, GTK, QT, wxWidgets, Windows Forms, Windows Presentation Foundation, and a dozen others and they all have simple and easy to use layout systems. It is common to have Grid layouts, wrapping layouts, and more.

What does CSS2 and HTML4 have specifically for layout?

Nothing specific to layout. A div is not specific to layout. I was using what the author called Holy Grail 3 column liquid-layout. However, after two days, I still can’t change the width of my right side bar without breaking the layout in some way, which is mostly because the layers and layers of div elements is a mess in this layout.

What does CSS3 and HTML5 have specifically for layout?
They have new elements: article, aside, audio, bdo, canvas, command, datalist, details, embed, figcaption, figure, footer,header, hgroup, keygen, mark, meter, nav, output, progress, rp, rt, ruby, section, source, summary, time, video, wbr

However, while you can use HTML5 and CSS3, just be aware your website will only look good in newer browser. Please don’t try to view your site on Windows XP with IE7 or IE8.

I want the developers of Firefox, Opera, Internet Explorer, Safari, Chrome, HTML5 and CSS3 to know that when it comes to layout, YOU HAVE FAILED!!!!

If there is one reason that I wish Silverlight could become the de facto internet standard is for the simple reason that the layout features in XAML are so far superior than those of even the new HTML5 and CSS3 that there isn’t even a comparison.

So what is the solution to an easy HTML layout?

It just doesn’t get easier than the good old table layout, but you can at least style your layout with CSS.  CSS is good at styling even if it fails at layouts.

Look how easy it is:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>3 Column Table Layout</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">

html, body {
  height: 100%;
}

body {
    margin:0
}

table.layout {
  height:100%;
  width: 100%;
  border-collapse:collapse;
}

tr.header {
  height:150px;
  background:black
}

tr.menu {
  height:50px;
  background:DarkGrey;
}

tr.body {
  height:100%;
}

tr.footer {
  height:150px;
  background:DarkGrey;
  height:150px;
}

td.leftcol {
  padding: 15px;
  width: 170px;
  min-width: 170px;
  background-color:Navy;
}

td.midcol {
  background-color:Grey;
  min-width: 625px; /* Make 425px for min res of 800x600 */
}

td.rightcol {
  padding: 15px;
  width: 205px;
  min-width: 205px;
  background-color:Navy;
}
</style>
</head>
<body>
<table class="layout">
<tr class="header">
<td colspan="3"></td>
</tr>
<tr class="menu">
<td colspan="3"></td>
</tr>
<tr class="body">
<td class="leftcol"></td>
<td class="midcol"></td>
<td class="rightcol"></td>
</tr>
<tr class="footer">
<td colspan="3">
  <p style="text-align: center;">
    <a href="http://validator.w3.org/check?uri=referer">
	  <img src="http://www.w3.org/Icons/valid-xhtml10" alt="Valid XHTML 1.0 Strict" height="31" width="88" />
    </a>
  </p>
</td>
</tr>
</table>
</body>
</html>
  1. t took less than 30 minutes to make this layout.
  2. It still uses CSS to style the layout.
  3. Changes are easy (any column can be re-sized in seconds).
  4. Left and right columns are always the same height.
  5. The background colors always extend vertically as far as needed.
  6. It is of course, W3C compliant.

Sorry CSS, until you have a real layout solution I think you lose to a good old-fashioned table.

But what about dynamically changing the layout?

Well, lets face, it. Dynamic changes are done in code anyway, and any good developer can code up that solution. Besides, most web sites are using some sort of Content Management System, like WordPress, Drupal, SilverStripe, or others. Each of these allow for Themes or Styles and so you can easily code up a way to switch styles with code such as php, asp.net, ruby, or any programming language.  Unfortunately,

Category: HTML & CSS  |  Comment

WPF Localization at run-time

January 27, 2012, 1:44 pm

I needed a better WPF Localization solution and I came up with one and posted it over on my WPF blog.

I would love some feed back, so if you are interested, check it out.

How to change language at run-time in WPF with loadable Resource Dictionaries and DynamicResource Binding (Example 1)

Category: Localization, WPF  |  Comment

C# Dictionary

January 24, 2012, 7:47 pm

In C# there is an object called Dictionary<TKey, TValue> that can be used to store data.  The Dictionary<TKey, TValue> is essentially a collection of KeyValuePair<TKey, TValue> objects.

C# Dictionary Example 1 – A word dictionary

In this example, we create a simple dictionary with a few words and there definitions and show you how they are accessed.

using System;
using System.Collections.Generic;
using System.Linq;

namespace DictionaryExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<String, String> words = new Dictionary<string, string>();
            words.Add("Hello", "An expression or gesture of greeting.");
            words.Add("Goodbye", "A concluding remark or gesture at parting.");
            words.Add("Computer", "A programmable usually electronic device that can store, retrieve, and process data.");
            words.Add("Friend", "One attached to another by affection or esteem");

            Console.WriteLine("Word - Definition");
            Console.WriteLine("===================================================");
            foreach (KeyValuePair<string, string> pair in words)
            {
                Console.WriteLine(string.Format("{0} - {1}", pair.Key, pair.Value));
            }
        }
    }
}

Accessing values in a C# Dictionary

You can access the value using the key. In the case of our word dictionary, the word is the key and the definition is the value.

While you could access the value as follows, there is a problem with the below method.

    private string GetDefinition(String inWord, Dictionary<String, String> inDictionary)
    {
        return inDictionary[inWord];
    }

Do you know what the problem is?  Right, it doesn’t handle a missing value.  If the value doesn’t exist, this will throw a KeyNotFoundException.

Handling a missing value in a C# Dictionary

There are two ways to prevent the KeyNotFoundException.

Method 1 – Use TryGetValue()

TryGetValue() return a bool It takes in the Key and also an out reference. It populates the out reference. Here is an example.

    private string GetDefinition(String inWord, Dictionary<String, String> inDictionary)
    {
        string retVal;
        // String is set to null if the value is not found
        return inDictionary.TryGetValue(inWord, out retVal) ? retVal : ;
    }

I am not a big fan of how the TryGetValue() function was implemented to return a bool However, I understand why it was implemented to return a bool. One might wonder why it returns bool. You may be thinking that TryGetValue() could return a value if found, null otherwise, right? Wrong! Reason 1 – Don’t forget that the value might actually be null. Reason 2 – While this Dictionary used a nullable type, string, another implementation might implement using a type that is not nullable, such as int.

Method 2 – Using ContainsKey()

Alternately you could check if the value exists first using ContainsKey(). Here is an example.

    private string GetDefinition(String inWord, Dictionary<String, String> inDictionary)
    {
        return inDictionary.ContainsKey(inWord) ? inDictionary[inWord] : string.Empty;
    }

I prefer this because to me, it is more readable than the TryGetValue() function, but feel free to make your own opinion.

Looping through a C# Dictionary

Now imagine you wanted to get all the words and their definitions that start with a certain letter. In this case you are creating a Dictionary that is a subset of the full Dictionary. You could do this with a foreach loop. Notice that the object in the foreach loop is a KeyValuePair.

        private Dictionary<String,String> GetWordsAndDefinitionsWhereWordsStartWith(Dictionary<String, String> inDictionary, char inChar)
        {
            Dictionary<String, String> wordsAndDefinitionsWhereWordsStartWithC = new Dictionary<string, string>();
            foreach (KeyValuePair<string, string> pair in inDictionary)
            {
                if (pair.Value.StartsWith(inChar.ToString(), StringComparison.CurrentCultureIgnoreCase))
                    wordsAndDefinitionsWhereWordsStartWithC.Add(pair.Key, pair.Value);
            }
            return wordsAndDefinitionsWhereWordsStartWithC;
        }

You could alternately use LINQ against the C# Dictionary to get the method body to be a single line.

    private Dictionary<String,String> GetWordsAndDefinitionsWhereWordsStartWith(Dictionary<String, String> inDictionary, char inChar)
    {
        return inDictionary.Where(pair => pair.Value.StartsWith(inChar.ToString(), StringComparison.CurrentCultureIgnoreCase)).ToDictionary(pair => pair.Key, pair => pair.Value);
    }

You could just get the words and not the definitions in a List<String> as well.

    private List<String> GetWordstartingWith(Dictionary<String, String> inDictionary, char inChar)
    {
        List<String> wordsStartingWith = new List<String>();
        foreach (KeyValuePair<string, string> pair in inDictionary)
        {
            if (pair.Value.StartsWith(inChar.ToString(), StringComparison.CurrentCultureIgnoreCase))
                wordsStartingWith.Add(pair.Key);
        }
        return wordsStartingWith;
    }

Again, you could use LINQ against the C# Dictionary to make this function one line.

    private List<String> GetWordstartingWith(Dictionary<String, String> inDictionary, char inChar)
    {
        return (from pair in inDictionary where pair.Value.StartsWith(inChar.ToString(), StringComparison.CurrentCultureIgnoreCase) select pair.Key).ToList();
    }

References

Category: C# (C-Sharp)  |  Comment

How to add a corner banner to your web page?

January 23, 2012, 3:12 pm

Today I noticed that a few sites, including WordPress.com have a corner banner on their pages to help alert others to a specific cause (in this case they are against SOPA & PIPA).

And so everyone can add a corner banner to their sites, I am going to post how to do it.

Step 1 – Create the image

There are dozens of ways to create the images and if you can create it yourself, just do so.

Note: While I for this cause WordPress would care if you used their image, I thought it best to make my own if for no other reason than to use my color style.

  1. Using your favorite image editor create a new image.
    Note: I am going to use the free Paint.NET program.
  2. Change the canvase size to be a square. Use a size between 150×150 to 200×200. I went with 175×175.
  3. Make the background transparent.
  4. Draw a line from corner 0,0 to corner 175,175.
    Note: In some applications, holding down shift while drawing your line will guarantee the line is a perfect 45 degree diagonal.
  5. Draw a second line from  60,0 to about 175,115.
    Note: Mine came out to 175,114, which is close enough.
  6. Fill the  area inside the lines as you desire.
    Note: I used a nice soft gradient.
  7.  In a new layer (also transparent), add text in a normal horizontal way.
  8. Rotate only the new layer 45 degrees. (-45.00 degree.)
  9. Show both layers.
  10. Move the text to the appropriate place in the image.
  11. Save as a png or jpg file.
  12. Upload the image to your site.

Here is my image. Feel free to download it and use it.

Stop Censorship

Step 2 – Change your web site code to display the image

  1. Add the following style to your css file. 
    #right-corner {
	position: fixed; /* Make sure you can align it exactly */
	cursor: pointer; /* Change the cursor on mouse over */
	top: 0px; /* Change to 100px to put it under a 100px banner */
	right: 0px; /* Change to 100px to put it left of a 100px right-side bar */
	z-index: 99999; /* make sure it is the top element always */
}

    Note: If you do not have a css file, then go to step two and add this as well in step 2.

    <style>
#right-corner {
	position: fixed; /* Make sure you can align it exactly */
	cursor: pointer; /* Change the cursor on mouse over */
	top: 0px; /* Change to 100px to put it under a 100px banner */
	right: 0px; /* Change to 100px to put it left of a 100px right-side bar */
	z-index: 99999; /* make sure it is the top element always */
}
</style>
  2. Open whatever html or script file that create the top part of your web site.
    Note: Often it is a top.htm, header.htm, or something similar.
  3. Find your <body> tag and add a link to http://americancensorship.org anywhere inside the <body> tag.
  4. For the tag, set the “id” to the css id called right-corner.
  5. Put your image inside the link.The code should look as follows: 
    <a id="right-corner" href="http://americancensorship.org/" target="_blank">
	<img src="/wp-content/uploads/2012/01/Stop-Censorship.png" alt="Stop Censorship">
</a>
  6. Save your changes.
  7. Refresh your page.

You now have a corner banner image on your page.

While I want to add a corner banner to my site and state that I am against SOPA and PIPA as well, here is my disclaimer:

I haven’t fully read the SOPA & PIPA document, so I am against it based on hearsay…but it is reliable hearsay. Also there may be statement in the document that I am for. Instead of telling you what I am against in the SOPA & PIPA document, it is easier just to write my thoughts.

  1. The U.S. Government should not censor the internet for the public in any way.
  2. The government should in no way tamper with or hinder the freedom of speech on the internet
  3. Certain organizations, such as parents at home, schools, or a business (except ISPs) may censor/filter the internet for their specific internet connection. (And hence anyone only using their internet access is also censored).
  4. The Government may censor the internet in locations they naturally control, such as in Government Buildings, military facilities, or government-paid-for schools.
  5. An ISP may provide an optional censorship/filtering service so long as it is not applied by default or when not specifically requested. If the ISPs whole business plan is based on the idea of a safe internet for families, such as MStar, then defaulting to enabling certain censorship/filtering service is allowed.
  6. Internet Registrars may enforce rules that make filtering easier, like having all porn sites end in .xxx or all gambling sites end in .gmb so they can easily be filtered, especially in homes, schools, and some work places.  But enforcement should be done by agreement of internet registrars and not really by the U.S. Government.
  7. The government should pursue theft of intellectual property the same on the internet as is does with theft of intellectual property off the internet with one stipulation: Only the most minimal part of a site should altered. For example, if a site posts a copyrighted movie, only the movie itself should be removed, every other part of the site should remain, including a broken link to the movie.

If the bill could be written with those few sentences, it would pass easily and I don’t think anyone would care.

Category: HTML & CSS  |  Comment

Why a developer’s next computer should be an Apple

January 11, 2012, 10:20 am

It is not because OS X is better

Let me start by saying that I do not fall into the “my os is better than yours” mantra. I like to talk about the right tool for the job.

  • For a home user, Windows 7 and OS X still beat Linux (yes, even Ubuntu).
  • For a geeky home user, Ubuntu or any other OS might be more fun.
  • If you want to give away your old computer but not give away your Operating System license, put Ubuntu or PC-BSD on it.
  • Similarly if you get a free computer without an OS and you don’t want to buy one, put Ubuntu or PC-BSD on it.
  • For most businesses, Windows 7 is the better solution for a lot of reasons, many of which are IT related and not even user related.
  • For an artist, OS X is the right choice. Sure Windows has caught up in graphic tools, but not in peer knowledge.
  • For a Web Server, I would never run windows or MAC, I would recommend BSD or Linux.
  • For a NAS server, I would use FreeNAS.
  • For an enterprise to sell a secure appliance I would recommend a BSD derivative.

Those are just a generalizations based on the idea of using the right tool for the job. In every case others have different opinions and there are always exceptions. The appropriate thought is that you should use the right tool for the job.
So if you are a developer, what is the right tool for the job? Here is my new generalization.

  • For a Developer, I now recommend Apple hardware.

Notice I said Apple Hardware, but I didn’t say that I recommend OS X. Run whatever OS you need.

It is not because Apple Hardware is better

Also, this has nothing to do with saying that Apple hardware is better. Dell, HP, Lenovo, Sony, and others all make some great hardware for running whatever OS you can run.

Many argue that Alienware makes the best hardware, not any of the above vendors.  It is not about the best hardware.  So if it was a hardware issue, I would be recommending Alienware. But it is not.

Let me repeat.

  • For a Developer, I now recommend Macintosh hardware.

Notice, I qualified this by saying For a developer. I am not telling everybody to get Apple hardware.

Answer #1: It is simply a licensing issue

Legally you cannot run OS X on any hardware other than Apple hardware (an no Hacintosh is not legal) . Since iOS development realistically can only happen on OS X, you cannot legally run iOS on hardware designed for windows either.

Answer #2 – The cross-platform world

You need every Operating System today.

Lets talk about where development has taken us.  We have gone from not really cross-platform (Windows only and sometimes support Macintosh too), to having to be able to code on Windows, Windows Phone 7, OS X, iOS, Android, and possibly Linux and Unix as well.

Lets list these in a table and you will see why buying an Apple Laptop frees you to develop on all those platforms.

Operating System Apple Hardware Windows Hardware
Windows Run OS and Develop for it Run OS and Develop for it
BSD/Linux Run OS and Develop for it Run OS and Develop for it
Android Emulate OS and Develop for it Emulate OS and Develop for it
OS X Run OS and Develop for it Not supported*
iOS Emulate OS and Develop for it Not supported*

* While it can be done it is illegal and breaks license agreements.

Only Apple hardware allows you to install on all the popular Operating Systems that exist today.

So Apple has put themselves in an interesting position where cross-platform development on all popular operating systems can only occur on Apple hardware. It is this position that has me making this statement.

  • For a Developer, I now recommend Macintosh hardware.

As for the operating system that I recommend, you probably have guessed from this post my recommendation: If you are a developer, run them all.

Category: Development, Operating Systems  |  2 Comments

How to compile WinNFSd with Visual Studio?

December 29, 2011, 4:31 pm

Recently I needed an NFS server on Windows, preferably written in C++. A long time ago I had used WinNFSd and sure enough the project still exists on Sourceforge, though unfortunately it hasn’t been updated since 2005.

However, I found that someone had updated it here: https://github.com/noodle1983/winnfsd-nd

So the big question, how do you compile this on windows with Visual Studio?

Step 1 – Download and extract the WinNFSd source

  1. Go to https://sourceforge.net/projects/winnfsd and download the source.
    Note: You can alternately download the git hub source as it has an update you might like:
    https://github.com/noodle1983/winnfsd-nd
  2. Click the Zip button at the top of the page to download the source as a zip.
    Note: Alternately if you have git working already you can clone this repo.
  3. Extract the zip file to a directory.  Remember where you extracted it as we will copy the source files later.

Step 2 – Create a new Visual Studio solution

  1. In Visual Studio, go to File | New | Project.
  2. Select Other Languages | Visual C++ | Empty Project.
    Note: Depending on your Visual Studio configuration you may Visual C++ in a different place.
  3. Name the solution WinNFSd.
  4. Click Ok.

Step 3 – Add the WinNFSd files to your solution

  1. In Visual Studio, right-click on your Project and click Open Folder in Windows Explorer.
  2. Create a new folder to hold your source code.
    Note: I simply named my folder src.
  3. Copy the source you extracted in Step 1 into the src directory.
  4. Highlight all the files in the src directory.
  5. Drag the files into Visual Studio and drop them on your project.
Note: If you try to build now, you will get 22 errors in debug mode and maybe 17 in release mode.

Step 4 – Configure the project properties

  1. In Visual Studio, right-click on your project and choose Properties.
    Note: The Configuration should say Active(Debug) currently.
  2. Go to Configuration Properties | Linker | Input.
  3. Add ws2_32.lib to the Additional Dependencies.
  4. Change the Configuration to Release and add ws2_32.lib for release as well.

Step 5 – Handle the Visual Studio C++ Runtime

If you were to compile now, and try to run your project on a different machine (not the one running Visual Studio) you would likely get an error due to a missing dll.  Here is the error you will likely receive.

The program can’t start because MSVCR100.dll is missing from your computer. Try reinstalling the program to fix this problem.

I am not going to explain the solution again here, because it is all documented here:
Avoiding the MSVCR100.dll or MSVCR100D.dll is missing error

Choose the best of the three solutions for you from the link above.

Note: For this single file exe, I prefer the statically linked option.

Step 6 – Build WinNFSd

  1. You should now be able to click Build | Build Solution and it should build.

You should be able to test both debug and release.

Note: I received 37 warnings, which would be nice to resolve, but I wouldn’t worry too much about them.

 

Tags:
Category: C++, Open Source  |  Comment

LANDesk Support Tools – Android Edition (Demo)

December 14, 2011, 5:20 pm

This is my first real project written for Android. Yes, I wrote it in C# using Mono for Android.

Category: Android, C# (C-Sharp), Tablets  |  Comment

How to connect to the LANDesk MBSDK using C#?

December 10, 2011, 7:12 pm

This article is to demonstrate to LANDesk admins how to connect to the LANDesk MBSDK with C#.

Prerequisites

LANDesk

  1. A LANDesk Core Server accessible via the network.
  2. Credentials to connect to the LANDesk Core Server.

Basically if you can hit the MBSDK with a browser and login, you are good to go.

http://CoreServer/mbsdkservice/msgsdk.asmx

Visual Studio

  1. It is assumed that you have Visual Studio Professional installed

Step 1 – Create a Visual Studio Project

  1. In Visual Studio, Go to File | New | Project.
  2. Select that project type.
    Note: For this example I chose Console Application.
  3. Give the Project a name.
    Note: I named my project TalkToMBSDK.
  4. Click OK.
    Note: I went ahead and left my client application configured for .NET 4 even though I know the server currently is .NET 3.5 Sp1.

Step 2 – Add a Web Reference to the MBSDK

  1.  In you new Visual Studio project, right-click on the project and click Add Service Reference.
    Note: We actually need a Web  Reference but this is how we get there.
  2. Click Advanced on the bottom left.
  3. Click on Add Web Reference, also on the bottom left.
  4. Enter the URL to the MBSDK on your Core Server: http://CoreServer/mbsdkservice/msgsdk.asmx
  5. Change the Web Reference Name (on the right) to mbsdk.
    Note: You can name it whatever you want, but because there is an object called MBSDK (all uppercase), I chose to make the namespace mbsdk (all lowercase).
  6. Click Add Reference.

Step 3 – Test using the LANDesk SDK

  1. In the Program.cs add the following code.  You next steps are in the code comments.
using System.Net;
using TalkToMBSDK.mbsdk;

namespace TalkToMBSDK
{
    class Program
    {
        static void Main(string[] args)
        {
            // Step 1 - You need to use your credentials
            string user = "SomeUser";
            string password = "SomePassword";
            string domain = "SomeDomain.tld";

            // Step 2 - Configure a CredentialCache object with the URL and your creds
            string uri = "http://CoreServer/MBSDKService/MsgSDK.asmx";
            CredentialCache MyCredentialCache = new System.Net.CredentialCache();
            MyCredentialCache.Add(new System.Uri(uri), "NTLM", new NetworkCredential(user, password, domain));

            // Step 3 - Create an MBSDK object and set its CredentialCache object to the one you just created
            MBSDK sdk = new MBSDK();
            sdk.Credentials = MyCredentialCache;

            // Step 4 - Go ahead an call methods from the MBSDK
            // Note: If you get 401 unathorized, are you a LANDesk Administrator?
            string[] configs = sdk.GetClientConfigurations();
            DeviceList list = sdk.ListMachines("");
            string who = sdk.WhoAmI();
        }
    }
}

Have fun LANDesk Admins.

Category: C# (C-Sharp), LANDesk  |  Comment

A test of encapsulation security in C#

December 10, 2011, 2:49 pm

I am taking a Computer Security course as part of my Masters of Computer Science and a specific question inspired the idea of testing the security of Encapsulation in C#.

I was curious, if exposing an object that is not exposed would be as simple as changing a single bit with a hex editor.

So I created two projects:

A dll that doesn’t expose two objects.

namespace EncapsulatedLibrary
{
    class Class1
    {
        public int i = 27;
    }

    class Class2
    {
        public int i = 29;
    }
}

An executable that references the dll and tries to use objects that are not exposed.

using EncapsulatedLibrary;

namespace TestLink
{
    class TestLinkProgram
    {
        static void Main(string[] args)
        {
            Class1 c1 = new Class1();
            int val1 = c1.i;
            Class2 c2 = new Class2();
            int val2 = c2.i;
        }
    }
}

Ok, now if you compile these, the dll compiles fine, but the exe fails to build.

Now try to use a hex editor to change the compiled version of the dll to expose these objects.

So real quick, I copied the dll and then changed the classes to public and recompiled. Then using a hex editor, HxD, I compared the two files.

Sure enough, on row 00000390, the 13th octet, I changed it from 00 to 01 and now Class1 is public.
On the very next row, 000003A0, the 10th octet, I changed it from 00 to 01 and now Class2 is public.

With this simple hack, I have made two objects public that should not be public. While in this example, this is not malicious, there are ways this could be used maliciously. Imagine if you had functionality limitations on users and they should not have rights to do certain processes but due to exposing a library, they can do these processes.

So now the next question left to be answered is this: What tools exist as controls to prevent such an attack?

Category: C# (C-Sharp), Security  |  1 Comment

How to find the duplicate in an array using Big O of N?

December 9, 2011, 11:33 am

Question

Write an algorithm that finds the duplicate in an array using Big O of N, not Big O of N^2.

Information

The array is an integer array and has a MAX_VALUE items (lets just use 1000 as an example). All integers are between 0 and MAX_VALUE (pretend the input is limited to values between 0 and MAX_VALUE). There is only one duplicate and you are not sure where it is. What is the most efficient way to find it.

    int[] i = new int[1000];

There is one duplicate and it is the worst case duplicate.  You can simulate a worst case duplicate as follows:

    for (int i = 0; i < 999; i++)
    {
        array[i] = i+1;
    }
    array[999] = 999;

So the duplicates are the second to last and the last.

Answer

This is one possible answer that assumes the values are between 0 and MAX_VALUE.

    /// <summary>
    /// Efficient because it has a Big O of n.
    /// </summary>
    public int FindDuplcate(int[] inArray)
    {
        bool[] tmpArray = new bool[1000];
        for (int i = 0; i < inArray.Length; i++)
        {
            if (tmpArray[inArray[i]] == true)
                return i;
            tmpArray[inArray[i]] = true;
        }
        return -1;
    }

Incorrect answers

Here is a little test app with two incorrect answers and two possible correct answer. Feel free to comment with your answers.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace FindDuplicateInArray
{
    class Program
    {
        const int MAX_VALUE = 1000;        

        static void Main(string[] args)
        {
            // Worst case
            int[] array = new int[MAX_VALUE];
            for (int i = 0; i < MAX_VALUE - 1; i++)
            {
                array[i] = i + 1;
            }
            array[MAX_VALUE - 1] = MAX_VALUE - 1;

            // Incorrect answer: Big O of N^2
            //IFindADuplicateInArrays dupFinder1 = new BruteForceDupFinder();
            //int dup = dupFinder1.FindDuplcate(array);

            // Incorrect answer: Big O of N^2
            //IFindADuplicateInArrays dupFinder2 = new LessBruteForceDupFinder();
            //int dup = dupFinder2.FindDuplcate(array);

            // Possible correct answer: Big O of N but with a limitation
            //IFindADuplicateInArrays dupFinder3 = new EfficientDupFinderWithLimitation();
            //int dup = dupFinder3.FindDuplcate(array);

            // Possbile correct answer: Big O of N
            IFindADuplicateInArrays dupFinder3 = new EfficientDupFinder();
            int dup = dupFinder3.FindDuplcate(array);

            Console.WriteLine(dup);
        }

        public interface IFindADuplicateInArrays
        {
            int FindDuplcate(int[] inArray);
        }

        /// <summary>
        /// Incorrect Answer: This is simple N*N alogithm. Big 0 = N^2
        /// </summary>
        public class BruteForceDupFinder : IFindADuplicateInArrays
        {
            #region IFindADuplicateInArrays Members

            public int FindDuplcate(int[] inArray)
            {
                for (int i = 0; i < inArray.Length; i++)
                {
                    for (int j = 0; j < inArray.Length; j++)
                    {
                        if (i != j && inArray[i] == inArray[j])
                            return j;
                    }
                }
                return -1;
            }

            #endregion
        }

        /// <summary>
        /// Incorrect Answer: This is N(N-1)/2 which is N*N/2-n/2 so remove the constants N^2-N.
        /// When there is N^2-N you can keep the N that grows fastest: Big O = N2
        /// But the original alrogithm is less N^2 than just N^2.
        /// </summary>
        public class LessBruteForceDupFinder : IFindADuplicateInArrays
        {
            #region IFindADuplicateInArrays Members

            public int FindDuplcate(int[] inArray)
            {
                for (int i = 0; i < inArray.Length; i++)
                {
                    for (int j = i + 1; j < inArray.Length; j++)
                    {
                        if (inArray[i] == inArray[j])
                            return j;
                    }
                }
                return -1;
            }

            #endregion
        }

        /// <summary>
        /// Possible Answer: Efficient because it has a Big O of n.
        /// Limitation: If an item in the array is greater than the MAX_VALUE,
        ///             an ArrayIndexOutOfBoundsException occurs.
        /// </summary>
        public class EfficientDupFinderWithLimitation : IFindADuplicateInArrays
        {
            #region IFindADuplicateInArrays Members

            public int FindDuplcate(int[] inArray)
            {
                bool[] tmpArray = new bool[1000];
                for (int i = 0; i < inArray.Length; i++)
                {
                    if (tmpArray[inArray[i]] == true)
                        return i;
                    tmpArray[inArray[i]] = true;
                }
                return -1;
            }

            #endregion
        }

        /// <summary>
        /// Possible Answer: Efficient because it has a Big O of n.
        /// </summary>
        public class EfficientDupFinder : IFindADuplicateInArrays
        {
            #region IFindADuplicateInArrays Members
            public int FindDuplcate(int[] inArray)
            {
                Dictionary<int, bool> table = new Dictionary<int, bool>();
                for (int i = 0; i < inArray.Length; i++)
                {
                    if (table.Keys.Contains(inArray[i]))
                        return i;
                    table.Add(inArray[i], true);
                }
                return -1;
            }
            #endregion
        }
    }
}

Run this through Visual Studio’s Performance Analysis tool once for each answer (comment and uncomment). To really see the difference, change MAX_VALUE to 1 million.

Tags:
Category: C# (C-Sharp)  |  5 Comments
« Previous Entries