Q1: Determine if 2 arrays contain the same elements Q2: Counting total number ch

Question

Q1: Determine if 2 arrays contain the same elements

Q2: Counting total number characters that have a duplicate within a string (i.e. "gigi the gato" would result in 7 (g x 3 + i x 2 + t x 2)

Q3: Finding an empty row in a 2-D array where empty is defined as an element with a 0 entry.

For each question, do the following:

Create an algorithm to solve the problem

Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.

Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.

Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count: the best case (lower bound) and worst case (upper bound).

Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation

Transform your count formula into big-O notation by:

Taking the efficiency with worst case input

Dropping insignificant terms.

Dropping constant coefficients.

Explanation / Answer

Q1. Determine if 2 arrays contains the same elements

We can use HashMap to solve this problem.
1. Add all elements into HashMap with element as key and count as values(number of times elements appears in array)
   HashMap<Integer, Integer> hashMap;
  
2. Now, traverswe through 2nd array.
   for each element check whether it is available in hashMap or not. If it is there then decrease
   count of that element. IF count value is one then remove from hashMap.
   If current element from 2nd array is not present in hashMap, then return false.
  
   boolean isSameElements(int arr1[], int arr2[]){
       // create hashMap
       HashMap<Integer, Integer> map = new HashMap<>();
      
       for(int x : arr1){
           if(map.containKey(x){ // if already there in map, increment count
               map.put(x, map.get(x)+1);
           }else{
               map.put(x, 1);
           }
       }
      
       // for each element of array 2
       for(int y: arr2){
           if(!map.containKey(y)) // if not available in map
               return false;
           if(map.get(y) == 1) // if count is 1 then remove from map
                   map.remove(y);
           else
               map.put(y, map.get(y) - 1); // decrement count
       }

   }
  
   Worst case time complexity: O(n), Space complexity: O(n)
  
  
Q2. counting total number of duplicates chracters

   1. create a HashMap with key as character and count as value(number of times it appears in string)
   2. traverse through map and if count is greater than one then add in result
  
   int countDuplicates(String str){
       // building a count map
       HashMap<Character, Integer> map = new HashMap<>();
      
       for(int i=0; i<str.length(); i++){
           char c = str.charAt(i);
           if(map.containKey(c)){ // increment count
               map.put(c, map.get(c) + 1);
           }
           else{
               map.put(c, 1);
           }
       }
      
       // traverse through map
       int result = 0; // initializing result
       for(Map.Entry<Character, Integer> entry: map.entrySet()){
           if(entry.getValue() > 1) // if count is greater than one
               result = result + entry.getValue();
       }
      
       return result;
   }
  
   Worst case time complexity: O(n), Space complexity: O(n)
  
  
Q3).
   Finding empty row in 2d array
  
   1. traverse through each row and check whether current row is empty or not
   2. if current row is empty then return true else go for next row
   3. if all rows are non-empty then return flase
  
   boolean isEmptyRow(int arr[][], int rows, int cols){
      
       for(int i=0; i<rows; i++){
           int j=0;
           for(j=0; j<cols; j++){
               if(arr[i][j] != 0) // if any entry of current row is not 0 then go for next row
                   break;
           }
          
           if(j == cols) // all entry of current row is 0
               return true;
       }
      
       return false;
   }
  
   Worst case time complexity: O(n^2), Space complexity: O(1)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.