Scott
BAN USERI was a SDET of Oracle OBIEE Team and I am looking for a new SDET/STE opportunity .
public int findBreakPoint(int [] array){
int sum = 0;
for (int i = 0;i<array.length ;++i){
sum+=array[i];
}
if (sum%2!=0){
return -1;
}
int res = 0;
int breakingPoint = 0;
for (; res<=sum/2;++breakingPoint){
res+=array[breakingPoint];
if (res==sum/2){
return breakingPoint;
}
}
return -1;
}
- Scott January 23, 2014dp
public int optimalPay(int [] coins , int money){
int [] dp = new int [money+1];
dp [0] = 0;
dp [1] = 1;
for (int i = 2; i<=money;++i){
dp[i] = i;
for (int j= 0; j<coins.length;++j){
if (i>=coins[j]){
dp[i]= dp[i-coins[j]]+1<dp[i]? dp[i-coins[j]]+1:dp[i];
}
}
}
return dp[money];
}
- Scott January 23, 2014import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Graph {
public void bfs(Node start){
Queue<Node> queue = new LinkedList<Node>();
queue.add(start);
while (queue.isEmpty()){
Node current = queue.poll();
for (Edge e : current.adj){
if (e.node.dest==Node.INFINITY){
e.node.dest = current.dest + 1;
e.node.pre = current;
queue.add(e.node);
}
}
}
}
public boolean isConnected(Node from , Node to){
if (to==null){
return false;
}else{
if (from ==to){
return true;
}else{
if (isConnected(from,to.pre)){
return true;
}
}
return false;
}
}
class Node{
public static final int INFINITY = Integer.MAX_VALUE;
Node pre;
List<Edge> adj;
int dest = INFINITY;
}
class Edge{
Node node;
int cost;
}
}
- Scott January 22, 2014import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Graph {
public void bfs(Node start){
Queue<Node> queue = new LinkedList<Node>();
queue.add(start);
while (queue.isEmpty()){
Node current = queue.poll();
for (Edge e : current.adj){
if (e.node.dest==Node.INFINITY){
e.node.dest = current.dest + 1;
e.node.pre = current;
queue.add(e.node);
}
}
}
}
public boolean isConnected(Node from , Node to){
if (to==null){
return false;
}else{
if (from ==to){
return true;
}else{
if (isConnected(from,to.pre)){
return true;
}
}
return false;
}
}
class Node{
public static final int INFINITY = Integer.MAX_VALUE;
Node pre;
List<Edge> adj;
int dest = INFINITY;
}
class Edge{
Node node;
int cost;
}
}
public static boolean matches(String text , String pattern){
int p_length = 0;
for (int i = 0 ;i<pattern.length();++i){
if (pattern.charAt(i)!='*'){
p_length++;
}
}
int i = 0 , j = 0;
int txt_length = 0;
boolean consecutive = false;
while (i<text.length()&&j<pattern.length()){
if (pattern.charAt(j)=='*'){
j++;
}else{
if (text.charAt(i)!=pattern.charAt(j)){
if (consecutive){
return false;
}
}else{
j++;
txt_length++;
consecutive = true;
}
}
i++;
}
return txt_length==p_length;
}
- Scott January 19, 2014public static int [] add(String a, String b){
char [] chs_a = a.toCharArray();
char [] chs_b = b.toCharArray();
int m = chs_a.length>=chs_b.length? chs_a.length:chs_b.length;
int [] result = new int [m+1];
int carry = 0;
int i = chs_a.length-1, j = chs_b.length-1;
while (i>=0&&j>=0){
result [m--] = ((chs_a[i]-'0') + (chs_b[j]-'0') + carry) %10;
carry = ((chs_a[i]-'0') + (chs_b[j]-'0') + carry)/10;
i--;
j--;
}
while (i>=0){
result [m--] = (chs_a[i] -'0' + carry)%10;
carry = (chs_a[i] -'0'+ carry)/10;
i--;
}
while (j>=0){
result [m--] = (chs_b[j] - '0'+ carry)%10;
carry = (chs_b[j] -'0'+ carry)/10;
j--;
}
if (carry!=0){
result [m--] = carry;
}
return result;
}
- Scott January 19, 2014import java.util.LinkedList;
import java.util.Queue;
public class PathFinder {
private Queue<Coordinator> queue;
public class Coordinator{
int x;
int y;
public Coordinator(int x , int y){
this.x = x;
this.y = y;
}
}
public PathFinder(){
queue = new LinkedList<Coordinator>();
}
char [][] maze = {{'a','b','c','d','e'},
{'f','g','h','i','j'},
{'k','l','m','n','o'},
{'p','q','r','s','t'},
{'u','v','w','x','y'},
{'z',' ',' ',' ',' '}};
public void setupCoordinator(String word){
for (int i = 0 ;i<word.length() ;++i){
queue.add(new Coordinator((word.charAt(i)-'a')/5,(word.charAt(i)-'a')%5));
}
}
public void findPath(){
Coordinator pre = new Coordinator(0,0);
int xMove = 0;
int yMove = 0;
while (!queue.isEmpty()){
Coordinator cur = queue.poll();
xMove = cur.x - pre.x;
yMove = cur.y - pre.y;
int i = pre.x;
int j = pre.y;
if (xMove >0){
for (i = pre.x+1 ; i<=pre.x + xMove;++i){
System.out.println("Down//now we are at " + maze[i][j]);
}
i-=1;
}else if (xMove<0){
for (i = pre.x-1; i>=pre.x - Math.abs(xMove);--i){
System.out.println("up//now we are at " + maze[i][j]);
}
i+=1;
}
if (yMove >0){
for (j = pre.y+1 ; j<=pre.y + yMove;++j){
System.out.println("Right//now we are at " + maze[i][j]);
}
j-=1;
}else if (yMove<0){
for (j = pre.y-1; j>=pre.y - Math.abs(yMove);--j){
System.out.println("Left//now we are at " + maze[i][j]);
}
j+=1;
}
System.out.println("OK//to select " + maze[i][j]);
pre = cur;
}
}
}
public static boolean find(int array []){
int sum = 0;
for (int i = 0 ;i<array.length ;++i){
sum+=array[i];
}
if (sum%2!=0){
return false;
}else{
return find (array, sum/2,0,0);
}
}
public static boolean find (int [] array, int sum ,int n ,int start){
if (n==sum){
return true;
}else if (n>sum){
return false;
}else{
for (int i = start ;i<array.length;++i){
n+= array[i];
if (find(array,sum,n,start+1)){
return true;
}
n-= array[i];
if (find(array,sum,n,start+2)){
return true;
}
}
return false;
}
}
- Scott January 17, 2014public static int max_depth_of_parentheses(char [] exp){
Stack<Character> stack =new Stack<Character>();
int max = Integer.MIN_VALUE;
int current = 0;
for (int i = 0 ;i<exp.length ;++i){
if (exp[i]=='('){
current++;
stack.push(exp[i]);
}
if (exp[i]==')'){
stack.pop();
}
if (stack.isEmpty()){
max = Math.max(max,current);
current = 0;
}
}
return current;
}
- Scott January 14, 2014public static void findPair(int [] array , int k){
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i =0 ; i<array.length;++i){
if (map.containsKey(array[i])){
System.out.println(map.get(array[i])+ " : " + array[i]);
}else{
map.put(k-array[i], array[i]);
}
}
}
- Scott January 14, 2014dp
public static int findMaxProfit(int [] wealth){
int max = Integer.MIN_VALUE;
int [] dp = new int [wealth.length];
//starting from 0
dp [0] = wealth [0];
//starting from 1
dp [1] = wealth [1];
for (int i = 2; i<wealth.length ;++i){
for (int j = 0; j<i-1;++j){
dp [i] = dp[i] >= wealth[i] + dp[j]? dp[i] : wealth[i] + dp[j];
max =Math.max(max, dp[i]);
}
}
return max;
}
- Scott January 12, 2014public boolean check(Node root, int curLevel, int preLevel){
if (root.left==null &&root.right==null){
// bottom of the tree
if (preLevel==0||preLevel==curLevel){
preLevel = curLevel;
return true;
}
return false;
}else{
//go to left sub tree
boolean bLeft= false;
if (root.left!=null){
bLeft = check(root.left, curLevel+1, preLevel);
}
boolean bRight = false;
if (root.right!=null){
bRight = check(root.right, curLevel+1, preLevel);
}
return bLeft&&bRight;
}
}
- Scott January 12, 2014dp solution
public static int findWaysDP (int [] []matrix , int x, int y){
int row = matrix.length;
int col = matrix[0].length;
int [] [] dp = new int [row][col];
dp [0][0] = 1;
for (int i = 0 ; i<row ;++i){
for (int j = 0 ; j <col ;++j){
// horizon
if (j+1<col){
dp [i][j+1] += dp[i][j];
}
//diagno
if (j+1<col &&i+1<row){
dp [i+1][j+1] += dp[i][j];
}
//down
if (i+1<row){
dp [i+1][j]+= dp[i][j];
}
}
}
return dp [x][y];
}
- Scott January 10, 2014recursive solution
public static int dofindNumOfWays(int [] [] matrix, int i ,int j,int value){
if (i>=matrix.length||j>=matrix[0].length){
return 0;
}else if (matrix[i][j]==value){
return 1;
}else{
int right = 0;
int down = 0;
int diagno = 0;
right = dofindNumOfWays(matrix,i,j+1,value);
diagno = dofindNumOfWays(matrix,i+1,j+1,value);
down = dofindNumOfWays(matrix,i+1,j,value);
return right + down + diagno ;
}
}
- Scott January 10, 2014public static String reorderByPattern(String src, String pattern){
int [] dp = new int [26];
char [] chs = src.toCharArray();
for (int i = 0 ;i<chs.length ;++i){
dp[chs[i]-'a']++;
}
int j = 0;
for (int i = 0; i<pattern.length() ;++i){
int count = dp [pattern.charAt(i)-'a'];
if (count !=0){
for (int k = 0 ;k<count ;++k){
chs [j++] = pattern.charAt(i);
}
}
}
return new String(chs,0,j);
}}
- Scott December 28, 2013public static void getWords(String [] words , char [] chs ){
boolean [] dp = new boolean [256];
boolean flag = true;
for (int i =0 ;i<chs.length;++i){
dp[chs[i]]=true;
}
for (String word : words){
for (int j =0; j<word.length() ;++j){
if (dp[word.charAt(j)]){
dp[word.charAt(j)] = false;
}else{
flag = false ;
break;
}
}
if (flag){
System.out.println(word);
}
//reset the dp
for (int j =0 ;j<word.length() ;++j){
dp[word.charAt(j)] = true;
}
}
}
- Scott December 23, 2013I just fixed the code, please help to test
public static int findPossibleWays(int val , int [] denominations){
int [] dp = new int [val+1];
dp[0] = 1;
for (int i =1 ;i<=val ;++i){
for (int j = 0;j<denominations.length ;++j){
if(i>=denominations[j]&&dp[i-denominations[j]]>0){
dp[i]++;
}
}
}
return dp[val];
}
- Scott December 22, 2013public static int findPossibleWays(int val , int [] denominations){
int [] dp = new int [val+1];
dp[0] = 0;
for (int i =1; i<=val ;++i){
for (int j =0 ;j<denominations.length ;++j){
if (i>=denominations[j]){
dp [i] =dp[i]>dp[i-denominations[j]]+1?dp[i]:dp[i-denominations[j]]+1;
}
}
}
return dp[val];
}
- Scott December 16, 2013public boolean isValid(CharStream in) {
while (in.hasNext()){
char c=in.next();
if (c=='('||c=='['){
stack.push(c);
} else if (c==')'){
if (stack.get(stack.size()-1)=='('){
stack.pop();
}
} else if (c==']') {
if (stack.get(stack.size()-1)=='['){
stack.pop();
}
}
}
return stack.size()==0;
}
public static boolean isAnagram (String str1,String str2){
int [] dp = new int [26];
for (int i =0 ; i < str1.length() ; ++i){
if (Character.isAlphabetic(str1.charAt(i))){
dp[str1.charAt(i)-'a']++;
}
}
for (int i =0 ; i < str2.length() ; ++i){
if (Character.isAlphabetic(str2.charAt(i))){
dp[str2.charAt(i)-'a']--;
}
}
for (int i =0 ;i<dp.length ;++i){
if (dp[i]!=0) return false;
}
return true;
}
- Scott November 27, 2013dynamic programming?
public static int findChain(int [] [] chain){
int [] dp=new int [chain.length];
dp [0] =1 ;
int max =1 ;
for (int i =1 ; i <chain.length ; ++i){
if (chain[i][0]>chain[i-1][1]){
dp [i]=dp[i]>dp[i-1]+1? dp [i] : dp[i-1]+1;
max=Math.max(dp[i], max);
}
}
return max;
}
- Scott November 26, 2013public static String Abbreviate(String sentence){
char [] chs =sentence.toCharArray();
boolean prehasSpace=true;
int charCount = 0;
int j =0, i =0 ;
for ( ; i < chs.length ; ++i){
if (Character.isAlphabetic(chs[i])){
//find the start of the word
if (prehasSpace){
prehasSpace=false;
chs[j++]=chs[i];
}else{
charCount++;
}
}else{
prehasSpace=true;
if (Character.isAlphabetic(chs[i-1])){
chs[j++]=(char)((charCount-1)+'0');
chs[j++]=chs[i-1];
charCount=0;
}
chs[j++]=chs[i];
}
}
if (Character.isAlphabetic(chs[i-1])){
chs[j++]=(char)((charCount-1)+'0');
chs[j++]=chs[i-1];
}
return new String(chs,0,j);
}
public static int find(int target, int left, int right , int [] rotate){
if (left>right){
return -1;
}
int mid = (left + right) /2 ;
if (rotate[mid] == target){
return mid;
}else if (target > rotate [mid]){
if (target>rotate[right]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[right]){
return find(target,mid+1,right,rotate);
}else {
return right;
}
}else {
if (target>rotate[left]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[left]){
return find(target,mid+1,right,rotate);
}else {
return left;
}
}
}
public static int find(int target, int left, int right , int [] rotate){
if (left>right){
return -1;
}
int mid = (left + right) /2 ;
if (rotate[mid] == target){
return mid;
}else if (target > rotate [mid]){
if (target>rotate[right]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[right]){
return find(target,mid+1,right,rotate);
}else {
return right;
}
}else {
if (target>rotate[left]){
return find(target,left,mid-1,rotate);
}else if (target<rotate[left]){
return find(target,mid+1,right,rotate);
}else {
return left;
}
}
}
public static int findStartPoint(int [] array){
int left=0;
int right=array.length-1;
while (left<=right){
int mid=(left+right)/2;
if (array[mid]<array[mid-1]){
return mid;
}
if (array[mid]<array[left]){
right=mid-1;
}else if (array[mid]>array[right]){
left=mid+1;
}else if (array[mid]>array[left]&&array[mid]<array[right]){
return 0;
}
}
return -1;
}
public static void permutationAll(char [] ch, StringBuilder sb,int count, boolean [] used){
for (int i=0;i<ch.length;++i){
if (used[i]){
continue;
}
sb.append(ch[i]);
System.out.println(sb.toString());
used[i]=true;
permutationAll(ch,sb,count+1,used);
sb.setLength(sb.length()-1);
used[i]=false;
}
}
public static void sumset(int [] array,int n,int s){
int [] tmp=new int[s];
microSoft(array,0,n,s,tmp,0,0);
}
public static void microSoft(int [] array, int current, int n,int s, int [] tmp, int count,int index){
if (current==n&&count==s){
StringBuilder sb=new StringBuilder();
for (int val:tmp){
//System.out.print(val+"+");
sb.append(val);
sb.append(",");
}
sb.setLength(sb.length()-1);
System.out.println(sb.toString());
}else if (count>=s){
return ;
}else if (current>n){
return;
} else{
for (int i=index;i<array.length;++i){
tmp[count]=array[i];
current+=array[i];
microSoft(array,current,n,s,tmp,count+1,++index);
current-=array[i];
}
}
}
public static void printNum(int n){
int [] array=new int [n];
sum_num(n,0,array,0,0);
}
private static void sum_num(int n,int cur,int [] array, int count,int next){
if (n==cur){
for (int i=0;i<count;i++){
System.out.print(array[i]+",");
}
System.out.println();
}else if (cur>n){
return;
}else{
for (int i=1;i<n;++i){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
sum_num(n,cur,array,count+1,i);{
cur-=i;
}
}
}
}
public static String reverseWord(String word){
char [] ch=word.toCharArray();
reverse(ch,0,ch.length-1);
int i=0,end=0;
while (i<ch.length){
if (ch[i]!=' '){
end=i;
while (i<ch.length&&ch[i]!=' '){
i++;
}
i--;
reverse(ch,end,i);
}
i++;
}
return new String(ch,0,ch.length);
}
private static void reverse(char [] ch, int start, int end){
for (int i=start,j=end; i<j;++i,--j){
char tmp=ch[i];
ch[i]=ch[j];
ch[j]=tmp;
}
}
public static String removeWhenOccurMoreThanOne(String target){
char [] ch=target.toCharArray();
int end=0;
boolean bSwitch=true;
for (int i=0;i<target.length();++i){
if (ch[i]!=' '){
ch[end]=ch[i];
bSwitch=true;
end++;
}else if (ch[i]==' '&&bSwitch){
end++;
bSwitch=false;
}
}
return new String(ch,0,end);
}
public static boolean isValid(String symbol){
LinkedList<Character> stack=new LinkedList<Character>();
char [] ch=symbol.toCharArray();
for (char c:ch){
if (stack.size()!=0){
char tmp=stack.getFirst();
if (tmp=='{'&&c=='}'){
stack.pop();
} else if (tmp=='['&&c==']'){
stack.pop();
} else if (tmp=='('&&c==')'){
stack.pop();
}else{
stack.push(c);
}
}else{
stack.push(c);
}
}
return stack.size()==0?true:false;
}
private static void Printer(int n,int cur, int []array,int count,int next){
if (cur==n){
for (int i=0;i<count;++i){
System.out.print(array[i]+";");
}
System.out.println();
}else if (cur>n){
return;
}else{
for (int i=1;i<n;i+=2){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
Printer(n,cur,array,count+1,i);
cur-=i;
}
}
}
public static boolean isStringSame(String str1,String str2){
int [] array=new int [256];
for (int i=0;i<str1.length();++i){
array[str1.charAt(i)]++;
}
for (int i=0;i<str2.length();++i){
array[str1.charAt(i)]--;
}
for (int i=0;i<array.length;++i){
if (array[i]!=0){
return false;
}
}
return true;
}
nt []array_Max={5, 5, 10, 2, 3};
int combine=0;
for (int i=0;i<array_Max.length;++i)
{
int j=i+1;
combine+=findCombination(array_Max,array_Max[i],j,15);
}
System.out.println(combine);
public static int findCombination(int []array, int sum, int iStart, int iTarget)
{
int n=0;
for (int i=iStart;i<array.length;++i)
{
if (sum+array[i]==iTarget)
{
n++;
}
n=n+findCombination(array,sum+array[i],++iStart,iTarget);
}
return n;
}
RepNelson Perez, Software Engineer
}
- Scott January 27, 2014