Scott
BAN USERI was a SDET of Oracle OBIEE Team and I am looking for a new SDET/STE opportunity .
public String find (int sum){
int n = sum/2 ;
int tail = 1 ;
int min = Integer.MAX_VALUE ;
int preSum = 0 ;
String s = "" ;
for (int i = 1 ; i <= n ; ++i) {
preSum += i;
while (preSum > sum) {
preSum -= tail ;
tail++;
}
if (preSum == sum) {
if (i - tail + 1 < min) {
min = i - tail + 1 ;
s = getResult (tail, i, sum);
}
}
}
return min == Integer.MAX_VALUE ? "IMPOSSIBLE" : s;
}
private String getResult(int s, int e, int sum){
StringBuilder sb = new StringBuilder();
for (int i = s ; i <= e ; ++i) {
sb.append(i) ;
sb.append("+") ;
}
sb.setLength(sb.length() - 1) ;
sb.insert(0, sum + " = ") ;
return sb.toString() ;
}
- Scott November 15, 2015I think the problem is a NP-hard problem
First , we need to make sure the pattern and string is only one to one map
one to one map like a -- fish and fish -- a
(a -- fish b -- fish ) is not a valid one to one map
To valid a one to one , we need to maps , this is why in the code , I wrote like this
a.put(key, val) ;
b.put(val, key) ;
if it is one to one map , then we continue to do a recursive call until we exceeds the length of Both Pattern and String
if not , we remove from the maps . then try next combination .
hope, this is helpful
Backtrack solution
public boolean isMatch (String c, String d) {
HashMap<Character,String> a = new HashMap<> ();
HashMap<String, Character> b = new HashMap<> ();
return helper (0, 0, c, d, a, b);
}
private boolean helper (int m , int n , String c, String d, HashMap<Character,String> a, HashMap<String,Character> b){
if (m >= c.length() && n >= d.length()) {
return true ;
}
if (m >= c.length() || n >= d.length()) {
return false ;
}
for (int i = n ; i < d.length() ;++i) {
char key = c.charAt(m) ;
String val = d.substring(n, i + 1) ;
if (!a.containsKey(key)) {
a.put(key, val) ;
b.put(val, key) ;
if (helper ( m + 1, i + 1, c, d ,a ,b)) {
return true ;
}
a.remove(key) ;
b.remove(val) ;
} else {
if (a.get(key).equals(val) && (b.containsKey(val) && b.get(val) == key)) {
return helper ( m + 1, i + 1, c, d ,a ,b) ;
}
}
}
return false ;
}
- Scott October 26, 2015O(n) solution
public void reorder(char [] A, int [] B){
for (int i = 0 ; i < B.length ; ++i) {
int tmp = i ;
while (B[tmp] != tmp) {
swap(A, B[tmp], tmp);
swapIndex (B, B[tmp], tmp) ;
tmp = B[tmp] ;
}
}
}
private void swap (char [] A, int i , int j){
char tmp = A[i] ;
A[i] = A[j] ;
A[j] = tmp ;
}
private void swapIndex (int [] A, int i , int j){
int tmp = A[i] ;
A[i] = A[j] ;
A[j] = tmp ;
}
- Scott October 26, 2015public List<Integer> add (int [] ar, int n){
List<Integer> rst = new ArrayList<> ();
if (ar == null || ar.length == 0) {
return rst ;
}
int [] sum = new int [ar.length] ;
sum[0] = ar[0] ;
for (int i = 1; i < ar.length ;++i) {
sum[i] = sum[i - 1] + ar[i] ;
}
int i = 0 ;
int preSum = 0 ;
while (sum.length - i >= n) {
int cur = sum[i + n - 1] - preSum ;
preSum += cur ;
i += n;
rst.add(cur) ;
}
if (i < sum.length) {
int a = sum[sum.length - 1] - preSum;
rst.add(a) ;
}
return rst ;
}
- Scott October 08, 2015bfs find shortest path between two nodes
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner (System.in);
int n = sc.nextInt() ;
int m = sc.nextInt() ;
int i = 0 ;
int [][] data = new int [n - 1][2] ;
while (i < n - 1) {
data[i][0] = sc.nextInt() ;
data[i][1] = sc.nextInt() ;
i++;
}
i = 0 ;
int [][] query = new int [m][2] ;
while (i < m) {
query[i][0] = sc.nextInt() ;
query[i][1] = sc.nextInt() ;
i++;
}
getPath(data, query, n);
}
public static HashMap<Integer,List<Integer>> createGraph (int n, int [][] ar){
HashMap<Integer,List<Integer>> graph = new HashMap<> ();
for (int i = 1 ; i <= n ; ++i) {
graph.put(i, new ArrayList<Integer>());
}
for (int [] a : ar) {
graph.get(a[0]).add(a[1]) ;
graph.get(a[1]).add(a[0]) ;
}
return graph ;
}
public static void getPath (int [][] ar, int [][] query,int n){
HashMap<Integer,List<Integer>> graph = createGraph (n ,ar);
HashMap<Integer,Boolean> city = new HashMap<> ();
city.put(1, true) ;
for (int [] a : query) {
if (a[0] == 1) {
city.put(a[1], true) ;
} else {
bfs (graph,city, a[1]);
}
}
}
public static void bfs (HashMap<Integer,List<Integer>> graph, HashMap<Integer,Boolean> city , int start){
HashMap<Integer,Integer> visited = new HashMap<> ();
Queue<Integer> q = new LinkedList<> () ;
visited.put(start, 0) ;
q.offer(start) ;
while (!q.isEmpty()) {
int cur = q.poll() ;
if (city.containsKey(cur)) {
System.out.println(visited.get(cur));
break;
}
for (int n : graph.get(cur)) {
if (!visited.containsKey(n)) {
visited.put(n, visited.get(cur) + 1) ;
q.add(n) ;
}
}
}
}
public int getTotalWaitTime (String s, int k){
int total = 0 ;
HashMap<Character,Integer> map = new HashMap<> ();
for (int i = 0 ; i < s.length() ; ++i) {
if (!map.containsKey(s.charAt(i))) {
map.put(s.charAt(i), i);
total++;
} else {
total += k - (i - map.get(s.charAt(i)) - 1) + 1 ;
map.put(s.charAt(i), i);
}
}
return total ;
}
- Scott September 14, 2015public int numOfWay (char [][] ch){
return solve(ch, 0);
}
private int solve (char [][] ch , int x){
if (x >= ch.length) {
return 1 ;
}
int total = 0;
for (int i = 0 ; i < ch[0].length ;++i) {
if(ch[x][i] == '*') {
continue ;
}
if (isValid(ch, x, i)) {
ch[x][i] = 'b' ;
total += solve(ch, x + 1);
ch[x][i] = '.' ;
}
}
return total ;
}
private boolean isValid (char [][] ch, int i , int j) {
int x = i - 1 ;
int y = j - 1 ;
//left corner ;
while (x >= 0 && y >= 0 && ch[x][y] != '*') {
if (ch[x][y] == 'b') {
return false ;
}
x--;
y--;
}
//right corner;
x = i - 1 ;
y = j + 1 ;
while (x >=0 && y < ch[0].length && ch[x][y] != '*') {
if (ch[x][y] == 'b') {
return false ;
}
x--;
y++;
}
return true ;
}
- Scott September 14, 2015public int [] add (int [] num){
if (num == null || num.length == 0) {
return num ;
}
int carrier = 1 ;
for (int i = num.length - 1 ; i >= 0 ; --i) {
int sum = num[i] + carrier ;
num[i] = sum % 10 ;
carrier = sum / 10 ;
}
if (carrier > 0) {
int [] rst = new int [num.length + 1] ;
rst[0] = carrier ;
System.arraycopy(num, 0, rst, 1, num.length);
return rst ;
}
return num ;
}
- Scott September 01, 2015two pass solution
first from left to right , then right to left
public int findMaxPositiveFrequency (int [] frequency){
int [] left = new int [frequency.length] ;
int max = 0 , min_so_far = frequency[0] ;
for (int i = 1 ; i < frequency.length ; ++i) {
if (frequency[i] < min_so_far) {
left[i] = max ;
min_so_far = frequency[i] ;
} else {
max = Math.max(max, frequency[i] - min_so_far) ;
left[i] = max ;
}
}
int [] right = new int [frequency.length] ;
max = 0 ;
int max_so_far = frequency[frequency.length - 1] ;
for (int i = frequency.length -2 ; i >= 0 ; --i) {
if (frequency[i] > max_so_far) {
right[i] = max ;
max_so_far = frequency[i] ;
} else {
max = Math.max(max, max_so_far - frequency[i]) ;
right[i] = max ;
}
}
max = 0 ;
for (int i = 0 ; i < frequency.length ; ++i) {
max = Math.max(max, left[i] + right[i]) ;
}
return max ;
}
public void mostBeautifuPath (int [][] matrix){
int r = matrix.length ;
int c = matrix[0].length ;
int [] dp = new int [r * c] ;
for (int i = 1 ; i < c ;++i ) {
dp[id (0 , i, c)] = id (0 , i - 1, c) ;
}
for (int i = 1 ; i < r ; ++i) {
dp[id (i , 0, c)] = id (i - 1 , 0, c) ;
}
for (int i = 1 ; i < r ; ++i) {
for (int j = 1 ; j < c ; ++j ) {
if (matrix[i - 1][j] <= matrix[i][j - 1]) {
dp[id(i , j , c)] = id (i - 1, j, c);
} else {
dp[id(i , j , c)] = id (i, j - 1, c);
}
}
}
int i = dp.length - 1 ;
List<Integer> rst = new ArrayList<> ();
int [] start = coordinator (dp.length - 1, c) ;
rst.add(matrix[start[0]][start[1]]) ;
while (i > 0 ) {
i = dp[i] ;
int [] pre = coordinator (i, c) ;
rst.add(matrix[pre[0]][pre[1]]) ;
}
Collections.sort(rst);
for (int v : rst) {
System.out.print(v + " ");
}
System.out.println();
}
public int id (int x, int y, int c){
return x * c + y ;
}
public int [] coordinator (int id, int c){
return new int [] {id / c , id % c } ;
}
my iterate way
public TreeNode findSuccessor(TreeNode root, TreeNode target) {
Stack<TreeNode> stack = new Stack<> ();
TreeNode cur = root ;
TreeNode pre = null ;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur) ;
cur = cur.left ;
} else {
TreeNode mid = stack.pop() ;
if (pre == target) {
return mid ;
}
pre = mid ;
cur = pre.right ;
}
}
return null;
}
public boolean isValid(List<TreeNode> nodes){
HashSet<TreeNode> children = new HashSet<> ();
// child node only has one parent node
for (TreeNode node : nodes) {
if (node.left != null) {
if (!children.add(node.left)) return false ;
}
if (node.right != null) {
if (!children.add(node.right)) return false ;
}
}
TreeNode start = null ;
int count = 0 ;
for (TreeNode node : nodes) {
if (!children.contains(node)) {
start = node ;
count ++ ;
}
}
// only has one root node
if (count > 1) return false ;
// running bfs to make sure all nodes can be constructed as a binary tree
Queue<TreeNode> q = new LinkedList<> ();
q.add(start) ;
while (!q.isEmpty()) {
int size = q.size() ;
for (int i = 0 ; i < size ; ++i) {
TreeNode cur = q.poll() ;
if (cur.left != null) {
q.add(cur.left) ;
children.remove(cur.left) ;
}
if (cur.right != null) {
q.add(cur.right) ;
children.remove(cur.right) ;
}
}
}
return children.size() == 0 ;
}
public void flatten(TreeNode root) {
helper (root);
}
private TreeNode helper (TreeNode root){
if (root == null) {
return null ;
}
if (root.left == null && root.right == null) {
return root ;
}
TreeNode left = helper (root.left);
TreeNode right = helper (root.right);
root.right = left ;
TreeNode p = root ;
while (p != null && p.right != null) {
p = p.right ;
}
if (p != null) {
p.right = right ;
}
root.left = null ;
return root ;
}
- Scott July 17, 2015this could be achieved by O(n) using index sort
public int findDUP (int [] array){
for (int i = 0 ; i < array.length ;++i) {
int m = array[i];
while (m != array[m - 1]) {
swap (array, i , m - 1);
m = array[i] ;
}
}
for (int i = 0 ; i < array.length ;++i) {
if (array[i] - 1 != i) {
return array[i] ;
}
}
return 0 ;
}
- Scott July 14, 2015my brutal force solution the time complexity is O(n!)
int min = Integer.MAX_VALUE ;
public int findMin (String [] a){
if (a == null || a.length == 0 || a.length == 1) {
return 0 ;
}
if (a.length == 2) {
return a[0].length() + a[1].length() ;
}
Arrays.sort(a);
boolean [] used = new boolean [a.length] ;
permutate (a, 0 , "", 0, used);
return min ;
}
public void permutate (String [] a , int pre ,String preWord , int index, boolean [] used){
if (index >= a.length) {
min = Math.min(2 * pre - preWord.length(), min) ;
return ;
}
for (int i = 0 ; i < a.length ;++i) {
if (i != 0 && a[i].length() == a[i - 1].length() && !used[i -1]) {
continue ;
}
if (used[i]) {
continue ;
}
used[i] = true ;
permutate (a, pre + a[i].length() , a[i] , index + 1 , used) ;
used[i] = false ;
}
}
public List<List<Integer>> findPath (TreeNode root, int target){
List<List<Integer>> rst = new ArrayList<List<Integer>> ();
if (root == null) {
return rst ;
}
List<Integer> cur = new ArrayList<> ();
helper (root, target, cur, rst);
return rst ;
}
private void helper (TreeNode root, int target, List<Integer> cur , List<List<Integer>> rst) {
if (root == null) {
return ;
}
if (root.left != null && root.right != null && target - root.val == 0) {
cur.add(root.val) ;
rst.add(new ArrayList<Integer> (cur));
cur.remove(cur.size() - 1) ;
return ;
}
cur.add(root.val) ;
helper (root.left, target - root.val, cur, rst);
helper (root.right, target - root.val, cur, rst);
cur.remove(cur.size() - 1) ;
}
- Scott July 06, 2015this can be done by dequeue with time complexity O(n)
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
// write your code here
ArrayList<Integer> rst = new ArrayList<> ();
if (nums == null || nums.length == 0) {
return rst ;
}
LinkedList<Integer> q = new LinkedList<> ();
for (int i = 0 ; i < k ;++i) {
while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
q.pollLast() ;
}
q.offer(i) ;
}
int tail = 0 ;
for (int i = k ; i < nums.length ;++i) {
rst.add(nums[q.peek()]) ;
while (!q.isEmpty() && q.peek() <= tail) {
q.poll() ;
}
while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
q.pollLast() ;
}
q.offer(i);
tail++;
}
rst.add(nums[q.peek()]) ;
return rst ;
}
public static void levelOrder (String start , Map<String,List<String>> graph){
Queue<String> q = new LinkedList<> ();
q.add(start) ;
HashSet<String> visited = new HashSet<> ();
int level = 1 ;
while (!q.isEmpty()) {
String cur = q.poll() ;
if (graph.containsKey(cur)) {
System.out.print("Level " + level + " - ");
for (int i = 0 ; i < graph.get(cur).size() ;++i) {
String next = graph.get(cur).get(i) ;
if (!visited.contains(next)) {
if (i != graph.get(cur).size() - 1) {
System.out.print(next + ",");
} else {
System.out.print(next);
}
visited.add(next) ;
q.add(next) ;
}
}
System.out.println();
level++;
}
}
}
- Scott June 25, 2015dynamic programming
f[i] = min (f[j -1] + 1, f[i])
public int numsOfWays (String s ){
long [] f = new long [s.length() + 1] ;
f[0] = 0;
for (int i = 1 ; i <= s.length() ;++i) {
f[i] = Integer.MAX_VALUE;
for (int j = 1 ; j <= i ;++j) {
if (s.charAt(j - 1) == '0'){
continue ;
}
int num = Integer.parseInt(s.substring(j - 1, i), 2) ;
if (isPower(num)) {
f[i] = Math.min(f[i], f[j - 1] + 1) ;
}
}
}
return f[s.length()] == Integer.MAX_VALUE ? -1 : (int)f[s.length()] ;
}
private boolean isPower (long val){
if (val == 0) {
return false ;
}
int n = (int)(Math.log(val) / Math.log(5));
return Math.pow(5, n) == val;
}
public void rearrange (int [] num) {
int odd = 0 , even = 1 ;
for (int i = 0 ; i < num.length ; ++i) {
while (odd < num.length && (num[odd] % 2) != 0) {
odd +=2 ;
}
while (even < num.length && (num[even] % 2) == 0 ) {
even +=2 ;
}
if (odd < num.length && (i % 2 != 0 && num[i] % 2 != 0)) {
swap (num,odd, i) ;
}
if (even < num.length && (i % 2 == 0 && num[i] % 2 == 0)) {
swap (num,even, i) ;
}
}
}
private void swap (int [] data , int i , int j){
int tmp = data [i] ;
data[i] = data[j] ;
data[j] = tmp ;
}
char [] opt = {'+', '-'} ;
public List<List<String>> GenerateSeq (int target , int [] array){
List<List<String>> rst = new ArrayList<List<String>>();
if (array == null || array.length == 0 || array.length == 1) {
return rst ;
}
List<String> curr = new ArrayList<> ();
curr.add(String.valueOf(array[0])) ;
generate (target, array[0], array, curr, rst, 1);
return rst ;
}
private void generate(int target , int sum , int [] array, List<String> curr, List<List<String>> rst , int index){
if (index >= array.length) {
return ;
}
if (index == array.length - 1) {
for (char c : opt) {
curr.add(String.valueOf(c)) ;
int val = cal (sum, array[index] , c) ;
if (val == target) {
curr.add(String.valueOf(array[index])) ;
rst.add(new ArrayList<String> (curr)) ;
curr.remove(curr.size() - 1) ;
}
curr.remove(curr.size() - 1) ;
}
return ;
}
for (char c : opt) {
curr.add(String.valueOf(c)) ;
curr.add(String.valueOf(array[index])) ;
int val = cal (sum, array[index] , c) ;
generate (target , val, array, curr, rst ,index + 1);
curr.remove(curr.size() - 1) ;
curr.remove(curr.size() - 1) ;
}
}
private int cal (int a , int b , char opt){
if (opt == '+') {
return a + b ;
} else {
return a - b ;
}
}
- Scott May 18, 2015public List<String> reconstruct(String [][] itinerary){
HashMap <String,String> graph = new HashMap<> ();
HashSet <String> relation = new HashSet<> ();
for (String [] it : itinerary) {
graph.put(it[0], it[1]) ;
relation.add(it[1]) ;
}
String start = "" ;
for (String [] it : itinerary) {
if (!relation.contains(it[0])) {
start = it[0] ;
}
}
if ("".equals(start)) {
return new ArrayList<String> ();
}
List<String> rst = new ArrayList<> ();
rst.add(start) ;
while (graph.containsKey(start)) {
start = graph.get(start) ;
rst.add(start) ;
}
return rst ;
}
public void reverseByGroup (int [] array, int k){
if ( array == null || array.length == 0 || k > array.length) {
return ;
}
int i = 0 , tail = 0;
int c = 1 ;
while ( i < array.length) {
if (c % k == 0){
reverse (array, tail ,i) ;
tail = i + 1 ;
}
i++;
c++;
}
}
private void reverse (int [] array, int i , int j){
for (; i < j ; ++i, --j) {
swap (array, i, j);
}
}
private void swap (int [] array , int i , int j){
int tmp = array[i] ;
array[i] = array[j] ;
array[j] = tmp ;
}
- Scott May 08, 2015the problem indicates that there are more than 100,000 so using recursive call may cause stack overflow , so I am using a stack to do inorder traverse , the time complexity is O(n)
public int getRange (TreeNode root, int x, int y){
int c = 0 ;
Stack<TreeNode> stack = new Stack<> ();
TreeNode cur = root ;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur) ;
cur = cur.left ;
} else {
TreeNode tmp = stack.pop() ;
if (tmp.val >= x && tmp.val <= y) {
c++;
}
cur = tmp.right ;
}
}
return c ;
}
- Scott April 24, 2015My clean java code
public String sumBinary (String a, String b){
int carrier = 0 ;
StringBuilder sb = new StringBuilder ();
int i = a.length() - 1 , j = b.length() - 1 ;
while (i >= 0 || j >= 0) {
int v1 = i < 0 ? 0 : a.charAt(i) - '0' ;
int v2 = j <0 ? 0 : b.charAt(j) - '0' ;
int sum = v1 + v2 + carrier ;
sb.append(sum % 2) ;
carrier = sum / 2 ;
i--;
j--;
}
if (carrier == 1) {
sb.append(carrier) ;
}
sb.reverse() ;
return sb.toString() ;
}
dynamic programming
public boolean isMatch(String s, String p) {
int pt = 0 ;
for (int i = 0 ; i < p.length() ;++i) {
if (p.charAt(i) != '*') {
pt++;
}
}
if (pt > s.length()) {
return false ;
}
boolean [][] f = new boolean[s.length() + 1][p.length() + 1];
f[0][0] = true ;
for (int i = 1 ; i <= p.length() ; ++i) {
f[0][i] = p.charAt(i - 1) == '*' && f[0][i-1];
}
for (int i = 1 ; i <= s.length() ; ++i) {
for (int j = 1 ; j <= p.length() ; ++j) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
f[i][j] = f[i - 1][j - 1] ;
}
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i - 1][j - 1] || f[i - 1][j] || f[i][j - 1] ;
}
}
}
return f[s.length()][p.length()] ;
}
- Scott April 08, 2015using extra memory O(N) N == row number
public void generateAll (int row){
int [] memory = new int [row];
memory[0] = 1;
generate (row, 0, memory) ;
}
private void generate (int row, int count , int [] memory){
if (row == count) {
System.out.println();
return ;
}
if (count == 0) {
System.out.println(memory[0] + " ");
generate (row, count + 1 , memory);
} else {
int pre = 0 ;
for (int i = 0 ; i <= count ; ++i) {
int rear = i == count ? 0 : memory[i] ;
int c = pre + rear ;
pre = rear ;
memory[i] = c ;
}
for (int i = 0 ; i <= count ;++i) {
System.out.print(memory[i] + " ");
}
System.out.println();
generate (row, count + 1 , memory);
}
}
public String convert(String target) {
char [] chs = target.toCharArray() ;
int count = 0 ;
int j = 0 ;
for (int i = 0 ; i <= chs.length ;++i) {
if (i == chs.length || i > 0 && (chs[i] == ' ' || !Character.isLetterOrDigit(chs[i])) && Character.isLetterOrDigit(chs[i - 1])) {
while (j < chs.length && !Character.isLetterOrDigit(chs[j])) {
j++;
}
if (j <= i) {
if (count % 2 == 0) {
toUpper (j, i - 1 , chs);
} else {
reverse (j, i - 1, chs) ;
}
j = i ;
count++;
}
}
}
return new String (chs) ;
}
private void reverse (int i , int j , char [] chs){
for (; i < j ; ++i , --j) {
char tmp = chs[i] ;
chs[i] = chs[j] ;
chs[j] = tmp ;
}
}
private void toUpper (int i , int j , char [] chs) {
for (int n = i ; n <= j ; ++n) {
chs[n] = Character.toUpperCase(chs[n]) ;
}
}
- Scott March 19, 2015dynamic programming
public int findMin (int d){
int to = (int) Math.sqrt(d) ;
int []f = new int[d + 1];
for (int i = 1 ; i <= d ; ++i) {
f[i] = i ;
for (int j = 1 ; j <= to ; ++j) {
if (i >= j * j) {
f[i] = f[i - j * j] + 1 < f[i] ? f[i - j * j] + 1 : f[i] ;
}
}
}
return f[d];
}
RepNelson Perez, Software Engineer
classical quick select
- Scott March 03, 2016