Java Interview Question
April 5, 2016
We have an interview question today:
Input comes from a file containing pipe-delimited records with three fields: student id (a positive integer), course title (a string), and score (a positive integer). You may assume that any combination of student id and course is unique. Here’s an example input file:
22|Math|45 23|English|52 22|English|51 26|Math|72 23|Math|61 21|English|81The file may have any number of records, and there is no limit on the number of unique courses. You should write a program to read the file and write a list of all courses in the file, combined with the score of the lowest-numbered student in the course. Thus, the correct output for the input shown above is:
Math 45 English 81
Your task is to write a program to solve the interview question; the original question specified a Java solution, but you are free to use any language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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