Problem

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t.

For example,"egg" and "add" are isomorphic, "foo" and "bar" are not.
function isIsomorphic(s, t) {
    if(s==null || t==null)
        return false;
 
    if(s.length != t.length)
        return false;
 
    if(s.length==0 && t.length==0)
        return true;

  var map = {};
  for(var i=0; i<s.length; i++){
        var c1 = s.charAt(i);
        var c2 = t.charAt(i);
 
        var c = getKey(map, c2);
        if(c != null && c!=c1){
            return false;
        }else if(map[c1]!=null){
            if(c2 != map[c1])
                return false;
        }else{
            map[c1]=c2;
        }
    }
 
    return true;
}
 
// a method for getting key of a target value
function getKey(map, target){
    for (var i in map)     {
        if (map[i] == target) {
            return i;
        }
    }
    return null;
}

console.log(isIsomorphic('ett','add'));
Read More

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.

For example:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Naive Approach

It can be solved using Stack
  1. Read array
  2. Push item into stack if it is number
  3. Pop numbers from stack, if item is operator, do the operation for those numbers and push into the stack
function evalRPN(tokens) {
    var returnValue = 0;
    var operators = "+-*/";

    var stack = [];
        for (var i=0; i<tokens.length; i++) {
                if (operators.indexOf(tokens[i]) == -1) {
            stack.push(tokens[i]);
        } else {
            var a = parseInt(stack.pop());
            var b = parseInt(stack.pop());
            switch (tokens[i]) {
            case "+":
                stack.push(a + b);
                break;
            case "-":
                stack.push(b - a);
                break;
            case "*":
                stack.push(a * b);
                break;
            case "/":
                stack.push(b / a);
                break;
            }
        }
    }

    returnValue = parseInt(stack.pop());

    return returnValue;
}

console.log(evalRPN(['2','1','+','3','*']));

Complexity

This algorithm takes O(n) space and O(n) time
Read More

Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?

Using intermediate array

  1. First find out correct number of rotations using mod
  2. Create temporary array
  3. Push array elements into that temporary array
  4. Copy that temporary array into  original array
function rotateArray(nums,k) {
    if(isNaN(k) || k < 0) {
      throw "provide valid order";
    }

    if(nums.length == 0) {
      throw "provide valid array";
    }

    if(k > nums.length) 
        k=k%nums.length;
 
    var result = [];
 
    for(var i=0; i < k; i++){
        result[i] = nums[nums.length-k+i];
    }
 
    var j=0;
    for(var i=k; i<nums.length; i++){
        result[i] = nums[j];
        j++;
    }
 
    nums = result.slice();
    console.log(nums);
}

Complexity

Observe above demo. It will take O(n) space and O(n) time

Using bubble rotate

By using bubble swap, we can solve this problem. Move array elements from right side to left side of the array using bubble swap
function rotateArray2(arr, order) {
    if(isNaN(order) || order < 0) {
      throw "provide valid order";
    }

    if(arr.length == 0) {
      throw "provide valid array";
    }
    for (var i = 0; i < order; i++) {
        for (var j = arr.length - 1; j > 0; j--) {
            var temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
    }
  console.log(arr);
}

Complexity

Observe above demo. It will take O(1) space and O(n*k) time

Using Reversal

Divide array into 2 parts based on given order. Reverse first part and then reverse second, then reverse whole array  
function rotate3(arr, order) {
    if(isNaN(order) || order < 0) {
      throw "provide valid order";
    }

    if(nums.length == 0) {
      throw "provide valid array";
    }
    
    order = order % arr.length;
 
    //length of first part
    var a = arr.length - order; 
 
    reverse(arr, 0, a-1);
    reverse(arr, a, arr.length-1);
    reverse(arr, 0, arr.length-1);
 console.log(arr);
}
 
function reverse(arr, left, right){
    while(left < right){
        var temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }   
}

rotate3([1,2,3,4,5,6],3);

Complexity

Observe above demo. It will take O(1) space and O(n) time
Read More
Javascript is most popular scripting language and it is always in first row of stackoverflow tags page.
So why we should not use javascript to implement algorithms. Generally in coding interview, you will have freedom to write algorithms in your favorite language. If you are good at Javascript, then why to go with other languages.

Lets implement some algorithm stuff with JS. The below topics were covered in this article

1) String/Array/Matrix, 2) Linked List, 3) Tree, 4) Heap, 5) Graph, 6) Sorting, 7) Recursion vs. Iteration,
8) Dynamic Programming, 9) Bit Manipulation, 10) Probability, 11) Combinations and Permutations

Debugging JS

to print content in console, we have to use below statement
console.log('hello world'); 
Use chrome or firefox to debug Javascript. Just "right click" > "inspect element" > "click on console".
Then you will see console.

Some useful operations in Javascript

To get char array from string

"Hello world!".split('')
["H", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d", "!"]

Get char from index

var str = "HELLO WORLD";
var res = str.charAt(0); // 'H'

Get length of string

var str = "HELLO WORLD";
var res = str.length; // 11

Get length of array

var sarr = ["H","E"];
var res = sarr.length; // 2

Substring

var str = "HELLO WORLD";
var res = str.substring(1); // "ELLO WORLD"
var res = str.substring(1,4); //"ELL"

Sort array

var nums= [4,2,3,1];
nums.sort(); // 1,2,3,4

Convert string to int

var num = parseInt("10");

Convert array to string

var sarr = ["H","E"];
var res = sarr.join(''); // HE

Slice and copy array

var nums= [4,2,3,1];
var newArr = nums.slice(); // copy array
var newArr = nums.slice(1,3); // 2, 3

Reverse the array

var nums = [1, 2, 3, 4];
nums.reverse(); // [3, 4, 2, 1]

Verify if variable is not a number

var str = "sample";
isNaN(str) // true
var num = 9;
isNaN(num) // false

Classic Problems (String / Array / Matrix)


Read More
Recently I have created Background-Color-Theif.js. In this article You can find logic behind this script.

Lets define background color first. Observe the below Image with plain background. Here main image was centered and background color was spread all over edges and corners of the image. Most of images have background color spread to corners and edges. So we can say " Most dominant color of edges and corners is the background color of the image " 
Lets Consider 10% of width of an Image ( both Left and Right side of image ) are vertical edges,  10% of height of an Image ( both Top and Bottom side of image ) are horizontal edges. Finally the selected areas of image will look like below image.

Project

Background-Color-Theif.js is for grabbing background color of an image. This code consists some code snippets from Color-Theif.js 

Top and Bottom edges

Below image is having size of 300 X 200.  You can see pixel count values in small rectangular boxes.
These edges covers corners also, So no need to retrieve corners pixel values.

Side Edges

You can find pixel count values of Left and Right edges below.
Get all pixel values from corners and edges and find dominant color of it and that color will be background color of image

How to use

Add script to your HTML page

<script src="background-color-theif.js" type="text/javascript"></script>

Define HTML markup

<img src="source.jpg" id="backgroundImage"/>
<div id="backGroundColor"></div>

Javascript

var backgroundColorThief = new BackgroundColorTheif();
var rgb = backgroundColorThief.getBackGroundColor(document.getElementById("backgroundImage"));
document.getElementById("backGroundColor").style.backgroundColor = 'rgb(' + rgb[0] + ',' + rgb[1] + ',' + rgb[2] +')';

Applications

I have implemented some online tools using this script. Take a look at below links
Read More
This is the program of resizing image on mouse wheel scroll. Here I am using image-scaling-library for resizing image, This library gives good quality scaled images. Display Image using JScrollPane to handle overflow of image situations.

Adding Panel to JScrollPane

JFrame frmImageZoomIn = new JFrame();
JScrollPane scrollPane = new JScrollPane();
frmImageZoomIn.getContentPane().add(scrollPane, BorderLayout.CENTER);
JPanel panel = new JPanel();
panel.setLayout(new BorderLayout());
scrollPane.setViewportView(panel);

Adding Image to Panel

Icon imageIcon = new ImageIcon(inputImage);
label = new JLabel( imageIcon );
panel.add(label, BorderLayout.CENTER);

Zoom factor based  on Mouse Wheel Scroll

 Observe notches variable in below code. If user scrolls mouse wheel up then notches value will be -1 or else it will be 1. based on notches  value zoom factor value be changed. Based on zoom factor value image will be scaled
public void mouseWheelMoved(MouseWheelEvent e) {
    int notches = e.getWheelRotation();
    double temp = zoom - (notches * 0.2);
    // minimum zoom factor is 1.0
    temp = Math.max(temp, 1.0);
    if (temp != zoom) {
        zoom = temp;
        resizeImage();
    }
}

Complete Java Code

Update inputImage  variable with the your image file path and then run this code
import java.awt.EventQueue;
import javax.imageio.ImageIO;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JScrollPane;
import java.awt.BorderLayout;
import javax.swing.JPanel;
import com.mortennobel.imagescaling.ResampleOp;
import java.awt.event.MouseWheelListener;
import java.awt.event.MouseWheelEvent;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

public class ImageZoom {

    private JFrame frmImageZoomIn;
    private static final String inputImage = "C:\\my-pfl-pic.jpg"; // give image path here
    private JLabel label = null; 
    private double zoom = 1.0;  // zoom factor
    private BufferedImage image = null;
    /**
     * Launch the application.
     */
    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                try {
                    ImageZoom window = new ImageZoom();
                    window.frmImageZoomIn.setVisible(true);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the application.
     * @throws IOException 
     */
    public ImageZoom() throws IOException {
        initialize();
    }

    /**
     * Initialize the contents of the frame.
     * @throws IOException 
     */
    private void initialize() throws IOException {
        frmImageZoomIn = new JFrame();
        frmImageZoomIn.setTitle("Image Zoom In and Zoom Out");
        frmImageZoomIn.setBounds(100, 100, 450, 300);
        frmImageZoomIn.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        
        JScrollPane scrollPane = new JScrollPane();
        frmImageZoomIn.getContentPane().add(scrollPane, BorderLayout.CENTER);
        
        image = ImageIO.read(new File(inputImage));
        
        JPanel panel = new JPanel();
        panel.setLayout(new BorderLayout());
        
        // display image as icon 
        Icon imageIcon = new ImageIcon(inputImage);
        label = new JLabel( imageIcon );
        panel.add(label, BorderLayout.CENTER);
        
        panel.addMouseWheelListener(new MouseWheelListener() {
            public void mouseWheelMoved(MouseWheelEvent e) {
                int notches = e.getWheelRotation();
                double temp = zoom - (notches * 0.2);
                // minimum zoom factor is 1.0
                temp = Math.max(temp, 1.0);
                if (temp != zoom) {
                    zoom = temp;
                    resizeImage();
                }
            }
        });
        scrollPane.setViewportView(panel);
    }
    
    public void resizeImage() {
           System.out.println(zoom);
           ResampleOp  resampleOp = new ResampleOp((int)(image.getWidth()*zoom), (int)(image.getHeight()*zoom));
               BufferedImage resizedIcon = resampleOp.filter(image, null);
           Icon imageIcon = new ImageIcon(resizedIcon);
           label.setIcon(imageIcon);
        }


}
Read More
In previous article, I have written Angular JS directive for Mouse Wheel Scroll. In this article we will see how to implement Image Zoom In and Zoom Out using those Angular JS directives.

Program Flow

  1. Style of the element can be manipulated by ng-style pre-defined directive. Initialize style for the object imgStyle = {  width:"100px" } and zoomWidth = 100
  2.  On Mouse scroll up increment zoomWitdth by 20 and assign to imgStyle.width
  3.  On Mouse scroll down decrement zoomWitdth by 20 and assign to imgStyle.width 

Markup

<img src="/my-pic.jpg" ng-init="zoomWidth = 100;imgStyle = {width:'100px'}" ng-style="imgStyle" 
ng-mouse-wheel-up="zoomWidth = zoomWidth + 20; imgStyle.width = zoomWidth +'px'; "  
ng-mouse-wheel-down="zoomWidth = zoomWidth - 20;imgStyle.width = zoomWidth  +'px'; "/>

Script

var myApp = angular.module('myApp', []);


function MyCtrl($scope) {
  // controller code here
}

myApp.directive('ngMouseWheelUp', function() {
        return function(scope, element, attrs) {
            element.bind("DOMMouseScroll mousewheel onmousewheel", function(event) {
                   
                        // cross-browser wheel delta
                        var event = window.event || event; // old IE support
                        var delta = Math.max(-1, Math.min(1, (event.wheelDelta || -event.detail)));
                
                        if(delta > 0) {
                            scope.$apply(function(){
                                scope.$eval(attrs.ngMouseWheelUp);
                            });
                        
                          // for IE
                          event.returnValue = false;
                          // for Chrome and Firefox
                          if(event.preventDefault) event.preventDefault();                        
                       }
            });
        };
});


myApp.directive('ngMouseWheelDown', function() {
        return function(scope, element, attrs) {
            element.bind("DOMMouseScroll mousewheel onmousewheel", function(event) {
                   
                        // cross-browser wheel delta
                        var event = window.event || event; // old IE support
                        var delta = Math.max(-1, Math.min(1, (event.wheelDelta || -event.detail)));
                
                        if(delta < 0) {
                            scope.$apply(function(){
                                scope.$eval(attrs.ngMouseWheelDown);
                            });

                          // for IE
                          event.returnValue = false;
                          // for Chrome and Firefox
                          if(event.preventDefault) event.preventDefault();                        
                       }
            });
        };
});
Read More
I found a way to implement mouse wheel scroll event with hamster.js which is complicated and costly process. So I came up with simple solution with less code. Here I have created two directives, one is for mouse scroll up event and another is for mouse scroll down event.
You can use these directives for image zoom-in and zoom-out as like shown in this article. Element binds to event DOMMouseScroll ( for firefox ), mousewheel ( for chrome),  onmousewheel (for IE)

Directive for Mouse Wheel Scroll Up

HTML Usage

<div ng-mouse-wheel-up="..expression here..">........</div>

Script

myApp.directive('ngMouseWheelUp', function() {
        return function(scope, element, attrs) {
            element.bind("DOMMouseScroll mousewheel onmousewheel", function(event) {
                   
                        // cross-browser wheel delta
                        var event = window.event || event; // old IE support
                        var delta = Math.max(-1, Math.min(1, (event.wheelDelta || -event.detail)));
                
                        if(delta > 0) {
                            scope.$apply(function(){
                                scope.$eval(attrs.ngMouseWheelUp);
                            });
                        
                            // for IE
                            event.returnValue = false;
                            // for Chrome and Firefox
                            if(event.preventDefault) {
                                event.preventDefault();                        
                            }

                        }
            });
        };
});

Directive for Mouse Wheel Scroll Down

HTML Usage

<div ng-mouse-wheel-down="..expression here..">........</div>

Script

myApp.directive('ngMouseWheelDown', function() {
        return function(scope, element, attrs) {
            element.bind("DOMMouseScroll mousewheel onmousewheel", function(event) {
                   
                        // cross-browser wheel delta
                        var event = window.event || event; // old IE support
                        var delta = Math.max(-1, Math.min(1, (event.wheelDelta || -event.detail)));
                
                        if(delta < 0) {
                            scope.$apply(function(){
                                scope.$eval(attrs.ngMouseWheelDown);
                            });
                        
                            // for IE
                            event.returnValue = false;
                            // for Chrome and Firefox
                            if(event.preventDefault)  {
                                event.preventDefault();
                            }

                        }
            });
        };
});
Read More
We can select rectangular area of an image using  Image editing tools. Here in this article, I am going to implement this feature with Java.

Program Flow

  1. Create one panel to display only image using graphics
  2. Implement mousepressed, mousereleased and mousedrag events and create create rectangular shapes based on these mouse events
  3. Get sub image of main image with coordinates from above selection
  4. Update selected area panel with above sub image 

ImagePanel.java

This class extends JPanel. It implements mouse events and it is responsible for user selection of image. Whenever user select rectangular area, it will trigger main panel to update selected region.
import java.awt.AlphaComposite;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionAdapter;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;
import javax.swing.JPanel;

public class ImagePanel extends JPanel {
    private static final long serialVersionUID = 1L;
    private BufferedImage image;
    private Shape shape = null;
    Point startDrag, endDrag;

    public ImagePanel( String inputImage, MainFrame mf1) throws IOException {
        final MainFrame mf = mf1;
        image = ImageIO.read(new File(inputImage));
        this.addMouseListener(new MouseAdapter() {
            public void mousePressed(MouseEvent e) {
                startDrag = new Point(e.getX(), e.getY());
                endDrag = startDrag;
                repaint();
            }

            public void mouseReleased(MouseEvent e) {
                if(endDrag!=null && startDrag!=null) {
                    try {
                        shape = makeRectangle(startDrag.x, startDrag.y, e.getX(),
                                e.getY());
                        mf.updateSelectedRegion(image.getSubimage(startDrag.x, startDrag.y, e.getX()-startDrag.x, e.getY()-startDrag.y));   
                        startDrag = null;
                        endDrag = null;
                        repaint();
                    } catch (Exception e1) {
                        e1.printStackTrace();
                    }   
                }
            }
        });

        this.addMouseMotionListener(new MouseMotionAdapter() {
            public void mouseDragged(MouseEvent e) {
                endDrag = new Point(e.getX(), e.getY());
                repaint();
            }   
        });
    }

    
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;
        g2.drawImage(image, 0, 0, null);
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);
        
        g2.setStroke(new BasicStroke(2));
        g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER,
                0.50f));

        if (shape != null) {
            g2.setPaint(Color.BLACK);
            g2.draw(shape);
            g2.setPaint(Color.YELLOW);
            g2.fill(shape);
        }
        
        if (startDrag != null && endDrag != null) {
            g2.setPaint(Color.LIGHT_GRAY);
            Shape r = makeRectangle(startDrag.x, startDrag.y, endDrag.x,
                    endDrag.y);
            g2.draw(r);
        }
        
    }

    private Rectangle2D.Float makeRectangle(int x1, int y1, int x2, int y2) {
        return new Rectangle2D.Float(Math.min(x1, x2), Math.min(y1, y2),
                Math.abs(x1 - x2), Math.abs(y1 - y2));
    }
    
}

MainFrame.java

This is the main window which has Image Panel and Selected area panel. Here update imagePath variable with your image file path.
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.IOException;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JLabel;

public class MainFrame {

    private JFrame frmSelectAreaIn;
    private JPanel selectedAreaPanel;
    private String imagePath="C:\\inputImage.jpg";
    
    /**
     * Launch the application.
     */
    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                try {
                    MainFrame window = new MainFrame();
                    window.frmSelectAreaIn.setVisible(true);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the application.
     * @throws IOException 
     */
    public MainFrame() throws IOException {
        initialize();
    }

    /**
     * Initialize the contents of the frame.
     * @throws IOException 
     */
    private void initialize() throws IOException {
        frmSelectAreaIn = new JFrame();
        frmSelectAreaIn.setTitle("Select Area In Image");
        frmSelectAreaIn.setBounds(100, 100, 708, 370);
        frmSelectAreaIn.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frmSelectAreaIn.getContentPane().setLayout(null);
        
        // Image Panel display selected area of the image
        selectedAreaPanel = new JPanel();
        selectedAreaPanel.setBounds(469, 36, 221, 289);
        frmSelectAreaIn.getContentPane().add(selectedAreaPanel);
        
        // Image Panel display image with graphics
        JPanel mainPanel = new ImagePanel(imagePath, this);
        mainPanel.setBounds(10, 11, 449, 314);
        frmSelectAreaIn.getContentPane().add(mainPanel);
        
        JLabel lblSelectedArea = new JLabel("Selected Area");
        lblSelectedArea.setBounds(469, 11, 221, 14);
        frmSelectAreaIn.getContentPane().add(lblSelectedArea);
    }

    // function to update selected region of the image
    public void updateSelectedRegion(BufferedImage bufferedImage) {
        Graphics g = selectedAreaPanel.getGraphics();
        g.clearRect(0, 0, 221, 289);
        g.drawImage(bufferedImage, 0, 0, null);
    }
}
Read More

Blogroll


Follow this blog by Email

Popular Posts