The question

Given a binary tree, check whether it’s a binary search tree or not.

My solution

I cheated a little in this question because I didn’t remember what a binary search tree is. After checking wikipedia I found the characteristic of a BST:

– The left subtree of a node contains only nodes with keys less than the node’s key.

– The right subtree of a node contains only nodes with keys greater than the node’s key.

– The left and right subtree each must also be a binary search tree.

– Each node can have up to two successor nodes.

– There must be no duplicate nodes.

The question

Given a source word, target word and an English dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all intermediate words being valid English words. Return the transformation chain which has the smallest number of intermediate words.

The solution

There are two parts to solving this problem. First we need to create a graph of the dictionary where each edge corresponds to a valid transformation of a word. We can represent this graph using a hash table (an object in JS). Then we do a breadth first search on this graph and that will give us the most efficient path.

The question

Given a linked list of integers and an integer value, delete every node of the linked list containing that value.

The solution

The tricky part about this problem is taking care of the edge cases. You have to go through all the elements in the list, so the efficiency is O(n).

• Initialize one variable(lastGood) to null
• Initialize one variable(first) to the head
• Check the first element on the linked list(current)
  • If it is not the number you are looking for assign lastGood=current and move current to the next node
  • If it is the number then check if lastGood has a value assigned
    • if lastGood doesn’t have a value it means we want to remove the first item so assign first to current.next
    • if lastGood has a value then assign lastGood.next to current.next
• Repeat for all elements

The question

Given an integer array, one element occurs even number of times and all others have odd occurrences. Find the element with even occurrences.

My answer

The first thing I thought of was using XOR, but then I realized that I am looking for the even number so it won’t actually work. My next idea was to use a hashtable:

1 – Start on the first elements and create a hashtable with the number of times each character is found

2 – Look for the even number in the hashtable

The question

Given a sorted array that can include duplicates find the number of times that a given number appears in the array.

The solution

The first thing that came to my mind was to do a binary search for the element and then check how many times it appears to the left and how many times it appears to the right. This has the drawback that if the array has a large number of appearances for that number then the performance might be greatly degraded because we would have to linearly search left and right.

To overcome this limitation we would need to do a custom binary search that searches for the first occurrence of a value and another that searches for the last element. Once we have those indexes we can find the difference and that is the number of appearances:

Since Android moved to Gradle I tought it would be a good idea to renew my post on building an Android app from scratch to use Gradle instead of ant.

The first thing we need to do is to create the folder structure for our project:

1
2
3
4
5
6
7
8
Project/
  |---build.gradle
  |---src/
       |---main/
            |---AndroidManifest.xml
            |---res
            |---java
                  |---src (Code goes here)

I made this little open source library for Android that I want to consume from an app I’m building. I have the easy option of checking in the .aar file into my repository as explained in my article but I want to do things right so I’m going to try to publish my app to central repository.

To get started you have to create a jira account and then create a ticket so they can create a project for you. There are a few mandatory fields:

– Summary: I am not sure what I was supposed to enter here so I just entered the name of my project. (conversion-graph)

– Group Id: The top level group you are going to use. (com.ncona)

– Project URL: I entered URL to the project on github. (https://github.com/soonick/conversion-graph)

– SCM URL: The same URL but with a .git extension (https://github.com/soonick/conversion-graph.git)

The question

Given an input string, reverse all the words. To clarify, input: “Interviews are awesome!” output: “awesome! are Interviews”. Consider all consecutive non-whitespace characters as individual words. If there are multiple spaces between words reduce them to a single white space. Also remove all leading and trailing whitespaces. So, the output for ” CS degree”, “CS degree”, “CS degree “, or ” CS degree ” are all the same: “degree CS”.

I have an Android project in gradle where I want to use a library packaged in an aar file. After some research I found the easiest way to consume it is by adding a flatDir repository to your build.gradle file.

1
2
3
4
5
repositories {
  flatDir {
    dirs 'libs'
  }
}

You probably already have a repositories section in your build.gradle file so you will only need to add the flatDir section. Also, make sure that you are adding it as a top level. The first time I tried I was adding it to the repositories section inside of buildscript and it was not working.

After specifying the repository you need to add your aar file inside the libs directory and reference it from the dependencies section inside build.gradle (also make sure it is top level):

1
2
3
dependencies {
  compile 'com.ncona.conversiongraph:conversion-graph:1.0@aar'
}

Now you can use your library within your app.

The question

Generate all permutations of a given string.

My solution

This is a question that I had been asked before and I wasn’t able to solve in the duration of an interview. I took some time to think about the problem and this is what I came with.

There are going to be n! permutations so that is what I should expect. The permutations of a string of length 1 is the string itself. The permutations for a string of length two is the string and the reversed string. With this in mind I came up with this recursive algorithm: