Tricky SQL Test: Part 1

Not long ago I went out looking for some freelance work to do in my spare time.  I found a list of “the top destinations for freelance work.”  I picked one of them and signed up.  I made it thought the initial screening, then it was on to THE TEST.  This is a bit of an “Ohh crap” moment.  In technology and I.T. It is common practice to have applicants take tests.  You can tell much about your prospective employer by these test.  Some of them give you tests relative to the job they are interviewing for.  Others give you tests which are unnecessarily difficult.  I’ve found employers in the second usually do this for two reasons. One, they want to test how you solve problems and come to conclusions.  Two, they are hiring for a low or entry level position.  Since people applying for these positions don’t generally have much experience to promote, so they are given difficult tests.

In the first of a three article series I will review some of the tests I’ve encountered.  The tests are for SQL.  The platform for these particular tests is MySQL.

The first test looks at calculating H-Indexes.  Don’t worry, I didn’t know what an H-Index was when I took this test either.  If you care to read up before going  any further check out H-Indexs according to Wikipedia.

The Test:

You are given two tables, author and publication, with the following structure:

CREATE TABLE `character` (
 `id` INT NOT NULL,
 `name` VARCHAR(30) NOT NULL,
 UNIQUE INDEX `id` (`id`)
);

CREATE TABLE `location`
(
  `characterId` INT NOT NULL,
  `locationName` VARCHAR(50) NOT NULL,
  `visited` INT NOT NULL,
  UNIQUE INDEX `IX_Location` (`characterId`, `locationName`)
);

insert into `character` (`id`, `name`) values (1, 'Homer');
insert into `character` (`id`, `name`) values (2, 'Marge');
insert into `character` (`id`, `name`) values (3, 'Bart');
insert into `character` (`id`, `name`) values (4, 'Lisa');
insert into `character` (`id`, `name`) values (5, 'Maggie');

insert into `location` (`characterId`, `locationName`, `visited`) values (1, 'Springfield Nuclear Plant', 30);
insert into `location` (`characterId`, `locationName`, `visited`) values (1, 'Shelbyville', 12);
insert into `location` (`characterId`, `locationName`, `visited`) values (1, 'Moes Tavern', 5);
insert into `location` (`characterId`, `locationName`, `visited`) values (1, 'Kwik-E-Mart', 3);
insert into `location` (`characterId`, `locationName`, `visited`) values (3, 'Krusty Burger', 0);
insert into `location` (`characterId`, `locationName`, `visited`) values (4, 'Springfield Elementary', 2);
insert into `location` (`characterId`, `locationName`, `visited`) values (4, 'The Jazz Hole', 2);

Records in the table character represent characters.  Records in the table location represents a location visited by a character from the character table.  For each character, the number of locations visited is known.

The H-index of a character is the largest number H such that the character has visited at least H locations, each of which has been visited at least H times.

Write a SQL query that returns a table containing all the characters (characterId and name) appearing in the table character and their respective H-indices (hIndex).  The table should be ordered by h_index (In descending order), characterId (In descending order).

 characterId | characterName | hIndex
-------------+---------------+---------
           1 | Homer         |       3
          15 | Lisa          |       2
          42 | Bart          |       0
          24 | Maggie        |       0
          12 | Marge         |       0

In this example, considering the locations visited by Homer, no four locations have been visited four times or more, so Homers’s H-Index has to be lower than 4.  However, there are at lest three locations that have been visited three times or more (In fact, there are four such locations: Springfield Nuclear Plant, Shelbyville, Moes Tavern and Kwik-E-Mart).  Therefore, Homer’s H-Index is 3.

The author Double has published one title (Single) that has been cited once, so Double’s H-Index is 1.

Lisa has visited two locations (Springfield Elementary and The Jazz Hole) twice, so Lisa’s H-Index is 2.

The remaining characters have not visited anything, so they should not appear in the result table.  Or appear with a value of 0.