DEV Community: Saurabh Kumar

Misc: Possible Ways to Add

Saurabh Kumar — Thu, 19 Aug 2021 21:41:34 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Problem

A very interesting and fairly easy question which I found during one interview was:

A batsman can score either {1,2,3} runs in a ball. Find the number of ways he can score "X".

Other variants - Given possible coins 2, 3, 5 - how many ways can result in a sum of 43

If you got stuck thinking or applying permutations and then visualizing it in code - just look at this simple code

Solution

    static int possibleWaysToReachScore(List<Integer> runs, int x) {

        // table[i] will store count of solutions for value i.
        int[] table = new int[x + 1];

        // Initialize all table values as 0
        Arrays.fill(table, 0);

        // Base case (If given value is 0)
        table[0] = 1;

        // One by one consider given runs
        // and update the table[]
        // values after the index greater
        // than or equal to the value of
        // the picked move
        runs.forEach(
                n -> IntStream.rangeClosed(n, x)
                        .forEach(i -> table[i] += table[i - n])
        );

        return table[x];
    }

Explanation:

given we have 1,2,3 and we want say 10 runs, we start with a dp array which will store all possible ways to get to the index (which represents the runs).
so, naturally table[0]=1
iteration for n = 1
- loop from 1 -> 10 and sum i + (i-1)
- table[1] = table[1]+table[0] = 1
- table[2] = table[2]+table[1] = 1 and so on...
- table[10] = table[10]+table[9] = 1
iteration for n = 2
- loop from 2 -> 10 and sum i + (i-2)
- table[2] = table[2]+table[0] = 1+1 = 2
- table[3] = table[3]+table[1] = 1+1 = 2
- table[4] = table[4]+table[2] = 1+2 = 3, 3
- table[6] = table[6]+table[4] = 1+3 = 4, 4
- table[8] = table[8]+table[6] = 1+4 = 5, 5
- table[10] = table[10]+table[8] = 1+5 = 6
iteration for n = 3
- loop from 3 -> 10 and sum i + (i-3)
- table[3] = table[3]+table[0] = 2+1 = 3
- table[4] = table[4]+table[1] = 3+1 = 4
- table[7] = table[7]+table[4] = 4+4 = 8
- table[10] = table[10]+table[7] = 6+8 = 14

then we loop over the range n (the current score possible till required score)

in the end we will have a dp containing all ways to reach any number till X
[(0=1), (1=1), (2=2), 3, 4, 5, (6=7), 8, 10, (9=12), 14]

Additional Info

of course, another variant of the same problem is Given possible scores a batsman can score in one ball is {1, 2, 3}, how many ways can he score X runs in B balls - that is a tough one to explain!

but here's the solution nonetheless!
GeeksForGeeks

Leetcode: Maximum Subarray

Saurabh Kumar — Tue, 17 Aug 2021 21:22:53 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #53 (Easy): Maximum Subarray

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

This problem can be complex and simple according to how you approach it.

Can we find out the pattern to find the max sum possible using a sub-array, say we have a list like 1, 2, 3, 4
the max sum possible would be 10 right ?
So can we say that starting from index 0
- max sum upto index 0 = 1
- max sum upto index 2 = 3
- max sum upto index 3 = 6
- max sum upto index 4 = 10

let's add some fun then!

now the list is 1, -2, 3, 4

max sum upto index 0 = 1
max sum upto index 2 = previous MaxSum or current Value +previous MaxSum? = 1
max sum upto index 3 = 4
max sum upto index 4 = 8

so, we can see that even if we summed all the digits, the values comes out to be 8.

let's go for the worse case
-2, 1, -3, 4, -1, 2, 1, -5, 4

max sum upto index 0 = -2 // by default first digit is max
max sum upto index 1 = -2 vs 1+-2 = -1 wait, this doesn't look right, if we have a positive number already, why do we have max sum = -1 ok, lets add another layer of check, max = max(num[i], num[i-1]+num[i], maxSum)
- max sum upto index 1 = -2 vs 1+-2 vs 1 = 1!
max sum upto index 2 = 1 vs -3 vs -3 = 1
max sum upto index 3 = 1 vs 4-3 vs 4 = 4
max sum upto index 4 = 4 vs -1+4 vs -1 = 4
max sum upto index 5 = 4 vs 2-1 vs 2 = 4 - wait again no! a series of 4, -1, 2 is ok, we can't just take the last two values, we need a concept of localSum. So now localMaxSum = nums[i] + Math.max(0, localMaxSum);
- max sum upto index 1 = 4 vs -1+2+4 vs 2 = 5!
max sum upto index 6 = 5 vs 5+1 vs 1 = 6
max sum upto index 7 = 6 vs 6-5 vs -5 = 6
max sum upto index 8 = 6 vs 6-5+4 vs 4 = 6

Implementation

  public static int maxSubArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSum = nums[0];
        int localMaxSum = nums[0];

        for (int i = 1, numsLength = nums.length; i < numsLength; i++) {
            localMaxSum = nums[i] + Math.max(0, localMaxSum);
            maxSum = Math.max(maxSum, localMaxSum);
        }

        return maxSum;
    }
}

Analysis

Leetcode: Longest Arithmetic Subsequence

Saurabh Kumar — Sat, 14 Aug 2021 20:27:25 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #1027 (Medium): Longest Arithmetic Subsequence

1027. Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], ..., nums[ik] with 0 <= i1 < i2 < ... < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].

Constraints:

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Pre-Requisite

What is an Arithmetic Subsequence ?

During high-school we learnt this concept with another name **Arithmetic Progression (AP)*.
The idea is pretty simple a sequence of numbers is called an AP if there are at least 3 numbers and they are equidistant from each other!

so, 1 8 15 is an AP as 1 (+7) 8 (+7) 15, we have a difference of 7 and so if I were to ask you what number would come next - what would you say?

22 ?

Also did you notice an interesting fact here - in a sorted list 1 + 15 = 2 x 8 -> the middle number when doubled is equal to the sum of its neighbours! DO NOT FORGET THIS 😉

Solution

So we know how to recognize an AP, but how do we find the longest AP, also consider these variations

The AP can have negative numbers
- -1 2 5 8 is a valid AP
The AP can be unordered (not sorted)
- 5 9 1 is a valid AP = 1 5 9
The AP subsequence
- 5 4 9 1 has a valid AP subsequence -> 1 5 9

ok so let take one example:
9 4 7 2 10

One way to look at the solution is to first sort them
2 4 7 9 10 -> can you see the AP Subsequence ?
4 7 10 - here the length is 3 and the difference is also 3

note 2,4 and 7,9 is not a valid AP even though they share the same difference. But for this problem we can say it has a length of 2 each with difference is also 2.

Figuring out the algorithm

Naturally when we see the maximization or minimization problem what we want is to compare ALL results and return the max or min. We will need Dynamic Programming concepts here!

If you see the example above, can we say the difference is out key and a pair of (last-index of our chain and max-length) is our value ?

why do you need a pair as value? say we have another example 1 2 14 15 16 27 29 30 43

as you can notice we have same difference but one pair of 14 has the most numbers 1 15 29 43

so if we store the DP values as a map of map with difference as key - maybe the problem is not that difficult!

Lets see the code

Implementation

    public int longestArithSeqLength(int[] nums) {
        int size = nums.length;
        // Stores the length of sequences having same difference
        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();

        // Stores the resultant length
        int res = 2;

        // Iterate over the array
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {

                // our dp key is diff
                int diff = nums[j] - nums[i];

                 // here we store the pair of last index which gives us max difference
                Map<Integer, Integer> temp = new HashMap<>();

                // Update length of subsequence
                if (dp.containsKey(diff)) {
                    temp = dp.get(diff);

                    if (temp.containsKey(i)) {
                        temp.put(j, temp.get(i) + 1);
                    }
                }

                temp.putIfAbsent(j, 2);

                dp.put(diff, temp);
                res = Math.max(res, temp.get(j));
            }
        }

        return res;
    }

Analysis

As you can see this solution is not the most complicated one, I found it easier to think to almost completion during an interview without knowing anything about AP beforehand.

If you take it upon you to use some 2-D Array based solution - go ahead 😄

We will have a default length of 2 for each pair!

j=2 -> 4-2 -> 2, (2, 2)
j=3 -> 7-2 -> 5, (3, 2)
j=4 -> 9-2 -> 7, (4, 2)

j=5 -> 10-2 -> 8, (5, 2)

j=3 -> 7-4 -> 3, (3, 2)

j=4 -> 9-4 -> 5, (3, 2) (4, 2)this is interesting we already have 5 as key, but when we picked the pair we don't have 2nd index as key - so we added a new pair for value set[2,7][4,9]

j=5 -> 10-4 -> 6, (5, 2)

```
j=4 -> 9-7 -> 2, (2, 2) (4, 2)
```

j=5 -> 10-7 -> 3, (3, 2) (5, 3)` this is interesting we already have 5 as key, so we will update its existing length to +1

j=5 -> 10-9 -> 1, (5, 1)
- so the maximum length is 3!

Leetcode: Two Sum

Saurabh Kumar — Sun, 08 Aug 2021 07:48:11 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #1 (Easy): Two Sum

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Pre-Requisite

Let's not waste time to thing a two loops solution is even worthy of consideration! Runtime: O(n^2)

Also, you have to understand that the solution requires you to return the index of the values needed to get this sum, so you can't sort the input to move left or right.

So, can you think of another way!

Solution

There can be multiple solutions but one approach can give you a O(n) runtime complexity. And that is with using hashmap's!

So how does it work?
say you store indexes of all the numbers from the array as a map, so that the numbers become the key of the hashmap and the indexes become value.

How will that help?

simply loop over the array again, find the required second number and check if it exists in the hashmap or not! If you found it, find the index and return the index of first number and second number.

This solution is really elegant and works really well, the only downside is that you need a O(n) space complexity as well.

Implementation

For some problems python really provides a concise solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dictionary = {}

        for index, value in enumerate(nums):
            dictionary[value] = index


        for i in range(len(nums)):
            second_number = target - nums[i]
            if second_number in dictionary.keys():
                second_index = nums.index(second_number)

                if i != second_index:
                    return sorted([i, second_index])

The result

** NOTE - the interviewer might ask you, why did you create two for loops instead of 1 - and yes you can do it more concisely - but i guess you understand the solution better with O(n) loop.

in java

int[] twoSum(int[] nums, int target) {

        final Map<Integer, Integer> map = IntStream.range(0, nums.length)
                .boxed()
                .collect(Collectors.toMap(i -> nums[i],
                        i -> i,
                        (a, b) -> b));

        for (int i = 0; i < nums.length; i++) {
            int secondNumber = target - nums[i];

            if (map.containsKey(secondNumber)) {
                int secondNumberIndex = map.get(secondNumber);

                if (secondNumberIndex != i) {
                    return new int[]{i, secondNumberIndex};
                }
            }

        }

        return new int[]{};
    }

Leetcode: Next Permutation

Saurabh Kumar — Mon, 02 Aug 2021 02:24:25 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #31 (Medium): Next Permutation

31. Next Permuation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3] Output: [1,3,2]

Example 2:

Input: nums = [3,2,1] Output: [1,2,3]

Example 3:

Input: nums = [1,1,5] Output: [1,5,1]

Example 4:

Input: nums = [1] Output: [1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Solution

The idea is little tricky, first of all the answer is not a number, but a rearrangement of digits shown in the input array. This might gives us a hint that we don't have to calculate the number by index 10.

You might think of that solution as brute force:

create all permutations of the input,
generate the number from that input variant,
find the next largest at this point you might be think of storing the array as a HashMap index and the number as its value

And there's nothing wrong in this except for the runtime O (n x n!) - WHAT!

So, immediately we have to pivot to some other approach - do we really need to calculate ALL permutations!

Let's see from an example:

input = [1, 2, 3] solution = [1, 3, 2]

can we say that we simply swapper the larger digit with the immediate smaller one from the right?

ok, but this will not work everytime

input = [1, 3, 2] solution = [2, 1, 3]

the ONLY trick needed here:
we start from right - compare the two digits until we find the index which is just smaller than 2, i.e. we compare n-1 <= n until we reach the leftmost or the failing case.

for [1, 3, 2] we reached till i = 0 (1)

now if we had reached -1 -> we cannot produce a bigger number, thanks to the problem statement, we simply reverse the number and return.

but if i >=0 , we again start from the end (say j), until we find a number greater than i
2 <= 1
so, j = 2 (2)

we swap i j
[2, 3, 1]

and the final step
we reverse all digits after the ith index (i+1)
2 [3, 1] -> 2 [1, 3]

Implementation:

    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;

        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        if (i >= 0) {
            while (nums[j] <= nums[i]) {
                j--;
            }

            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

**Bonus
since some of you like python -> Enjoy ;)

def next_perm(n):
    i = len(n) - 2
    while i >= 0 and n[i + 1] <= n[i]:
        i -= 1

    if i >= 0:
        j = len(n) - 1
        while n[j] <= n[i]:
            j -= 1

        swap(n, i, j)

    return reverse(n, i + 1)


def swap(n, i, j):
    n[i], n[j] = n[j], n[i]


def reverse(n, from_index):
    res = []
    for i in range(0, from_index):
        res.append(n[i])

    for i in range(len(n) - 1, from_index - 1, -1):
        res.append(n[i])

    return res

Java Concurrency Is Easy Day-1

Saurabh Kumar — Tue, 06 Jul 2021 03:34:17 +0000

The first thing you need to understand is Concurrency is not Threads!

Thread is a task - Concurrency is about how you can do it so that tasks run safely in your application. Concurrency can be challenging when some enthusiast dev tries to over-engineer a problem that is not really well managed.

Also, make note that Parallelism is not the same as Concurrency! Read more here.

How do you make concurrent tasks?

The most common way is making a Thread (read about threads start(), run() etc. methods) - and over time Java has come up with a very simple library class called Executors.
They are the sole handlers of how/when to run your threads (actions). You can submit a task to them, and they will run it as soon as possible. We don't really need to care about anything other than the task itself!

So a simple way to making an Executor and then submitting a task

ExecutorService executor = Executors.newCachedThreadPool();
executor.submit(()-> () -> System.out.println(MathUtils.factorial(5));

and that's it - the executor will simply run the task as it sees fit.
You can actually use this approach and keep adding more tasks, and each task will ideally be run on a separate thread.

So, what exactly is Concurrency!

A basic problem

You have a dictionary, you want to search a word "stoic" - the first thought that came to head after reading this is that "oh - yes! I will simply skip more than half of dictionary as "S" comes after the mid - and hence I will be closer to my goal

but think your sister also wanted to find the word "manic" - she tries to access the dictionary, but wait - you were using it, so she asks you "could you please give me the dictionary and you reply "I'm not done yet..."

In the best case, she waits until you are done or she steals the dictionary from your hand and runs away 😉 If she was happy to wait for you - turn the pages, and eventually you reach the location of the word.

Now in java terms

What you can imagine is that there were two Thread - who had a defined work and it is possible that the work might be conflicting by nature or you and your sister can do some mutually exclusive work without ever fighting.

To summarize, we have

threads (with some action - in java we call them Runnable)

shared resources (your CPU memory just like the dictionary)

and a manager says your mom dictates who will get the dictionary first and who will wait or if you should stop what you were doing and give the resource to your sister! (in java we call it "interrupt") - obviously every runnable can be interrupted so we always guard the threads with a notification system with isInterrupted flag, this is very important

Now the question is shouldn't it be better that we could specify that You are using the dictionary exclusively and your sister respects this!

So, in Java the concept of Lock came into the picture - with just two basic methods - lock() and unlock()

Please forget about the synchronized keyword for now which every genius programmer will tell you in concurrency. This is critical that you first understand Lock and then the fancy keyword.

So any class (the resource which can be shared eg. Account) can keep the property of this Lock type inside and as soon as you start accessing the resource - you set it to accountLock.lock() - now the other person can't lock() it until you explicitly say accountLock.unlock() stating that the task is done.

Essentially this is how you handle concurrency in simpler terms. Some more interview worthy examples are:

Producer consumer problem
- the one thread adds biscuits on the racks, other eats from the rack, if you are doing both simultaneously chances are that you won't have enough to sell!
Reader Writer problem
- A reader is reading a post and in the meanwhile another write is editing and saving it, now the reader is always confused. Think about wikipedia!

We will see how we can fix it properly - spoilers "everything is handled by locks " 😋

🔚

So - if you are clear until this point, do let me know and wait for Day-2 😄

A Tiny URL design and code ✔️

Saurabh Kumar — Sun, 27 Jun 2021 19:46:35 +0000

This is a simple encode() and decode() function.

Note that we haven't created the MD5 hashing approach here as this only deals with the concept.

Step:

encode()

save the long url in db, get a unique long id from db for that url
pass that long id to the encode(id) function
so for a long value we keep diving it by 62 and pick a value from the allowed chars array and keep adding it
make sure to reverse the created string

    private static final String allowedString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final char[] allowedCharacters = allowedString.toCharArray();
    private final int base = allowedCharacters.length; // 62

    public String encode(long input){
        var encodedString = new StringBuilder();

        if(input == 0) {
            return String.valueOf(allowedCharacters[0]);
        }

        while (input > 0) {
            encodedString.append(allowedCharacters[(int) (input % base)]);
            input = input / base;
        }

        return encodedString.reverse().toString();
    }

decode()

send the last part of the url - which is the encoded string
convert the string to array
from first value we pick index of value and multiply it with 62^remaining characters
the number is the decoded id

    public long decode(String input) {
        var characters = input.toCharArray();
        var length = characters.length;

        var decoded = 0;

        //counter is used to avoid reversing input string
        var counter = 1;
        for (char character : characters) {
            decoded += allowedString.indexOf(character) * Math.pow(base, length - counter);
            counter++;
        }
        return decoded;
    }

So if we have the decoded url, we could simply return it as a header location - with the response code of 302 (FOUND)

@GetMapping(value = "{shortUrl}")
public ResponseEntity<Void> getAndRedirect(@PathVariable String shortUrl) {
        var url = urlService.getOriginalUrl(shortUrl);
        return ResponseEntity.status(HttpStatus.FOUND)
                .location(URI.create(url))
                .build();
    }
}

The problems:

we are relaying on a single db table id to generate the ids
not scalable, how do we handle a fixed size return url
how do we allow customised URLs
can we reuse a short-url which is removed/expired?

I will be working on a more distributed solutions in coming posts, Thanks you for reaching here.
Here's a 🍪

HackerEarth: Rank of a word in Dictionary

Saurabh Kumar — Sat, 26 Jun 2021 14:50:02 +0000

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

HackerEarth Problem (Medium): Rank of a Word

Rank of a Word

Problem

Cham was studying Permutation and Combinations . He was deeply fascinated by the problem that asks to calculate the rank of the word S in a dictionary (given that the dictionary only comprises of the alphabets that are present in S and all the words in the dictionary have the same length as S and same number of alphabets as in S )

For the calculation procedure please refer to the given link :- Rank of a Word

Your task is simple help Cham to calculate the Rank of words .

Solution

Rank of a word is basically deduced from making all combinations of the alphabets from the given word - sorting them in order as in dictionary and checking the position of our given word.

For example word = BALL

all possible combinations = 4!/2! (as L appears twice) = 12
sort them -> [A, B, L, L] ```bash

1 : ABLL
2 : ALBL
3 : ALLB
4 : BALL -- this is our desired word
5 : BLAL
6 : BLLA
7 : LABL
8 : LALB
9 : LBAL
10 : LBLA
11 : LLAB
12 : LLBA

**so the rank is 4**

---------------------------
Let us take few examples to understand it better.

Let's start with the words “*RAIN*” and “*SOCCER*”

The word rain has four alphabets and all of them are different. Hence, the number of words that can be formed using all the alphabets of the word “RAIN” are `4!=24`. 

Similarly, the word soccer has six alphabets, of which 2 are similar (C is repeated twice). Hence, the number of words that can be formed using all the alphabets of the word “SOCCER” are `6!/2! = 360`. 
This is the first step.

- Step 1: Find the total number of words that can be formed using all the alphabets of the given word.

Once you have done that, your next step shall be to arrange the alphabets of the word in chronological order. Thus, the letters of the word rain shall be arranged as `{A, I, N, R}` and the letters of the word “soccer” shall be arranged as `{C,C,E,O,R,S}`. It shall be noted that since C appeared two times in soccer, it shall be written two times here also. This is your second step.

- Step 2: Arrange all the letters of the word in alphabetical order. If few letters are repeated in the original word, repeat them the same number of times here also.

Now, here we are ready to fetch the big fish *a.k.a step 3*. Suppose we had to find the rank of the words “rain” and “soccer” itself.

----------------------
> {A,I,N,R}

Pick A. Once you have done that, you are left with three alphabets all different, from which you can form 3!=6 words. But none of these words can be rain, since rain stars with R and not A. So you can be pretty sure that the rank is nowhere from 1 to 6. (Agree?)

Next, pick I. Once you have done that, you're again left with three alphabets all different, from which `3!=6` words can be formed, none of them being rain, since rain starts with R and not I. Safe to say the rank of the word is nowhere from 7 to 12. (Agree?)

Similarly, we shall pick N next and can say that the rank of the word “rain” is nowhere from 13 to 18.

We shall now pick up R. Now we are left with {A,I,N} in the order. The 6 words that can be formed are

Rain
Rani
Rian
Rina
Rnai
Rnia

Clearly, rain is the first among these 6, making it the first after previous 18. Thus the rank of the word rain is 19.



> {C,C,E,O,R,S}

Pick C. Once you have done that, you're left with 5 alphabets all different, from which you can form 5!=120 words. But none of these words can be soccer, since soccer starts with S and not C. So, you can be pretty sure that the rank is nowhere between 1 to 120. (Agree?)

There's no need to pick the second C, since you have already picked one. (This is one of the most common mistakes students do).

Next, pick E. Once you have done that, you're now left with 5 alphabets of which two are similar. Thus, the number of words that can be formed which start with E are 5!/2!=60, none of which can be soccer. Thus, no rank from 121 to 180.

Similarly, pick O and you can say no rank possible from 181 to 240. Pick R and no rank possible from 241 to 300.

Finally (the Rock has come to…), let's pick S. 

Now, we have {C,C,E,O,R}. Pick C as the second letter and 4!=24 words now start with SC. No word possible from 301 to 324. 

Pick E = 4!/2! = 12 -> Similarly, rank 325 to 336 is taken by SE. 

Now, we SO from 337 to 348. Our soccer lies here only. Fortunately, if you arrange alphabetically now, you would find soccer has 337th rank.



  
  
  Implementation


So the theory is done - lets see it in code (this handles both unique and with duplicate cases)


create a map of all characters and their occurrences




    public static long findRank(String word) {
        long rank = 1;
        long suffixPermCount = 1;
        final Map&lt;Character, Integer&gt; charCounts = new HashMap&lt;&gt;();

        for (int i = word.length() - 1; i &gt;= 0; i--) {
            char x = word.charAt(i);
            int xCount = charCounts.containsKey(x) ? charCounts.get(x) + 1 : 1;

            charCounts.put(x, xCount);

            for (Map.Entry&lt;Character, Integer&gt; e : charCounts.entrySet()) {
                if (e.getKey() &lt; x) {
                    rank += suffixPermCount * e.getValue() / xCount;
                }
            }

            suffixPermCount *= word.length() - i;
            suffixPermCount /= xCount;
        }

        return rank;
    }


</code></pre></div><h3>
  <a name="a-shortcut-method" href="#a-shortcut-method">
  </a>
  A shortcut method
</h3>

<ol>
<li>assign each character a number in sorted order (same number for duplicates)</li>
<li>start from index 0 -&gt; check how many numbers in right till end are smaller than the index value</li>
<li>for each index divide by the number of duplicates factorial</li>
<li>then multiply each index result with our general factorial</li>
<li><strong>rank = sum all indexes + 1 (as it is 1 based rank)</strong></li>
</ol>

<p>ex: SMALL -&gt; 58<br>
<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/231rd1jp7fhtk3z9jje5.png" alt="image"></p>

<p><img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vj5j8bpcs4v2z4ni87xm.png" alt="alt text"></p>

Maths for Coders : Chapter 1

Saurabh Kumar — Fri, 25 Jun 2021 21:00:34 +0000

Starting a thread where I will be adding some common math problems expected from developers in interview rounds or aptitude tests.

These will always come in handy - so I have added the cleanest version of some common functions

find all prime factors
check if a Number is odd-even
find LCM of n elements
find HCF of n elements

Java StringBuilder Demystified

Saurabh Kumar — Wed, 16 Sep 2020 10:55:05 +0000

Let's understand what makes every lead developer say that you should know how to create your own StringBuilder if you plan to modify your strings.
And most of all - what is the difference between string concatenation vs using this pattern.

Simply put what we want to do is - an efficient management of space and performance.

This is the simplest of all the implementations with core characteristics of a StringBuilder

.append()
.length()
.toString()

MyStringBuilder

import java.util.Arrays;

public class MyStringBuilder {

    private static final int INIT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    private static final int MULTIPLIER = 2;

    private int currentCapacity = INIT_CAPACITY;

    // store the total number of characters in our string builder
    private int count;

    // storage area for our characters
    private char[] chars;

    public MyStringBuilder() {
        chars = new char[INIT_CAPACITY];
    }

    public MyStringBuilder(String str) {
        this();
        append(str);
    }

    public MyStringBuilder append(String newStr) {

        final int length = newStr.length();

        // check if resized or not
        boolean inflated = ensureCapacity(length);

        if (inflated) {
            final char[] newBuffer = new char[currentCapacity];
            // copy current content
            System.arraycopy(chars, 0, newBuffer, 0, count);
            // copy new content
            System.arraycopy(newStr.toCharArray(), 0, newBuffer, count, length);

            // update the store array
            chars = newBuffer;
        } else {
            // add the new content to the remaining array space
            System.arraycopy(newStr.toCharArray(), 0, chars, count, length);
        }

        // update the count of chars
        count += length;

        return this;
    }

    private boolean ensureCapacity(int newLength) {
        boolean isInflated = false;
        // ensure the new length is properly accommodated
        while (Float.compare((float) (count + newLength) / currentCapacity, LOAD_FACTOR) >= 0) {
            currentCapacity *= MULTIPLIER;
            isInflated = true;
        }

        return isInflated;
    }

    public int length() {
        return count;
    }

    @Override
    public String toString() {
        return new String(Arrays.copyOfRange(chars, 0, count));
    }
}

public class MyStringBuilderDriver {

    public static void main(String[] args) {

        var sb = new MyStringBuilder();

        sb.append("Hi").append(" ");
        sb.append("Saurabh").append(",").append(" ");
        sb.append("how are you today ?");

        System.out.println(sb);
        System.out.println(sb.length());
    }
}

If you feel it's cool - let me know which Java language framework object I should demystify.

Create your ENUM (yes from Java')

Saurabh Kumar — Wed, 02 Sep 2020 19:55:45 +0000

If you are always in awe of the simple yet powerful Enums in java, follow along ;)

In Java, enum data type internally inherits from java.lang.Enum class.

Use cases to consider:

should have methods name(), ordinal() as final which no one can override
always maintain singleton status for each enum value
you shouldn't be able to access enum constructor (make it private)
should have ordinal (consider sequential numbering idea)
the enum should have a values() which returns all enum values.

I wrote a simple yet fairly complete implementation, so I welcome any feedback.

import java.util.List;

abstract class EnumBase implements Comparable<EnumBase>, Serializable {

    private final int ordinal;
    private final String name;

    protected EnumBase(int ordinal, String name) {
        this.ordinal = ordinal;
        this.name = name;
    }

    public final int ordinal() {
        return ordinal;
    }

    /**
     * non overridable
     *
     * @return always gives ENUM Constant name
     */
    public final String name() {
        return name;
    }

    /**
     * It is desired to be overloaded
     *
     * @return default to enum constant name
     */
    @Override
    public String toString() {
        return name;
    }

    @Override
    public final boolean equals(Object o) {
        return o == this;   // as singleton always yield true
    }

    @Override
    public final int hashCode() {
        return super.hashCode();    // don't need it as there can only be ONE instance on an Enum
    }

    @Override
    public final int compareTo(EnumBase o) {
        return Integer.compare(o.ordinal, ordinal);
    }

    /**
     * This guarantees that enums are never cloned, which is necessary
     * to preserve their "singleton" status.
     */
    protected final Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException();
    }

    /**
     * prevent default deserialization
     */
    private void readObject(ObjectInputStream in) throws IOException,
            ClassNotFoundException {
        throw new InvalidObjectException("can't deserialize enum");
    }

    private void readObjectNoData() throws ObjectStreamException {
        throw new InvalidObjectException("can't deserialize enum");
    }
}

public class MyEnum {
    private static int ordinalCounter = 0;

    /**
     * Utility class where we fix the ordinal as sequential integers
     */
    private abstract static class AbstractEnum extends EnumBase {
        private AbstractEnum(String name) {
            super(++ordinalCounter, name);
        }
    }

    // singleton instance
    public static final FIRST FIRST = new FIRST();

    static class FIRST extends AbstractEnum {
        private FIRST() {
            super(FIRST.class.getSimpleName());
        }
    }

    public static final SECOND SECOND = new SECOND();

    static class SECOND extends AbstractEnum {
        private SECOND() {
            super(SECOND.class.getSimpleName());
        }
    }

    public static List<EnumBase> values() {
        return List.of(FIRST, SECOND);
    }
}

class MyEnumDriver {
    public static void main(String[] args) {
        // FIRST 1
        System.out.println(MyEnum.FIRST.name() + " " + MyEnum.FIRST.ordinal());
        // true
        System.out.println(MyEnum.FIRST == MyEnum.FIRST);
        // FIRST 2
        System.out.println(MyEnum.SECOND.name() + " " + MyEnum.SECOND.ordinal());
        // values
        System.out.println(MyEnum.values());
    }
}

Implementing Queue with 2 Stacks

Saurabh Kumar — Sun, 23 Aug 2020 12:46:59 +0000

BEGIN:

I'm assuming you are familiar with the vocabulary of

Stack

PUSH = Add to end
POP = Get from end
Queue

ENQUEUE = Add to end
DEQUEUE = Return from beginning

Prerequisite: You only need to know this

In Java when you "ADD" to ArrayList, it adds in the end.
Similarly, if you use Javascript, you "PUSH" to an array, it adds the value in the end of the array.

So, I came across this simple yet interesting topic of implementing a Simple Queue (FIFO) with 2 Stacks (LIFO)

Having done this program in university (where I used scratch implementation in C++), I believe now more conciseness is required for interview preparations - and hence I'm using JAVA's native ArrayList to implement my own Stack and Queues.


import java.util.ArrayList;
import java.util.List;

public class MyStack {

    private final List<Integer> stack = new ArrayList<>();

    void push(int item) {
        stack.add(item);
    }

    int pop() {
        if (!stack.isEmpty()) {
            return stack.remove(stack.size() - 1);
        }
        return -1;  // if nothing found
    }

    int size() {
        return stack.size();
    }

    boolean isEmpty() {
        return stack.isEmpty();
    }
}

So, now we have our Stack - it's that simple ;)

And here's our Queue


public class MyQueueWithTwoStacks {

    private final MyStack firstStack;
    private final MyStack secondStack;

    public MyQueueWithTwoStacks() {
        this.firstStack = new MyStack();
        this.secondStack = new MyStack();
    }

    boolean isEmpty() {
        return firstStack.isEmpty() && secondStack.isEmpty();
    }

    int size() {
        return firstStack.size() + secondStack.size();
    }

    void enqueue(int item) {
        firstStack.push(item);
    }

    /**
     * We will use the second stack to out the values, if the second bucket is
     * empty that means we need to copy over all stack1 entries to it
     *
     * @return returns the value
     */
    int dequeue() {
        if (secondStack.isEmpty()) {
            while (!firstStack.isEmpty()) {
                secondStack.push(firstStack.pop());
            }
        }

        return secondStack.pop();
    }
}

Reference:

If you like theoretical overview, here's a super nice Post by @jellybee

END.