For each problems segment given below, do the following: 1. Create an algorithm
ID: 3574918 • Letter: F
Question
For each problems segment given below, do the following:
1. Create an algorithm to solve the problem
2. 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.
3. 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.
4. 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).
5. Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation
6. Transform your count formula into big-O notation by:
-Taking the efficiency with worst case input,
-Dropping insignificant terms.
-Dropping constant coefficients.
a. Determine if 2 arrays contain the none of the same elements elements (assume all elements are distinct)
b. 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)
c. Finding a row where every entry is 'a' in a 2-D array.
Explanation / Answer
a) Determine if 2 arrays contains the same elements
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[]){
HashMap<Integer, Integer> map = new HashMap<>();
for(int x : arr1){
if(map.containKey(x){
map.put(x, map.get(x)+1);
}else{
map.put(x, 1);
}
}
for(int y: arr2){
if(!map.containKey(y))
return false;
if(map.get(y) == 1)
map.remove(y);
else
map.put(y, map.get(y) - 1);
}
}
Worst case time complexity: O(n)
Space complexity: O(n)
b) 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){
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(map.containKey(c)){
map.put(c, map.get(c) + 1);
}
else{
map.put(c, 1);
}
}
int result = 0;
for(Map.Entry<Character, Integer> entry: map.entrySet()){
if(entry.getValue() > 1)
result = result + entry.getValue();
}
return result;
}
Worst case time complexity: O(n)
Space complexity: O(n)
c) Finding 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)
break;
}
if(j == cols)
return true;
}
return false;
}
Worst case time complexity: O(n^2)
Space complexity: O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.