Archive for the ‘Uncategorized’ Category.

The Maximum Subarray Problem

I was asked this in an interview sometime ago. The problem simply stated is “Find the contiguous subsequence in a sequence of numbers which has the largest sum.”. The problem was first presented in 1977, and a linear time solution was reported in 1984. Of course I was asked to solve it in the course of a ~30min interview. 🙂

The linear time solution is called Kadane’s Algorithm, you can read about it on wikipedia. The solution first simplifies the problem, by saying we’re only looking for positive sums. That is, we don’t care about the case where the maximum sum is negative. We can then solve the problem relatively easily but finding the maximum run to each position, if the current maximum subarray value every drops below zero we just discard it (because we’d never want to sum from a negative value, it would be better to sum from zero). Here’s a python implementation of this from wikipedia:

1
2
3
4
5
6
def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

If we now want to generalize this to the case where the maximum subarray is negative (i.e. everything in the array is negative). We can do that, rather than saying if we go below zero we want to discard the previous parts of the array, we say if the sub goes below the current value as follows:

1
2
3
4
5
6
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Here’s a solution in C++:

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

int max_subarray(vector<int> &array) {

int max_ending_here = array[0];
int max_so_far = array[0];

for(int n=1;n<array.size();n++) {
if(array[n] < (max_ending_here+array[n])) max_ending_here = max_ending_here+array[n];
else max_ending_here = array[n];
if(max_so_far < max_ending_here) max_so_far = max_ending_here;
}

return max_so_far;
}

int main() {

vector<int> data;

srand(time(NULL));
for(int n=0;n<10;n++) data.push_back((int)(rand()%10)-5);
cout << "data: ";
for(int n=0;n<data.size();n++) cout << data[n] << " ";
cout << endl;

int maxsub = max_subarray(data);

cout << "Max subarray is: " << maxsub << endl;

}

Most common git screwups/questions and solutions

I was looking to learn a bit more about the parts of git I’ve not ventured into yet. What better way that looking the most common ways people screw them up and how to fix the resulting problems! Here’s a short list, compiled from my own experience and issues I’ve come across on the Internet.

I wrote the wrong thing in a commit message

If the commit hasn’t been push you can do the following, which will allow you to edit the message on the most recent commit:

git commit --amend

How can I undo the last commit?

You can use git reset e.g.:

git reset --hard HEAD~1

HEAD~1 means HEAD-1 commit. It should be noted that this is the nuclear option, and any changes you made will be discarded. If you want to keep your changes in the working tree use:

git reset --soft HEAD~1

If you’ve already published your commits, you should use revert. This is create new commits undoing the last change:

git revert HEAD~1..HEAD
git revert commitid

Delete a Git branch remotely

git push origin --delete branchname

What are the differences between ‘git pull’ and ‘git fetch’?

git pull, is git fetch followed by git merge. git fetch gets the remote changes, they get kept under refs/remotes//. However it doesn’t affect your local branches, and won’t change your working copy. git pull then merges these changes with the local copy.

How do I undo a ‘git add’ before committing

You did a “git add filename” accidentally and want to undo it before committing your change. You can simply do:

git reset filename

To unstage your changes to that file.

How do I deal with merge conflicts

Use “git mergetool” which gives a handy interface for solving merge conflicts.

Remove all local untracked files (and directories) from your local clone

Careful! You might want to take a backup before doing this:

git clean -f -d

Clone all remote branches

You probably already have, they’re just hiding! Use the following to see all the branches:

git branch -a

You can then use “git checkout origin/branchname” to take a look at the branch. Or “git checkout -b branchname origin/branchname”. To create a local tracking branch.

Rename local branch?

git branch -m oldname newname

Revert to a previous Git commit

You can use reset as above to revert to a previous commit, this assumes you mean go back to where you were before permanently rather than just take a look (for that you want to checkout an old version). The commit ID, should be as shown in the output of “git log”.

git reset --hard commitid

Again this will discard all changes in your working tree, so make sure this is really what you want to do! Or look at using –soft rather than –hard.

Remove a git submodule

Creating a submodule is pretty straight-forward, but deleting them less so the commands you need are:

git submodule deinit submodulename   
git rm submodulename
git rm --cached submodulename
rm -rf .git/modules/submodulename

Over-write local files when doing a git pull

Git reset is your friend again:

git fetch --all
git reset --hard origin/master

How can I add an empty directory to my repository?

You can’t! git doesn’t support this, but there’s a hack. You can create a .gitignore file in the directory with the following contents:

# Ignore everything in this directory
*
# Except this file
!.gitignore

I don’t believe it actually matters what’s in the .gitignore (and this .gitignore will ignore all files).

git export, exporting the source code as with “svn export”

Use git archive e.g:

git archive --format zip --output /full/path/to/zipfile.zip master 

Discard all my unchecked in changes

git checkout -- .

Create a new remote branch from the current local one

git config --global push.default current
git push -u

Restore a deleted file

First find the commit when the file last existed:

git rev-list -n 1 HEAD -- filename

Then checkout that file

git checkout deletingcommitid^ -- filename

Revert a single file to a specific previous commit

Similar to the above, but a bit simpler:

git checkout commitid filename

Make git ignore permissions/filemode changes

git config core.fileMode false

Get git to remember my password when checking out with https

It’ll only remember your password for 15mins:

git config --global credential.helper cache

You can make it remember your password longer with:

git config --global credential.helper "cache --timeout=XXXX"

Take a quick look at an old revision of a single file

git show commitid:filename

Select random line from a file in a single pass

I was asked this in an interview a few years back and I though it was kind of neat. The question is how do you select a single line from a file randomly, such that each line has a equal probability of being selected. The naive solution is of course to count the number of lines in the file, and then to select a line and get it from the file. But can you do it in a single pass, without seeking through the file?

The solution is kind of neat, have a buffer to store a “selected” line from the file. Then you read each line in turn, you then randomly swap your “selected” line with the new line with decreasing probability. The probability decreases to compensate for the fact that previous lines are more likely to have been replaced already.

Here’s a C++ solution:

1
2
3
4
5
6
7
8
9
10
11
12
string selected_line;
for(size_t linenumber=0;!file.eof();linenumber++) {
 
  string s = file.getline();
 
  int64_t r = rand64();
  r = r%linenumber;
  if(r==0) {
    selected_line = s;
  }
}
cout << selected_line << endl;

You can read more about this here.

Serving content over HTTPS in golang

Serving HTTPS content with golang is pretty straight forward. You’ll need to your certificate/key pem files to ListenAndServeTLS but that’s about it. However you may also want to insure that your users always use HTTPS in which case you can also listen on port 80 and just redirect them to the HTTPS site using RedirectHandler. The example below shows how you might do this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main
 
import (
    "net/http"
    "net"
)
 
func main() {
 
  http.Handle("/", http.FileServer(http.Dir(".")))
 
  go func() {
    err := http.ListenAndServe(":80", http.RedirectHandler("https://mywebsite.com", http.StatusFound))
    if err != nil {
      panic("Error: " + err.Error())
    }
  }()
 
 
  err := http.ListenAndServeTLS(":443", "cert.pem", "key.pem", nil)
  if err != nil {
    panic("Error: " + err.Error())
  }
 
}