manishsat

/*
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
    
Time Complexity : O(N^2)
*/

manishsat

/*
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character
*/
public int editDistance(String w1, String w2){

manishsat

/*
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

manishsat

/*
Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \

manishsat

public static void morrisInOrderTraverse(TreeNode root){
    	TreeNode ptr = root;
	while (ptr != null){
		if (ptr.left == null){
			visit(ptr);
			ptr = ptr.right;
		}else{
			TreeNode node = ptr.left;
			while (node.right != null && node.right != ptr)
				node = node.right;

manishsat

/*
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
•Only one letter can be changed at a time
•Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"

manishsat

/*
Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

manishsat

public static int solve(int N){
    int[] primes = new int[N];
    int cnt = 0;
    boolean[] isp = new boolean[N+1];
    Arrays.fill(isp, true);
    isp[0] = false;
    isp[1] = false;

    for (int i=2; i<=N; i++){
        if (isp[i]){

manishsat

/*
 * Time complexity : O(n), Space Complexity : O(n), 
 * We could just use a n size char array instead of using nRows' StringBuilder array. See the convert0 for the detail
 */
public static String convert(String s, int nRows){
    if (s == null || s.length() <= 1 || nRows <= 1)
        return s;
    StringBuilder[] sbs = new StringBuilder[nRows];

    for (int i=0; i<nRows; i++){

manishsat

/**
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"