Recursion and Sort - should be asked everytime

I am surprised with my new manager because he is so technical (He can code). He is trying to come up with interview coding questions to test candidates and has asked me to look at it. If I don't know any better he is trying to test me too. I did an interview with coding questions before and most of the questions that i have encountered are mostly about recursion and sort. Recursion and sort questions are very reasonable to ask a candidate who is going to code because recursion and sort  will be mostly all over any code base. So when my manager asked me to look at his coding test in the back of my mind i would suggest a question about recursion and sort.


When i was preparing myself for such an interview (the one with a coding question) I have found this http://codingbat.com/ as a great place for practice..much like crossword puzzle.  After trying a few questions at codingbat.com, I thought i can come up with questions like that too.

Here is a sample question that i came up with:
1. Using java, sort an array of object Foo (class below) with a performance of n log n that preserves the order of equal elements.
   class Foo {
      public Foo[] subordinateFoo;
      public int fooValue;
   }

   - This question is a give away question. First, if you are a java programmer and have read the Arrays.sort API description it uses mergesort - which means that it is a stable sort (preserves the order of equal elements) and has a guaranteed performance of n log n. So the solution here is to just use Arrays.sort or Collections.sort and have the object implement the Comparable interface.
2. Using the same Foo object (class above) write code that will add all the fooValue of the member subordinateFoo (which is an array of Foo) and it's own fooValue
    - This question can be implemented in several different ways, but it is to test if the programmer understands recursion and how to go about coding recursive logic.


Here is a sample answer that i come up with for my questions above:

 import java.util.Arrays;
public class HelloWorld{     
     public static int totalFooValue = 0;
     public static void main(String []args){
       Foo leadFoo = new Foo();
       leadFoo.fooValue = 600;
       Foo foo1 = new Foo(); 
       foo1.fooValue = 500;       
       Foo foo2 = new Foo();    
       foo2.fooValue = 400;
       Foo foo3 = new Foo();
       foo3.fooValue = 300;
       Foo foo4 = new Foo();
       foo4.fooValue = 200;
       Foo foo5 = new Foo();
       foo5.fooValue = 100;
       foo3.subordinateFoo = new Foo[] {foo4, foo5};       
       leadFoo.subordinateFoo = new Foo[] {foo1, foo2, foo3};
       sortFooBasedOnValue(foo3.subordinateFoo);
       sortFooBasedOnValue(leadFoo.subordinateFoo);
       System.out.println(calculateTotalFooValue(leadFoo));
     }
     
    public static int calculateTotalFooValue(Foo foo) {
      System.out.println("Adding foo " + foo.fooValue);
      totalFooValue = totalFooValue + foo.fooValue;            
      if(foo.subordinateFoo != null){
          for (int i = 0;i < foo.subordinateFoo.length; i++){              
          calculateTotalFooValue(foo.subordinateFoo[i]);
           }             
      }
     return  totalFooValue;
   }
   
   public static void sortFooBasedOnValue(Foo[] foos) {
       Arrays.sort(foos);
   } 
}


class Foo implements Comparable{
      public Foo[] subordinateFoo;
      public int fooValue;      
 public int compareTo(Object arg0){
     Foo foo1 = (Foo) arg0;
     int returnInt = 0;
     if (this.fooValue == foo1.fooValue){
         returnInt = 0;
     } else if(this.fooValue > foo1.fooValue){
         returnInt = 1;
     }else if(this.fooValue < foo1.fooValue){
         returnInt = -1;
     }
    return returnInt;
 }
}


Comments

Post a Comment

Popular posts from this blog

OAuth 1.0a Request Signing and Verification - HMAC-SHA1 - HMAC-SHA256

Image
This is a security project that I did this Fall semester. I was interested in why the OAuth1.0a specification did not require you to sign a request using RSA-SHA1 or any RSA algorithm. The first issue that I found is where would you store your private keys in a javascript client? - as a javascript encrypted file ? from the browser ?  - that will be a security hole if you allow javascript to get private keys. These are some of the questions that got me asking and which I cannot find answers to for now. OAuth 1.0a Signature Signing and Verification using JavaScript Implementation Background The OAuth specification tries to define an API authentication method that allows consumer websites or applications to access protected API Resources from a Service provider. The advantage that OAuth provides is that the user of the website or application is not required to disclose their credentials to their service provider. Another advantage of using OAuth to authenticate is that it does not
Read more

Spark DataFrame - Array[ByteBuffer] - IllegalAurmentException

IllegalArgumentException - ByteBuffer - Spark DataFrame I was processing a several million documents (~ 20 million) in which we need to extract the NLP features using NLP4J, OpenNLP, and WordNet. The combination of the three NL features blows up each record to 11 times its original size. We are using all three because we do not know yet what feature sets will be helpful to us. The original dataset is in parquet files in HDFS (16 partitions). I thought that was convenient just use withColumn and pass a UDF (User Defined Function) on the column where it needs those features. withColumn adds the calculated column back to the DataFrame. So I created the spark job (I am on Spark 1.5.2-cdh5.5.2)for the above, and things started to get nasty. I am blowing up the ByteBuffer array on the in-memory columnar storage. This is the exception that I am getting. There seems to be no reference in my code in this stack trace. java.lang.IllegalArgumentException at java.nio.ByteB
Read more

Gensim Doc2Vec on Spark - a quest to get the right Vector

Ever since I joined the R & D group we have been doing a lot of cool things, like trying IBM Watson (see previous blog entry). Now we are doing a lot of Natural language processing.  We wanted to compare the similarity of two documents. There is this excellent project Gensim ( doc2vec ) that easily allow to you to translate large blocks of text to a fixed length feature vector to make comparisons. Here is the link to the  original paper  from some people from Google that explains the approach. In essence, they wanted to find a representation that will overcome the weaknesses of the bag of words model. The doc2vec approach proves to be a reliable approach to comparing similarities of documents because it takes into consideration the semantics and the order of the word in context. So with that, we wanted to use it for a corpus of 26 million documents. Calculating the doc2vec for 26 million documents is not a small task, so we need to process it in Spark. The problem is that there
Read more