.NET
“The missing number” programming exercise
This is another entry in the brain teaser / programming exercise / interview question collection. It goes like this:
Imagine a list of consecutive numbers. The list is, however, unsorted and one number is missing. Write a function that finds which number is missing with the constraint that you may only allocate O(1) memory (i.e. the amount of memory you use cannot vary with the size of the list).
The fact that the list is unsorted means that you cannot step through in a pairwise fashion and compare each element of the list to the next to see if they are consecutive. Sure, we could sort the array first but the fact that you cannot allocate memory according to the size of the array means that you cannot create a helper array in the solution and certain sorting algorithms are ruled out. An in-place sorting algorithm such as quicksort would do it, but I don’t think that sorting the array is the best way to go.
What if we sum the list? We’re talking about a sequence of integers, after all. It turns out that there is a linear formula for calculating the sum of a sequence of consecutive integers: sum(1..n) = n(n+1) / 2.
This means that you can work out what the sum of the input list should be; all we must do it actually sum the list and the difference between the two will be the missing number. Our implementation then looks like this:
let findMissing (list : int array) =
let n = list.Length + 1
let expectedSum = n * (n + 1) / 2
let actualSum = Seq.sum list
expectedSum - actualSum
Note the let n = list.Length + 1. We have to add one to the length of the list to get the max element in the list because one element is missing. After that it’s pretty simple!
Exceptions and error logging
At my current work I see an awful lot of code that looks like this:
public class ServiceA : IServiceA
{
private readonly ILogger _logger;
public ServiceA(ILogger logger)
{
_logger = logger;
}
public void DoIt()
{
try
{
// Do something...
}
catch(Exception e)
{
_logger.LogError(e);
throw;
}
}
}
At first blush this looks reasonable: it has constructor-based dependency injection, an abstraction, error logging… What could my issue be?
Tabs or Spaces?
Tabs are blatantly the correct answer.
Tabs separate code content from presentation. Indentation style becomes entirely personal, and each dev can adjust to their own tastes without affecting anyone else. Imagine that I have my editor set to tabs as four spaces. Then, I open a file from another developer who has tabs set as two spaces. Now, in order to write into his file, I have to go into my editor’s options and change my settings to reflect his convention otherwise the code that I’ve written will not match the code that he’s written. Bad times.
A functional Fizzbuzz
After reading Scott Wlashin’s post (http://fsharpforfunandprofit.com/posts/railway-oriented-programming-carbonated/) on writing FizzBuzz in a more functional style and with the ability to have more rules (other than 3 => fizz, 5 => buzz, etc) I decided to give it a go myself. This represents the most idiomatic F# I could come up with, and I think it reads pretty well. It uses partial application, list operations, shorthand match-expressions-as-functions and option types.
let carbonate rules i =
rules
|> List.choose (fun (divisor, replacement) ->
if i % divisor = 0 then Some replacement else None)
|> function [] -> string i | list -> String.concat "" list
let carbonateAll rules = List.map (carbonate rules)
let fizzbuzzbazz = carbonateAll [3, "fizz"; 5, "buzz"; 7, "bazz"]
fizzbuzzbazz [100..110] |> printfn "%A"
See if you can follow how it works.
Testing the queries in your data access layer
When it comes to writing automated tests I have, in the past, tended to ignore the data access layer. Do you really need to test your queries? As long as the code was loosely coupled and I could test everything else, I was happy. After talking at work I was convinced that, in some cases, it might be worth testing your queries themselves in order to check that they’re returning the data that they should be.
This provided a dilemma, because I will always try to avoid writing integration/database tests if I can help it, but how do you test queries without a database? A possible answer is as follows, taken from my post on StackOverflow:
After some deliberation, my colleague and I came up with a way to separate the query from the persistence layer. I threw together a quick example below:
Automatically finding missing and duplicate files in CSProj (Revisited)
As promised in I have come back to the problem of detecting errors in Visual Studio project files. I have updated the script to now report CS files that are on disk that do not appear in the list of included (and compiled) files in the Project. This has a few limitations, including that it only works with CS files (although the script could be easily amended to look for any file extension you like).
Var: Possibly the most contraversial language feature ever?
I’ve been prompted to write this post after it cropped up in my office recently, and I was reminded of a job interview I had a couple of years ago. I’ve also seen some discussions online, and wow, some people hate var. I mean really, really hate it. I even saw one guy in a post saying that if he saw a job applicant using var in an interview he would instantly refuse to hire the guy.
Now, I understand the points that the opponents of var are making, but I don’t agree. I accept that in the case of:
var data = GetData();
we can’t tell what type “data” is, but this is one of the few examples where this is the case. You might also argue that the method “GetData” has been atrociously named (okay, no arguing, it has been atrociously named), but following most programming rules I’d expect that method to return an object of type “Data”. In this example that’s probably not the case, but it does highlight my point, that this:
The Eight Queens problem
My colleague recently introduced me to the eight queens problem (you can read more about it over at Wikipedia). In summary, you have to be able to place eight queens down on a chess board without any of them attacking any other.
This sounds easy at first, but I found that taking a few guesses on a piece of paper yielded no results. Rather than simply solving the problem, I decided it would be more fun to write a program that would find all the solutions for me. I’d been looking for a nice little programming problem to teach myself F# for a while, so I thought I’d give this a go. Well, after a few false starts and a lot of F# Googling, here’s my solution:
Validating .NET MVC 4 anti forgery tokens in ajax requests
CSRF (Cross-Site Request Forgery) is an attack against a website “whereby unauthorized commands are transmitted from a user that the website trusts.” [Wikipedia]. Protection against this attack is essential for any modern web application.
In the case of .NET MVC, Microsoft have implemented an easy-to-use protection method against CSRF. There’s an attribute in the MVC framework that you can put on your controller actions: ValidateAntiForgeryToken. This works well, but it has a few disadvantages:
-
You must manually decorate all your post actions with the attribute.
It’s easy to forget to do this, so it’s preferable to decorate your entire controller with the attribute (or better yet, a base controller that your whole application uses). Unfortunately, this doesn’t work with the standard ValidateAntiForgeryToken attribute, as this causes all your GET actions to be validated as well (and they will always blow up, as the client doesn’t send any form data with a GET request). -
It doesn’t work with ajax posts.
The standard attribute doesn’t work with ajax because it inspects the Request.Form collection when looking for the token field. When you’re making ajax posts this form is always empty. This is the reason I originally started looking for alternative implementations of the anti forgery token validation.
EntityFramework 6 and async database queries
Microsoft is going all-out on .NET 4.5 and C#5’s async feature. Windows RT (the .NET libraries for interfacing with the windows runtime) makes heavy use of task-based asynchrony in the API, and Microsoft’s rule of thumb to all .NET developers is to make any method that can reasonably be expected to take more than 50ms should be asynchronous. This includes web service requests, file read and save operations, and more.
Given the examples in the previous paragraph, most people will instantly think “Well, what about databases?” (as I did). Indeed, so did Microsoft, and they’ve got us covered. Entity Framework 6.0 (currently in alpha state at time of writing) has been updated to support asynchronous queries. What does this look like? Currently there are five methods that make use of asyncrony – SaveChangesAsync() and ExecuteSqlCommandAsync() for non-queries, and FindAsync(), SingleAsync() and ToListAsync() extension methods for IEnumerable.
I’m looking forward to testing this code out to see how it runs. So far I haven’t used async in production code, but from the work I’ve done on my own personal projects, I can say that I’m very impressed with how well .NET async works as well as how easy it is to use.
- ← Previous
- 1
- 2
- 3
- Next →
Richiban 