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:

The question

There is an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array.

My solution

The idea that came to my mind first involved using a hash-table.

– Go over all the elements in the second array and add them to the hash table

– Go over all the elements in the first array and try to get it from the hash table. If it is not there, that’s the number.

The hash table solution has a complexity of O(n) but it uses a lot of space by creating a hash table with all the elements in the array.

The question

We are given 3 strings: str1, str2, and str3. Str3 is said to be a shuffle of str1 and str2 if it can be formed by interleaving the characters of str1 and str2 in a way that maintains the left to right ordering of the characters from each string. For example, given str1=”abc” and str2=”def”, str3=”dabecf” is a valid shuffle since it preserves the character ordering of the two strings. So, given these 3 strings write a function that detects whether str3 is a valid shuffle of str1 and str2.

The question

Find the first non-repeated (unique) character in a given string.

My answer

At first glance I am tempted to start from the left and add each character go to a hashtable with the number of times I have seen it. Once I have gone through the whole string I will do it again now searching for the first character that returns 1.

The question

Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle. Our program will be called multiple times with different rectangular regions from the same matrix.

My solution

Just from the question I am not completely sure what they are asking me but it sounds like I will have a matrix of integers (I will assume a 2 dimensional matrix) and then they will give me coordinates for two opposite corners and I just need to sum all numbers inside the limits of those coordinates. They also mention that the program will be called multiple times with different rectangular regions which makes me thing that I’m expected to do some kind of caching.

I spent some time thinking of how to do this in an efficient way but I couldn’t come up with something that felt right.

The question

Given a string of opening and closing parentheses, check whether it’s balanced. We have 3 types of parentheses: round brackets: (), square brackets: [], and curly brackets: {}. Assume that the string doesn’t contain any other character than these. No spaces, words or numbers. Just to remind, balanced parentheses require every opening parenthesis to be closed in the reverse order opened. For example ‘([])’ is balanced but ‘([)]‘ is not.

The question

Given two strings, check if they’re anagrams or not. Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. Each letter should have the same count in both strings. For example, ‘Eleven plus two’ and ‘Twelve plus one’ are meaningful anagrams of each other.

My solution

The solution I came up with consists of having a hash-table where we will store how many times a character is found in string1. Then we will do the same for string2. At the end these should match.

The question

Given an array of integers (positive and negative) find the largest continuous sum.

My solution

These are the steps I followed:

– Get the first number and add it to a variable where you will store the largest sum so far(largest).

– Create another variable(currentSum) where you will store the value of the current sum so far and assign the same number to it.

– Move to the next number. Calculate the sum of n1 and n2, if it is positive then assign it to currentSum.

– Check if currentSum is larger that largest. If it is, update largest.

– If currentSum became negative then assign 0 to it.

You have to go through each number in the array once, so the complexity is O(N).