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|81

The 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.

Pages: 1 2

18 Responses to “Java Interview Question”

  1. 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;
    
    
  2. import Data.Map (assocs, fromListWith)
    import Data.List.Utils (replace)
    
    summary = assocs ∘ fromListWith min ∘ map (row ∘ words) ∘ lines ∘ replace "|" " "
      where row [_, course, score] = (course, read score)
    
    main = getContents ↪-↱_format ∘ summary
      where format (course, score) = putStrLn $ course ⧺ " " ⧺ show (score :: ℤ)
    
  3. matthew said

    @josejuan: nice, not seen Haskell written like that. I’m puzzling over what ‘↪-↱_’ might mean though.

  4. Jussi Piitulainen said

    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
    
    end
    

    And I replaced the course names just to see that character encodings still work.

    $ ./julia ~/courses.jl ~/cdb.vbsv
    Venäjä 81
    Matikka 45
    $ 
    
  5. Mike said

    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)
    
  6. @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 )

  7. Jussi Piitulainen said

    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.

    $ guile courses.guile cdb.vbsv
    Matikka 45
    Venäjä 81
    $ 
    
  8. matthew said

    @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);
                      });
                  });
    });
    
  9. Dale said

    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);

  10. Mike said

    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.txt
    
    
  11. Jussi Piitulainen said

    Pure 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.)

    $ sort -t \| -k 2,2 -k 1,1n --stable cdb.vbsv | sort -t \| -k 2,2 --unique
    22|Matikka|45
    21|Venäjä|81
    $ 
    
  12. matthew said

    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";
         });
    }
    
  13. shinshan75 said

    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

  14. r. clayton said

    Oh ok, a Java solution, output sorted by course name.

  15. matthew said

    @r.clayton: isn’t that just showing the lowest score, rather than the score of the lowest numbered student?

  16. r. clayton said

    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.

  17. r. clayton said

    A Java solution redux.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: