Java Interview Question
April 5, 2016
I don’t do Java — I don’t have enough fingers to type so much — so I’ll write my solution in Awk, which is perfect for data-laundry problems like this one:
BEGIN { FS = "|" }
! ($2 in students) {
students[$2] = $1
scores[$2] = $3 }
$2 in students {
if ($1 < students[$2]) {
students[$2] = $1
scores[$2] = $3 } }
END { for (s in scores)
print s, scores[s] }
The BEGIN action sets the field delimiter, the first comparison saves the minimal student id and score for a new course, the second comparison resets the minimal student id and score for an existing course when a new minimal student id is found, and the END action prints the result. Assuming the program shown above is written in a file scores.awk, you can run the program from a command prompt like this:
$ awk -f scores.awk input.txt Math 45 English 81
The order of the output is non-deterministic. You can run the program at http://ideone.com/FCg9cI.
Perfect problem for perl to solve as it’s extraction/parsing….
my %x; foreach (map {[split m{\|}]} <> ) { ## Returns an array of arrayrefs.... $x{$_->[1]}=$_ unless exists $x{$_->[1]} && $x{$_->[1]}[0] < $_->[0]; ## If doesn't exist - or current "lowest value" is > than value } print map { $_,' '.$x{$_}[2] } keys %x;@josejuan: nice, not seen Haskell written like that. I’m puzzling over what ‘↪-↱_’ might mean though.
Fear my leet Julia skills (just kidding). Storing the lowest-numbered student’s score for each course (what a weird request, by the way). There are Pair datatypes for that and the min function has an appropriate method out of the box :)
module Whatever lowest = Dict{UTF8String,Pair{Int,Int}}() for line in eachline(open(ARGS[1])) user, course, score = split(line, '|') p = parse(Int, user)=>parse(Int, score) lowest[course] = min(get(lowest, course, p), p) end for (course, p) in lowest println("$course $(p[2])") end endAnd I replaced the course names just to see that character encodings still work.
Python:
import fileinput data = {} for line in fileinput.input(): sid, title, score = line.strip().split('|') value = (int(sid), score) if value < data.setdefault(title, value): data[title] = value for title, (sid, score) in data.items(): print(title, score)@matthew I’m using enomsg/vim-haskellConcealPlus, yes, it make code less readable (if not use these symbols) but it’s nice if you are accustomed :) (symbols mapping here https://github.com/enomsg/vim-haskellConcealPlus/blob/master/after/syntax/haskell.vim )
There needs to be a Scheme version. This is whatever version of Guile they had on the server (rather old actually). The hash tables, string-split, command-line and some module system with a read-line in it are Guile. The solution itself is the same that I already wrote in Julia.
(use-modules (ice-9 rdelim)) ;read-line (define t (make-hash-table)) (define (finder port) (let ((line (read-line port))) (or (eof-object? line) (call-with-values (lambda () (apply values (string-split line #\|))) (lambda (user course score) (let ((this (cons (string->number user) (string->number score)))) (hash-set! t course (lesser (hash-ref t course this) this)) (finder port))))))) (define (lesser old new) (if (< (car new) (car old)) new old)) (call-with-input-file (list-ref (command-line) 1) finder) (hash-for-each (lambda (key value) (display key) (write-char #\space) (write (cdr value)) (newline)) t)It seems to deal with my UTF-8 input and output. Good.
@josejuan: Thanks for that, interesting. I thought this looked like a good problem for map reduce, I’m not too keen on Java, but here’s a solution in Javascript & node.js:
var mapreduce = require('mapred')(); var fs = require('fs'); var filename = process.argv[2]; fs.readFile(filename, 'utf8', function(err, data) { if (err) return console.log(err); var lines = data.toString().split('\n'); mapreduce(lines.map(function(line) { return [line]; }), function(key, value){ var a = key.split('|') if (a.length < 3) return []; else return [[a[1],{student: a[0], score: a[2]}]]; }, function(key, values){ return values.reduce(function(a,b) { return a.student < b.student ? a : b; }); }, function(result){ Object.keys(result).sort().forEach(function(k) { console.log(k,result[k].score); }); }); });This was just begging to be solved in R:
data <- read.csv(file = "~/Desktop/input.csv", sep="|", header = FALSE);
aggregate(by = as.data.frame(data[,2]), as.data.frame(data[,3]), min);
Might as well add an awk version:
awk -F'|' '{if(!($2 in i)||($1<i[$2])){i[$2]=$1;s[$2]=$3}};END{for(k in s)print k,s[k]}' test.txtPure sort version (GNU coreutils) 8.4. (So the output is just the relevant lines from the file and still needs formatting, can’t do that in sort.)
Well, we haven’t had a C++ version yet, so here is one. Needs C++14 (specifically auto for lambda parameters). Assumes course ids are non-zero.
#include <stdio.h> #include <iostream> #include <map> #include <string> #include <algorithm> int main(int argc, char *argv[]) { std::string line; std::map<std::string,std::pair<int,int>> a; while(std::getline(std::cin, line)) { int student, start, end, score, valid = 0; sscanf(line.c_str(), "%d|%n%*[^|]%n|%d%n", &student, &start, &end, &score, &valid); if (valid) { auto &entry = a[std::string(line.c_str(),start,end-start)]; if (!entry.first || student < entry.first) { entry.first = student; entry.second = score; } } } std::for_each (a.begin(),a.end(),[](auto e) { std::cout << e.first << " " << e.second.second << "\n"; }); }file= open(“input.txt”,”r”)
dict = {}
for line in file:
cuurent = line.split(“|”)
if cuurent[1] not in dict:
dict[cuurent[1]]=int(cuurent[0])
elif dict[cuurent[1]] > int(cuurent[0]):
dict[cuurent[1]]= int(cuurent[0])
print dict
Oh ok, a Java solution, output sorted by course name.
@r.clayton: isn’t that just showing the lowest score, rather than the score of the lowest numbered student?
Yup. I either misread the problem (most likely), or twisted it around in my head by the time I got to writing that part of the code. I guess I don’t get that job.
A Java solution redux.
Java solution using the stream API: https://gist.github.com/gdejohn/91e26d20a95fb2c16d778a908ab5f173