Thursday, July 30, 2015

Find Max Sum in a pyramid traversal


Problem : Given an array of n integers. find the max sum while traversing from parent to children when elements are arranged as a pyramid.
For ex: input = [5, 4, 12, 3, 11, 7, 2, 8, 1, 9 ]
     index = [0, 1, 2,  3, 4,  5, 6, 7, 8, 9 ]
        5
      4  12
    3  11   7
  2   8   1   9

 Output : 36
  5 + 12 + 11 + 8

 valid move: 4 to 3 or 11
 invalid move: 4 to 5 / 12 / 7 / 2
Basic idea is that at each level the number of elements are level +1.
Level 0= 1 element
Level 1= 2 elements
Level n-1 = n elements
Level n = n+1 elements.

For an elements its children would be at (index of element + level +1) and (index of an element +2) .
Traverse all levels recursively, find the max among both of its children, add it to the max and pass the new index and level to next recursion. Do this till index+level+2 < array.size.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 public long findMaxSum(List<Integer> input) {
  if(input == null || input.size() < 1){
   return 0;
  }
  return findMaxSum(input, 0, 0,input.get(0));
 }
   
 public long findMaxSum(List<Integer> input, int level, int parentIndex, int sum){
  if(parentIndex+level+2 < input.size()){
   parentIndex = (input.get(parentIndex+level+1) > input.get(parentIndex+level+2)) ? parentIndex+level+1 : parentIndex+level+2;
   sum = sum + input.get(parentIndex);
   return findMaxSum(input, ++level, parentIndex, sum);
  }else{
   return sum;
  }
 }
Posted by at No comments:
Labels:

Sunday, July 26, 2015

Find Single Number


Problem : Given an array of integers, every element appears twice except one. Find that single one in linear time. Can you do it in without using extra memory ?
Basic idea is to scan the array you take a xor of each element. Duplicate elements will cancel each other.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    public int singleNumber(int[] nums) {
        
        if(nums == null){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int result =0;
        for(int i=0; i < nums.length; i++){
            result = result^nums[i];
        }
        
        return result;
    }
}
Posted by at No comments:

2 Majority elements in an array


Problem : Given an array of n integers. Find all the elements which occur more than n/3 times in the array.

Basic idea is to use negation technique. There can be only 2 elements which can exist more than n/3 times in a given array. Take two temp variables and two counters and scan the array. Every time a new elements is encountered, store it in the temp variable and increase the counter by one. If next element is same as one of the two temp variables then increase the respective counter. If next element is different then decrease the counter, If one of the counter reaches 0 then replace that element with the new found element and set the counter to 1(This works on the same technique of negation of elements in case 1 element was present more than n/2 times). If we consider each element occurring for more than n/3 times and count them and decrease the count when we encounter a different which is less than n/3 times. In the end we will be left with at least 1 count of elements which exist more than n/3 times. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public List<Integer> majorityElement(int[] nums) {
        int countCheck = (nums.length/3) +1;
        int [] elements = new int[2];
        int count1 = 0;
        int count2 =0;
        List<Integer> arrayList = new ArrayList<Integer>();
        if(nums.length <1){
            return arrayList;
        }
        if(nums.length == 1){
            arrayList.add(nums[0]);
            return arrayList;
        }
         if(nums.length == 2 && nums[0] == nums[1]){
            arrayList.add(nums[0]);
            return arrayList;
        }
         if(nums.length == 2 && nums[0] != nums[1]){
            arrayList.add(nums[0]);
            arrayList.add(nums[1]);
            return arrayList;
        }
        
        for(int i = 0; i< nums.length; i++){
            if(nums[i]== elements[0] || nums[i]==elements[1]){
                if(nums[i] == elements[0]) count1++;
                else if(nums[i]== elements[1])count2++;
            }else if(count1==0){
                elements[0] = nums[i]; 
                count1++;
            }else if(count2 ==0){
                elements[1]=nums[i];
                count2++;
            }else {
                if(count1 >0){
                    count1--;
                }
                if(count2>0){
                    count2--;
                }
            }
        }
        count1=0;
        count2=0;
        System.out.println(elements[0]);
        System.out.println(elements[1]);
        for(int i=0; i< nums.length; i++){
            if(elements[0]==nums[i])
                count1++;
            if(elements[1] == nums[i])
            count2++;
        }
        if(elements[0] != elements[1]){
            if(count1 > (nums.length)/3 && nums.length>2){
                arrayList.add(elements[0]);
            }
            if(count2 > (nums.length)/3 && nums.length >2){
                arrayList.add(elements[1]);
            }
        }else{
            arrayList.add(elements[0]);
        }
     
        return arrayList;
    }
Posted by at No comments:

Saturday, July 25, 2015

Minimum cost path

Problem : Given a matrix and start point and end point what is the minimum cost to reach from start point to end point. Given that you can only go right or down.

Basic idea is that for each node you can only either come from up or down. Start from 0,0 and for each node check the minimum path from both directions. For row = 0, there is only right direction to go so keep adding the cost . for column = 0 there is only down direction to go. For rest of the T[i][j] check T[i][j] = T[i][j] +Min( T[i-1][j]], T[i][j-1] ). This will give the total sum for each node in the matrix. To back track and find the path. check where the sum came from and add that value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public int[] minimumCostPath(int[][] input){
  // total number of nodes traversed would be m+n-1
  if(input.length < 1 || input[0].length < 1){
   return new int [] {0};
  }
  int[] result = new int[input.length + input[0].length - 1];

int total  = input[0][0];
  for(int i = 0; i < input.length; i++){
   for(int j = 0; j< input[i].length; j++){
    if(i == 0 && j != 0){
     input[i][j] = input[i][j] + input[i][j-1];
     total = input[i][j];
    }else if(j != 0 && i != 0){
     input[i][j] = Math.min(input[i][j] + input[i-1][j], input[i][j] + input[i][j-1]);
     total = input[i][j];
    }else if(j == 0 && i != 0){
     input[i][j] = input[i][j] + input[i-1][j];
     total = input[i][j];
    }
   }
  }
  //get path;
  int path = result.length -1;
  int i = input.length-1;
  int j = input[0].length -1;
  while(total != 0){
   if(i > 0 && j > 0){
    if(input[i-1][j] < input[i][j-1]){
     result[path] = total-input[i-1][j];
     total = input[i-1][j];
     i = i-1;
     path--;
    }else{
     result[path] = total - input[i][j-1];
     total = input[i][j-1];
     j = j-1;
     path--;
    }
    
   }else if(j == 0 && i != 0){
    result[path] = total - input[i-1][j];
    total = input[i-1][j];
    i = i-1;
    path--;
   }else if(i == 0 && j != 0){
    result[path] =total - input[i][j-1];
    total = input[i][j-1];
    j = j-1;
    path--;
   }
   else if(i == 0 && j == 0){
    result[path] = input[i][j];
    total = total - input[i][j];
    path--;
   }
  }
  return result;
 }
Posted by at No comments:
Labels:

Longest Palindromic Subsequence


Problem: Given a string, find the longest palindromic subsequence possible. 

Basic idea is to divide the problem in subproblems. 
1. Start with a substring of length 1 and then 2 and 3 and so on.
2. As we are solving the sub problems store them in a matrix.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int longestPalindSubSequence(String s){
  char[] str = s.toCharArray();
  int[][] T = new int[s.length()][s.length()];
  for(int i=0; i<s.length(); i++){
   for(int j=0; j<s.length(); j++){
    if(i==j){
     T[i][j] =1;
    }
   }
  }
  
  for(int i = 0; i < s.length(); i++){
   for(int j=0; j < s.length()-i-1; j++){
    if(str[j]== str[i+j+1]){
     T[j][j+i+1] = 2 + T[j+1][i+j];
    }else{
     T[j][j+i+1] = Math.max(T[j+1][j+i+1], T[j][j+i]);
    }
   }
  }
  //test to see the result matrix;
  for(int i=0; i < T.length; i++){
   for(int j=0; j< T[i].length; j++){
    System.out.print(T[i][j]);
   }
   System.out.println();
  }
  return T[0][s.length()-1];
  
 }
 
 public int recursivePalindSubSeq(String s, int start, int len){
  if(len == 1){
   return 1;
           }
   if(len ==0){
   return 0;
           }
  if(s.charAt(start) == s.charAt(start+len-1)){
   return 2+ recursivePalindSubSeq(s, start+1, len-2);
  }else{
   return Math.max(recursivePalindSubSeq(s, start+1, len-1), recursivePalindSubSeq(s, start, len-2));
  }
 }
Posted by at No comments:
Labels:

Find holes


Problem : Given a matrix of 0 and 1s. Find all the possible holes and return an array with hole sizes. 
All adjacent 1's are part of 1 hole as long as they are left,right, up and down to each other. diagonal 1's do not matter. 

Example 1 : {1,0,1,1},
    {0,0,1,1},
    {1,0,1,1},
    {0,1,0,0},
    {1,1,0,1}
Result : {1,6,1,3,1}

Example 2 : {1,1,1,1},
    {1,1,1,1},
    {1,1,1,1},
    {1,1,0,0},
    {1,1,0,1}
Result : {16, 1}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public int[] findHoles(int[][] input){
  int [] results = new int[input.length *2];
  //initialize a temp array to maintain state and set all states to 0
  //0 = unvisited, 1 = visited. 
  int total =0;
  int[][]temp = new int[input.length][input[0].length];
  for(int i=0; i < temp.length; i++){
   for(int j=0; j < temp[i].length; j++){
    temp[i][j]=0;
   }
  }
  Stack stack = new Stack();
  for(int i=0; i < input.length; i++){
   for(int j=0; j < input[i].length; j++){
    
    if(input[i][j]==1 && temp[i][j] ==0){
     temp[i][j] = 1;
     int count =1;
     int [] neighbour = new int[] {i,j};
     if(neighbour[0] != -1){
      stack.push(neighbour);
     }
     while(neighbour[0] != -1 || !stack.isEmpty()){
      if(neighbour[0] != -1){
       neighbour = getNeighbour(neighbour[0],neighbour[1],input, temp);
       if(neighbour[0] != -1){
        stack.push(neighbour);
        count++;
       }
      }else{
       neighbour = (int[])stack.pop();
       neighbour= getNeighbour(neighbour[0],neighbour[1],input, temp);
       if(neighbour[0] != -1){
        stack.push(neighbour);
        count++;
       }
      }
       
     }
     results[total] =count;
     total++;
    }
   }
  }
  return results;
 }
 
 public int[] getNeighbour(int i, int j, int[][] input, int[][] temp){
  //check for last element by checking "j < input[i].length -1"
  int [] result = new int[2];
  //check right
  if(j < input[i].length -1 && input[i][j+1] ==1 && temp[i][j+1]==0){
   temp[i][j+1] =1;
   result[0]=i;
   result[1]= j+1;
   return result;
  }//check right
  else if(j > 0 && input[i][j-1] ==1 && temp[i][j-1]==0){
   temp[i][j-1] =1;
   result[0]=i;
   result[1]= j-1;
   return result;
  }//check up
  else if(i>0 && input[i-1][j] ==1 && temp[i-1][j]==0){
   temp[i-1][j] =1;
   result[0]=i-1;
   result[1]= j;
   return result;
  }//check down
  else if(i< input.length -1 && input[i+1][j] ==1 && temp[i+1][j]==0){
   temp[i+1][j] =1;
   result[0]=i+1;
   result[1]= j;
   return result;
  } 
  //if no neighbor then return -1,-1
  result[0]=-1;
  result[1]= -1;
  return result;
 }
Posted by at No comments:
Labels:

Friday, July 24, 2015

Sort array of strings with alphabetical string values and integer String values


Problem : Given an array of Strings with alphabetical string values and integer String values, sort the array mentaining their respective order of data type. 

For Ex : Input  ["bat", "cat", "3", "apple", "1", "2", "11"]
Result : ["apple", "bat", "1", "cat", "2", "3", "11"]

Basic idea is to first sort the string (which might not have natural sorted order for numbers), then create a Treeset of integer and string. Tree set will mention their natural sorting order. Then check the type of each index in original array and insert elements from trees one by one in the array based on index type in original array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public String[] sortAlphanumeric(String[] input){
  
  if(input== null || input.length == 1){
   return input;
  }
  String[] temp = Arrays.copyOf(input, input.length);
  Arrays.sort(temp);
  
  Set<Integer> intgr = new TreeSet<Integer>();
  Set<String> str = new TreeSet<String>();
  for(int i=0; i < temp.length; i++){
   try{
    int t= Integer.parseInt(temp[i]);
    intgr.add(t);
   }catch(NumberFormatException e){
    str.add(temp[i]);
   }
  }

  for(int k=0; k< temp.length; k++){
   boolean isIntgr = checkType(input[k]);
   if(isIntgr){
    temp[k] = intgr.iterator().next() + "";
    intgr.remove(intgr.iterator().next() );
   }else{
    temp[k] = str.iterator().next();
    str.remove(temp[k] );
   }
  }
  return temp;
 }
 
 public static boolean checkType(String s){
  try{
   Integer.parseInt(s);
   return true;
  }catch(NumberFormatException e){
   return false;
  }
  
 }
 public static void swap(int i, int j, String [] input){
  String temp = input[i];
  input[i] = input[j];
  input[j] = temp;
 }
Posted by at No comments:

Thursday, July 23, 2015

Largest Rectangle in Histogram



Problem : Given n nonnegative integers representing the histogram's bar height where the width of each bar is 1. find the area of largest rectangle in histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For Ex : Given height [2,1,5,6,2,3]
Return 10. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
    public int largestRectangleArea(int[] height) {
        //if stack is empty or current height is greater than previous height, 
        //push it in stack.
        // if height is equal ignore it.
        // if height is less than the previous height, keep popping heights 
        //till you find a lesser height or stack is empty. 
        //while popping calculate respective area and update max area.
        
        if(height == null || height.length <1){
            return 0;
        }
        Stack index = new Stack();
        Stack hStack = new Stack();
        int maxArea =0;
        for(int i=0; i < height.length; i++){
            if(hStack.isEmpty() || (int)hStack.peek() < height[i]){
                hStack.push(height[i]);
                index.push(i);
            }else if((int)hStack.peek() > height[i]){
                int lastIndex =0;
                
                while(!hStack.isEmpty() && (int)hStack.peek() > height[i]){
                    int hi = (int)hStack.pop();
                    int in = (int)index.pop();
                    lastIndex = in;
                    
                    int area = (i- in)* hi;
                    
                    if(area > maxArea){
                        maxArea = area;
                    }
                }
                //push current height now
                hStack.push(height[i]);
                //push the last index of the height which was popped
                //beacouse area of rectangle including current height will 
                //be counted from previous smaller rectangle. 
                index.push(lastIndex);
            }
        }
        
        while(!hStack.isEmpty()){
            int hi = (int)hStack.pop();
            int in = height.length - (int)index.pop();
            int area = in* hi;
            if(area > maxArea){
                    maxArea = area;
            }
        }
        return maxArea;
    }
    
}
Posted by at No comments:
Subscribe to: Comments (Atom)