Lab 02
Here is a pdf version of the ppt I covered during the lab. And the codes that I (skimmed through) / (demonstrated live).
content.pdf (The pdf version of the ppt shown)
binary_search.cpp (Implementing binary search ourselver)
stl_binary_search.cpp (Using STL algorithms default implementation of binary search)
set_intersection.cpp (Implementing set intersection using our own binary search method)
throwns.cpp (Solution to this problem)
Apart from all this I would like you all to go through these function below for many different use cases -
binary_search (This function assumes the vector/array to be already sorted)
lower_bound (Assumes vector to be sorted. Also see upper_bound)
unique (Returns a iterator/pointer to the end of the resulting vector, see example for clarity)
set_intersection (In the example given, this function uses back_inserter())
set_union (Similar to above one)
tuple (See the example here, highlights are - can use auto to make_tuple() and can also do get<data_type> if ensured that there is only entry in the tuple having data_type)
Challenge Questions -
Q) Given an already sorted vector V and a target variable Z in input, check if there exists 2 elements in v, such that x + y = z, where x and y both belong to V. This should be done in O(n) (Do note - The vector in this case is sorted already in input)
Solution
// Let the vector be V and the target be Z. Assuming V to be sorted. int l = 0; for(int r = (int)V.size() - 1; r >= 0; r--) { while(V[l] + V[r] < z and l + 1 < r) l++; if(V[l] + V[r] == z) { cout<<"Found --> "<<V[l]<<" "<<V[r]<<endl; break; } } // The broad idea is to have 2 pointers, one on the left most // side of the vector and the other on the right most side. // Now slowly move the right pointer leftwards, i.e decrement // its postion by -1. While you are moving it to the left you // will realise that the net sum of A[l] + A[r] would decrease, // because A[r] < A[r + 1], so to again up this value close // to Z, you move l pointer forward, i.e increment it.
Q) Try to do set_union for 2 already sorted vectors A and B in O(n) using a 2-pointer style approach. (Will resemble to the merge operation in a merge sort) Update - 2 pointer approach basically means avoid using set_union and set_intersection
Solution
// Assuming I have vector A<> and vector B<> sorted. int l1 = 0, l2 = 0, top = -1; // top denotes the current top value in the res vector. // I am assuming that both the vectors will NOT contain any -1. // -1 is a sentinel value used to make the code shorter. vector&l;int&rt; res; //The vector which will have the union result. while(l1 < (int)A.size() or l2 < (int)B.size()) { if(l1 == (int)A.size()) { if(B[l2] != top) res.push_back(B[l2]), top = B[l2]; l2++; } else if(l2 == (int)B.size()) { if(A[l1] != top) res.push_back(A[l1]), top = A[l1]; l1++; } else { if(A[l1] <= B[l2]) { if(A[l1] != top) res.push_back(A[l1]), top = A[l1]; l1++; } else { if(B[l2] != top) res.push_back(B[l2]), top = B[l2]; l2++; } } } for(auto v : res) cout<<v<<" "; cout<<endl; // Here the broad idea is that you keep 2 pointers // where you move the one which points to the smaller element // and push it in the res vector if and only if the current // element at the top of the res vector is different from the element // being pushed. This ensured that an element is only pushed once. // Therefore it is equivalent to a set_union. // If you did NOT keep the top condition and just pushed it regardless of // the current top, then this would be the code for the merge step in // a merge-sort algorithm implementation.
Q) Sort a collection of names (represented as strings using only ‘a’ - ‘z’ without any spaces) first based on ascending length of the names, incase of ties, break the ties by descending order of the names themselves (Ex. {“abc”, “ab”, “xyz”} in sorted order will be {“ab”, “xyz”, “abc”})