3Sum Closest -- Leetcode

Question:

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).

Answer:

public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int res = 0, min = Integer.MAX_VALUE;

        

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

            int j = i+1;

            int k = nums.length - 1;

            while(j < k){

                int sum = nums[i] + nums[j] + nums[k];

                int diff = Math.abs(sum - target);

                if( diff < min){

                    min = diff;

                    res = sum;

                }

                if(sum < target){

                    j++;

                }else{

                    k--;

                }

            }

        }

        return res;

}

3Sum Smaller -- Leetcode

Question:

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Answer:
Time: O(n^2), sort method.
public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
     
        for(int i=0; i < nums.length; ++i){
            int j = i+1;
            int k = nums.length - 1;

            while(j < k){
                if(nums[i] + nums[j] + nums[k] < target){
                    count += (k-j);
                    j++;
                }else if(nums[i] + nums[j] + nums[k] >= target){
                    k--;
                }
            }
        }
        return count;
}

Android Timer example

package com.example.androidtimer;

import android.app.Activity;
import android.os.Bundle;
import android.view.Menu;
import android.view.MenuItem;
import android.os.Handler;
import android.os.SystemClock;
import android.view.View;
import android.widget.Button;
import android.widget.TextView;

public class MainActivity extends Activity {

private Button startButton;
private Button pauseButton;

private TextView timerValue;

private long startTime = 0L;

private Handler customHandler = new Handler();

long timeInMilliseconds = 0L;
long timeSwapBuff = 0L;
long updatedTime = 0L;

@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

timerValue = (TextView) findViewById(R.id.timerValue);

startButton = (Button) findViewById(R.id.startButton);

startButton.setOnClickListener(new View.OnClickListener() {

                        public void onClick(View view) {

startTime = SystemClock.uptimeMillis();
customHandler.postDelayed(updateTimerThread, 0);
}
});

pauseButton = (Button) findViewById(R.id.pauseButton);

pauseButton.setOnClickListener(new View.OnClickListener() {

public void onClick(View view) {

timeSwapBuff += timeInMilliseconds;
customHandler.removeCallbacks(updateTimerThread);
}
});
}

private Runnable updateTimerThread = new Runnable() {

public void run() {

timeInMilliseconds = SystemClock.uptimeMillis() - startTime;

updatedTime = timeSwapBuff + timeInMilliseconds;

int secs = (int) (updatedTime / 1000);
int mins = secs / 60;
secs = secs % 60;
int milliseconds = (int) (updatedTime % 1000);
timerValue.setText("" + mins + ":"
+ String.format("%02d", secs) + ":"
+ String.format("%03d", milliseconds));
customHandler.postDelayed(this, 0);
}
};
}

Android -- Eventbus

/*

public class EventBus {

HashMap<String, List<Event>>

public void register(String eventName, Event event) {};

public void unregister(String eventName, Event event){};

public void postEvent(String eventName, Object Data){};

public interface Event {

  void onEvent(Object data);

}

}

*/

class EventBus {

  private Map<String, List<Event>> map;

  

  public EventListener() {

    map = new HashMap<String, List<Event>>();

  }

  

  public void register(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).add(event);

    } else {

      List<Event> events = new ArrayList<Event>();

      events.add(event);

      map.put(eventName, events);

    }

  };

  

  public void unregister(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).remove(event);

    }

  };

  public void postEvent(String eventName, Object data) {

if(map.containsKey(eventName)){

List<Event> events = map.get(eventName);

for(Event event : events){

event.doEvent(data);

}

}

 

/*

    Event event = new Event();

    event.doEvent(data);

    this.register(eventName, event);

    */

  };

} 

class Event {

  private Object data;

  

  public void doEvent(Object data) {

    this.data = data;

  };

}

Valid Palindrome -- Leetcode

Question:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Answer:
public boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            char a = s.charAt(i);
            char b = s.charAt(j);

            while (i < j && !Character.isLetter(a) && !Character.isDigit(a)) {
                a = s.charAt(++i);
            }

            while (j > i && !Character.isLetter(b) && !Character.isDigit(b)) {
                b = s.charAt(--j);
            }

            if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
                return false;
            }
        }
        return true;
    }

Answer 2:

/*

public class EventBus {

HashMap<String, List<Event>>

public void register(String eventName, Event event) {};

public void unregister(String eventName, Event event){};

public void postEvent(String eventName, Object Data){};

public interface Event {

  void onEvent(Object data);

 }

}

*/

class EventBus {

  private Map<String, List<Event>> map;

  

  public EventListener() {

    map = new HashMap<String, List<Event>>();

  }

  

  public void register(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).add(event);

    } else {

      List<Event> events = new ArrayList<Event>();

      events.add(event);

      map.put(eventName, events);

    }

  };

  

  public void unregister(String eventName, Event event) {

    if (map.containsKey(eventName)) {

      map.get(eventName).remove(event);

    }

  };

  public void postEvent(String eventName, Object data) {

if(map.containsKey(eventName)){

List<Event> events = map.get(eventName);

for(Event event : events){

event.doEvent(data);

}

}

 

/*Event event = new Event();

    event.doEvent(data);

    this.register(eventName, event);

    */

  };

} 

class Event {

  private Object data;

  public void doEvent(Object data) {

    this.data = data;

  };

}

Inorder Successor in BST -- Leetcode

Question:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Answer:
1. Iterative: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //case 1 : if p has right subtree
        if(p.right != null){
            return minNode(p.right);
        }
       
        //case 2 : p has no right child, succ is the parent of p
        TreeNode succ = null;
        // Start from root and search for successor down the tree
        while(root != null & root != p){
            if(p.val < root.val){
                succ = root;
                root = root.left;
            }
            else if(p.val > root.val){
                root = root.right;
            }
        }
        return succ;
    }
   
    public TreeNode minNode(TreeNode root){
        if(root==null)return null;
        while(root.left != null){
            root = root.left;
        }
        return root;
    }

2. Recursive: O(h) + O(1)
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return Util(root, p, null, null);
    }

    public TreeNode Util(TreeNode root, TreeNode p, TreeNode min, TreeNode max){
        if(p.val >= root.val){
            if(root.right != null){
                return Util(root.right, p, root, max);
            }else{
                return max;
            }
        }
        //if p.val < root.val
        else{
            if(root.left != null){
                return Util(root.left, p, min, root);
            }else{
                return root;
            }
        }
    }

Find smallest larger element than target in BST

Question:

Given a BST:

                 10

        7                    14

    4      8      12              19

                         13     16    20

   

[4,7,8,10,12,13,14,16,19,20]

Q1.  Find smallest larger element than target,  

     Example: input: target = 13,  output: 14

Q2.  Find largest smaller element than target,  

     Example: input: target = 13,  output: 12

Answer:

public class Solution {

//Q1.  Find smallest larger element than target:           Time:O(logn), Space:O(1)

public static int findNLR(TreeNode root, int target, int min, int max) throws Exception{

              //if root.val > target, return the smallest element in the subtree

        if(root.val > target){

               if(root.left != null){

                            //go left branch

                      return findNLR(root.left, target, min, root.val);

               }else{

                      return root.val;

                }

         }          

        else{

              if(root.right != null){

                          //go right branch

                     return findNLR(root.right, target, root.val, max);

              }else{

                      if(max != Integer.MAX_VALUE){

                             return max;

                     }

                     else{

                            throw new Exception();

                      }

              }

        }           

}

public static int findNL(TreeNode root, int target) throws Exception{

         return findNLR(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

//Q2.  Find largest smaller element than target:               Time:O(logn), Space:O(1)

public static int findPSL(TreeNode root, int target, int min, int max) throws Exception{

                  //if root.val < target, return the largest element in the subtree

        if(root.val < target){

             if(root.right!=null){

                            //go right branch

                    return findPSL(root.right, target, root.val, max);

             }else{

                    return root.val;

             }

        }

        else{

               if(root.left!=null){

                            //go left branch

                      return findPSL(root.left, target, min, root.val);

               }else{

                      if(min != Integer.MIN_VALUE){

                            return min;

                      }

                      else{

                             throw new Exception();

                      }

               }

         }

}

public static int findPS(TreeNode root, int target) throws Exception{

         return findPSL(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

   

  public static void main(String[] args) throws Exception {

        TreeNode root = new TreeNode(10);

        root.left = new TreeNode(7);

        root.right = new TreeNode(14);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(8);

        root.right.left = new TreeNode(12);

        root.right.left.right = new TreeNode(13);

        root.right.right = new TreeNode(19);

        root.right.right.left = new TreeNode(16);

        root.right.right.right = new TreeNode(20);

        int res = findNL(root, 13);

        System.out.println(res);   

   }

}

Binary Tree Path -- Leetcode

Question:

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Answer:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if(root==null){
            return res;
        }
       
        List<List<Integer>> tmp = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Util(root, path, tmp);
       
        for(int i=0;i<tmp.size();++i){
            List<Integer> path_int = tmp.get(i);
            String path_str = convertStr(path_int);
            res.add(path_str);
        }
        return res;
    }
   
    public void Util(TreeNode root, List<Integer> path, List<List<Integer>> res){
        if(root==null){
            return;
        }
        //edge case
        path.add(root.val);
        if(root.left==null && root.right==null){
            //clone a new path array
            ArrayList<Integer> path_new = new ArrayList<Integer>(path);
            res.add(path_new);
            //backtrack!
            path.remove(path.size()-1);
            return;
        }
        //Recursive case
        Util(root.left, path, res);
        Util(root.right, path, res);
        //backtrack!
        path.remove(path.size()-1);
        return;
    }
   
    public String convertStr(List<Integer> path){
        if(path == null || path.size()==0) return null;
       
        StringBuilder sb = new StringBuilder();
        int len = path.size();
        for(int i=0; i<len-1; ++i){
            sb.append(path.get(i));
            sb.append("->");
        }
        sb.append(path.get(len-1));
        return sb.toString();
    }
}

Number of Island -- Leetcode

Question:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Answer:
1. Inplace, Time: O(m*n), Space:O(1)

public class Solution {

    public int numIslands(char[][] grid) {

        if(grid==null)return 0;

        int m = grid.length;

        if(m==0)return 0;

        int n = grid[0].length;

        int count=0;

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

            for(int j=0;j<n;++j){

                if(grid[i][j]=='1'){

                    count++;

                    DFS(grid, i,j);

                }

            }

        }

        return count;

    }

    public void DFS(char[][] grid, int i, int j){

        int m=grid.length, n=grid[0].length;

        if(i<0||i>=m||j<0||j>=n)return;

        if(grid[i][j]!='1'){

            return;

        }

        grid[i][j]='2';

        DFS(grid,i-1,j);

        DFS(grid,i,j-1);

        DFS(grid,i+1,j);

        DFS(grid,i,j+1);

        return;

    }

}


2.  Time: O(m*n), Space:O(m*n), using additional boolean[m][n] flag.
public class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null)return 0;
        int m = grid.length;
        if(m==0)return 0;
        int n = grid[0].length;
        int count=0;
        boolean[][] flag;
       
        flag = new boolean[m][];
        for(int i=0;i<m;++i){
            flag[i] = new boolean[n];
            for(int j=0;j<n;++j){
                flag[i][j]=false;
            }
        }
               
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(grid[i][j]=='1' && flag[i][j]==false){
                    count++;
                    DFS(grid,i,j,flag);
                }
            }
        }
        return count;
    }

    public void DFS(char[][] grid, int i, int j, boolean[][] flag){
        //check valid boundary
        int m=grid.length, n=grid[0].length;
        if(i<0||i>=m||j<0||j>=n)return;
       
        if(grid[i][j]=='1' && flag[i][j]==false){
            flag[i][j]=true;
            DFS(grid,i-1,j,flag);
            DFS(grid,i,j-1,flag);
            DFS(grid,i+1,j,flag);
            DFS(grid,i,j+1,flag);
        }
        return;
    }
}

Inorder Successor in BST -- Leetcode

Question:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Answer:

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(p.right != null){
            return minNode(p.right);
        }
        TreeNode succ = null;
       
        // Start from root and search for successor down the tree
        while(root!= null){
            if(p.val < root.val){
                succ = root;
                root = root.left;
            }
            else if(p.val > root.val){
                root = root.right;
            }
            else{
                break;
            }
        }
        return succ;
    }
   
    public TreeNode minNode(TreeNode root){
        if(root==null)return null;
        TreeNode q = root;
        TreeNode p = root.left;
        while(p!=null){
            q=p;
            p=p.left;
        }
        return q;
    }
}

Serialize and Deserialize Binary Tree -- Leetcode

Question:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.


Answer:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private StringBuilder str = new StringBuilder();
   
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuilder sb){
        if(root==null){
            str.append("# ");
        }
        str.append(root.val + " ");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
   
   
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null || data.length()==0){
            return null;
        }
        StringTokenizer st = new StringTokenizer(data, " ");
        return deserialize(st);
    }
   
    public TreeNode deserialize(StringTokenizer st){
        if(!st.hasMoreTokens()){
            return null;
        }

        String str_val = st.nextToken();
       
        if(str_val.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(str_val));
        root.left = deserialize(st);
        root.right = deserialize(st);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Divide two integers -- LIKI

class Solution {
public:
    int divide(int dividend, int divisor){      
       unsigned long dvd = dividend < 0 ? -dividend : dividend;
       unsigned long dvs = divisor < 0 ? -divisor : divisor;
       if (dvd < dvs) return 0;
     
       bool nega = (dividend > 0) ^ (divisor > 0);          //nega = true: -xxx; =false: +xxx.
     
       unsigned long originDvs = dvs;
       int power = 0;
       unsigned long result = 0;
     
       while (dvs < dvd){
            dvs = dvs << 1;
            power++;
       }                                    //dvd < dvs now
       while (dvd >= originDvs){
            if (dvd >= dvs){
                 dvd -= dvs;
                 result += (unsigned long) 1 << power;
            }
            while(dvd < dvs){                    //to get biggest dvs < dev everytime
                dvs = dvs >> 1;
                power--;
            }
       }
     
       return nega? -result : result;
   }
};

Thread-safe blocking queue -- LIKI

import java.util.LinkedList;

import java.util.List;

public class BlockingQueue {

 private List queue = new LinkedList();

 private int  limit = 10;

 public BlockingQueue(int limit){

   this.limit = limit;

 }

 public synchronized void enqueue(Object item)

 throws InterruptedException  {

   while(this.queue.size() == this.limit) {

     wait();

   }

   if(this.queue.size() == 0) {

     notifyAll();

   }

   this.queue.add(item);

 }

 public synchronized Object dequeue()

 throws InterruptedException{

   while(this.queue.size() == 0){

     wait();

   }

   if(this.queue.size() == this.limit){

     notifyAll();

   }

   return this.queue.remove(0);

 }

}

HashMap Implementation -- LIKI

import java.lang.Object;

public class HashMap {

    int SIZE_OF_TABLE = 128;

    HashEntry[] table;

HashMap() {

    table = new HashEntry[SIZE_OF_TABLE];

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

          table[i] = null;

    }

}

public void put(int key, int value) {

    int index = hashCodeNew(key);

   

    HashEntry hashEntry = new HashEntry(key, value);

    if (table[index] == null) {

        table[index] = hashEntry;

    } else {

        HashEntry runner = table[index];

        while (runner.next != null) {

               if (runner.key == hashEntry.key) {

                     runner.value = hashEntry.value;

                     break;

    } else {

         runner = runner.next;

    }

}

if (runner.next == null) {

       if (runner.key == hashEntry.key) {

       runner.value = hashEntry.value;

} else {

       runner.next = hashEntry;

}

}

}

}

public int get(int key) {

      int index = hashCodeNew(key);

      if (table[index] == null) {

      return -1;

} else {

     HashEntry runner = table[index];

     if (runner.key == key) {

           return runner.value;

}

while (runner.next != null) {

     if (runner.key == key) {

     return runner.value;

}

}

     return -1;

}

}

public int hashCodeNew(int h) {

      h ^= (h >>> 20) ^ (h >>> 12);

      int hashCode = h ^ (h >>> 7) ^ (h >>> 4);

      return hashCode % SIZE_OF_TABLE;

}

}

class HashEntry {

      int key;

      int value;

      HashEntry next = null;

       HashEntry() {

       }

public HashEntry(int key, int value) {

      this.key = key;

      this.value = value;

}

public int getKey() {

      return this.key;

}

public int getValue() {

      return this.value;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

HashMap hashMap = new HashMap();

hashMap.put(10, 20);

hashMap.put(20, 11);

hashMap.put(21, 1);

hashMap.put(20, 10);

int value = hashMap.get(20);

assert value != 10;

}

}

Infix To postfix -- LIKI

 public String InToPost(String infixString) {
        String postfixString = " ";

        for (int index = 0; index < infixString.length(); ++index) {
            char chValue = infixString.charAt(index);
            if (chValue == '(') {
                push('(');
            } else if (chValue == ')') {
                Character oper = peek();
                while (!(oper.equals('(')) && !(isEmpty())) {
                    postfixString += oper.charValue();
                    pop();
                    oper = peek();
                }
                pop();
            } else if (chValue == '+' || chValue == '-') {
                //Stack is empty
                if (isEmpty()) {
                    push(chValue);
                    //current Stack is not empty
                } else {
                    Character oper = peek();
                    while (!(isEmpty() || oper.equals(new Character('(')) || oper.equals(new Character(')')))) {
                        pop();
                        postfixString += oper.charValue();
                    }
                    push(chValue);
                }
            } else if (chValue == '*' || chValue == '/') {
                if (isEmpty()) {
                    push(chValue);
                } else {
                    Character oper = peek();
                    while (!oper.equals(new Character('+')) && !oper.equals(new Character('-')) && !isEmpty()) {
                        pop();
                        postfixString += oper.charValue();
                    }
                    push(chValue);
                }
            } else {
                postfixString += chValue;
            }
        }
        while (!isEmpty()) {
            Character oper = peek();
            if (!oper.equals(new Character('('))) {
                pop();
                postfixString += oper.charValue();
            }
        }
        return postfixString;
    }

Different Ways to Add Parentheses -- Leetcode

Question:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

https://leetcode.com/problems/different-ways-to-add-parentheses/

Answer:

public class Solution {
    public Integer compute(Integer a, Integer b, char op){
        if(op=='+') return a+b;
        else if(op=='-')return a-b;
        else if(op=='*')return a*b;
        return 0;
    }
   
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
        int len = input.length();
       
        if(Character.isDigit(input.charAt(0))){
                int i=0;
                int number = input.charAt(i) - '0';
                while(i+1<len && Character.isDigit(input.charAt(++i))){
                    number = number*10 + input.charAt(i)-'0';
                }
                      //edge case for recusrion, input is just a number, no operator.
                if(i==len-1){
                    res.add(number);
                    return res;
                }
        }
   
           //recursion dp, res(i,j) = res(i,k) op res(k+2,j), op = input[k+1].
        for(int k=0;k<len;++k){
             if(Character.isDigit(input.charAt(k)) == false){
                 List<Integer> left = new ArrayList<Integer>();
                 List<Integer> right = new ArrayList<Integer>();
               
                 left = diffWaysToCompute(input.substring(0,k));
                 right = diffWaysToCompute(input.substring(k+1));
               
                 for(int i=0;i<left.size();++i){
                     for(int j=0;j<right.size();++j){
                         char op = input.charAt(k);
                         Integer subres = compute(left.get(i), right.get(j), op);
                         res.add(subres);
                     }
                 }
             }
        }
        return res;
    }
}