CoderPad Interview Question

Here we will go through an interview question and answer from a CoderPad interview. For those who don’t know, CoderPad is an online tool that provides an editor, timer, and also the facility for recording software interviews. So, this article is an example of a real live coding interview question – or in other words, a real time, interactive, coding interview. The problem could have been solved in whatever language was chosen from the options – of which there were many. One hour was given to complete the problem, and communication was done through a Google Hangout.

An answer and explanation is also provided in Java – but I really recommend that you try to solve this one on your own – and not just using paper and pencil, but choose a language you’re proficient in and code it up with a proper compiler and everything. It’s not that difficult, and it’s also a good test to see how fast you can come up a solution in your language of choice. Speed is really important here as well because for this test in particular only one hour was given.

Here is the actual question:

import java.io.*;
import java.util.*;

/* 
Suppose you are creating an internal networking site for your company.

You have two data sets to work with. The first data set is the employees at your company, and the second is all the pairs of employees who are virtually friends so far. It does not matter which employee's ID is in which column, the friendships are bidirectional. To get started, you need to represent each data set in code.

Furthermore, you want to know who’s friends with whom. You need to implement a function that, given the employees and friendships as parameters, returns this data in the form of an adjacency list representation. This is a mapping of each employee ID to a list of his/her friends on the site.

So, there are two parameters - the employees and the friendships.  Here's one possible example of the employees input array and the friendships input array:

 String[] employeesInput = {
      "1,Richard,Engineering",
      "2,Erlich,HR",
      "3,Monica,Business",
      "4,Dinesh,Engineering",
      "6,Carla,Engineering"
    };


    String[] friendshipsInput = {
      "1,2",
      "1,3",
      "2,4"
    };

And this would be considered an acceptable form of output for the adjacency list:

# 1: 2, 3
# 2: 1, 4
# 3: 1
# 4: 2
# 6: None
 */

CoderPad Interview Question Answer and Explanation

First things first – what exactly do we want as output? Well, it’s pretty simple – we just want an adjacency list as output – something that looks like this:

# 1: 2, 3
# 2: 1, 4
# 3: 1
# 4: 2
# 6: None

You might have noticed in the adjacency list output above the fact that we are not really concerned with the name or the department of the employees – just the ID’s. So, we can effectively ignore the names and departments in the employeesInput array.

The friendshipsInput array is really the key here. This indicates which employees are friends. So, an entry of “1,2” in the friendshipsInput array means that in the adjacency list output we will want to list both 2 as a friend of 1, and 1 as a friend of 2. That is why in the sample output above there is an entry for “1:2” and “2:1” – that’s what is meant when it says the friendships are “bidirectional” in the instructions above.

Also note that if someone in the employeesInput array does not have any friends (poor guy/girl!) – based on the friendshipsInput array – we will want to output “None” in the adjacency list. An example from above would be employee ID 6 – Carla – who has no friends to show in the friendshipsInput array. So, for the ID of 6, we output “None” in the adjacency list output.

Now, we have a clearer idea of what the problem asks for, so we just need to figure out how to get an efficient solution.

What data structure should we use here?

We also need to store the data somewhere – so before we output an adjacency list, we need to store that data in some sort of data structure. What data structure would be best here?

Perhaps a better question to ask before choosing a data structure is how exactly will we be storing the data?

Let’s think a little bit more about our output here. For each employee ID we basically want to store all of the friendships as a list and then output them. So, it’s sort of a mapping between each employee ID and all of that employee’s friends. Whenever there is a mapping, you should immediately think in terms of a hash table.

It’s a hashtable interview question

Essentially all we need to do for this problem is store the mappings and then retrieve them and output in the form of an adjacency list. So, using data structure terminology, we just need to insert and then lookup – and of course we want those things to be fast! A hash table is perfect for this because it does both of those things in constant time, or O(1). We’re not really concerned with searching for values so we don’t need to use a tree here.

What’s the key in the hash table here?

In this case, the “key” would be the employeeID and the values would be the friendship Id’s. So, we could have some employee Id’s which map to just one other employee ID – indicating just one friendship (like 3 to 1 in the example above), some employee Id’s mapping to multiple friendships (like 2 to both 1 and 4 in the example above), or even some employee ID’s with no mapping – like 6.

A Solution to CoderPad interview question in Java

So, clearly we would need to map each employee ID to potentially more than one other employee ID. What would that look like using a hash table in Java?

Let’s rewrite the adjacency list to make it even clearer what we want exactly:

1 => 2, 3
2 => 1, 4
3 => 1
4 => 2
6 => None

Hopefully the “=>” makes it a bit clearer that “1” will map to “2” and “3”.

Does the order matter?

The order doesn’t really matter here because we just want to list all the friendships. If the order did matter we could use the LinkedHashMap class instead, since that will maintain the friendship id’s in the order in which they were inserted.

Another very important question that you might be having is whether a hash table in Java can have a single key mapping to multiple values, and if so what would that look like? That’s an excellent question – and could be considered the “tricky” part of this question – so pay special attention here.

One way we can do this is to use the HashMap class, with Integer as the key value (the employee ID), and then for the actual mapped value, we can use an ArrayList of integers. So, the “value” from the key->value mapping for our hash table would really be multiple values – an ArrayList of integers.

Here is what that would actually look like in Java – let’s just call it friendsMap:

Map<Integer, ArrayList<Integer>> friendsMap = new   HashMap<Integer, ArrayList<Integer>>();

Multimap example in Java interview question

Worth noting is the fact that the code above is formally known as a multimap – which, from the Wikipedia definition, is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Also, another good thing to be aware of is that there are Java libraries like Guava (built by Google engineers) which provide multimap implementations. But, for the purpose of answering this question in an interview, it’s probably best to just use some code like what’s shown above.

Note that you should be able to come up with the code for this from memory – it really will save you a lot of time, regardless of what language you are using.

Can we overwrite an existing value?

Another excellent question that will arise is whether inserting a value for a given key will overwrite any existing value for that given key. So, for example, if employee ID of 1 already has an entry mapping his friendship to employee ID 2, then will inserting an employee ID of 3 overwrite that entry? Yes, it will actually – so we will have to account for that in our solution.

Let’s go through that piece of code right now to make it clearer.

Let’s say we use employee “1” as our key and we now want to insert his friends. So, we put in “2” as his friend. This is what it would look like:

friendsMap.put(1, 2);

But what if we want to put in another friendship for employee 1? It would look like this:

friendsMap.put(1, 3);

The problem here is that it will overwrite the existing friendship – so there will no longer be a mapping between 1 and 2, just a mapping between 1 and 3. So, what do we do instead? Well, we can just check the hash table for that given employee ID before we insert anything into it. If there is no entry for a particular employee ID, then we can just go ahead and insert that friendship pair.

But, if there is already an entry for a particular employee ID we just retrieve the ArrayList associated with that particular employee ID, add the new friendship mapping to that ArrayList, and then put the ArrayList back in the hash table. So, it would look like this:

Note that here emp2 is assumed to be the id of the friend while emp1 is the key – the employee Id for which we are constructing a friends list:

 ArrayList<Integer> emp1Friends = friendsMap.get(emp1);
 ArrayList<Integer> temp = new ArrayList<Integer>();

if(emp1Friends != null)
{
   emp1Friends.add(emp2);
   friendsMap.put(emp1, emp1Friends);      
   //and then put the array back in the hash table
}

You will see the same code above as in our full solution provided below.

Coderpad Interview Tips

Finally, I want to emphasize that knowing syntax well can really pay off in a timed CoderPad test like this – that is one of the best tips I can give you. Even though you are allowed to look up syntax type questions, knowing it already will save you time. It’s not enough these days to come up with a whiteboard or pseudocode solution – you need to be able to quickly and efficiently do things in the language of your choice.

For instance, when you look at our full solution below, you will see some code that looks like this, where namesList is an array of Strings – and we are just taking the 0th element:

int emp1 = Integer.parseInt(namesList[0]);

In the code above we are just taking a String and converting it to an integer primitive type. But, I think you should know the syntax for things like this by heart for the purpose of an interview – no matter what language you are dealing with. And, if you know you are going to have a CoderPad, HackerRank, or a “live coding” type interview – you will be a lot less nervous if you can do things like this from memory in the language of your choice.

Solutions in other languages to CoderPad interview question

You should be able to run the code below as is in your own Java environment if you want to see how it works, play around, etc. But I also encourage readers to provide solutions in the languages of their choice (C++, Python, Ruby, whatever) in the comments – and I will update the page to share those as well.

import java.io.*;
import java.util.*

class Solution {
 
  public static void main(String[] args) {
    String[] employeesInput = {
      "1,Richard,Engineering",
      "2,Erlich,HR",
      "3,Monica,Business",
      "4,Dinesh,Engineering",
      "6,Carla,Engineering"
    };


    String[] friendshipsInput = {
      "1,2",
      "1,3",
      "2,4"
    };
    
    Map<Integer, ArrayList<Integer>> friendsMap = findFriends(friendshipsInput);
    
    for (String employee : employeesInput) {
      
      int employeeId = Character.getNumericValue(employee.charAt(0));


      System.out.print(employeeId + ": ");
      
      
      ArrayList<Integer> friendsList = friendsMap.get(employeeId);
      
      
      if(friendsList != null)
      {
        for(int friend: friendsList)
        {
          System.out.print(friend + " ");
        }
       System.out.println("");
       
      }
      
      else
      {
        
       System.out.println("None"); 
      }
      
    }
    
  }


  public static Map<Integer, ArrayList<Integer>> findFriends(String[] friendshipsInput)
  {
    //int employeesLength = employeesInput.length;
    int friendsLength = friendshipsInput.length;

    //build hash table for friendshipsInput
    //each key maps to an array of ints
      
    Map<Integer, ArrayList<Integer>> friendsMap = new   HashMap<Integer, ArrayList<Integer>>();
    
      //could use an enhanced for loop here instead
      for (int x = 0; x< friendsLength; x++)
      {
          String entry = friendshipsInput[x];
          
          //get the 2 friends from each entry
          String[] namesList = entry.split(",");  
        
          int emp1 = Integer.parseInt(namesList[0]);
          int emp2 = Integer.parseInt(namesList[1]);
        
        /*
        check for the given employee Id if there is already an
        arraylist in the hashmap and if so then we want to get
        that array list and then we want to just add the friend to that array list and then add the array list back to the hashmap
        
        if that employeeId does not have any associated arraylist - no friendslist - then we create a new arraylist, take the friend and add it to that arraylist and then add the arraylist to the hashmap for that particular employeeid
        
        */
        
          /*check if for each employee there is already
            an arraylist of friends in the hash table */
          ArrayList<Integer> emp1Friends = friendsMap.get(emp1);
          ArrayList<Integer> emp2Friends = friendsMap.get(emp2);
        
          ArrayList<Integer> temp = new ArrayList<Integer>();
          
          ArrayList<Integer> temp2 = new ArrayList<Integer>();
        
          //don't want to overwrite existing element in arraylist
         //so first we get it then we add to it
           
          if(emp1Friends != null)
          {
            emp1Friends.add(emp2);
            friendsMap.put(emp1, emp1Friends);      
            //and then put the array back in the hash table
          }
        
         //if nothing there we can just put it in without
         //fear of overwriting anything:
          else  
          {
            temp.add(emp2);  
            friendsMap.put(emp1, temp);
          }
         
         if(emp2Friends != null)
          {
            //and then put the array back in the hash table  
            emp2Friends.add(emp1);
            friendsMap.put(emp2, emp2Friends);
          }
        
          else
            
          {
             temp2.add(emp1);
             friendsMap.put(emp2, temp2);
          }
        
          //otherwise we know that the array is empty 
          //so we just create a new one and then add it       
      }
  
       return friendsMap;
}
}




Follow Varoon Sahgal, author, on Google Plus