DEV Community: Deepak Venkatachalam

Programming Exercise: Frequency Sort

Deepak Venkatachalam — Fri, 12 Jun 2020 23:34:10 +0000

Background

Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. You can find some of the other solutions in the series table above this section.

Problem

Frequency Sort
Given a string, return another string where the characters are sorted by the frequency of their appearance with the most repeating at the beginning.
Eg:

Input: tree
Output: eert
Input: aabbbc
Output: bbbaac

Solution

Whenever I see a problem like this, where the output depends on the how each item in a list relate to another item in the list (here for e.g. how many times each element appears in the list) my mind immediately jumps to a two pass approach with a hashmap.

This is not because hashmaps are my favorite data structure (I don't have a favorite data structure), but rather the ease of lookup of hashmaps. So usually my mind thinks how I can store the data in a hashmap in the first pass, so that I can look it up in the second pass thereby avoiding a nested loop.

This problem was no different and I started out the same way. But when I started to write down what the hashmap I needed I realized I might need two hashmaps. One to represent how many counts of a characters there are, and another to represent the different counts itself. (There might be a better way of doing it, but this is what I came up with in the first try)

So my two hashmaps for the second example above looked like this at the end of the first pass:

// For each character a string with their frequency
{
  a: aa,
  b: bbb,
  c: c
}
// For each count a list of characters with the count
{
  1: [a, b, c],
  2: [a, b],
  3: [b],
}

Now there is some repetition in the second map, but that was ok since I didn't want to add additional complexity of lookup in the first pass.

From here it was a matter of sorting the counts and then forming a string from the other map.

This yielded the following code:

Complexity

Since there are a few different steps involved in here lets see the complexity of each step:

First pass - constructing the hashmap - O(n) where n is the length of the string.
Sorting the counts - O(k.log k) where k is the number of unique counts.
Second pass - constructing the result - 3.1 O(n) - if each character appeared only once. 3.2 O(k + n) - if there are k counts each with more than one item. But since k < n, that is really O(n)

So the most expensive operation here is the sort.

Leetcode Problem: Valid Parenthesis

Deepak Venkatachalam — Thu, 04 Jun 2020 23:03:35 +0000

Background

Problem

Valid Parentheses
Given a string of parentheses determine if the string is valid. The string is valid if and only if, the opening and the closing parentheses match.

For e.g.

{([])} - valid
{{{ - Invalid
()() - Valid
({) - Invalid

Solution

I know the answer to this problem from my college intro to Algo class. The trick here is to use a Stack data structure. One of the first benefits I remember of stacks was to use stacks to verify certain kinds of grammar which is what this question is about. Verifying a grammar of parentheses.

The pseudo algorithm is:

Walk through every character in the array.
If the character is a opening parentheses push into the array.
If the character is a closing parentheses pop the top element in the array.
If it is the corresponding opening parentheses, move on ; else return false (fail quick)
If all elements have been processed, then the string is valid if the stack is empty.

Coding the solution

The following is the first version of the solution that I wrote:

After I verified that this works, I wanted to clean up a bit. A easy win would be to flip the inner if loop so that I don't have to keep two maps. Also that would take care of invalid (non parentheses) characters. So I got here:

Sidebar

One other difference in the above two solution is that I have a special case for empty string in the second case. The reason for is two-fold:

First of course is fail early. No need to try and work on string when we already know the result.
Second is something I learned today (#til). In java if you split an empty string by an empty string, it results in an array of length 1 with an empty string as the only element. 😮

Here is an e.g.

jshell> "".split("")
$1 ==> String[1] { "" }

Leetcode Problem: Group Anagrams

Deepak Venkatachalam — Sun, 31 May 2020 16:57:11 +0000

Background

Problem

Group Anagrams
Given a list of strings, return a list where all anagrams are grouped together.

Input: [ate, cat, tac, eat, mat, tea, tam, bat]
Output: [[ate, eat, tea] [cat, tac], [mat, tam], [bat]]

Note

A word is considered an anagram of another if it can be formed by rearranging all the letters of the first word.

Solution

Finding an anagram

There are a couple of ways to finding if a word is an anagram of another.

Sorted String

If you have two string bac and cab if you sort them, they both result in the same string abc. Hence they are anagrams of each other.

Count of characters

With the same two strings bac and cab if you can count the number of characters in each one of the like { a: 1, b: 1, c: 1 } and if these match, then they are anagrams of each other.

Grouping Anagrams

My first thought was that counting characters might not be straightforward. So I went with the sorted string approach.

The rough algorithm was:

Initialize an empty map which will store SortedString -> List of original Strings
For every string in the list,

2.1 Sort the string

2.2 If there is an entry in the map for the string add current string to the list.

2.3 Create a new list with this element and add it to map.
Return a list of all values in the map.

This yields the following code:

Complexity

The complexity of this solution is O(n.m.logm) where is n is the number of strings in the list and m is the average length of the strings in the list.

Note

After solving this, I went through the solutions in leetcode, and found that you can use the character count solution to get a better O(n.m) solution. I will attempt that next.

Leetcode Problem: Three sum

Deepak Venkatachalam — Thu, 28 May 2020 01:42:38 +0000

Background

Problem

3 Sum Problem
Given a list of numbers and a sum k, return all unique triplets such that

x + y + z = k

Note

This is a subset of the n-sum problem and a level higher in difficulty compared to often asked 2 sum problem. I have personally asked 2 sum problem multiple times in interview but have never gotten to solving the three sum problem.

Solution

2 Sum

From previous experience, I know that the fastest way to solve the 2 sum problem is by maintaining a hashmap.

The rough algorithm for a list of size n with a sum k is as follows:

Iterate through the list.
In each iteration check if the hashmap contains the key k - currentElement
- if it does you have found a tuple
- else place the currentElement in the hashmap.

This solution yields a O(n) solution where n is the number fo elements in the list.

3 Sum as an extension to 2 sum

My first thought to solve this problem, was to think of extending the hashmap solution from 2sum.

My first idea was to see if I could maybe use a nested hashmap. So, somehow in each step, I would check every other element. But then I realized I would have to check every other element twice, once for the top level set of keys and once for the second nested level. While I am not sure if this would work (I didn't try implementing this) it would at least involve a n^3 solution.

An optimization which might be useful is to use the 2 sum problem. So the modified algorithm could be:

For every element in the list
Get the value of k - currentElement
Call twoSum with the value from above step and the rest of the list.

Given twoSum is O(n) and it is called n times, this solutions would be O(n^2)
This is clearly better than my first approach so I decided to implement it.

Implementation

I wrote a quick twoSum method and then added a third parameter to it skippedIndex so that I can skip the current element. There is probably a better way to pass around the rest of the list.
My first run was successful, but then I hit a snag. I was getting duplicate triplets.
To get around this, I used a Set instead of an array (more on Java's Set here)
There was still an issue. If my two sum code returned two set of triplets 1, 2, 3 and 3, 2, 1 the Set interface in java treated this as two different elements. To get around this problem, I simply sorted the triplet before inserting it into the set. This ensures uniqueness of the triplets. See sidebar below on how this works.
You can find my full solution here

Sidebar

Here is a quick example of Sets and how you can add sorted lists to a set to maintain uniqueness.

jshell> Set<List<Integer>> s = new HashSet <List<Integer>>();
s ==> []

jshell> List<Integer> a = new ArrayList<Integer>(List.of(1, 2, 3))
a ==> [1, 2, 3]

jshell> List<Integer> b = new ArrayList<Integer>(List.of(3, 2, 1))
b ==> [3, 2, 1]

jshell> s.add(a)
$6 ==> true

jshell> s
s ==> [[1, 2, 3]]

jshell> s.add(b)
$8 ==> true

jshell> s
s ==> [[1, 2, 3], [3, 2, 1]]

jshell> Set<List<Integer>> s = new HashSet <List<Integer>>();
s ==> []

jshell> s.add(a)
$11 ==> true

jshell> Collections.sort(b)
jshell> s.add(b)
$13 ==> false

jshell> s
s ==> [[1, 2, 3]]

Leetcode: Integer to Roman

Deepak Venkatachalam — Mon, 25 May 2020 20:59:38 +0000

Background

Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. Any feedback on improving the solution is welcome. This is not really meant to be instructive but rather just a journal for my own thought process.

Problem

Integer to Roman

So the problem is straightforward. Given an integer value, return the roman numeral version of it. (In this specific problem, the input range was limited between 1 and 3999)

Solution whiteboarding

I had previously solved the roman numeral to integer problem and similar to that solution, my first idea was to create a map with all possible values -> symbol combination.

This yielded this :

{
    1000: M,
    500: D,
    100: C
   //  … so on
}

First idea : Division (incorrect?)

Having solved number based problems before, my first thought was to use a division based solution. I thought I could keep a static highestDivisor
value and then somehow step through the values by dividing by the highest divisor possible for a number (for e.g. for 432 the highest divisor would be 100)

Roadblock 1: 5xx and special cases

The first roadblock I hit was that there was 5xx (5, 50, so on) so dividing by 10 might not be a very good way? Also do I do about the special cases?

To address the second problem first, I added the special cases to the map.

{
    1000: M,
    900: CM,
    500: D,
    400: CD,
    100: C
   //  … so on
}

But I still had the issue with division.

Second idea

So I thought my initial assumption to try and parse the numbers were right. But division might not be the best approach. Maybe, I could try just subtraction?

I had created the map from highest to lowest values. So, the solution I came up with was the subtract (when I was done, I checked the solutions tab of leetcode the first solution was similar to this)

So the steps would be :

Starting with the highest value in the map see if subtracting the number gives a positive number
If I can't move to the next smaller value.
When I find the value which can be subtracted from the number, concat the corresponding symbol and keep subtracting until you can't subtract anymore.

This yielded the following java method (You can find my whole solution here

Set<Integer> keys = valueSymbolMap.keySet();
Integer [] keysI = keys.toArray(new Integer[keys.size()]);
String result = "";
int i = 0;
while (num > 0) {
    while (i < keysI.length) {
        if (num - keysI[i] >= 0) {
            result = result.concat(valueSymbolMap.get(keysI[i]));
            num -= keysI[i];
        } else {
            i+= 1;
        }
    }
}
return result;

Implementation Notes:

I used a LinkedHashMap to make sure I get the keyset in the same order as the element added always.
I can probably do without the double while loop.

Final Thoughts

I wonder if there is a more elegant solution to this without some of the hardcoded values but I couldn't think of any.