Overroot Blog

Following are some of the interview questions for the post of Software Engineer – New Grad

• Write a function to return the most repeated character in the string
• How would you find most repeated word in a document?
• How would you find most repeated word in a document that is too big to fit in the memory?
• Add multi threading to the solution of previous problem
• Given a document, how would you identify which language this document belongs to?
• How would you scale the solution of the previous problem? What will be the bottlenecks?

Natural Sorting is the sort order that is used by Windows Explorer to sort names of files.
If we have strings ["a11", "a2", "a1"] then Array.Sort on strings would return us ["a1", "a11", "a2"] however natural sort requires the order to be ["a1", "a2", "a11"].

Jeff Atwood suggests on his blog post that it would require 40 lines of C# code.
Ian Griffith proved that the claim is not quite correct. Nonetheless his code was 20+ lines too.

Allow me to give you natural sorting in C# using Linq in a single line of code:

var sorted = items.OrderBy(s => Regex.Replace(s, @"[ \d]", String.Empty))
                  .ThenBy(s => Int32.Parse(Regex.Replace(s, @"\D", String.Empty) + "0"));

To understand why this works, is left as an exercise for you dear reader :)

And by the way, in Ian’s code the Compare method can be reduced to as under:

 public int Compare(IEnumerable<T> x, IEnumerable<T> y)
{
            return x.Zip(y, (a, b) => comp.Compare(a, b))
                    .FirstOrDefault(c => c != 0);
}

Following are some of the questions that I’ve been asked in interview for the position of Software Development Engineer

• If you had limited memory and you had to sort large no. of items such that all of them don’t fit in memory, how would you sort them? Write algorithm. What will be its complexity?
• Write a function that calculates Fibonacci number.
• Write an algorithm to shuffle a deck of cards. What will be its complexity?
• Rate yourself from 1-10 in C#. Justify the number. What do you need to do to improve this number?
• Describe the algorithm that generates schedule of interview of given list of candidates that are only available at certain timeslots. Each candidate has to be interviewed 3 times by 3 different interviewers. We also have limited no. of halls to conduct the interview. There should be no collisions/clashes between two interviews. Finally write a function in C# that validates that a certain schedule is valid (also model the schedule).
• If you’re maintaining a high traffic website and all of a sudden the customers start complaining about performance of the website, how would you find out and fix the issue?
• What project are you currently working on? How big is the team?
• Model an elevator simulation. How would the scheduling work? What if there are multiple elevators in the building, how would scheduling be done?
• You’re given an array of integers and you have to find out all pairs of numbers that sum up to 10.

Today I was bored so I decided to write code to generate permutations with LINQ.
According to the article at mathsisfun there are two types of permutations

1) With repetitions

2) Without repetitions

The code for generating permutations with repetitions can be as follows

        static IEnumerable<string> Permutations(int n, params char[] chars)
        {
            if (n > 1)
                return from a in chars
                       from b in Permutations(n-1, chars)
                       select a+b;
            else
                return chars.Select(c=>c.ToString());
        }

The code for generating permutations without repetitions can be as follows

        static IEnumerable<string> Permutations(int n, params char[] chars)
        {
            if (n > chars.Length)
                throw new ArgumentException("chars can not be less than n", "chars");

            if (n > 1)
                return from a in chars
                       from b in Permutations(n-1, chars.Where(c=>c!=a).ToArray())
                       select a+b;
            else
                return chars.Select(c=>c.ToString());
        }

Note the check on chars length and n in the second version. This is necessary because you cant generate permutations of length 10 without repetitions using only 4 chars.

That permutation lock picture in the article reminds me of a object oriented hit counter I wrote (which is maybe inappropriately named ‘mechanical clock’).

The code for hit counter is as follows

    class Clock<T>
    {
        Ring<T> firstRing;
        List<Ring<T>> rings = new List<Ring<T>>();

        public Clock(int length, params T[] digits)
        {
            if (digits.Length == 0)
                throw new ArgumentException("You must provide one or more digits", "digits");

            IVisitable<T> left = new NullVisitable<T>();
            for (int i = 0; i < length; i++)
            {
                var nums = new Digit<T>[digits.Length];
                for (int j = 0; j < nums.Length; j++)
                    nums[j] = new Digit<T>(digits[j]);
                var ring = new Ring<T>(nums);
                ring.Left = left;
                left = ring;
                rings.Add(ring);
            }
            this.firstRing = rings.Last();
        }

        public IEnumerable<T> GetValue()
        {
            for (int i = 0; i < rings.Count; i++)
                yield return rings[i].Value;
        }

        public void Tick()
        {
            firstRing.Visit();
        }
    }

Every time a clock ticks or a hit occurs on a hit counter, the right most ring moves by one step.
When the ring reaches its last digit, it turns the ring on its left by one step (just like a clock’s needle work).

    class Ring<T> : IVisitable<T>
    {
        IList<IVisitable<T>> digits;
        int currentNumber;

        public Ring(params IVisitable<T>[] digits)
        {
            this.digits = digits.ToList();
        }

        public T Value
        {
            get { return digits[currentNumber].Value; }
        }

        public IVisitable<T> Left
        {
            get { return digits[0].Left; }
            set { digits[0].Left = value; }
        }

        public void Visit()
        {
            currentNumber = (currentNumber + 1) % digits.Count;
            digits[currentNumber].Visit();
        }
    }

Ring as seen on a hit counter/car mileage tracker/permutation lock, is a set of digits

    class Digit<T> : IVisitable<T>
    {
        public T Value { get; set; }
        public IVisitable<T> Left { get; set; }

        public Digit(T value)
        {
            Value = value;
            Left = new NullVisitable<T>();
        }

        public void Visit()
        {
            Left.Visit();
        }
    }

IVisitable interface represents the behavior of being able to change a value, maybe it should have been named ITurnable that has Turn() instead of visit.
Null Visitable class represents a static value

    class NullVisitable<T> : IVisitable<T>
    {
        public T Value { get; private set; }
        public IVisitable<T> Left { get; set; }
        public void Visit() { }
    }

This is how you would use the clock

               var clock = new Clock(5, 0, 1);
                for (int i = 0; i < 5; i++)
                {
                    Console.WriteLine(clock.GetValue().AsString());
                    clock.Tick();
                }

AsString is an extension method which is as follows

       public static string AsString(this IEnumerable<T> items)
        {
            string output = items.Aggregate(new StringBuilder(), (a, x) => a.Append(x)).ToString();
            return output;
        }

The net effect of calling tick repeatedly on the clock is of generating permutations with repetitions. This can be modified to generate permutations without repetitions which is left as an exercise for you.

There have been updates in the client since I last blogged about the SO client. Since the first version received some attention I thought there might be people who are just interested in downloading the client instead of building one so I quickly added some features, cleaned it up and upload the binaries on http://stackoverflowclient.codeplex.com

In order to turn that sample into a working client I had to add another class called StackOverflowNotifier.

    class StackOverflowNotifier
    {
        event EventHandler LoggedIn;
        int PollInterval { get; set; }
        event EventHandler QuestionsReceived;
        event EventHandler RequestLogin;
        void Start();
        void Stop();
    }

As you can see the class polls the stackoverflow active questions page periodically and downloads all the questions. The Start method, starts the timer that raises its ‘Tick’ event after regular intervals.
It was important to use the System.Windows.Forms.Timer timer because it raises the tick events on the UI thread and you can not interact with the WebBrowser control from a non UI thread.

The default polling interval is 2 minute as of now and when the questions are downloaded you are notified in system tray via a popup only if there are any questions received with ‘Interesting’ attribute set to true.
Though the latest list of questions is updated in the list view so you can click on the tray icon to view the current list of questions.

I found a very nice Tray notification control for WPF at http://www.hardcodet.net/projects/wpf-notifyicon which I used in the project. I used the FancyBaloon user control shipped in its samples and modified it so that it can be bound to a collection view so I can put the next/previous buttons and allow user to navigate through questions from the same popup instead of showing 10 different popups.

The above mentioned minor re-factoring helped clean up the code in the MainWindow. I also fixed a couple of bugs and added a trace listener that shows popup on the tray if the client barfs on exception while parsing the html.

Thats pretty much it. Go get your copy of the latest version and start answering some questions on SO

Introduction

If you’ve discovered this blog post via search engine most likely you want to build a StackOverflow desktop client. Someone once said ‘talk is cheap, show me the code’ so you can go straight to http://stackoverflowclient.codeplex.com/ and download the code sample that logs you into StackOverflow site and shows you all the latest posts in a WPF application.

StackOverflow client as we know it is a popular site for asking programming related questions. One of the great things about this site is that it has a reputation system in which you get upvoted for the right answers and downvoted for the wrong answers. What this means is that people with higher reputation are most likely very smart people like Jon Skeet and Marc Gravell. However if you have low reputation this could also mean that you do not have time to visit the site more often and answer more questions. This is exactly why you would need a desktop client for SO. Without boring you with further introductory information lets get straight to the code.

Design

There are many ways in which you can build a client for SO

1. Monitor the RSS feeds and show desktop popups (Easiest but not very useful)
2. Log into the site using WebClient class and maintain the sessions (Harder way and can be easily detected and blocked unless done right)
3. Put a Web Browser control on your form and simulate navigation on it, read and parse the html to extract information (Medium difficulty and can easily break with css/markup changes but they are not very frequent.)

I chose the 3rd way of building the client.
So essential ingredients for writing a client in WPF/C# for SO using the 3rd methods are as follows:

• WPF Window / Form
• Hidden WindowsFormHost control on the WPF window
• HtmlAgilityPack
• Lots of patience

A question on StackOverflow can be represented by a class with following definition

class Question
{
public Uri Url { get; set; }
public string Title { get; set; }
public bool Interesting { get; set; }
public int Votes { get; set; }
public int Answers { get; set; }
public int Views { get; set; }
}

All the information in this class can be easily populated by parsing the home page of the SO site.
The bool interesting property tells if you’ve marked the tag as interesting on your SO profile which highlights the questions for you so you can easily find questions that have the same tags in which you’re interested.

So for parsing the html of the page you will need a component in your code called StackOverflowParser.
I’ll cut the implementation details here and just tell you what services each component provides.
So the Parser currently has two methods

public IEnumerable GetQuestions(string html){}
public bool IsLoggedIn(string html){}

Both the methods take html of a page and return you some information based on the parsed html (using HtmlAgilityPack).

To determine that you’re logged in the IsLoggedIn just checks for a link to logout page in the html “/users/logout”. This link would only appear on a page if you’re logged in.

To get the questions from the home page, the GetQuestions method finds all the divs with id “question-summary”. These divs contain all the questions and information related to them that can be parsed into Question object.

Now that the basic parsing component is ready we need a component that uses this parser and navigates on the site to particular pages that have the relevant html on them.
For this you need a StackOverflowNavigator component. This component currently has following methods:

public void BeginNavigateToHome(Action callback){}
public void BeginGetActiveQuestions(Action> callback){}
public void EnsureLoggedIn(Action action){}

And following events

public event EventHandler RequestLogin = delegate { };
public event EventHandler LoggedIn = delegate { };

BeginNavigateToHome asynchronously navigates the WebBrowser control (which is passed in the constructor) to the Home Page and then executes the action that you’ve passed as callback.

BeginGetActiveQuestions similarly navigates to the home page, parses out the questions and raises the callback that you’ve passed. This method also ensures that you’re logged in using EnsureLoggedIn method because ‘bool interesting’ property of Questions can only be populated if you’re logged in hence it checks if you’re not logged in then it raises the ReqestLogin event. The form on receiving this event should open up a window with the same WebBrowser control on it and make it visible because the navigator will have navigated the page to the login page of SO site.

When the user enters his login/password SO redirect the person to the home page. The navigator constantly monitors the Web Browser control and on each navigation it checks where the user is now logged in and as soon as the user is logged in it raises the LoggedIn event. This is when you can hide the window because user is now logged in and soon your call back of activequestions will be raised because thats one of the pending tasks the navigator had to do.

As soon as you get the callback with questions you can then iterate over the questions and show popups on desktop to notify the user about new questions.

You will obviously need to keep last set of questions to make sure that you don’t show the popups repeatedly.

The code sample on codeplex simply shows the active questions on WPF window in a ListBox control. Since Overroot is going to pursue some other ideas as our upcoming products you are free to take this project from here and build a complete SO client on it.

If you want to contribute to this project contact hasan#overroot$com (Replace # with @ and $ with .)
If you have any trouble understanding the code just leave a comment on this post or send me an email.

Happy coding!

Event logging is a standard way for applications to record important events. Most of the windows applications log their messages, warnings and errors in event log.

Microsoft SharePoint Server, although, has it’s own centralized logging mechanism but it does not log it’s messages to event log. SharePoint LogViewer has a new feature in it’s most recent version (v2.5) to record all or few of the events in window’s event log. You can select the minimum SharePoint severity level from which the logs should be reported to event log.

In SPLV, we used System.Diagnostics.EventLog class to write messages to event log.
Following is the C# code to write log entries to event log.

string source = "Demo Application";
if (!EventLog.SourceExists(source))
EventLog.CreateEventSource(source, "Application");
EventLog.WriteEntry(source, "Message!", EventLogEntryType.Error);

Although, these lines of code work fine, it, however, requires the application to run under the administrator’s account otherwise it may throw a System.Security.SecurityException.

To have this feature working in SPLV, we recommend it’s users to run SPLV under the administrative privileges.

The classic way for modifying page markup at runtime as we know it, is using ASP.NET Response Filter.
People have been using response filter for pulling off different tricks in SharePoint 2007 and it all worked fined until SharePoint 2010 arrived.

SharePoint 2010 uses ASP.NET substitution caching a.k.a Post Cache Substitution which allows it to cache the entire page except for certain portion of the page which continues to remain dynamic. More explanation can be found at http://blah.winsmarts.com/2006/05/26/aspnet-20–post-cache-substitution.aspx

Anyways so the thing is post cache substitution is not compatible with response filters. Here is the official Microsoft kb article http://support.microsoft.com/kb/2014472

The only solution they suggest is to either not use substitution caching or not use response filters. They are mutually exclusive. Well since we can’t change SharePoint the only option left is to not use response filter. So there isn’t really any solution right now. If you figure it out do leave out a comment on this post.

With SharePoint 2010 on the verge of it’s release, it is very important to make your existing SharePoint applications compatible with it. SharePoint LogViewer was initially built for viewing SharePoint 2007 logs but it still could be used to view SharePoint 2010 logs until one of the most powerful feature ‘Live Monitoring’ was introduced.

‘Live Monitoring’ requires you to run SPLV on machines where SharePoint is installed. Earlier it was only able to detect SharePoint 2007 while SharePoint 2010 logs could not be monitored. SPLV detects the SharePoint installation by reading registry keys. To find the SharePoint location on a machine, SPLV used to read a registry entry ‘Location’ under the path
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Shared Tools\Web Server Extensions\12.0.
But this only worked for SharePoint 2007 as SharePoint 2010 has a different registry key
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Shared Tools\Web Server Extensions\14.0.

Now SPLV tries to locate any of the above mentioned two registry keys to detect SharePoint installation which makes it possible to monitor Live logs for both SharePoint 2007 as well as SharePoint 2010.

For those of you who want to deploy their SharePoint 2007 solutions on SharePoint 2010, Andri Yadi’s article SharePoint 2010 Solution Installer may help.

Download the latest version of SPLV from here