6
\$\begingroup\$

I recently had a potential employer send me a programming test to read through a file and write to another file all the words that were anagrams (two or more words containing the same letter). The following code worked on my machine, but the recruiter told me I didn't pass the test without giving me any feedback. Since he won't tell me why, I'm hoping someone here will. I am posting my code followed by one of the test files I was given. What's wrong?

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class AnagramSearch {
    public static void main(String[] args) {
        if (args.length != 2) {
            System.out.println("Usage: java -cp . AnagramSearch <location of input file> <location of output file>");
            System.out.println("Program ending.");
            System.exit(0);
        }

        String input = getInput(args[0]);
        writeAnagrams(input, args[1]);
    }

    public static String getInput(String inputFile) {
        String inputString = "";

        try {
            BufferedReader reader = new BufferedReader(new FileReader(inputFile));
            String line;
            while ((line = reader.readLine()) != null) {
                if (line.endsWith(".")) {
                    line = line.substring(0, line.length() - 1);
                }

                if (line.contains(";")) {
                    line += ";";
                }

                if (line.contains(" ")) {
                    line += " ";
                }
                if (line.contains(", ")) {
                    line += ", ";
                }

                inputString += line;
            }

            reader.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println("Input file not found.  Please make sure you entered the correct file location.");
            System.out.println("Program ending.");
            System.exit(0);
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("IOException thrown.");
            System.out.println("Program ending.");
            System.exit(0);
        }

        return inputString;
    }

    public static void writeAnagrams(String inputString, String outputFile) {
        String[] stringArray = null;

        if (inputString.contains(";")) {
            stringArray = inputString.split(";");
        } else if (inputString.contains(", ")) {
            stringArray = inputString.split(", ");
        }

        Map<String, String> anagrams = new HashMap<String, String>();
        for (int i = 0; i < stringArray.length - 1; i++) {
            if (! anagrams.keySet().contains(stringArray[i])) {
                for (int j = i + 1; j < stringArray.length; j++) {
                    if (isAnagram(stringArray[i], stringArray[j])) {
                        anagrams.put(stringArray[i], stringArray[j]);
                    }
                }
            }
        }

        Iterator<String> iterator = anagrams.keySet().iterator();
        try {
            PrintWriter printWriter = new PrintWriter(new FileWriter(outputFile));
            while (iterator.hasNext()) {
                String nextString = iterator.next();
                printWriter.println(nextString + " " + anagrams.get(nextString));
            }
            printWriter.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            System.out.println("Error locating output file.");
            System.out.println("Program ending.");
            System.exit(0);
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("IO Error.");
            System.out.println("Program ending.");
            System.exit(0);
        }
    }

    public static boolean isAnagram(String firstWord, String secondWord) {
        char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
        char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
        Arrays.sort(word1);
        Arrays.sort(word2);
        return Arrays.equals(word1, word2);
    }
}

The test file:

come, get, give, go, keep, let, make, put, seem, take, be, do, have, say, see, send, may, will, about, across, after, against, among, at, before, between, by, down, from, in, off, on, over, through, to, under, up, with, as, for, of, till, than, a, the, all, any, every, no, other, some, such, that, this, I, he, you, who, and, but, or, if, though, while, how, when, where, why, again, ever, far, forward, here, near, now, out, still, then, there, together, well, almost, enough, even, little, much, not, only, quite, so, very, south, east, west, please, yes.
account, act, art, attack, attempt, attention, attraction, authority, back, balance, base, behaviour, belief, birth, bit, bite, blood, blow, burn, burst, business, butter, canvas, care, cause, chalk, chance, change, cloth, coal, colour, comfort, cook, copper, copy, cork, cotton, cough, country, cover, crack, credit, crime, crush, cry, current, curve, damage, danger, daughter, day, death, debt, decision, degree, design, desire, destruction, detail, development, digestion, direction, discovery, discussion, disease, disgust, distance, distribution, division, doubt, drink, driving, dust, earth, edge, education, effect, end, error, event, example, fact, fall, family, father, fear, feeling, fiction, field, fight, fire, flame, flight, flower, fold, food, force, form, grain, grass, grip, group, growth, guide, harbour, harmony, hate, hearing, heat, help.
page, pain, paint, paper, part, paste, payment, peace, person, place, plant, play, pleasure, point, poison, polish, porter, position, powder, power, price, print, process, produce, profit, property, prose, protest, pull, push, quality, question, rain, range, rate, ray, reaction, request, respect, rest, reward, rhythm, rice, river, road, roll, room, rub, rule, run, salt, sand, scale, science, sea, seat, secretary, selection, self, sense, servant, sex, shade, shake, shame, shock, side, sign, silk, sky, sleep, slip, slope, smash, smell, smile, smoke, sneeze, snow, soap, society, son, song, sort, sound, soup, space, stage, start, statement, steam, steel, step, stitch, stone, stop, story, stretch, swim, system, talk, taste, tax, teaching, tendency, test, theory, thing, thought, thunder, time, tin, top, touch, trade, transport, trick, trouble, turn, twist, unit, use, value, verse, vessel, view, voice, walk, war, wash, waste, water, wave, wax, way, weather, week, weight, wind, wine, winter, woman, wood, wool, word, work, wound, writing, year.
angle, ant, apple, arch, arm, army, baby, bag, ball, band, basin, basket, bath, bed, bee, bell, berry, bird, blade, board, boat, bone, book, boot, bottle, box, boy, brain, brake, branch, brick, bridge, brush, bucket, bulb, button, cake, camera, card, cart, carriage, cat, chain, cheese, chest, chin, church, circle, clock, cloud, coat, collar, comb, cord, cow, cup, curtain, cushion, dog, door, drain, drawer, dress, drop, ear, egg, engine, eye, face, farm, feather, finger, fish, flag, floor, fly, foot, fork, fowl, frame, garden, girl, glove, goat, gun, hair, hammer, hand, hat, head, heart, hook, horn, horse, house, island, jewel, kettle, key, knee, knife, knot, leaf, leg, library, line, lip, lock, map, match, moon, mouth, muscle, nail, neck, needle, nerve, net, nose, nut, office, orange, oven, parcel, pen, pencil, picture, pig, pin, pipe, plane, plate, plough, pocket, pot, potato, prison, pump, rail, rat, receipt, ring, rod, roof, root, sail, school, scissors, screw, seed, sheep, shelf, ship, shirt, shoe, skin, skirt, snake, sock, spade, sponge, spoon, spring, square, stamp, star, station, stem, stick, stocking, stomach, store, street, sun, table, tail, thread, throat, thumb, ticket, toe, tongue, tooth, town, train, tray, tree, trousers, umbrella, wall, watch, wheel, whip, whistle, window, wing, wire, worm.
able, acid, early, elastic, electric, equal, fat, fertile, first, fixed, flat, free, full, general, good, great, grey, hanging, happy, hard, healthy, high, hollow, important, kind, like, living, long, male, married, material, medical, military, natural, new, normal, open, parallel, past, poor, possible, present, private, probable, quick, quiet, ready, red, regular, responsible, right, round, same, sticky, stiff, straight, strong, sudden, sweet, tall, thick, tight, tired, true, violent, waiting, warm, wet, wide, wise, yellow, young.
awake, bad, bent, bitter, blue, certain, cold, complete, cruel, dark, dead, dear, delicate, different, dirty, dry, false, feeble, female, foolish, future, green, ill, last, late, left, loose, loud, low, mixed, old, opposite, public, rough, sad, safe, secret, short, shut, simple, slow, small, soft, solid, special, strange, thin, white, wrong.
\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

Inefficient algorithm

Your algorithm takes \$O(n^2)\$ time, where \$n\$ is the number of words. You could do this in \$O(n)\$ time with a small modification.

Instead of storing words into your HashMap with the word as the key, you should store each word with its sorted string as the key. That way, for each new word, you simply sort the word and see if the sorted word exists in the HashMap already. If it does, you can add the word to the anagram list.

The only detail that remains is to also add the word from the HashMap when you find an anagram for it (and to only add it once even if there are multiple anagrams for it). So for example, if you had the words asp spa sap, you would end up with each word added to the anagram list once.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.