Space Emergency is a nice little puzzle from Google Code Jam 2011.
The solution is quite simple. Fly as long as the boosters are built. Once they are done, reorder your remaining distance. Use the boosters on longest distances. Voila – that’s it.
Let’s see the straight forward implementation for the small input.
Continue reading
With the small coding contest some weeks ago we got many comments and it’s worth to make a conclusion for the solutions in different languages. What language is easier to write, has better memory usage or better performance?
To clarify the question:
We have a text file with 13 Million entries, all numbers in the range from 1.000.000 to 100.000.000. Each line has only one number. The file is unordered and we have about 1% duplicate entries. Remove the duplicates.
Be efficient with the memory usage and / or find a performant solution. The script should be started with the filename and linenumber and print the result to stdout.
First I generate the random numbers as test files with a simple python script. All tests will started with bench.py over all test files. See the sourcecode on github.com.
The command line tool /usr/bin/time can detect the cpu and memory consumption. This will be started as a sub process. After each run the user time, system time and maximum memory usage will saved. The result is stored into a JavaScript Object for the highchart. You can see the charts in the middle of this article.
Feel free to add new solutions and make some improvements.
The first solution in the comments was sorting all numbers. The expected memory usage should be 13.000.000 * 4 byte (100.000.000 fits into 32bit integers) if the sorting algorithm is not using an extra array for swapping. The average case effort for the sorting algorithm (quicksort or merge sort) is O(n + log n).
The command line tool sort can do this:
sort -u rand_numbers.txt > unique_numbers.txt
A small optimization with
sort
is comparing alpha-numerical instead string. It will use less memory:
sort -u -n rand_numbers.txt > unique_numbers.txt
The same solution in c should be compare-able with the sort-command. But I could not find the exact sort algorithm behind the method qsort. The implementation of standard qsort method could be mergesort, partition-exchange sort or quicksort and the memory usage will be higher than the pure memory amount for an array of integer.
int main(int argc, char*argv[]) {
char line[100];
int i=0, last;
FILE *fp = fopen(argv[1], "r");
int count = (int)atoi(argv[2]);
//allocating the size for the n values
int32_t *digits = (int32_t *)malloc(count * sizeof(int32_t));
// reading the lines, convert into an int, push into array
while (fgets(line, 100, fp)) {
digits[i++] = (int32_t)atoi(line);
}
fclose(fp);
//sort the complete array
qsort(digits, count, sizeof(int), compare);
//Print all entries, ignoring doubles
last = -1;
for (i=0; i<count; i++) {
if (last!=digits[i]) printf("%d\n", digits[i]);
last = digits[i];
}
}
This example is simple and not optimized, the same solution in python is not surprising (but shorter):
last = ""
for n in sorted(open(sys.argv[1])):
if last != n:
sys.stdout.write( n )
last = n
This simple python version sort the input file as strings and print the values (sys.stdout.write is faster than the print method!). Converting the input file into an integer array will save memory usage. The result files will have a large diff because sorting as numbers or as string has different results.
values = map(int, open(sys.argv[1]))
values.sort()
last = 0
for n in values:
if last != n:
sys.stdout.write("%d\n" % n)
last = n
In the charts you can see the O(n*log n) execution time. I separated the user and system time to clarify the algorithm calculation time vs. the system reading time.
The non-linear computing time results of the randomized entries in the test files.
The sort command can split the input array into small chunks (for sorting), save it to disk and merge it with limited memory usage. The command line tool
ulimit -d <n>
limits the memory for all processes and sort use temporary files. But I chose the build-in parameter from the sort command with the
--buffer-size=SIZE
option.
sort -u -n -S 20M rand_numbers.txt
After successful testing I the built an memory limited sorting variant with python as a second example. The magic merge-component can be found in the module heapq. It offers the functionality to merge a list of open file iterators with the pre-sorted chunks.
import sys, tempfile, heapq
limit = 40000
def sortedFileIterator(digits):
fp = tempfile.TemporaryFile()
digits.sort()
fp.write("\n".join(map(lambda x:str(x), digits)))
fp.seek(0)
return fp
iters = []
digits = []
for line in file(sys.argv[1]):
digits.append(int(line.strip()))
if len(digits)==limit:
iters.append(sortedFileIterator(digits))
digits = []
iters.append(sortedFileIterator(digits))
#merge all sorted ranges and filter doubles
oldItem = -1
for sortItem in heapq.merge(*iters):
if oldItem != sortItem:
print sortItem.strip()
oldItem = sortItem
The both constant lines in the chart are the two examples with constant memory usage.
The second solution simply put all entries into a hashmap. The values be will used as keys and the data structure will remove the duplicate entries automatically. This can be seen in the perl example.
Some languages offers a set - this data structure stores only the unique keys without a value. The point of interest while benchmarking will be the memory usage for the “easy to use” build-in data structure for millions of integers.
perl -lne'exists $h{$_} or print $h{$_}=$_'
for n in set(open(sys.argv[1])):
sys.stdout.write( n )
local set = {}
for n in io.lines(arg[1]) do
if not set[n] then
print(n)
set[n] = true
end
end
All solutions can be written in short time and will work. But the memory usage is terrible! The solutions needs 10 times of memory than the raw integer array. And the normal effort for using a hashmap with O(n) (set and get for n million in this case) is not correct. The “brute force inserting” keys into a hashmap will trigger the reorganisation of the bucket tables of the hashmap data structure! You can see this in the memory usage chart.
The limits in the problem description offers a more elegant solution. The raw memory usage for 13 million 32-bit integer is ~49MB. Mapping all integers from 1 million to 100 million to the bit position (in linear memory) will use ~ 11MB (99 million bits / 8). So the memory usage for the bitarray will be lower and constant. And the computation for the very short map function will be short.
int main(int argc, char*argv[]) {
char line[100];
const minValue = 1000000;
const maxValue = 100000000;
char *bitarray = (char *)malloc((maxValue - minValue) / 8);
FILE *fp = fopen(argv[1], "r");
int pos;
while (fgets(line, 100, fp)) {
pos = atoi(line);
if (!(bitarray[(pos-minValue)>>3] & 1<<(pos%8))) {
printf("%d\n", pos);
bitarray[(pos-minValue)>>3]|=(1<<(pos%8));
}
}
fclose(fp);
return 0;
}
We got a python solution with the module bitarray. If you dont have the module bitarray you have to install it. On the default ubuntu installation you need the python-dev and the setuptools packages. The bitarray module is available with easy_install after successful package installlation.
sudo apt-get install python-dev python-setuptools sudo easy_install bitarray
The python solution is short, but the execution time is much longer than the c variant.
import sys, bitarray
minValue = 1000000
maxValue = 100000000
bits = bitarray.bitarray(maxValue-minValue+1)
for line in file(sys.argv[1]):
i = int(line)
if not bits[i - minValue]:
bits[i - minValue] = 1
sys.stdout.write(line)
A co-worker rated the file access higher than the computation time and offered a variant with mmap. The mmap function maps the input file into memory and you can iterate over it as a byte array. Because the parsing part of integers is easy the variant should be compareable with the bitarray c variant.
https://github.com/ChristianHarms/uc_sniplets/blob/master/no_duplicates/solve_nmap_bitmap.c
The memory usage for the bittarray-mmap variant will increase because the command line tool recognize the mapped memory as process memory usage.
The bitarray solution has constant, low memory usage and fast execution time. It will only work because the available numbers are limited in range.
Using hashmap / set solutions can result in massive memory usage.
Sorting the input entries is the only one solution with the possibility to work with limited memory.
Find more about language performance with the "c++ / go / java / scala" language performance benchmark by google on readwriteweb.com.
This is a problem I particularly enjoyed. I had to turn it around a few times in my head before I found the solution.
First I was thinking about simulation the chickens moving before noticing I am going in the totally wrong direction.
Then it dawned to me, that the solution is quite simple.
We can break the solution down into two parts.
Leaving all other aspects aside, just check if enough chickens can make it to the barn in time. If this is not the case, it’s an IMPOSSIBLE one to solve.
For this to find out, you only need to get their position, add the speed multiplied by the time you have at hands and see if they make it into safety, also known as the barn.
int finishers = 0;
boolean[] isFastEnough = new boolean[startposition.length];
for (int i = 0; i < startposition.length; i++) {
if ((startposition[i] + speed[i] * time) >= barnPosition) {
isFastEnough[i] = true;
finishers++;
} else {
isFastEnough[i] = false;
}
}
if (finishers < chicksNeedToFinish) {
return "IMPOSSIBLE";
}
This is where the actual work is done. I decided to assign every chicken a tag, if it would make it to the barn. So you end up with an array of ones and zeroes or true and false according to the chicken’s start position. For example:
barn at position 10 with 5 seconds on the clock position: 0 2 3 5 7 speed: 2 1 1 1 4 finisher: 1 0 0 1 1
This is the information you need to calculate the swaps. Start from the right end of the array and walk to the front. If you find a finisher, increase the chickens which are safe and move on. If you find a slow one, you need to swap the next finisher in front of it, so you increase the costs of swapping by one. For the next speedy chicken you find, you increase swaps by the costs you determined.
// start from closest to barn to furthest swap speedy chicken until we have the required number
finishers = 0;
int position = startposition.length - 1;
int priceOfSwap = 0;
int swaps = 0;
for (int i = startposition.length - 1; i >= 0; i--) {
if (isFastEnough[i]) {
finishers++;
if (priceOfSwap > 0) {
swaps += priceOfSwap;
}
} else {
priceOfSwap++;
}
if (chicksNeedToFinish == finishers) {
return String.valueOf(swaps);
}
}
That’s all the you need. The code is, as usual, on github.
With the Google Code Jam 2011 less than four weeks away, it is time for some finger exercises.
Let’s start with the Minimum Scalar Product, which should only take you a few minutes.
Here’s the Java version, which will only work for the small input set. I’ll explain later.
public static int getMinimumScalarProduct2(int[] x, int[] y) {
Arrays.sort(x);
Arrays.sort(y);
int sum=0;
for (int i = 0; i < x.length; i++) {
sum += x[i] * y[x.length -1 -i];
}
return sum;
}
What we do is sort both arrays, then multiply them. One starting from the beginning, the other from the end. So our biggest numbers are multiplied with the smallest. The math is on Google's solution page, we're just looking at coding here.
This works for the small input set, but not the large one. Why?
Take a look at the Limits:
Large dataset
T = 10
100 ? n ? 800
-100000 ? xi, yi ? 100000
The result of the large dataset will not fit in an int. So we switch to BigInteger, which can hold our results.
public static BigInteger getMinimumScalarProduct(int[] x, int[] y) {
Arrays.sort(x);
Arrays.sort(y);
BigInteger sum = BigInteger.ZERO;
for (int i = 0; i < x.length; i++) {
sum = sum.add( new BigInteger(""+ x[i]).multiply(new BigInteger(""+y[x.length -1 -i])));
}
return sum;
}
Take a look in the BigInteger API doc, I'm very sure you'll need it for this years jam. I initially made the mistake of not assigning the result of sum.add() to sum.
Now, as I try to do a bit python, I will also present my python solution. Maybe Christian can spot my classic java thinking and provide a more python like version for my lines.
f = open('../resources/codejam/msp-large.in', 'r')
cases = int(f.readline())
for i in range (0, cases):
nrOfIntegers = f.readline()
xs = f.readline()
ys = f.readline()
x = [int(s) for s in xs.split()]
y = [int(s) for s in ys.split()]
x.sort()
y.sort()
sum = 0
size = len(x)
for j in range(0, size):
sum+= int(x[j])* int(y[size -1 - j])
print sum
It's the exact same idea, so no suprises here.
Happy practicing.
John Resig (creator and lead developer of jQuery) has published two interesting articles about data structure for a lookup to a huge wordlist (dictionary lookups and trie performance). Read in his articles about all the variants and preconditions.
I implemented six variants for the data structure (started with simple String search, Array to Trie) and benchmarked them to find the best solution. But let’s start with the rules:
The data structure should be as short as possible and available as an JavaScript file from a CDN. I created the complete data variants with python and uploaded the files on the google app engine (caching header and gzip as default).
You can transfer a compressed data structure and extract it in the client. This can double your memory usage. Limit and test the memory usage – it should run on mobile devices with limited memory and cpu. I added the heap snapshots from the chrome developers tools to get the usage in an browser (John does it with node.js).
Find the existence of given word (or only his word stem) in the wordlist – the function for searching have to be benchmarked. I included an interactive page with loading the data files and a JSLitmus benchmark.
wordlist = ["works", "worksheet", "tree"];
findWord("worksheet")=="worksheet"
findWord("workshe")=="works"
findWord("workdesk")==false
I used the default wordlist available on every linux system (
/usr/share/dict/
). The English wordlist contains 74137 unique words (filter out 1-letter, with apostrophe and lowercased) – the German wordlist has 327314 words. I chose 100 words containing / not containing in the list for benchmarking the access speed.
The shortest variant is putting the complete wordlist as a plain string in the loader.
words.load("String", "aah aahed aahing aahs aal zyzzyvas zzz");
filesize for English wordlist: 660 kB (gzip: 195 kB) – loading time: 20ms
filesize for German wordlist: 4223 kB (gzip: 857 kB)
findInString: function (word) {
var data = this.data.String;
while (word) {
if (data.indexOf(word) !== -1) {
return word;
}
word = word.substring(0, word.length - 1)
}
return false;
}
Wow, searching a non-existing word with
String.indexOf
is quite expensive!
The memory usage (1.3 MB) is factor 2 then the plain file size (650 kB) because the JavaScript String is using utf-16.
For a better search performance we can split the wordlist on server side and offer the split up wordlist (splitting in client side will double the memory usage).
words.load("Array", ["aah","aahed","aahing","aahs","aal","zyzzyvas","zzz"]);
filesize for English wordlist: 805 kB (gzip: 200 kB) – loading time: 42ms
filesize for German wordlist: 4862 kB (gzip: 876 kB)
Searching in a sorted Array is simple binary search with O(log n).
findInArray: function (word) {
var data = this.data.Array;
var i = Math.floor(data.length / 2);
var jump = Math.ceil(i / 2);
while (jump) {
if (data[i] === word) return word;
i = i + ((data[i] < word) * 2 - 1) * jump;
jump = (jump === 1) ? 0 : Math.ceil(jump / 2);
}
if (word.indexOf(data[i - 1]) === 0) return data[i - 1];
return (word.indexOf(data[i]) === 0) ? data[i] : "";
}
The memory usage is factor 5 (String and Array) than the file size.
Because binary search with many items is more expensive than key-access we can use a hashmap (or a native JavaScript Object). Accessing should be optimized and with stripping the " from ASCII key-names the file size is not longer than the Array variant.
words.load("Hashmap", {zzz:1,aal:1,aahed:1,aah:1,aahing:1,aahs:1,zyzzyvas:1});
filesize for English wordlist: 797 kB (gzip: 325 kB) - loading time: 96ms
filesize for German wordlist: 5302 kB (gzip: 1804 kB)
Accessing the words in a hasmap is O(1), searching the word stem is O(m) (m is the maximum word length).
findInHashmap: function (word) {
var data = this.data.Hashmap;
while (word) {
if (word in data) {
return word;
}
word = word.substring(0, word.length - 1)
}
return false;
}
The memory usage is factor 10, the loading time factor 2 - but access to the words is quite fast (as expected).
An trie is a special tree data structure for searching ASCII data (mostly for similar words). Every letter is one node and realized as a recursive Object. We can save the file size by stripping the " in key-names (if this letter is a valid variable name in JavaScript).
words.load("Trie", {a:{a:{h:{i:{n:{g:{$:1}}},s:{$:1},e:{d:{$:1}},$:1},l:{$:1}}},z:{y:{z:{z:{y:{v:{a:{s:{$:1}}}}}}},z:{z:{$:1}}}});
I run the Javascript unpacker and beautifier for better reading:
words.load("Trie", {
a: {
a: {
h: {
i: {
n: {
g: {
$: 1
}
}
},
s: {
$: 1
},
e: {
d: {
$: 1
}
},
$: 1
},
l: {
$: 1
}
}
},
z: {
y: {
z: {
z: {
y: {
v: {
a: {
s: {
$: 1
}
}
}
}
}
}
},
z: {
z: {
$: 1
}
}
}
});
As you see this is the complete normalized version and has some useless subtrees in the example with 7 words. The structure would be better with many similar words. There exists many generators which offers better tries (John Resig did some work).
filesize for English wordlist: 950 kB (gzip: 142 kB) - loading time: 237ms
filesize for German wordlist: 4016 kB (gzip: 464 kB)
Searching words in a trie (including the word stem) is O(m) (m is the maximum word length).
findInTrie: function (word) {
var node = this.data.Trie;
var result = "";
for (var i = 0; i < word.length; i++) {
if (node.$) result = word.substring(0, i);
if (word[i] in node) node = node[word[i]];
else
return result;
}
return result;
}
The memory usage is factor 8, the loading time factor 5 - but access to unknown words is quite fast (as expected).
Depending on your wordlist the file size can decreased if the most used starting letter are used for the level-1 key.
words.load("Trie2", {
aa: {
hed: 1,
h: 1,
hing: 1,
l: 1,
hs: 1
},
zy: {
zzyvas: 1
},
zz: {
z: 1
}
}, 2);
In the English wordlist with 74137 unique words is the optimal split after 3 letter, in the German wordlist with 327314 words after 8 letter.
filesize for English wordlist: 599 kB (gzip: 204 kB) - loading time: 69ms
filesize for German wordlist: 3273 kB (gzip: 991 kB)
Searching the word in this 2-level trie (including the word stem) is O(m) like the hashmap variant (m is the maximum word length).
findInTrie2: function(word) {
var data = this.data.Trie2;
while(word) {
var first = word.substring(0, this.opt.Trie2);
var second = word.substring(this.opt.Trie2);
//console.info("word: "+word);
if (word.length>this.opt.Trie2) {
if (first in data && second in data[first])
return word;
}
else {
if (first in data) return word;
}
word = word.substring(0, word.length-1)
}
return false;
}
This data structure is offered by Mathias Nater (hyphenator.js at http://code.google.com/p/hyphenator/). All words ordered by length and concatenated into strings.
words.load("StaticStr", {
"8": "zyzzyvas",
"3": "aahaalzzz", // three words concat
"4": "aahs",
"5": "aahed",
"6": "aahing"
});
filesize for English wordlist: 588 kB (gzip: 241 kB) - loading time: 18ms
filesize for German wordlist: 4203 kB (gzip: 991kB)
Searching the word in the static string map is a binary search on the m entries and result in O(log n * m) .
findInStaticStr: function(word) {
var data = this.data.StaticStr;
var s, i, step;
for (var len=word.length; len>1; len--)
if (len in data) {
i = Math.floor(data[len].length/(len*2));
jump = Math.ceil(i/2);
while (jump) {
s = data[len].substring(i*len, i*len + len);
if (s===word) return word;
i = i + ((s<word)*2-1)*jump;
jump=(jump===1)?0:Math.ceil(jump/2);
}
s1 = data[len].substring(i*len, (i+1)*len);
s2 = data[len].substring((i+1)*len, (i+2)*len);
if (s1.length===len && word.indexOf(s1)===0) return s1;
if (s2.length===len && word.indexOf(s2)===len) return s2;
}
}
The file size, memory usage and loading time are better than the plain string (and the best in the competition). And the accessing time is fast enough. As you see this static string map variant dont make the heavy use of hashmaps and is the best solution for saving resources for mobile html apps.
Parsing time on a Core I7 is significant - so it will on a mobile parser a NO-GO!
I included the benchmarking page as an iframe - feel free to load and run the benchmarks. Open your JavaScript console to see some debugging lines or play with the global words-object. The code can found at http://pyunitedcoders.appspot.com/words.js.
We all like a playback progress bar underneath our media players, so we can see how far we are and, if necesary, drag the thumb to were we want it to be.
Lets do this on Android: enter http://developer.android.com/reference/android/widget/SeekBar.html
As we will need a Runnable to update the bar regularly, let you class implement Runnable. Let’s look at the run() method.
@Override
public void run() {
// mp is your MediaPlayer
// progress is your ProgressBar
int currentPosition = 0;
int total = mp.getDuration();
progress.setMax(total);
while (mp != null && currentPosition < total) {
try {
Thread.sleep(1000);
currentPosition = mp.getCurrentPosition();
} catch (InterruptedException e) {
return;
} catch (Exception e) {
return;
}
progress.setProgress(currentPosition);
}
}
What we’re doing here is set the ProgressBar to our current position, then sleep for a second and do it again.
Continue reading
HTML5 brought many good features, but it also brought back user-agent sniffing.
User-Agent sniffing is the nemesis of good modern web development, and that’s for a good reason. As a person who uses Opera since version 4 as his main browser for surfing (not for development though) I have suffered through many bad scripts which try to exclude me just on the grounds I am using neither Internet Explorer nor Firefox. Or neither Internet Explorer nor Netscape. I have ranted against scripts that told me my browser was outdated and I should switch do a newer, faster and better browser like IE, even though I used the latest ubuntu version of Opera.
User-Agent sniffing dates back to when browser vendors extended their products with cool new features like the marquee element (I hope you noticed the sarcasm) and web developers had to find out, if they could use these. Often that led to two completely seperate versions of the web site and the user being redirected to one of them depending on his user-agent (or not being redirected at all, if the user-agent did neither match the sniffing for IE or Netscape).
Many web developers fought the fight to replace user-agent sniffing by feature testing. Instead of looking at the user-agent and thereby deriving from a name what the browser is capable of, it is definitevly better to look at what the browser says it is capable of. This is an example for a very common use case:
function addListener (element, type, callback) {
if (element.addEventListener) {
element.addEventListener(type, callback, false);
}
else if (element.attachEvent) {
element.attachEvent("on" + type, callback);
}
}
This script handles the different event models which exist in browsers, the standardized model of the W3C (addEventListener) and the proprietary model of Microsoft (attachEvent).
What is the advantage of feature detection? It does not break future versions of browsers. If a future version (like IE9) supports a certain feature (like the W3C event model, which by the way it does), we don’t have to change our script, it continues to work. User-agent sniffing on the other hand, has to be adapted whenever a new browser or a new version of an existing browser is released, since that browser might support a feature a former version did not.
Now most will agree that feature detection is superior to user-agent sniffing. However, feature detection is not a replacement for user-agent sniffing, in fact, sometimes we have to use user-agent sniffing. We rarely need it, but the use of HTML5 increases the need of user-agent sniffing.
User-agent sniffing is necessary when a browser does support a certain feature but has a bug in it. I once had the case that a former version of Safari had a bug in its implementation of
document.querySelectorAll
, where in certain circumstances the returned NodeList contained
null
. While there is the theoretical possibility to feature-test bugs, this fails when the browser crashes when using a feature in a special way, as it happened to a friend of mine on a beta version of Safari. There is no way to feature detect a browser crash.
Bugs in implementations of features are quite rare, but what if a browser supports a feature, but not in a way you like? This is very common for features of HTML5.
HTML5 has several new type for the
input
element. A very convenient type is
date
. It is quite easy to do a feature test, if the browser supports that type:
function hasTypeSearch() {
var input = document.createElement("input");
input.setAttribute("type", "date");
return input.type === "date";
}
This test works because browsers which do not support
date
will fall back to the type
text
. But this does not help at all. Opera’s support for the
date
type looks like this:
While Chrome’s support looks like that:
Both browsers support the
date
type, but while Opera has a full featured date picker, Chrome only has two buttons to increase or decrease the date.
Now if you want to enhance browsers which do not have a datepicker natively – maybe by adding a jQuery UI datepicker – there is no way to feature detect that.
Similar, the
search
type is supported by many browsers. On Safari for Mac it looks like that:
On all other browsers I tried it looks like an ordinary text field. This is due to the specification, which says:
On platforms where search fields are distinguished from regular text fields, the Search state might result in an appearance consistent with the platform’s search fields rather than appearing like a regular text field.
Offering that little
x
to reset the search is a feature one would like in all browsers on all platforms, but again, there is no way to feature detect this.
HTML5 makes us need user-agent sniffing.
What can we do about this? Nothing. We could only keep user-agent sniffing to a minimum. That is, first try to feature detect. Only if that succeeds, do a user-agent sniffing.
function hasDatepicker () {
var input = document.createElement("input");
input.setAttribute("type", "date");
if (input.type !== "date") {
// does not support type date
return false;
}
// currently only Opera supports date as we want it
return navigator.userAgent.indexOf("Opera") !== -1;
}
This leaves us in the sorry state that we have to monitor browser development closely. Whenever a browser changes, we might need to adapt our sniffing. HTML5 brought many good features, but it also brought back user-agent sniffing.
Hey, this time I have a litte quiz. The implementation will be in different languages but the task is always the same.
This is also a good interview question to see how the candidate’s skills in different areas are and it’s brief enough for phone interviews, as she can provide the idea on how to solve the problem and does not need to implement code.
We will use bash, some scripting or higher language and database specific solutions.
We have a text file with 13 Million entries, all numbers in the range from 1.000.000 to 100.000.000. Each line has only one number. The file is unordered and we have about 1% duplicate entries. Remove the duplicates.
the task remove the duplicates. the challenge: be efficient and brief
(in the interview it would be: give me one answer per field, in comments it’s enough to post one answer, but the more the better )
There’s no limit on what you’re allowed to do. Just try not to stress the cpu unnecessarily and memory too much.
I’m excited to see your solutions.
If you had the chance to build a website from scratch. A website that is going to be launched in the late summer of this year. And an old version of that website already exists, which will be maintained but not developed further…
How would you build the frontend?
I have given that some thought in the last time. And here are the three most important conclusions I came to:
While the first two might seem obvious, the third sounds like madness. How can I seriously even think of excluding like fifty percent of the users (less in Europe, more in the US)? It’s only logical (and I admit I’ll cut that down a little later on). But let me explain the first two points first.
HTML5 offeres a broad variety of new structural elements. And the basis for a good website is semantic markup. footer, header, nav, article, time and so on are HTML5’s answers to a ton of divs that we used in old (and current) websites. But HTML5 is more, using the audio and video elements you can easily embed multimedia to your site. OK, video is still a mess if you don’t want to double encode your content, but that might change in the near future, since Google announced to drop support for H.264 last week.
There are a lot more techniques that help building a light-weight application, part of which are associated with HTML5, but are not part of the specification. Offline-applications, drag and drop, the File-API, local storage, geolocation and more.
If that application was a blog, then the elements article, header, footer and so on come in quite naturally. Using these results in clearly structured, semantic markup. Maybe sometimes I would want to blog about a video I made. Or a song I wrote. I could include these without any plugins and therefore would not need a flash-detection library either. And that would work without Javascript. So if my big paranoid brother, who generally disables Javascript and any plugin in his browser, would want to read my blog, fine. He would be able to view all content. Even if some geeky friend of mine would want to read my blog using lynx, fine too. He would not be able to view the video, but he could download it easily.
Using the application as the blog author would be heavily supported by these techniques. Want to post a video? Just drag and drop it into the browser (using the DnD- and File-API). Write while onboard a train? You’ll notice no difference thanks to offline support and local storage.
This seems obvious as well. It means, if you want to have rounded corners, don’t use a bunch of images, use border-radius. If you want semi-transparent background, don’t use a png image, but use rgba colors. If you want animations, use transitions instead of bloaty Javascript code. If you want a shadowed box, don’t use images, use box-shadow. You want to use your corporate identity font for headings? Do not use images, use @font-face. And most of all, if you want your application to fit in a mobile browser, use media-queries.
So using CSS3 drastically can decrease the number of files you need and therefore the improve the performance of your application.
There is one drawback, though. CSS3 support is not complete in most browsers. Opera for example does not have gradients. Firefox does not support transitions. That’s partly because these specifications still are working drafts. But let’s be honest. Does it really hurt, if Opera users have a single background color instead of a gradient? If Firefox users don’t have an animated hover effect? Form follows function.
If you have a look at what browsers support today, you can see that many, many features I would use already are supported in Opera, Chrome, Firefox and Safari. So if we dropped IE support, we could be using them today.
And if you then have a look at what will be, you can see that in mid/late 2011, when IE9 is released, most of the features are supported by all browsers. So I correct myself: Drop IE<9 support. As I said it. If you build an application that will be launched in the second half of 2011, use HTML5, CSS3 and don't care about IEs. But how long will it take users to adapt to IE9? My guess is, pretty quickly. Those using IE8 will switch quickly. Those using IE7 or - godforbid - IE6 will probably stick to it forever and eventually die out. You can still send them to the old version of your application (which is a prerequisite of IEs. If you don't have an old version you most likely cannot afford to drop IE support).
What should be done in the meantime? How should we spend the time until IE9 is released? Build a new javascript library. Large part of current libraries are concerned with selecting dom elements, providing animations, offering functionality that already found its way into Ecmascript 5 (like JSON, Array extras and so on). Throw them away. Use querySelector/querySelectorAll instead of sizzle. Use CSS3 for animations. Ecmascript 5 is widely supported in many browsers today. Again, IE8 is far behind the others, but IE9 is the paragon for ES5 support. It even finally implements the Event model of W3C.
So spend the time building a library that adds the few missing functions. That works around the remaining browser bugs and inconsitencies. Build a library for the future.
When you use semantic markup, media queries and progressive enhancement for the advanced features (and do everything right), then you have a mobile web app almost for free. You don’t have to build an extra app for iPhone, Android… Now wouldn’t that be nice? Think of all the time (and money) you could save. So go ahead and start.
Solving an problem from project euler can be a challenge or coding fun. The result of every problem is only one number, calculated by an algorithm. Some algorithms can be written as one expression. You get an one-liner if you can embed it in a function with only one line of code.
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
After solving some project euler problems with python I got some one-line solutions with nice usage of list comprehensions and functional programming. These code examples are not clean code but a challenge to find more one-line solutions. This article include my first 10 solutions for project euler as one-line python function. Dont use it to cheating the project – it should be a motivation to find smart coding solutions and participate to project euler.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
def task1():
return sum(filter(lambda x:x%3==0 or x%5==0, list(range(1,1000))))
The version as list comprehension look similar:
def task1():
return sum([x for x in range(1,1000) if x%3==0 or x%5==0])
I found a ruby one-liner for problem 1 on cslife.wordpress.com.
The sum of the squares of the first ten natural numbers is:
12 + 22 + ... + 10^2 = 385
.
The square of the sum of the first ten natural numbers is:
(1 + 2 + ... + 10)2 = 55^2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is
3025 - 385 = 2640
.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
def task6():
return sum(range(1,101)) ** 2 - sum([x*x for x in range(1,101)])
I found a groovy one-liner on jared.cacurak.com and the correct O(1) solution on basildoncoder.com (as comment ) and shaunabram.com.
Find the greatest product of five consecutive digits in the given 1000-digit number (given as string).
def task8(n):
return max([int(n[i])*int(n[i+1])*int(n[i+2])*int(n[i+3])*int(n[i+4]) for i in range(len(n)-5)])
I generated a list of all products for five consecutive digits and used
max
to find the greatest number in the list.
On scrollingtext.org are many comments with different solutions and on codesnippt.com is my brute-force solution.
Pythagorean triplet is a set of three natural numbers,
a < b < c
, for which
a^2 + b^2 = c^2
.
For example:
3^2 + 4^2 = 9 + 16 = 25 = 5^2
.
There exists exactly one Pythagorean triplet for which
a + b + c = 1000
.
Find the product
a * b * c
.
def task9():
return [a*b*c for a in range(1,1000) for b in range(1,1000) for c in [1000-b-a] if a*a+b*b==c*c and a<b and b<c][0]
Multi-dimension loops can generated by more for-statements in a list comprehension. This can also solved by pen and paper – see the euler project forum after submit the solution. Or read the answers on stackoverflow.com with the correct mathematical solution.
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
def task13(listOfNumbers):
return str(sum(listOfNumbers))[:10]
There is no limit of the digit-length from an integer in python – problem solved fast. If your language dont support long integer use only the first 12 digits to solve the problem. The same solution found on blog.dreamshire.com and stefanoricciardi.com in F#.
2^15 = 32768
and the sum of its digits is
3 + 2 + 7 + 6 + 8 = 26
.
What is the sum of the digits of the number
2^1000
?
def task16():
return sum([int(x) for x in str(2**1000)])
My solution in python (but commented) found at realultimateprogramming.blogspot.com or stackoverflow.com.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
My first solution was straight-forward:
def task19():
c = 0
for year in range(1901, 2001):
for month in range(1, 13):
c += datetime.datetime(year,month, 1).weekday()==6
return c
This can be converted in an one-liner, but the truly short solution look like this:
def task19():
return 100*12/7
Find the sum of the digits in the number 100! (=
factorial(100)
).
def task20():
return sum([int(x) for x in list(str(math.factorial(100)))])
There is a small cheat – you have to include the math-module. But the stand-alone solution works too:
def task20():
return sum([int(x) for x in str(reduce(lambda a,b:a*b, range(1,101)))])
I found an one-liner on theburningmonk.com in F#.
What is the first term in the Fibonacci sequence to contain 1000 digits?
My first solution is the classic non-recursive solution with only three variables.
def task25(self):
'''What is the first term in the Fibonacci sequence to contain 1000 digits?'''
a1 = 1
a2 = 1
n = 3
while 1:
a1 = a1 + a2
if len(str(a1))==1000:
return n
n += 1
a2 = a1 + a2
if len(str(a2))==1000:
return n
n += 1
Looks like clean code and performance optimized. The one-line solution have to generate the fibonacci numbers in a list and stop if the 1000-digits member of the fibonacci sequence is reached.
def task25():
return 1+len(reduce(lambda a,b:len(str(a[-1]))==1000 and a or a.append(a[-2]+a[-1]) or a,range(5000),[1,2]))
Using
reduce
without reducing is not fine – but a one-line solution. And it’s brute-force – step back to your mathematical knowhow: Fibonacci terms converge to
(n)*Phi=(n+1)
, where Phi is the Golden Ratio:
(1+sqrt(5))/2
– detailed description can found on geekality.net.
def task25():
return int(math.floor( (1000 - 1 + math.log10(math.sqrt(5))) / math.log10((1+math.sqrt(5))/2)))
I found an one-liner on sharp.it in F#.
Consider all integer combinations of
a*b
for 2 <= a <= 5 and 2 <= b =1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
.
How many distinct terms are in the sequence generated by
a * b
for
2 <= a <= 100
and
2 <= b <= 100
?
I have to generate all combinations for the
a^b
and put it into a set to eliminate the duplicates.
def task29():
res = set()
for a in range(2, 101):
for b in range(2, 101):
res.add(a**b)
return len(list(res))
I used the same trick like in problem 9. Starting an two-dimensional list-comprehension, converting all products in a python-set to remove the duplicates and counting the elements in the set.
def task29():
return len(set([a**b for a in range(2,101) for b in range(2,101)]))
If you have other one-line solution and/or in other programming languages feel free to comment or link your blogs. Next year I will post the next 10 solutions.
Happy new Year!
By continuing to use the site, you agree to the use of cookies. more information
The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.