DEV Community: Akhil

Form design for developers Part - 1

Akhil — Sat, 16 Jan 2021 15:50:20 +0000

Ever dropped out during a signup process or felt frustrated during filling a web form? chances are it's due to bad user expertise during filling the form.

Forms are ubiquitous on the internet, here are form design tips for a better User Experience.

1. Leverage HTML input types

HTML input field offers us a collection of various types to specify the type of data expected. We can take advantage of it to provide a better user experience while delegating simple error handling to client-side browsers.

Input types:
1> type="email" specifies that the type of input must be an email address.

<input type="email" id="email" name="email">

Pros:

When users enter an invalid id, most modern browsers show an appropriate error message.
On mobile phones, most of the keyboards show the "@" symbol for easy access in turn improving user experience.

Cons:
Due to its limitations, it will accept john@gibbrishfdsf.com as a valid email id, server-side validation is still required.

2> type="number" specifies that the type of input must be a number.

<input type="number" id="plotNumber" name="plotnumber">

It allows only number input preventing accidental alphabet inputs while preventing a user from making a mistake.
On mobile phones, it opens a numerical keypad giving users the ability to type numbers quickly.

3> type="tel" specifies that the type of input is going to be a telephone number.

<input type="tel" id="phoneNumber" name="phonenumber">

On the desktop, it's similar to normal input, but on mobile phones, it opens a numerical keypad that has the ability to type special characters or alphabets, giving users the ability to type numbers quickly while giving them the liberty to type non-numerical characters.

2. Use autofill.

Give users the ability to autofill forms that are saved in the browser. Users will be able to fill the form quickly by auto-filling common fields like name, email, etc, and focus on more important input tasks.

Google found that by correctly using autofill, users filled forms 30% faster. Read more here:Google Developers

<input type="tel" name="phone" id="phoneNumber" placeholder="+91-45345345435" autocomplete="tel">

3. Dropdowns should be the last resort.

A dropdown is like a swiss army knife for forms, they standardize input, provides predictability, and are flexible, but usability studies show that using a dropdown increases user efforts while filling a form.

4. Use dropdown with search.

When a user has to select their country, the dropdown is probably the best option since it's compact but still, the user has to search through a list of 150+ countries.

A way to provide a good user experience is to allow users to manually enter a search query and dynamically filter the list of available options.

HTML comes with datalist tag which when combined with input tag provides a powerful dropdown + search capability

<form action="/action_page.php" method="get">
  <label for="browser">Choose your country from the list:</label>
  <input list="browsers" name="browser" id="browser">
  <datalist id="browsers">
    <option value="Japan">
    <option value="India">
    <option value="Singapore">
    <option value="Thailand">
    <option value="United States">
  </datalist>
  <input type="submit">
</form>

5. Prevention over correction

Nothing is more frustrating than going through the process of filling a form, clicking captcha image titles that look like "traffic lights" only to find after clicking submit that one of the input was wrongly filled.

Want to experience it?
Go to dribbble.com (a place where designers share their work) and try to signup.

The frustrating part of the signup process is that there's no way for a user to know whether the "username" is available during the signup process. If the username is not available, they show it as an error after we submit it, so we have to again go through the process of guessing a new "username", hope it's available, click on captcha images again and pray.

What they could've done to improve user onboarding is to allow users to signup just with their email and once the is user onboarded, they could let users go through the process of finding a username.

Here's how hashnode does something similar but in a much smoother way.

"To err is human" it's important for us to figure out way's to prevent errors along the way instead of correcting them after the user has gone through a tedious process of filling a form.

If you made it till here, thanks for reading!
This is part 1 of form design guidelines, more design + dev related blogs coming soon.

The algorithm behind Ctrl + F.

Akhil — Sun, 05 Jul 2020 02:39:28 +0000

Ctrl + F on chrome opens up a search box that is used to find text on a web page, pdf, etc. It's one of the fastest ones I have seen and decided to dig deeper into what's going on.

So let's go on a journey of implementing a fast string matching algorithm.

Note: The algorithm which we will implement might be similar to the one used in Chrome, but since its Google we're talking about, they might've made optimizations

You might be wondering why do we need an algorithm when we have regular expression which does the same?

Yes we have regular expressions at our disposal but regular expressions are slow when we task it with finding patterns on large data, regular expression is awesome when we task it with finding a "dynamic patter" like all 10 digit phone numbers starting with +91, but in this case, we want to find one particular string.

If you want to know more Read here

This leaves us the only option of implementing a pattern matcher. Let's start with basic we can think about. We're given a document containing millions of words and we want to find one word, how shall we approach this? It's like finding a needle in a haystack.

Naive Approach

The first idea that we think of is comparing pattern and string character by character :

Implementation :



let string = "ATAATTACCAACATC";
let pattern = "ATC";
let position = [];
let found = true;
for(let i=0;i<string.length;i++){
  found = true;
  for(let j=0;j<pattern.length;j++){
    if(string[i+j] != pattern[j]){
      found = false;
      break;
    }
  }
  if(found){
    position.push(i);
  }
}

console.log(position);

But this performs in O(nm) time complexity, which is very slow.

How to optimize it?

For each string, if it doesn't match, we move by one character. How about skipping the whole word?

In this case, instead of starting all over again, we skip the string when it mismatches.

In the previous approach, we compared string nearly 45 times, here we compared string only 15 times which is a huge leap.

Here we can perform an optimization, instead of comparing from the front, how about comparing from the end?

In this case, we compared the string just 9 times, which is nearly half of the previous case.

But as you might've guessed this has a huge flaw of, what if the end characters match but starting character mismatch.

So we need a concrete algorithm that will skip characters such that overall character comparison decreases.

What other options do we have?

One thing which we could do is instead of moving the entire pattern, we move a part of the pattern.

We match each character between mismatched string and pattern, then we check if we have any common characters, if we do then we move only part of those characters.

In this case, we did 12 comparison operations and this will work if compare string and pattern from either side.

This algorithm is called the Boyer Moore Pattern Matching algorithm.

Implementation of Boyer Moore Pattern Matching algorithm

This is a modified version of the original algorithm, the original algorithm found only the first instance of the pattern, here we're finding all the occurrences of the pattern.

Step 1> create an empty map of size 256 (because 256 ASCII characters) and set to -1.



let string = "ATAATTACCAACATCATAATTACCAACATCATAATTACCAACATCATAATTACCAACATCATC";
let pattern = "ATC";

let M = pattern.length;
let N = string.length;
let skip;                            //to determine substring skip
let res = [];                        //to store result

let map = new Array(256);            //array of 256 length

Step 2> Map character to its index in the pattern.



for(let c = 0;c<256;c++){
  map[c] = -1;                       //initialize to -1
}

for(let j=0;j<M;j++){
  map[pattern[j]] = j;               //initialize to the it's index in pattern
}

Step 3> Loop over the string, notice that in the for loop, instead of "i++", we're using i+= skip, ie skip that part of the string.



for(let i=0;i<=N-M;i+=skip)

Step 4> Set skip to 0 during each iteration, this is important.



for(let i=0;i<=N-M;i+=skip){
  skip=0;
}

Step 5> Match pattern with string.



for(let i=0;i<=N-M;i+=skip){
  skip=0;
  for(let j = M-1;j>=0;j--){

    if(pattern[j] != string[i+j]){
      skip = Math.max(1,j-map[string[i+j].charCodeAt(0)]);
      break;
    }
  }
}

Step 6> If there's a mismatch, find the length that must be skipped, here we perform



   skip = Math.max(1,j-map[string[i+j]]);

In some cases like eg : "ACC" and "ATC", in these cases the last character's match but rest do not.
Logically we must go back and match first "C" of the string with "C" of pattern, but doing so will mean that we are going back which we logically shouldn't or else we will be stuck in an infinite loop going back and forth.
To ensure that we keep on going forward with the matching process, we ensure that whenever we come across situations when there's a negative skip, we set skip to 1.

Step 7> If the skip is 0, ie there we no mismatch, add "i" to the result list.



if(skip == 0){
    console.log(skip)
    res.push(i);
    skip++;
  }

Combining them all :



let string = "ATAATTACCAACATCATAATTACCAACATCATAATTACCAACATCATAATTACCAACATCATC";
let pattern = "ATC";

let M = pattern.length;
let N = string.length;
let skip;
let res = [];

let map = new Array(256);

for(let c = 0;c<256;c++){
  map[c] = -1;
}

for(let j=0;j<M;j++){
  map[pattern[j]] = j;
}

for(let i=0;i<=N-M;i+=skip){
  skip=0;
  for(let j = M-1;j>=0;j--){

    if(pattern[j] != string[i+j]){
      skip = Math.max(1,j-map[string[i+j].charCodeAt(0)]));
      break;
    }
  }
  if(skip == 0){
    res.push(i);
    skip++;
  }
}

console.log(res);

That's it! That's how Boyer Moore's pattern matching works.

There are many other Pattern Matching algorithms like Knuth Morris Pratt and Rabin Karp but these have their own use cases.

I found this on StackOverflow you can read it here but in a nutshell:

Boyer Moore : Takes O(m) space, O(mn) worst case ,best case Ω(m/n). preforms 25% better on dictionary words and long words. Pratcial usecase includes implementation of grep in GNU for string matching, chrome probably uses it for string search.

Knuth Morris Pratt: Takes O(m) space, O(m+n) worst case, works better on DNA sequences.

Rabin Karp: Use O(1) auxiliary space, this performs better under searching for long words in a document containing many long words (see StackOverflow link for more).

I hope you liked my explanation. I usually write about how to solve interview questions and real-life applications of algorithms.

If I messed up somewhere or explained something wrongly, please comment down below.

Thanks for reading! :)

github:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/boyermoore.js

PS: I am looking for job, if you want someone who knows's how to design UI/UX while keeping development in mind, hit me up :) thanks!

Kth Smallest Element in a BST, solving Netflix Interview question.

Akhil — Sat, 04 Jul 2020 03:01:25 +0000

Question: Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Eg : Input: root = [5,3,6,2,4,null,null,1], k = 3

Output: 3

Let's solve this.

First, we need to traverse the tree, but how?

Looking at the question we can see that it's a BST it a Binary Search Tree.

A binary search tree has the following properties :
1 > All the elements on the left subtree of a node have values less than the current node.
2 > All the elements on the right subtree of a node have values greater than the current node.
3 > Performing inorder traversal on a Binary search tree will result in a sorted list.

Since we want to find the kth Smallest node, performing inorder traversal on the tree would make sense since we will get a sorted list and it will be easier to determine the kth smallest element.

Inorder travesal Algorithm

In Inorder traversal, we first process all nodes in left subtree of a node, then process the current node, then visit all the nodes in right subtree.

Visually :

Let's work on the next part ie determining the kth smallest element, one way could be to store all the node values in an array and determine the kth smallest, another space-saving way will be to keep a counter, keep on increasing it, and when the counter hit's k, return the node value.

Visually :

Converting coffee to code :

var kthSmallest = function(root, k) {
    let val;
    function inorder(root){
        if(root == null) {
            return;
        }

        inorder(root.left);
        k--;

        if(k == 0) {
            val = root.val;
            return;
        }

        inorder(root.right);
    }
    inorder(root);
    return val;
};

If you've made it till here, comment on the expected time complexities in the best case, the average case, and worst-case scenarios.

I hope you liked my explanation. If you know a better way then please share it with us :)

Github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/kthSmallestInaBST.js

Sum root to leaf numbers, solving an Amazon interview question

Akhil — Sun, 28 Jun 2020 02:25:49 +0000

Question : Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Eg :

         1
        / \
       2   3

For the tree above,
Path 1 = 1 -> 2 = 12
Path 2 = 1 -> 3 = 13
Output will be 12 + 13 = 25

Just by reading the question, we can say that we've to traverse the tree, but we've to traverse in such a way that the parent -> child relation is maintained.

Depth First Traversal is a type of traversal in which we select a node, and explores as far as possible along each branch before backtracking.

An animation from Wikipedia :

Converting it to code:

   dfs(node){
       if(node == null) return;

       // do something

       dfs(node.left);
       dfs(node.right);
   }

Next is how to process the value at the current node, if we look closely, at each level we're multiplying previous level result by 10 and add the value at the current node level.
Something like this :

  dfs(node,prev){
      if(node == null) return;

      let curr = prev * 10 + node.val;

      dfs(node.left,curr);
      dfs(node.right,curr);

A bit about call stack :

Since here we're recursively calling dfs, for each call a separate call stack is maintained which tracks the root -> current node value and it doesn't interfere with root -> node value of other nodes since they exist in a separate call stack . See animation at the end to understand this better.

The last obstacle is how to return the computed value.

We know that a leaf node is a node whose left and right child are null , that's our clue to return the root -> leaf value for a particular subtree path.

    if(root.left == null && root.right == null) 
       return prev*10 + node.val;

When we come across an internal node, we just add the values returned from the left and right subtrees and return it.

     return dfs(root.left,curr) + return dfs(root.right,curr);

Visualizing each step :

Putting everything together in a code :

var sumNumbers = function(root) {
    return dfs(root,0);
};

function dfs(node,prev){
    if(node == null) return 0;
    if(node.left == null && node.right == null){
        return prev*10 + node.val;
    }

    let curr = prev*10 + node.val;

    return dfs(node.left,curr) + dfs(node.right,curr);
}

I hope you liked my explanation :D

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/rootToleaf.js

Valid parentheses, solving a Facebook interview question.

Akhil — Sat, 27 Jun 2020 02:07:45 +0000

This is one of the most commonly asked screeing questions, Especially if the interview is conducted by Hackerrank, there's a good chance that they will ask this question. I was asked this exact same question 4 times by Hackerrank.

Question : Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
An empty string is considered valid.

Eg:



   string = "()[]{}"              //valid
   string = "[{()]}"              //invalid
   string = ""                    //valid

Let's solve this,

At its bare minimum, the question is asking us to find matching opening and closing parentheses. So for :
"(", ")" is the valid closing parentheses
"{", "}" is the valid closing parentheses
"[", "]" is the valid closing parentheses

Or in other words, we can say that the "pairs" cancel out each other, from this we can say that the order matters.

A good data structure that will help us with :
1 > Storing the parentheses and cancel them when the match is found,
2 > Keeping track of parentheses

is Stack. We shall push the opening parentheses on to the stack and pop it when we encounter a closing parenthesis, and that the same time we can check if the closing parenthesis is the valid match for the parentheses being popped.

Implementation - 1

Here we can make a small optimization of checking if the length is even if it's not then obviously the string is not valid.
Converting the above idea into code :



var isValid = function(S) {
    let stack = [];
    if(S == '') return true;
    if(S%2 != 0) return false;
    for(let s of S){
        if(s == '(' || s == '{' || s == '['){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c == '(' && s != ')'){
                return false;
            }
            if(c == '{' && s != '}'){
                return false;
            }
            if(c == '[' && s != ']'){
                return false;
            }
        }
    }

    if(stack.length != 0) return false;      // for conditions like "{([])}}}" 
    return true;
};

Now this works well, but can we do better? There are a lot of if-else conditions just for checking the "pairs". Let's try to make it more concise.

Implementation - 2

Since the main work of the if conditions are to match the parentheses, we use another data structure, the Hashmaps.

Since a closing parenthesis must match with a corresponding opening parenthesis, we create a mapping between closing and opening parenthesis.

So the algorithm works this way :
1 > Check if the current symbol is in the hashmap, if not the push it on the stack.
2 > If the current symbol is in the hashmap, then pop from the stack and compare it with the value corresponding to hashmap entry.

So if the top of the current symbol is ")" then we pop from the stack, compare the popped value with the value corresponding to ")" in hashmap which is "(", if they arent same then the string is not valid.

The code will make it a lot clear.



var isValid = function(S) {

    if(S == '') return true;
    if(S.length%2 != 0) return false;

    let map = {};
    map[")"] = "(";
    map["}"] = "{";
    map["]"] = "[";

    console.log(map);

    let stack = [];
    for(let s of S){
        if(!map[s]){
            stack.push(s);
        }else{
            if(stack.length == 0) return false;
            let c = stack.pop();
            if(c != map[s]) return false;
        }
    }

    if(stack.length !=0) return false;
    return true;
};

I hope you liked my explanation if you know a better way of solving this problem then please share it with us :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js

Longest substring without repeating characters, solving Google interview question.

Akhil — Sun, 21 Jun 2020 02:03:35 +0000

Question : Given a string, find the length of the longest substring without repeating characters.

Eg : Input = "abcabcbb" Output = 3, Since "abc" is longest substring without repeating characters.

From the question it self, we can say that we need some sort of data structure that can keep track of unique characters.

This paves the way towards using Set

Now how to parse the string ? Notice that question asks for "substring".

If question asks for any sort of substring releated, try solving it with two pointer appraoch

Two Pointer approach

1 > This approach is simple and intuitive, for this question we will keep two pointer, left and right.
2 > We shall initialize left and right to 0.
3 > Move the right pointer by 1, and add the corresponding character to the set.
4 > If character is already present in the set then remove the character at left pointer and move the left pointer by 1.
5 > Keep on doing this till right pointer reaches the end of string.

The code is really simple and intutive :

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let right = 0;
    let max = 0;
    let set = new Set();
    while(right<s.length){
        if(set.has(s[right])){
            set.delete(s[left]);
            left++;
        }else{
            set.add(s[right]);
            right++;
            max = Math.max(max,set.size);
        }
    }
    return max;
};

That's it ! Hope you liked my explanation :)

Cracking the interviews is easy if we can see the hidden patterns :P

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/longestSubstringwithUniqueCharacters.js

Remove Nth node from the end of a Linked List. Solving a Paypal interview question.

Akhil — Sat, 20 Jun 2020 02:26:44 +0000

Question: Given a linked list, remove the n-th node from the end of the linked list and return its head.

eg if we're given a linked and asked to remove the 2nd node from the end:

Give it a try and comeback.

Brute Force

A naive approach might be :
1 > Calculate the total length for the linked list.
2 > Determine the count of the node which is going to be nth from the end.
3 > Parse through the linked list and delete the node by setting it's previous node's next to current node's next.

Code :

var removeNthFromEnd = function(head, n) {
    if(n == 0) return head;
    let dummy = head;
    let len = 0;
    while(dummy.next != null){
        len++;
        dummy = dummy.next;
    }
    let nth = len-n+1;
    let prev = null;
    dummy = head;
    while(nth-- !=0){
        prev = dummy;
        dummy = dummy.next;
    }
    if(prev !=null)
    {   prev.next = dummy.next;
        dummy.next = null;
    }else{
        return head.next;
    }
    return head;
};

An edge case: if for eg:

List : [1,2]
n : 2

In this case, 2 - 2 = 0, so the head must be removed, which means prev will be null. So the following case :

if(prev !=null)
    {   prev.next = dummy.next;
        dummy.next = null;
    }else{
        return head.next;
    }

But here we parsed the linked list twice, can we do better?

To solve this efficiently, we use concept of two pointers. The idea is really simple and intuitive.

Algorithm :
Step 1> Create two pointers slow and fast,
Step 2> first move the fast pointer to the nth node.
Step 3> now move the fast (at nth) and slow (at head) pointers one node at a time.
Step 4> when the fast pointer reaches the end, slow pointer is at the nth node.

Animation :

var removeNthFromEnd = function(head, n) {
    let fast = head;
    let slow = head;
    while(n-- > 0){
          fast = fast.next;
    }
    let prev = null;
    while(fast != null){
        fast = fast.next;
        prev = slow;
        slow = slow.next;
    }
    if(prev == null){
        return head.next;
    }
    prev.next = slow.next;
    slow.next = null;
    return head;

};

That's it ! Hope you liked my explanation.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/removeNthNodefromEnd.js

Power of 2, solving a google interview question. Playing with bits.

Akhil — Sat, 13 Jun 2020 02:43:10 +0000

Question : Given an integer, write a function to determine if it is a power of two. (Range: 1 - 2^31-1)

Eg: Input : 16, Output : true since 2^4 = 16.
Input : 18, Output : false.

Brute Force

So the obvious brute force approach will be to just divide 2 and check if it reaches 1.

var powerOftwo = function(n){
    if(n<=0) return false;
    while(n%2 == 0) n = n/2;
    return n == 1;
}

Percompute and Use Set

Since we're give that the range is in between 0 - 2^31-1, we could use this to precompute various possible output, save them into a set and cross check:

  let set = new Set();

  for(let i=0;i<31;i++){
    set.add(Math.pow(2,i));
  }

  console.log(set);

  var powerOfTwo = function(n){
    if(set.has(n)) return true;
    return false;
  }

Now that we know what we want to accomplish, let's think about what google might expect from us.

Tip : One common pattern I noticed is that whenever a company asks a question which looks easy on understand and easy to implement, that question has to be somehow related to bit manipulation.

So how do we relate power of 2 and bits

As we know, for a computer everything boils down to a combination of 0's and 1's including numbers. So let's see how the numbers which represent 2^n for n=0 to 31 are represented in bit form.

So the common pattern here is that the numbers that are power of 2's have only 1 bit set to 1 and rest of it is 0.

So how do we use this to our advantage ? Let's look at what operations we have to work with.

   &: and operator          1&1 = 1, 0 & anything = 0
   |: or  operator          0&0 = 0, 1 & anything = 1
   ^: xor operator          x^x = 0, x^n = 1
   ~: negate                ~1 = 0 | ~0 = 1

Tip: if the question is regarding bit manipulation, first try solving with & and ^ operators

Let's try solving this with & operator. But what should we & it with ?

Let's generate a number, if a number is odd, +1/-1 will generate an even number and vice versa.

Now that we have "&" operator and 2 numbers let put them together.

   even number : 6  = 110 
            +1 : 7  = 111
            -1 : 5  = 101

   6&7 = 6   6&5 = 4

   multiple of 2 : 16 = 10000
              +1 : 17 = 10001
              -1 : 15 = 01111

   16&17 = 16  16&15 = 0

Here comes our solution, 16&15 becomes 0 since as proved earlier that a number if it's power of 2, has only 1 bit set, so n-1 will set all previous bit's from current position to 1.

eg:

   8 : 1000       7: 0111      8&7 = 0
   16: 10000     15: 01111    16&15 = 0 
   32: 100000    31: 011111   32&31 = 0

But at the same time if we use an odd number

eg:

   17: 10001     16: 10000     17&16 = 16

From this we can say that n&(n-1) = 0, if n is power of 2.

Due to this our code boiled down to :

   var powerOfTwo = function(n){
    n = n&(n-1);
    return n == 0;
   }

Amazing isn't it ? How few bit manipulation cause such drastic results aand lead us to a more concise readable code.

If you want to practice something similar, solve this :

Question : Count the number of ones in the binary representation of the given number.

Comment your solution for this question :)

I hope you liked my explanation comment down below if I messed up somewhere.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/powerOfTwo.js

Topological sort, Solving Google Interview Question

Akhil — Sun, 07 Jun 2020 02:42:36 +0000

If we want to become a full-stack developer we follow the following path :

First, we learn basic HTML & CSS, then we learn Javascript. Then the path diverges into FrontEnd development and BackEnd development, for becoming a backend developer we need to study a database and finally we become a full stack developer.

So this path is fixed, to learn a frontend framework, you need to know the basics of HTML, CSS, and JavaScript.

There is a one-directional relationship between components, we can't first learn React and then learn HTML.

Topolocial Sort is the ordering in which things should happen/occur, there are many real-life use like when processing large data, data is supplied in chucks so that the resource utilization is optimal and then the processed data is transferred. Largest friendship distance in the network also known as six degrees of separation on a social media network is solve using Topological Sort.

Now that we know what's topological sort and it's uses, let's solve a question asked frequently at Google.

X-----------------------------------------------------------X

Question: Course Scheduler

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

Given input is numCourses for the number of courses to take, prerequisites array which determines the dependency between courses. If it's not possible then return 0.

For eg : if give data is [[2,0],[2,1],[3,2],[4,2],[4,5],[6,3],[6,4]]

Our graph will look like :

From this we can say a possible order could be : [0,1,5,2,3,4,6]

Step 1: Building the graph

Graphs are represented as adjacency list/adjacency matrix. Both are easy to implement. In this case, we shall use the adjacency list since the graph is a sparse graph (ie many nodes aren't connected to each other).

Along with our graph, we shall maintain an array, indegree which will maintain the count of prerequisites for node "i"

     var topologyOrder = function(numCourses,prerequisites){

        // create each individual node
        let graph = new Array(numCourses+1);

        // to track the number of dependencies required by each node
        let indegree = new Array(numCourses+1).fill(0);

        for(let i=0;i<numCourses+1;i++){
            graph[i] = []; 
        }

        for(let prerequisite of prerequisites){
            let from = prerequisite[1];
            let to = prerequisite[0];
            graph[from].push(to);
            indegree[to]++;
        }
        console.log(graph);
        console.log(indegree);
  }

By end of this operation our graph will look like :

   graph = [[2]                // 0 -> 2
            [2]                // 1 -> 2
            [3,4]              // 2 -> 3, 2 -> 4
            [6]                // 3 -> 6
            [6]                // 4 -> 6
            [4]                // 5 -> 4
            []]                // 6 -> end   

 indegree = [ 0,               // 0 ie no prerequisites
              0,             
              2,               // 2 courses are required before this
              1,               // 1 course is required
              2,               
              0,
              2 ]

Now that we have a graph, information about how many courses needs to be finished before taking a certain course. Let's move ahead to the next step.

Breadth First Travesal

First step will be to take classes which have indegree of "0" ie no prerequisites.

Also, we maintain a queue to process each node in graph as we always do in a BFS traversal.

   let queue = [];

   for(let i=0;i<indegree.length;i++){
       if(indegree[i] == 0){
            queue.push(i);
       }
   }

Our next step will be to process each node in queue, but before that, we need to ensure that there are nodes to be processed in the queue.

Eg: if given input is [[0,1],[1,0]], ie 0 -> 1 and 1 -> 0. We're in a deadlock.

   if(queue.length == 0) return 0;

Our next question is how to process the nodes? And at the same time, we have to ensure that there's a unidirectional flow and a node isn't visited again because then we end up in an infinite loop.

So we create an array and a set and a counter :

   let res = [];                // to store the result
   let visited = new Set();     // to store visited nodes
   let count = 0;               // safety check to ensure all nodes are visited

Next steps are :
Step 1> Go through the queue,
Step 2> Pop a node
Step 3> Process that node by setting it as visited and adding it to result
Step 4> visit all the child nodes of current node and decrease their indegree by 1
Step 5> Increment the count
Step 6> repeat steps 1 - 5 till queue is empty.

while(queue.length>0){
      // pop a node from queue
      let node = queue.shift();

      // check if it's visited, if it's the return 0
      if(visited.has(node)) return 0;

      // add node to visited set
      visited.push(node);

      // add node to result
      res.push(node);

      //loop over all the nodes require current node as a prerequisite
      for(let n of graph[node]){

          // since current node is processed, decrease the indegree of node "n" by 1
          indegree[n]--;

          // if node "n" indegree equals 0, add it to the queue so that it can be processed
         if(indegree[n] == 0) queue.push(n);
      }

      // incremenet count by 1
      count++;
}

Let's see the above steps in animation. If possible open the gif in another tab and compare each step with the above code.

putting it all together :

 var topologyOrder = function(numCourses,prerequisites){

       let graph = new Array(numCourses);

       let indegree = new Array(numCourses);

       for(let i=0;i<numCourses;i++){
           graph[i] = []; 
       }

       for(let prerequisite of prerequisites){
           let from = prerequisite[1];
           let to = prerequisite[0];
           graph[from].push(to);
           indegree[to]++;
       }

       let queue = [];

       for(let i=0;i<indegree.length;i++){
            if(indegree[i] == 0){
               queue.push(i);
            }
       }

       if(queue.length == 0) return 0;

       let res = [];                
       let visited = new Set();     
       let count = 0;

       while(queue.length>0){
             let node = queue.shift();
             if(visited.has(node)) return 0;
             visited.add(node);
             res.push(node);
             for(let n of graph[node]){
                  indegree[n]--;
                  if(indegree[n] == 0) queue.push(n);
             }
             count++;
      }

      return count == numCourses ? res : 0;
}

Thanks a lot if you made it till here :) I hope you liked my article.

If I messed up somewhere or didn't explain clearly, do comment.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/TopologicalSort.js

Convert Number to Hexadecimal, solving a short Facebook Interview question

Akhil — Sat, 06 Jun 2020 14:17:21 +0000

Question : Given an integer, write an algorithm to convert it to hexadecimal.

Lets tart with what's hexadecimal numbers ?

Hexadecimal number are the number represented in base 16, it consists of 16 symbols

   +--------------------------------------------------------------------+
   | Decimal     : 0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 |
   | Hexadecimal : 0  1  2  3  4  5  6  7  8  9   A   B   C   D   E   F |
   +--------------------------------------------------------------------+

To make our lives easier, let's create an array that will store the hexadecimal values to its corresponding decimal index.

   let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];

Handling Positive Numbers

Handling positive numbers is easy. It's a 3 step operation and it's intuitive :

Step 1 : store the result of num%16
Step 2 : perfrom num/16
Step 3 : perform step 1,2 till num > 0

    let res = "";

    while(num > 0) {
        let digit = num % 16;
        res = arr[digit] + res;
        num = Math.floor(num / 16);
    }

Handling Negative Integers

Handling negative integers becomes a bit tricky, since we can't write -#3AC to represent negative hexadecimal numbers, so let's a dive deeper and represent numbers in their binary forms.

And since any number is bolied down to binary 0's and 1's, we face the same issue of representing negative numbers in binary format since a computer won't understand -0010.

So to solve this issue, negative numbers are represented by setting Most Significant Bit to 1.

So how can we use this two key information to solve our problem ?
On closer look we see this :

Since an integer is 32-bit, which is further broken down to parts of 4-bit, and binary representation of numbers 8 - 16 have 1 set as their Most Significant Bit and 8 - F represent those numbers, so we could say that 8 - F range could be used to represent negative numbers.

So a hex number #FFFFF63C represents a negative number.

Whenever we come across a number < 0, we add 2^32, to it to convert into a format which could be mapped with hexadecimal mappings.

var toHex = function(num) {
    let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];

    if (num == 0) return "0";

    if (num < 0) {
        num += Math.pow(2,32);
    }
    let res = "";

    while(num > 0) {
        let digit = num % 16;
        res = map[digit] + res;
        num = Math.floor(num / 16);
    }
    return res;
};

This was a normal way to do it, now let's see an even smarter way of achieving the same which will definitely impress your interviewer.

Smarter way

For this we need to understand two basic concepts of bit manipulation.

   & operator
   1 & 1 = 1
   0 & 0 = 0
   0 & 1 = 0
   1 & 0 = 0

   >>> right shit operator
   shifts bit's to right
   5 >>> 1 = 101 >>> 1 = 10 = 2. 
   Here the number is being shifted right once.

So if we perform -14&15 , -14&15 we get, &15 because we want to convert it to hex and F equals 15 :

Based on this we can say that &15 will convert negative decimal in relevant hexadecimal negative value while preserving positive decimal value.

Now all the basics out of the way, this technique consists of two steps.

Step 1 > res += map[num&15]
Step 2 > num>>>4.
Step 3 Repeat step 1 & 2 till num != 0

We performing step 2 is similar to diving num/16. Since 15 is 1111 ie 4 bits in binary form, we preform the "&" operation and remove those 4 bits.

Converting it to code :

var toHex = function(num) {
    if (num == 0) return '0';
    let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
    let result = '';
    while (num != 0) {
        let c = map[num & 15]; // map last 4 bits to a hex digit
        result = c + result;
        num = num >> 4;
    }
    return result;
};

I hope you liked my article :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/decimalToHex.js

How did this image brick Android phones?

Akhil — Sat, 06 Jun 2020 03:51:18 +0000

Few day's ago this tweet went viral,

People tried it anyway and this was the aftermath :

So why is this beautiful landscape picture bricking Android phones?

The answer lies in one pixel and basic math.

A pixel comprises of a color and a color comprises of three basic colors, Red, Green, Blue or RGB.

As you might remember from CSS, the typical range for R:G:B lies between 0 - 255, and android handles it well. But there's a huge range of color space which android doesn't understand and converts it RGB.

What's color space? It's basically this :

as you might see, the android sRGB space is narrow compared to other color spaces, but how is this relevant?

The above image was captured in Prophoto RGB color space, so when you open the image in the gallery, android tries to convert the image into sRGB color space, and here lies the problem.

Even dev.to converts it to relevant color space :

There's one pixel in this image that causes this issue.

So when Android comes across a photo whose color space it doesnt support it modifies the image by the following formula :

and the overall result of this must be < 255.

But for one pixel the RGB values are:

Doing the math,

But android, instead of taking floating value rounds off the numbers:

Since 256 above the max limit, android throws an error. When we open the image in the gallery, it encounters the error and just might shut off the gallery.

But when we set the image as a wallpaper, it's like setting up an endless loop of errors. At some point the overflow and crashes the phone.

It's fix ?

   pixel_value = Math.min(255,res);
   //might be more complicated than this but this is my best guess

Crazy isn't it? How one pixel could crash our phones.

I hope you liked my article. Until next time :)

Source : https://twitter.com/UniverseIce/status/1266943909499826176
https://www.youtube.com/watch?v=iXKvwPjCGnY
https://del.dog/suthokuxid.log
https://twitter.com/HrX2003/status/1267049418659901440
https://hdqwalls.com/wallpaper/5120x2880/sunset-at-st-mary-lake-glacier-national-park-5k

Design Trie. Solving an Uber Interview Question

Akhil — Sun, 31 May 2020 02:57:01 +0000

I came across this post on how a puzzle landed him a job at Google. This article is about the Data structure he used to solve the problem.

In this article we shall cover :
1> What are Tries trees.
2> Why and how are they used.
3> How to Implement a simple Trie in javascript.

So bisaclly he used a Trie/Suffix Tree to solve the puzzle,

What are Trie ?

Tries are a tree-based Data Structure used to efficiently store string.

How are they used ?

Imagine you're tasked with storing all city names in the United States.

The naive approach would be to get all the city name and store it in an array, but since you're a ninja developer you notice a pattern that might help to reduce the total space required to store names of all cities.

Eg: following is the list of all cities that have prefix "New" in their name.

 "New Albany"                          "New Bedford"
 "New Bern"                            "New Braunfels"
 "New Britain"                         "New Kensington"
 "New London"                          "New Madrid"
 "New Market"                          "New Martinsville"
 "New Mexico"                          "New Milford"
 "New Orleans"                         "New Paltz"
 "New Philadelphia"                    "New Rochelle"
 "New Smyrna Beach"                    "New Ulm"
 "New Windsor"                         "New York"
 "New York City"                       "New Brunswick"
 "New Castle"                          "New Glarus"
 "New Hampshire"                       "New Harmony"
 "New Haven"                           "New Hope"
 "New Iberia"                          "New Jersey"

So instead of repeating "New" everytime, how about compressing it ?

Since "New" is a common prefix, we could remove the "New" from all the words and create a data structure which automatically attaches "New" to cities mentioned above something like :
Eg: for 4 cities, it will look like :

But how about going a step even further?
Since "New Madrid", "New Market" and, "New Martinsville all have "New Ma" in common, let's compress out string even further.

By doing so for each city we reach here :

Have fun building one here

Cities that have the same common prefix are grouped together, this helps in decreasing the space.

And there's more !!!
Searching becomes a lot faster by using tries, how?

Let's simulate a search which is present in both trie and array:

Search is super fast since instead of iterating over an array, within 6 ticks we got to the result.

Search string which isn't present in trie and array:

Within 4 ticks, we could determine if the search string is present or not.

Applications :

Trie are used in many places like autocomplete feature (we shall build this in a next blog), Data Analytics, Gnome Analysis, Spell Checkers etc.

Now that we know what's trie, and why is it useful, let's build one !

Building a Trie

We shall build Trie for: ['abc','abab','babc','cab']

To be a bit more efficient we shall build Trie using Objects to leverage O(1) lookups.

Step 1

Since we're basically building a Tree, we need a root, for Trie, the root will be empty but will store information about its child objects.

class Trie{
    constructor(){
         this.root = {}
    }
}

Step 2:

Now let's iterate through each string in the array ['abc','abab','ba','cab'] and create a tree.

First is 'abc':
We check is 'a' is present in the tree, since root is empty, it's not present so add 'a' to trie, then 'b', then 'c'. Now since we've reached the end of trie, we store the word "abc" to signify that "yes", "abc" is a valid word.

We end up here :

Second "abab".
We repeat the same process, we check is "a" is present, since it is present, we won't create a new node instead go to "a" node, then we check is "b" is present, it's connected to "a" so go to "b" node, then again we check if "a" is present, since no "a" node is connected to "b", we create a new "a" node, connect it to "b" and keep on repeating the operation.

So inserting a string into a Trie boils down to 3 basic steps :

1> If the character isn't connected to node, create a new one and travese.
2> If the character is connected to node, travese it.
3> If it's the end of string, add the string to the leaf of current subtree.

Visualizing :

Let's translate it into code :

  insert(word) {
    let node = this.root;                            
    for (let c of word) {
      if (node[c] == null) node[c] = {};             //if {c} not present, create one
      node = node[c];                                // travese{c} 
    }
    node.isWord = true;                              // add word.
  }

So for each string, start from root and travese.
For each character c, check if object is created, if not then create one and travese it.
At the end we set "abc" to true signifying that, "yes, string with "abc" is possible.

So for ["abc","abab"] our actual trie will look like :

let root = {
  "a":{
    "b":{
      "c":{
        isWord:true
      },
      isWord:false,
      "a":{
        "b":{
          "isWord":true
        },
        isWord:false
      },
      isWord:false
    },
    isWord:false
  },
  isWord: false
}

console.log(root.a);
console.log(root.a.b);
console.log(root.a.b.c);
console.log(root.a.b.c.isWord);
console.log(root.a.b.a);
console.log(root.a.b.a.b);
console.log(root.a.b.a.b.isWord);
console.log(root.a.b.isWord);
console.log(root.a.b.f == null);

Now let's create a function to traverse it, which is similar to inserting:

 traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

For searching, we traveser the the string and in the end we check if "isWord" set to true :

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }

putting it all together :

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (let c of word) {
      if (node[c] == null) node[c] = {};
      node = node[c];
    }
    node.isWord = true;
  }

  traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }
}

I think this article is long enough, next article I will write about how to create a search autocomplete based on Trie.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/DataStructures/Trie.js