Construct Tree from given Inorder and Preorder traversals

Problem:
Give two strings representing the inorder and preorder traversals of binary tree, construct the tree.

The key here is that preorder traversal, the first char is the tree root. And then based on that char, find the its position in inorder string, then its left portion of in order string is the left subtree, right portion is the right subtree.

And do it recursively, make it simpler.

public static Node constructTree(String pre, String in){

if(pre.isEmpty())

return null;

if(pre.length() == 1)

return new Node(pre.charAt(0));

Node root = new Node(pre.charAt(0));

String[] ins = splitStringBy(in, pre.charAt(0));

                root.left = constructTree(pre.substring(1, ins[0].length()+1), ins[0]);

root.right = constructTree(pre.substring(ins[0].length()+1), ins[1]);

return root;

}

public static String[] splitStringBy(String str, char root){

String[] re = new String[2];

re[0] = str.substring(0, str.indexOf(root));

re[1] = str.substring(str.indexOf(root)+1);

return re;

}

divide number and return result in a string

This is a google interview question: 

Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5.

Here is my attempt, the key is to doing module and division, also figure out how many 0s are there after decimal point. 

public static String divideToString(int num1, int num2){
    int d = num1/num2;
    int m = num1%num2;
    boolean flag = false;
    Set<Integer> seen = new HashSet<Integer>();
    StringBuilder sb = new StringBuilder();
    sb.append(d);
    while(m!=0){
    if(!flag){
        sb.append(".(");
        flag = true;
    } 

     

    num1 = m*10;
    d = num1/num2;
    m = num1%num2;

       

    if(seen.contains(num1)){
    sb.append(")");
    break;
    }else{
    sb.append(d);  
    seen.add(num1);
    }
    }

   

    return sb.toString();
}

Print all valid combinations of n-pairs of parentheses

For example, if n=1
{}
for n=2
{}{}
{{}}

Most of the solutions found online are using recursion. Here is the version which does iterative. 

The key is to keep track of the number of open parentheses, if there are open ones left, then add it to, also if number of open parentheses is bigger than close ones, then add close parentheses as well.

public static void allParenthesis(int k){

Map<String, Integer> list = new HashMap<String, Integer>();

list.put("(", 1);

for(int i = 1 ; i < k*2; i++){

Map<String, Integer> temp = new HashMap<String, Integer>();

for(String s : list.keySet()){

int left = list.get(s);

int right = s.length() - left;

if(left<k){

temp.put(s + "(", left+1); 

}

if(left>right){

temp.put(s + ")", left);

}

}

list = temp;

}

for(String s: list.keySet())

System.out.println(s);

}

Find the row with maximum number of 1s

This is from the geeksforGeeks site:

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

Example
Input matrix
0 1 1 1
0 0 1 1
1 1 1 1  // this row has maximum 1s
0 0 0 0

Output: 2

The solution is simple. for each row, we will start from the end and move backwards until 0 is found. and the starting position for each row is equal to the previous row's starting position of 1. 

 public static int findMaxOnes(int[][] nums){

  int max = nums[0].length-1;

  int index = 0;



  for(int i = 0; i<nums.length; i++){

   for(int j = max; j>=0; j--){

    if(nums[i][j]==0)

     break;

    max = j;

    index = i;

   }   

  }  

  return index;

 }

Find Longest Common Subsequence Length of two strings

Problem:
Given two strings: "AGGTAB", "GXTXAYB", find the length of the longest common subsequence.

The answer for the two strings is 4, "GTAB". Note subsequence is the substring of string with the characters appears in the order as they are in the string but not necessary contiguously.

Solution 1. 

Do it recursively

 /* do it recursively

* @param s1

* @param s2

* @return

*/

public static int findLongestCommonSubsequence(String s1, String s2){

if(s1.isEmpty() || s2.isEmpty())

return 0;

String substring1 = s1.substring(0, s1.length()-1);

String substring2 = s2.substring(0, s2.length()-1);

if(s1.charAt(s1.length()-1) == s2.charAt(s2.length()-1)) {

return 1+StringQ.findLongestCommonSubsequence(substring1, substring2);

} else{

return Math.max(StringQ.findLongestCommonSubsequence(s1, substring2), StringQ.findLongestCommonSubsequence(substring1, s2));

}

} 

Solution 2.

Do it iteratively:

       public static int findLongestCommonSubsequence2(String s1, String s2){

char[] cArray1 = s1.toCharArray();

char[] cArray2 = s2.toCharArray();

int[][] lcs = new int[s1.length()+1][s2.length()+1];

for(int i=0; i<cArray1.length; i++){

for(int j=0; j<cArray2.length; j++){

if(cArray1[i] == cArray2[j])

lcs[i+1][j+1] = lcs[i][j] + 1;

else

lcs[i+1][j+1] = Math.max(lcs[i+1][j], lcs[i][j+1]);

}

}

return lcs[s1.length()][s2.length()];

}

Longest Arithmetic Progression

Problem: 

 Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

The solution is to that using difference between two numbers in the list as key to store the maximum length for each difference. If the difference is already met before, then we can skip it.

Complexity: O(n^2) since there is n*(n-1) differences between the numbers in a list

public static List<Integer> findMaxArithmeticsSeq(int[] num){

int maxL = 0;

List<Integer> result = new ArrayList<Integer>();

//the difference between two numbers in the list defines the maxL of the sequence

//store the mapping will help to reduce the number of the iterations

Map<Integer, Integer> diff2Length = new HashMap<Integer, Integer>();

for(int i=0; i<num.length-1; i++){

for(int j=i+1; j<num.length; j++){

int diff = num[j]-num[i];

//we don't need to continue since max Length for this difference is already found

if(diff2Length.containsKey(diff))

continue;

List<Integer> found = new ArrayList<Integer>();

found.add(num[i]);

int pre = num[i];

for(int k=j; k<num.length; k++){

if(num[k] - pre == diff){

found.add(num[k]);

pre = num[k];

}

}

diff2Length.put(diff, found.size());

if(found.size() > maxL){

maxL = found.size();

result = found;

}

}

}

return result;

}

Permutations of list of numbers

Given a collection of numbers, return all possible permutations.

Problem description:

Input:
list of numbers: [8, 4, 13]

Output:
all permutations of the numbers in the list

[8, 4, 13]

[4, 8, 13]

[4, 13, 8]

[8, 13, 4]

[13, 8, 4]

[13, 4, 8]

Solution 1:

/**
* do it iteratively
*/

public static ArrayList<ArrayList<Integer>> getPermutations(int[] nums){
ArrayList<ArrayList<Integer>> result = new ArrayList<>();

  //start with an empty list
  result.add(new ArrayList<Integer>());
 
  for(int i=0; i<nums.length; i++){
ArrayList<ArrayList<Integer>> temp = new ArrayList<>();

//go through the list from previous round and add the number into the list
   for(ArrayList<Integer> each : result){
for(int index = 0; index<=each.size(); index++){
ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list
dest.add(index, nums[i]); //insert the number into all possible positions
temp.add(dest);
}
}
  
// switch over to prepare for the next round
 result = temp;
}
return result;
}

Solution 2:

/**

 *  do it recursively

**/

public static List<List<Integer>> getPermutations(List<Integer> nums){

List<List<Integer>> result = new ArrayList<>();

if(nums.size()==0){

result.add(new ArrayList<Integer>());

return result;

}

Integer n = nums.remove(0);

List<List<Integer>> subResult = getPermutations(nums); //get the permutation for sub list

for(List<Integer> each : subResult){

for(int index = 0; index<=each.size(); index++){

ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list

dest.add(index, n); //insert the number into all possible positions

result.add(dest);

}

}

return result;

}