Interview Question difficulty

k2788

I was given this question on Hacker-rank as a pre-screening interview test

Two words are matched if they are anagrams.
Given a set of words, print out all matched words.

- Each set of words should be printed on a separate line.
- Words that are not matched should not be printed.
- The output should be alphabetically ordered across each line and within each line.

Input : "lamp", "palm", "finger", "deal", "elbow", "fringe", "silent", "teaching", "below", "bowel",

Expected output :

lamp palm
finger fringe
below bowel elbow

On first glance, how difficult would you class this question ?

This was one of two code questions (the other is write a method to check if two unsorted string arrays are equal) and two multiple choice questions about MultiThreading. The test was 90 minutes.

I am not worried about the solution but If anyone is interested, here was my attempt.

public static void main(String[] args) {
 
        String[] testArray2 = { "lamp", "palm", "finger", "deal", "elbow",
                "fringe", "silent", "teaching", "below", "bowel", };
     
        matchingWords(testArray2);
 
    }
 
    private static matchingWords(String[] input) {
 
        /*  1. Loop through String array to find anagrams
            2. Add all anagrams to a LinkedHashSet (to remove duplicates)
            3. Convert LinkedHashSet to array of Strings
            4. Traverse to print out sets of anagrams
        */
         
        LinkedHashSet<String> set1 = new LinkedHashSet<>();
         
        for (int i = 0; i < input.length; i++) {
             
            for (int j = i + 1; j < input.length; j++) {
 
                boolean isMatch = isAnagram(input[i], input[j]);
 
                if (isMatch == true) {
                    set1.add(input[i]);
                    set1.add(input[j]);
                }
            }
        }
         
        System.out.println("LinkedHashSet : " + set1);
         
        //  This will output : [lamp, palm, finger, fringe, elbow, below, bowel] 
 
        String[] stringArray = Arrays.copyOf(set1.toArray(), set1.toArray().length, String[].class);

        // Question is unfinished
 
    }
 
    private static boolean isAnagram(String string, String string2) {
 
     // Removing code but method works and returns a boolean 
 
    }
}

Looking back I think the ideal way to solve would be :

Normalize all Strings "abcabcd" into "aabbccd", then create a LinkedHashMap<String, TreeSet<String>> with key the normalized Strings, and value a List (or Set) of the input Strings.

I don't think a single developer in my office would have gotten the answer out correctly. (I am a Junior on a team of web developers) Only someone who is probably working with HashMaps and TreeMaps on a daily basis and who is lucky enough to spot the correct structure would stand any chance.

Personally I felt this was difficult (within the time frame) but maybe I am underestimating the Java developer required skill level.

Talisman

It's a simple enough problem to solve which you will encounter on websites such as exercism.io

I would solve it by first sorting the provided list - by doing so you ensure that the output is in alphabetical order.

Python is so succinct for solving such problems - it's like writing pseudo code:

def key_from_string(s):
    return ''.join(sorted(s.lower()))

word_list = ['lamp', 'palm', 'finger', 'deal', 'elbow',
             'fringe', 'silent', 'teaching', 'below', 'bowel']

results = dict()

word_list.sort()

for word in word_list:
    key = key_from_string(word)
    if key in results:
        results[key].append(word)
    else:
        results[key] = [word]

for key in results:
    if len(results[key]) > 1:
        print(' '.join(results[key]))

Output:

below bowel elbow
finger fringe
lamp palm

14ned

k2788 wrote: »

Personally I felt this was difficult (within the time frame) but maybe I am underestimating the Java developer required skill level.

Dunno, seems pretty bread and butter to me. And easily doable within the time limit. You mention lack of awareness of hash maps, but any competent fresh graduate ought to know all about hash maps.

Harder tests which I've also seen have been graph colouring problems, which tend to go NP hard at scale and you need to have memorised the polynomial graph algorithm shortcuts for the various special cases. That sort of interview question would be asked by Google during its standard interview, for example.

Niall

k2788

14ned wrote: »

Dunno, seems pretty bread and butter to me. And easily doable within the time limit. You mention lack of awareness of hash maps, but any competent fresh graduate ought to know all about hash maps.

Harder tests which I've also seen have been graph colouring problems, which tend to go NP hard at scale and you need to have memorised the polynomial graph algorithm shortcuts for the various special cases. That sort of interview question would be asked by Google during its standard interview, for example.

Niall

I wouldn't be so sure a graduate would find this problem easy regardless of expertise in hashmaps, although I may be very wrong. Obviously there are A+ students in every class but after a few months work in role that doesn't use Java day in - day out, the ability to solve these types of problems on the spot under pressure slips away quickly.

I am certain that none of the graduates I know from the springboard course would be able to complete it.

As for the graph coloring I wouldn't have any idea even where to start !

Either way, there is no point in making excuses if this is the required java level and I'm happy that I am aware of this now and not when Im desperately looking for a new job. Hopefully other graduates can take from this too.

Better get going on exercism.io

Talisman

k2788 wrote: »

I am certain that none of the graduates I know from the springboard course would be able to complete it.

I wouldn't equate a candidate who completed a springboard course with one who completed an undergraduate degree. The courses undertaken are two different beasts.

In my experience some springboard graduates think that completing the course is mission complete when in reality they are likely to be out of their depth unless they have been doing additional study which would have fallen outside the bounds of their course.

Software developers need to be able to break down concepts into smaller problems and solve them with code. To solve the problem you write an algorithm. To be successful it’s essential to know how to write algorithms, work with data structures and be able to apply the fundamentals of Computer Science.

Big-O complexities of common algorithms used in Computer Science

After completing the course how familiar are you with data structures like trees, algorithms and recursion?

14ned

k2788 wrote: »

I am certain that none of the graduates I know from the springboard course would be able to complete it.

As for the graph coloring I wouldn't have any idea even where to start !

That doesn't reflect well on the Springboard course, then. Makes me think they're just training in cheap low quality workers to make Ireland more into a low cost offshoring centre than it already is.

I'll put this another way, in C++ we've asked fresh graduates to implement the three main types of hash map on the whiteboard. Often they don't know that there are three main types because compsci degrees are so lousy in this country, so we usually need to explain the difference between sparse, dense and chained implementations. The better candidates make a reasonable stab at all three after being described to them, and if they do, they get hired. Exceptional (usually self taught) candidates can tell us all about each in detail, at which point we normally have decided to hire them with a golden handshake without seeing their usually excellent code. Truly exceptional candidates would rubbish the notion of a hash map altogether, and get into the continuum of implementation between the many forms of associative mapping in general. Not seen one of those yet though.

There is a huge gap between the top 1% and the top 5% in fresh graduates, and then another huge gap between the top 5% and the rest. I know this sucks, but the great thing about compsci is you can markedly self improve easier than almost any other profession. The right proactive "go getter" attitude is the single biggest determinant of great candidates, not where they studied, IQ level, or any other factor. Great graduates are great despite their course, rather than because of it. And I've known many great engineers who were not intellectually gifted, but were hard workers who applied themselves relentlessly until they got there.

Niall

Dubba

One thing that might catch people out is that HackerRank will run a series of tests on your code. They don't make these tests visible, only provide a helpful "Terminated due to timeout " message when one of these tests fail.

In my example below pairsSlow() will only pass the first few tests, while pairsFast() will pass all of them. So if anyone was wondering about this error message, it's probably due to the optimization of your algorithm.

This might be obvious to a lot of people, but for Juniors / Grads it could be hard to spot. Especially with a time limit.

    public static void main(String[] args) {

        // There are 3 pairs of integers in the set with a difference of 2: 
        // [5,3], [4,2] and [3,1].

        int[] arr = {1, 5, 3, 4, 2, 5};
        pairsFast(2, arr));
    }

    static int pairsSlow(int target, int[] array) {
        Arrays.sort(array);
        int count = 0;
        for (int i = 0; i < array.length; i++)
            for (int j = i + 1; j < array.length; j++)  // O(n^2) 
                if (array[j] - array[i] == target)
                    count++;
        return count;
    }

    static int pairsFast(int target, int[] array) {
        Set<Integer> numSet = new HashSet<>();
        for (int i = 0; i < array.length; i++)          // O(n) 
            numSet.add(array[i]);

        int count = 0;
        for (int i = 0; i < numSet.size(); i++)
            if (numSet.contains(array[i] - target))
                count++;
        return count;
    }

fergalr

14ned wrote: »

I'll put this another way, in C++ we've asked fresh graduates to implement the three main types of hash map on the whiteboard. Often they don't know that there are three main types because compsci degrees are so lousy in this country, so we usually need to explain the difference between sparse, dense and chained implementations. The better candidates make a reasonable stab at all three after being described to them, and if they do, they get hired. Exceptional (usually self taught) candidates can tell us all about each in detail, at which point we normally have decided to hire them with a golden handshake without seeing their usually excellent code. Truly exceptional candidates would rubbish the notion of a hash map altogether, and get into the continuum of implementation between the many forms of associative mapping in general. Not seen one of those yet though.

This is just silly.
The idea that compsci degrees in the country are lousy because people don't know the "three main types of hash map".

I bet you are missing out on a lot of great candidates.

I'm actually in favor of asking people problem-solving questions in interviews, whiteboard coding etc; but this is crossing the line to where you are asking trivia.

As is this:

14ned wrote: »

Harder tests which I've also seen have been graph colouring problems, which tend to go NP hard at scale and you need to have memorised the polynomial graph algorithm shortcuts for the various special cases.

Also silly stuff, IMO. The idea that someone would go and 'memorize a bunch of special cases'.

You can't really think this is the best basis to hire on?
Surely it's really expensive to end up turning down great candidates who don't memorize all this stuff?

counterpointaud

I don't think it's hugely difficult to be honest, and you don't need to have knowledge of loads of data structures to have a stab at it, but it does require a bit of thought.

What does "The output should be alphabetically ordered across each line and within each line" mean though? That the words in the rows should be ordered alphabetically, and also the column, or what?

Anyway, here is an implementation in sort of functional-ish style Javascript, to show how it can be approached without knowledge of a lot of data structures if you break it down enough. If you are not familiar with the => syntax, those are functions, and won't run until invoked.

const inputArray = [
  'lamp', 'palm', 'finger', 'deal', 'elbow',
  'fringe', 'silent', 'teaching', 'below', 'bowel'
];

/* Get a key which is the alphabetically sorted chars of the string */
const getKey = str => str.split('').sort().join();

/* Join array of strings to one string, with spaces between */
const arrayToString = arr => arr.join(' ');

/* Check array has more than one element */
const hasMatch = v => v.length > 1;

/* Log string to console */
const logRow = row => console.log(row);

/*
  Build an object with keys which are the sorted string passed,
  and values that are sorted arrays of the strings that are the same
  as that key when the characters are sorted alphabetically
*/
const concatToSortedList = (memo , str) => {
  const key = getKey(str);
  return {
    ...memo,
    [key]: (memo[key] || []).concat(str).sort()
  }
};

/* Compose the above together */
const findAnagrams = (strings) => {
  return Object.values(strings.reduce(concatToSortedList, {}))
      .filter(hasMatch)
      .map(arrayToString)
      .map(logRow);
};

findAnagrams(inputArray);

14ned

fergalr wrote: »

This is just silly.
The idea that compsci degrees in the country are lousy because people don't know the "three main types of hash map".

I often wonder what on earth they are teaching there. I get the argument that they want to teach the theory above the practice, the universally relevant stuff, but fundamental theory like optimising data layout and access patterns in exchange for latency just doesn't seem to be taught. If it is, then I see little evidence of it being considered important.

I bet you are missing out on a lot of great candidates.

I look for candidates who self improve over time via hard work and have a natural curiosity about the divergence between algorithms and reality. I'll take almost any evidence, if there is hard-to-fake supporting proof.

I'm actually in favor of asking people problem-solving questions in interviews, whiteboard coding etc; but this is crossing the line to where you are asking trivia.

If you re-read my statement, I wasn't talking about what I'd do. I was talking about what some multinationals do.

Also silly stuff, IMO. The idea that someone would go and 'memorize a bunch of special cases'.

I once had an interview at Bloomberg New York which had the following rough layout:

Hour 1: Explain time and space complexities for randomly chosen functions from the C++ 11 STL and for each of the three major implementations in particular (tip: if you hadn't memorised these by heart, you were sunk).

Hour 2: Math puzzle solving which involved a lot of recursing to infinity to solve (tip: unless you recently took your maths degree, you were sunk). I remember one was taking pi to the power of the square root of minus 1, or something like that. You had to solve six of these in sixty minutes.

Hour 3: Data layout and access pattern tuning for the recent Intel Xeon CPUs and motherboards as used in Bloomberg terminals (tip: if you hadn't memorised these by heart, you were sunk).

They threw me out after hour three as clearly an inferior human being. And I should mention that this was for a top end role, very well paid, it was no graduate position.

But you are very, very wrong that tech multinationals don't interview on the basis that candidates have memorised a bunch of special cases. I've seen it frequently when interviewing with them. They assume this, because the ones really keen to get in have been swotting up and rote learning for weeks beforehand. So if you haven't done the same, you look inferior.

Niall

smacl

14ned wrote: »

I once had an interview at Bloomberg New York which had the following rough layout:

Hour 1: Explain time and space complexities for randomly chosen functions from the C++ 11 STL and for each of the three major implementations in particular (tip: if you hadn't memorised these by heart, you were sunk).

Hour 2: Math puzzle solving which involved a lot of recursing to infinity to solve (tip: unless you recently took your maths degree, you were sunk). I remember one was taking pi to the power of the square root of minus 1, or something like that. You had to solve six of these in sixty minutes.

Hour 3: Data layout and access pattern tuning for the recent Intel Xeon CPUs and motherboards as used in Bloomberg terminals (tip: if you hadn't memorised these by heart, you were sunk).

Strange interview requirements. Any of the high end development stuff I've seen in recent years has tended to be specialist, combining a good fluency in a preferred programming language with an in-depth domain knowledge, e.g. C++ and OpenCV and QT, CUDA and meshing with a background in combinatorial geometry, C# and machine learning with a civil engineering background. For a graduate, you're hiring someone you're going to build into an asset, for a high end developer they need to be productive from day one. Highly productive developers in any specific context will be specialists rather than generalists. Personally, if I was conducting an in-depth technical interview, it would be open book as that reflects the working environment. Memorising reams of technical information is not a great use of anyone's time.

FWIW, all the really good programmers that I've known over the years have programmed as a hobby in addition to any academic qualifications. I'd agree a degree in computer science isn't a particularly strong indicator of programming ability. A simple test I've given candidates in the dim and distance past that worked well was to write a game of noughts and crosses in four hours or less.

14ned

smacl wrote: »

Strange interview requirements.

Imagine me in the interview! Some time in hour three I remember I started laughing at the ridiculousness of it. They got well annoyed with me. I told them it was European humour thing, and they shouldn't take it as in any way important.

Memorising reams of technical information is not a great use of anyone's time.

FWIW, all the really good programmers that I've known over the years have programmed as a hobby in addition to any academic qualifications. I'd agree a degree in computer science isn't a particularly strong indicator of programming ability. A simple test I've given candidates in the dim and distance past that worked well was to write a game of noughts and crosses in four hours or less.

I'm in pretty strong agreement.

I don't care about candidates having a degree personally. Irrelevant. I do care if they have reading and writing skills matching those of a graduate though. And I'm very strongly biased towards those with proven open source contributions. If I'm facing twenty CVs and only one has proven open source work, they'll be at the lead until F2F, which are mainly for checking they can be worked with and aren't psychopaths and don't have excessive hygiene problems.

Niall

fergalr

14ned wrote: »

If you re-read my statement, I wasn't talking about what I'd do. I was talking about what some multinationals do.

I took issue with you complaining graduates didn't know the "the three main types of hash map" when you interview them. This is a very arbitrary filter. I probably wouldn't pass it :-)

14ned wrote: »

I look for candidates who self improve over time via hard work and have a natural curiosity about the divergence between algorithms and reality. I'll take almost any evidence, if there is hard-to-fake supporting proof.

That sounds laudable; but the more you filter on noise (arbitrary knowledge) the less you can filter on "hard work and natural curiosity" or whatever.

You can argue that everyone should know that hash map stuff; I disagree, and given that you're filtering on noise.

14ned wrote: »

I often wonder what on earth they are teaching there. I get the argument that they want to teach the theory above the practice, the universally relevant stuff, but fundamental theory like optimising data layout and access patterns in exchange for latency just doesn't seem to be taught. If it is, then I see little evidence of it being considered important.

The thing is, it's not that generally important for a general CS grad any more.
Most people aren't writing hugely performance-constrained embedded systems any more.
That is now a rare specialty, and too application specific for an undergrad education, IMO.

Its more important to equip them with foundational skills for understanding and thinking about and optimizing systems, and if they need to go down a 'optimizing data layout' rabbit-hole, then they can.

14ned wrote: »

But you are very, very wrong that tech multinationals don't interview on the basis that candidates have memorised a bunch of special cases. I've seen it frequently when interviewing with them. They assume this, because the ones really keen to get in have been swotting up and rote learning for weeks beforehand. So if you haven't done the same, you look inferior.

I'm sure they do this to some extent. They probably shouldn't.

Even then I'd bet its not actually "graph colouring problems, which tend to go NP hard at scale and you need to have memorised the polynomial graph algorithm shortcuts for the various special cases."

Graph coloring problems is esoteric.
I bet if a multinational is asking about something in that domain, it's just a problem solving problem where you can do it without memorizing particular graph coloring algorithms. Genuinely expecting people to memorise shortcut algorithms for special cases of graph coloring is nonsensical.

John_C

14ned wrote: »

mainly for checking they ... don't have excessive hygiene problems.

I would expect this produces a lot of false negatives. Even people with excessive hygiene problems will probably have a wash the morning of an interview.

Tar.Aldarion

>>> sorted('anagram') == sorted('ganaram')
True

There's other python functions that would be just as easy such as counter from the collections library. Second question just sort and compare again.


Most interviews are silly (and have much harder questions) as all people do for them is study interview questions for a few months, do the interview and forget about it.
A lot of them want you to know something you'll never really use (sieve of eratosthenes and so on) or rely on you remembering some API under pressure in an interview, when realistically you'll never have to remember a lot of the stuff as we all work on computers. Even worse when they say you can't use functions in the language and have to code them yourself. It's like a minigame you do to get jobs. My workplace has no technical written exam at all and get by great.

Donald Trump

Talisman wrote: »

It's a simple enough problem to solve which you will encounter on websites such as exercism.io

I would solve it by first sorting the provided list - by doing so you ensure that the output is in alphabetical order.

Python is so succinct for solving such problems - it's like writing pseudo code:

def key_from_string(s):
    return ''.join(sorted(s.lower()))

word_list = ['lamp', 'palm', 'finger', 'deal', 'elbow',
             'fringe', 'silent', 'teaching', 'below', 'bowel']

results = dict()

word_list.sort()

for word in word_list:
    key = key_from_string(word)
    if key in results:
        results[key].append(word)
    else:
        results[key] = [word]

for key in results:
    if len(results[key]) > 1:
        print(' '.join(results[key]))

Output:

below bowel elbow
finger fringe
lamp palm

You call that succinct? It's two lines in Perl :P

push@{$r{join"",sort split//}},$_ for qw/lamp palm finger deal elbow fringe silent teaching below bowel/;
$#{$r{$_}}&&print"@{$r{$_}}\n"for keys%r

Output

elbow below bowel
finger fringe
lamp palm

h57xiucj2z946q

Scala:

Seq("lamp", "palm", "finger", "deal", "elbow", "fringe", "silent", "teaching", "below", "bowel")
  .groupBy(_.sorted)
  .filter(_._2.size > 1)
  .toSeq
  .reverse
  .foreach(x => println(x._2.mkString(" ")))