Enable contrast version

# Tutor profile: Dhawal H.

Inactive
Dhawal H.
Expert Programmer
Tutor Satisfaction Guarantee

## Questions

### Subject:Writing

TutorMe
Question:

Essay Tips: 7 Tips on Writing an Effective Essay

Inactive
Dhawal H.

### Subject:C++ Programming

TutorMe
Question:

Given an input string and a pattern, check if characters in the input string follow the same order as determined by characters present in the pattern. Assume there won’t be any duplicate characters in the pattern. Examples: Input: string = "engineers rock", pattern = "er"; Output: true All 'e' in the input string are before all 'r'. Input: string = "engineers rock", pattern = "egr"; Output: false There are two 'e' after 'g' in the input string. Input: string = "engineers rock", pattern = "gsr"; Output: false There are one 'r' before 's' in the input string.

Inactive
Dhawal H.

In this approach we first assign a label (or order) to characters of pattern. The labels are assigned in increasing order. For example, the pattern “gsr” is labeled as following "g" => 1 "s" => 2 "r" => 3 It means ‘g’ will come first, then ‘s’, then ‘r’ After assigning labels to pattern characters, we iterate through string characters. While traversing, we keep track of label (or order) of last visited character. If label of current character is less than previous character, we return false. Otherwise we update last label. If all characters follow order, we return true. Below is the C++ implementation // C++ program to find if a string follows order // defined by a given pattern. #include <bits/stdc++.h> using namespace std; const int CHAR_SIZE = 256; // Returns true if characters of str follow // order defined by a given ptr. bool checkPattern(string str, string pat) { // Initialize all orders as -1 vector<int> label(CHAR_SIZE, -1); // Assign an order to pattern characters // according to their appearance in pattern int order = 1; for (int i = 0; i < pat.length() ; i++) { // give the pattern characters order label[pat[i]] = order; // increment the order order++; } // Now one by check if string characters // follow above order int last_order = -1; for (int i = 0; i < str.length(); i++) { if (label[str[i]] != -1) { // If order of this character is less // than order of previous, return false. if (label[str[i]] < last_order) return false; // Update last_order for next iteration last_order = label[str[i]]; } } // return that str followed pat return true; } // Driver code int main() { string str = "engineers rock"; string pattern = "gsr"; cout << boolalpha << checkPattern(str, pattern); return 0; }

### Subject:C Programming

TutorMe
Question:

Given N-point on a 2D plane as a pair of (x, y) co-ordinates, we need to find a maximum number of a point which lies on the same line. Examples: Input : points[] = {-1, 1}, {0, 0}, {1, 1}, {2, 2}, {3, 3}, {3, 4} Output : 4 Then maximum number of point which lie on same line are 4, those point are {0, 0}, {1, 1}, {2, 2}, {3, 3}

Inactive
Dhawal H.

We can solve above problem by the following approach – For each point p, calculate its slope with other points and use a map to record how many points have the same slope, by which we can find out how many points are on the same line with p as their one point. For each point keep doing the same thing and update the maximum number of point count found so far. Some things to note in implementation are: 1) if two-points are (x1, y1) and (x2, y2) then their slope will be (y2 – y1) / (x2 – x1) which can be a double value and can cause precision problems. To get rid of the precision problems, we treat slope as a pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by their gcd before inserting into the map. In below code points which are vertical or repeated are treated separately. 2) If we use unordered_map in c++ or HashMap in Java for storing the slope pair, then total time complexity of solution will be O(n^2) /* C/C++ program to find maximum number of point which lie on same line */ #include <bits/stdc++.h> using namespace std; // method to find maximum colinear point int maxPointOnSameLine(vector< pair<int, int> > points) { int N = points.size(); if (N < 2) return N; int maxPoint = 0; int curMax, overlapPoints, verticalPoints; // map to store slope pair unordered_map<pair<int, int>, int> slopeMap; // looping for each point for (int i = 0; i < N; i++) { curMax = overlapPoints = verticalPoints = 0; // looping from i + 1 to ignore same pair again for (int j = i + 1; j < N; j++) { // If both point are equal then just // increase overlapPoint count if (points[i] == points[j]) overlapPoints++; // If x co-ordinate is same, then both // point are vertical to each other else if (points[i].first == points[j].first) verticalPoints++; else { int yDif = points[j].second - points[i].second; int xDif = points[j].first - points[i].first; int g = __gcd(xDif, yDif); // reducing the difference by their gcd yDif /= g; xDif /= g; // increasing the frequency of current slope // in map slopeMap[make_pair(yDif, xDif)]++; curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]); } curMax = max(curMax, verticalPoints); } // updating global maximum by current point's maximum maxPoint = max(maxPoint, curMax + overlapPoints + 1); // printf("maximum colinear point which contains current // point are : %d\n", curMax + overlapPoints + 1); slopeMap.clear(); } return maxPoint; } // Driver code int main() { const int N = 6; int arr[N] = {{-1, 1}, {0, 0}, {1, 1}, {2, 2}, {3, 3}, {3, 4}}; vector< pair<int, int> > points; for (int i = 0; i < N; i++) points.push_back(make_pair(arr[i], arr[i])); cout << maxPointOnSameLine(points) << endl; return 0; }

## Contact tutor

Send a message explaining your
needs and DHAWAL will reply soon.
Contact DHAWAL