-
Is it possible to have a best case constant time function for finding a value in an array?
- No, because it would have to terminate before is has looked at the other values.
- Exception would be to find minimal value in a sorted array.
-
Describe a algorithm in pseudo code that stores the 3 greatest values of an array.
array A
Int max1=0, Max2=0, Max 3=0 ;
for (int i =0 ; i <n.length() ; i++){
- if (A[i]>Max1) {
- Max3 =Max2 ;
- Max2 =max1 ;
- Max1= A[i]
- }
- if (A[i]>Max2) {
- Max3 =Max2 ;
- Max2= A[i]
- }
- if (A[i]>Max3)
- Max3= A[i]
- }
}
-
Write the body of a method:
public static boolean hasDuplicates(int[] a, int k)
That takes an array of numbers and a constant k, where all numbers in the array are between 0 up to and including k.
It returns true if and only if the array contains any duplicate values.
For full points the worst case time (and memory) complexity of your function should be O(k).
- if(a.length > k) return true;
- Boolean[] bs = new Boolean [k+1] ;
for(int i=0 ; i<a.length ; i++) {
if(bs[a[i]] == true) return true;
-
Implement a binary search on an array of integers.
Describe the algorithm in java code.Make both the head of the function and the body.
- public Boolean binaryS ( int[] arr , int x) {
- int low = 0 ;
- int high = arr.length-1 ;
while(high>= low) {
int middle = (low + high) / 2 ;
if( arr[middle] == x ) return true ;
- if( arr[middle] < x )
- {
- low = middle +1 ;
- }
- if ( arr[middle] > x ){
- high = middle -1}
- }
- return false;
- }
-
Use class Heap with a constructor Heap()
together with methods
void add(int element)
int removeMin()
to write the body of a method:
public static void heapSort(int[] arr)
That takes an array and sorts it using the Heap sort algorithm.
- public static void heapSort(int[] arr){
- Heap h = new Heap();
for(int i=0 ; i < arr.length ; i++) {
- for(i=0 ; i arr.length; i++) {
- arr[i] = h.removeMin();
- }
}
-
Write the body of a method:
public static int countCommon(int[] a, int [] b)
That takes two sorted arrays and returns the number of values that are in both arrays (you may assume there are no duplicates in either array).
For instance for inputs {1,2,4,5,7} and{2,4,6,7,8} the result would be 3 because 2, 4 and 7 are in both arrays.
Complexity should be linear in the input size. (Hint: Use a simplified version for the merge algorithm for sorted arrays)
- public static int countCommon(int[] a, int [] b) {
- int i = 0 , j=0 , res=0;
- While (i<a.length && j <b.length) {
-
- if( a[i]<b[j] ) i++ ;
else if( a[i]>[b[j] ) j++;
- else { res++ ; i++ ; j++; }
- }
- return res ;
- }
-
Hur byter man plats på två element i en array?
- Först sparar man ett av elementen
- Sen byter genom att skriva över de sparade
- Sen sätt tillbaks de sparade på sin nya plats
-
Code an insertion sort algo
-
Code a depth first Search/Traversal for tree using a stack
-
Code a breadth first search/Traversal on a tree
-
-
-
-
-
-
-
-
-
-
-
-
|
|
