Leetcode Medium: Letter Combinations of a Phone Number

A few days back I coded a Leetcode medium problem: Letter Combinations of a Phone Number (problem #17) as follows:

import java.util.Hashtable;

class Solution {
    public List<String> letterCombinations(String digits) {
        ArrayDeque<String> res = new ArrayDeque<>();
        res.add("");
        
        Hashtable<Integer, String> ht = new Hashtable<>();
        ht.put(2, "abc");
        ht.put(3, "def");
        ht.put(4, "ghi");
        ht.put(5, "jkl");
        ht.put(6, "mno");
        ht.put(7, "pqrs");
        ht.put(8, "tuv");
        ht.put(9, "wxyz");
        
        letterCombinationsRecur(digits, 0, ht, res);
        return new ArrayList<String>(res);
    }
    
    private void letterCombinationsRecur(final String digits, int digPtr, final Hashtable<Integer, String> ht, final ArrayDeque<String> res) {
        
        if (digPtr==digits.length()) {
            if (res.peekFirst().equals(""))
                res.removeFirst();
            return;
        }
        
        int inputResCnt = res.size();
        ArrayList<String> resAL = new ArrayList<>(res);
        
        
        String newLastChars = ht.get(digits.charAt(digPtr) - '0');
        int nlcLen = newLastChars.length();
        for (int nlcIdx=0; nlcIdx<nlcLen; nlcIdx++) {
            
            for (int i=0; i<inputResCnt; i++) {
                res.add(resAL.get(i) + newLastChars.charAt(nlcIdx));
            }
            
        }
        
        for (int i=0; i<inputResCnt; i++) {
            res.removeFirst();
        }
        letterCombinationsRecur(digits, ++digPtr, ht, res);
        
    }
}

Today, I revisited that problem and thought I could use a simplified technique to solve the problem by modifying the above solution to rely less of Level Order BFS-like dequeue population and rely more over recursion. Here's the result that resultantly significantly simpler:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return result;
        
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        letterCombinationsRecur (digits, 0, "", mapping, result);
        return result;
    }
    
    void letterCombinationsRecur (String digits, int digitPtr, String currentLetterCombination, String[] mapping, List<String> result) {
        if (digitPtr == digits.length()) {
            result.add(currentLetterCombination);
            return;
        }
        
        String currDigLetters = mapping[digits.charAt(digitPtr)-'0'];
        for (int i=0; i<currDigLetters.length(); i++) {
            letterCombinationsRecur(digits, digitPtr+1, currentLetterCombination+currDigLetters.charAt(i), mapping, result);
        }
    }
    
}

Let me know your thoughts in the comment section below! Meanwhile, happy coding!!

Leetcode Medium: Single Number II

Here's jot of my Leetcode submission in Java to "Single Number II" problem (problem #136) on leetcode.

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
        }
        
        for (int key : hm.keySet()) {
            if (hm.get(key) == 1)
                return key;
        }
        
        return -1;
    }
}

As always you can track my recent-most submissions on my leetcode page: https://leetcode.com/chandniverma/

Feel free to share your thoughts in comments.

Leetcode Medium - Find Peak Element

Following is my Solution to Problem #162: Find Peak Element. Feel free to discuss and/or add your comments.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        for (int i=1; i<nums.length; i++)
            if (nums[i]<nums[i-1]) {
                return i-1;
            }
        
        return nums.length-1;
    }
}

There's a faster solution that guarantees answer in O(lg(n)) time. It uses Binary Search trick.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        int min = 0;
        int max = nums.length-1;
        while (min<max) {
            int mid = min+ (max-min)/2;
            
            if (nums[mid]<nums[mid+1])
                min = mid+1;
            else
                max = mid;
        }
        
        return min;
    }
}

Leetcode Medium - Number of Islands

Today, I started solving Leetcode medium questions.

For reference purpose, I'll be jotting down my solutions to these problems here.

Following is an accepted quick solution to the  Number of Islands problem (problem #200) on Leetcode. This solution implements it using the land "sinking" technique.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length==0)
            return 0;
        
        int islands = 0;
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    islands += dfs(grid, i, j);
                }
            }
        }
        return islands;
    }
    
    int dfs(char[][] grid, int i, int j) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0') {
            return 0;
        }
        
        //sink
        grid[i][j] = '0';
        
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        
        return 1;
        
    }
}

LeetCode Problems Asked At FAANG Interviews - Part 1

The world has seen a number of job cuts worldwide. Some of the software engineering workforce has quit their jobs by their own will.

In such trying times when all economies are dwindling, it is the chance for the workforce to instead of giving up, pause and introspect on their ideal next workplace, and give their best to come out of the lockdown with flying colours.

I am a Software Engineer myself and with the aim of providing a not so unconventional path to help other software engineers reach their similar goals, in the last 2-3 weeks of my free time I audited the frequently asked problems at one of the big gigs in the software industry, particularly focussing on Amazon, the 'A' of "FAANG"(Facebook, Amazon, Apple, Netflix and Google).

In this blogpost I have collated some of those problems asked at Amazon, which will be useful for anyone preparing for interviews at Amazon and also someone who is trying to just get started with interviewing in general.

Amazon Interview Questions solved and audited by me:

1. First Unique Character in a String
2. Single Number
3. Power of Two
4. Robot Return to Origin
5. Missing Number
6. Best Time to Buy and Sell Stock II
7. Path Sum
8. Letter Combinations of a phone
9. Remove Element
10. Climbing Stairs
11. Lowest Common Ancestor of BST
12. Jewels and Stones
13. Container with most water
14. First unique character in a string
15. Flood Fill
16. Reverse Linked List - Try Iterative and Recursive both
17. Most Common Word
18. Unique Email Addresses

My LeetCode profile is : https://leetcode.com/chandniverma/ for you to checkout!

I would encourage all those who are getting set for preparing them for interviews to go through these problems by their own and feel free to ask their questions and share their doubts with me to keep this discussion open-ended and the Let's Code_ problem solving community alive! As you would have seen, the problems asked at Amazon are fairly simple and most come under the easy category of problems on LeetCode so they are good for starters.

Mock-interviews go a long way to help judge your standing among peers and have helped me many times as well.

I particularly conduct and give interviews on PRAMP (www.pramp.com) an acronym for PRActice Makes Perfect, and if you ever need PRAMP credits to sharpen your skills, feel free to get in touch! Do ping me with your account and I'll be happy to share some with you.

Until then, Happy Coding!!

Lockdown and Upskilling Problem Solving

Being busy has never given anyone a chance to reflect and up-skill themselves.

One of the best things a programmer can do to up-skill their coding capabilities is to work on the Art of Problem Solving and becoming world-class in doing it.

Why not must one utilise the Lockdown period with up-skilling oneself using techniques outlined by veterans like the CCDSAP curriculum which is laid down as a guidance mechanism to gain control over exactly what you want - problem solving using programming!

With the same line of thought in mind, I have restarted my programming practice and I'll document for you, how I go about the curriculum as we progress through this blog!

There are a few other up-skilling sites I keep in touch with like spoj.com, leetcode.com and hackerrank.com and I'll blog about solving problems there as well.

So, Let's Code!!!

A Oneliner for grepping character-by-character differences between two files anywhere on filesystem

Long story short:

Install git.
Hit this at command-prompt from within any git repo(can create afreash using `git init`):

 git diff  --no-index --word-diff=color --word-diff-regex=. /path/to/file1 /path/to/file2

Sample Result:

Dear Cybernauts,

Many a times you might have wondered a way to compare 2 files not just word to word but character-by-character, nicely coloured, and easy to spot on minute changes!

Without finding anything easily on the Internet apart from purchasable solutions (such as desktop versions of diffchecker.com..) not worth the pennies, I dug up some manuals and found it worth the effort to document it for the lazyweb. There you go! ^^ 😉(HaCk tHe BuSy-NeSSeS build on top of it!??!!! Use the 'man' if needed!)


~Namaste
🙏