ARTS #007
ARTS #007
ARTS is an activity initiated by
由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.
ARTS 007
This is the 7th article. I used to be confused when looking at algorithms, but now I am slowly getting a feel for it and I have ideas. I hope it will get better and better in the future.
Algorihm algorithm question
leetcode algorithm question 15 3Sum: Difficulty: Moderate
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
The first method that comes to mind is as follows, which is of course the least efficient. On my device, it takes 15 seconds to test 3,000 pieces of data.
int** threeSum(int* nums, int numsSize, int* returnSize) {
int **a= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2; i++) {
for (int j =i+1; j < numsSize-1; j++) {
for (int k =j+1; k<numsSize; k++) {
int first = nums[i];
int second = nums[j];
int third = nums[k];
if (first + second + third == 0) {
if (first < second ) {
int temp =first;
first = second;
second = temp;
}
if (first < third ) {
int temp =first;
first = third;
third = temp;
}
if (second<third) {
int temp =second;
second = third;
third = temp;
}
int b = 0;
if(a != NULL){
for (int loop = 0; loop < count; loop++) {
int *aa = a[loop];
if (aa[0] == first && aa[1] == second) {
//已经存在
b = 1;
break;
}
}
}
if (b == 0) {
int* result = (int*)malloc(sizeof(int) * (3));
result[0] = first;
result[1] = second;
result[2] = third;
if (count ==0) {
count++;
a=(int**)malloc(sizeof(result)*count);
}
else{
count++;
a=(int**)realloc(a,sizeof(int*)*count);
}
a[count-1] = result;
}
}
}
}
}
*returnSize = count;
return a;
}
Looking at the prompts, they all sort first. After sorting, I thought of binary search, so I implemented it as follows
/插入排序
int* insertionSort(int nums[],int numsSize) {
for (int j = 1; j < numsSize; j++) {
int sortingNum = nums[j];
for (int i = j-1; i >=0; i--) {
if (sortingNum < nums[i] ) {
int temp = nums[i+1];
nums[i+1] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
// 二分查找
int binary_search(int arr[],int left,int right,int element){
while(left<=right) {
int mid = (left+right)/2;
if(arr[mid]>element){
right = mid - 1;
}
else if(arr[mid]<element){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
int** threeSum3(int* nums1, int numsSize, int* returnSize) {
int *dddsd = insertionSort(nums1,numsSize);
if(dddsd[0] > 0)
return NULL;
if(dddsd[numsSize-1] < 0)
return NULL;
int **result= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2 && dddsd[i] <=0; i++) {
for (int j =numsSize-1; j >i && dddsd[j] >= 0; j--) {
int first = dddsd[i];
int second = dddsd[j];
int third = 0 - first - second;
int dfsd =binary_search(dddsd, i+1, j-1, third);
if (dfsd == -1) {
continue;
}
third = dddsd[dfsd];
int b = 0;
if(result != NULL){
for (int loop = 0; loop < count; loop++) {
int *aa = result[loop];
if (aa[0] == first && aa[1] == second) {
//已经存在
b = 1;
break;
}
}
}
if (b == 0) {
int* sums = (int*)malloc(sizeof(int) * (3));
sums[0] = first;
sums[1] = second;
sums[2] = third;
if (count ==0) {
count++;
result=(int**)malloc(sizeof(sums)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = sums;
}
}
}
*returnSize = count;
return result;
}
The above algorithm, in order to prevent duplication, will compare it with the previous one every time the result is added. This operation can actually be optimized, and the final implementation is as follows:
//插入排序
int* insertionSort(int nums[],int numsSize) {
for (int j = 1; j < numsSize; j++) {
int sortingNum = nums[j];
for (int i = j-1; i >=0; i--) {
if (sortingNum < nums[i] ) {
int temp = nums[i+1];
nums[i+1] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
// 二分查找
int binary_search(int arr[],int left,int right,int element){
while(left<=right) {
int mid = (left+right)/2;
if(arr[mid]>element){
right = mid - 1;
}
else if(arr[mid]<element){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
int *sortedNums = insertionSort(nums,numsSize);
if(sortedNums[0] > 0)
return NULL;
if(sortedNums[numsSize-1] < 0)
return NULL;
int **result= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2 && sortedNums[i] <=0; i++) {
if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
continue;
}
for (int j =numsSize-1; j >i && sortedNums[j] >= 0; j--) {
if (j < numsSize-1 && sortedNums[j] == sortedNums[j+1]) {
continue;
}
int first = sortedNums[i];
int second = sortedNums[j];
int third = 0 - first - second;
int dfsd =binary_search(sortedNums, i+1, j-1, third);
if (dfsd == -1) {
continue;
}
third = sortedNums[dfsd];
int* sums = (int*)malloc(sizeof(int) * (3));
sums[0] = first;
sums[1] = second;
sums[2] = third;
if (count ==0) {
count++;
result=(int**)malloc(sizeof(sums)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = sums;
}
}
*returnSize = count;
return result;
}
Review
Get with the program WANT a job with a successful multinational? You will face lots of competition. Two years ago Goldman Sachs received a quarter of a million applications from students and graduates. Those are not just daunting odds for jobhunters; they are a practical problem for companies. If a team of five Goldman human-resources staff, working 12 hours every day, including weekends, spent five minutes on each application, they would take nearly a year to complete the task of sifting through the pile.
Looking for a position in a successful multinational company? Then you have to face a lot of competition. Two years ago Goldman Sachs received 250,000 job applications from students and graduates. This not only makes job seekers have a slim chance of success, but also brings real trouble to the company. Assuming that a team of five employees in Goldman Sachs’ human resources department worked 12 hours a day, around the clock, and spent five minutes on each application, it would take nearly a year to sift through this mountain of applications.
Little wonder that most large firms use a computer program, or algorithm, when it comes to screening candidates seeking junior jobs. And that means applicants would benefit from knowing exactly what the algorithms are looking for.
It’s no wonder that most large companies use a computer program, known as an algorithm, to screen candidates for lower-level positions. This means job seekers can benefit from knowing exactly what the algorithm is looking for.
Victoria McLean is a former banking headhunter and recruitment manager who set up a business called City CV, which helps job candidates with applications. She says the applicant-tracking systems (ATS) reject up to 75% of CVs, or résumés, before a human sees them. Such systems are hunting for keywords that meet the employer’s criteria. One tip is to study the language used in the job advertisement; if the initials PM are used for project management, then make sure PM appears in your CV.
Victoria McLean, a former banking headhunter and recruitment manager, started a company called City CV to help job seekers craft their applications. She said the Applicant Tracking System (ATS) rejects up to 75% of applications before a human can process the resume. These systems search for keywords that match the employer’s criteria. A quick tip is to research the language used in the job ad. If the initials PM are used to refer to project management, then make sure you have PM on your resume.
This means that a generic CV may fall at the first hurdle. Ms McLean had a client who had been a senior member of the armed forces. His experience pointed to potential jobs in training and education, procurement or defense sales. The best strategy was to create three different CVs using different sets of keywords. And jobhunters also need to make sure that their LinkedIn profile and their CV reinforce each other; the vast majority of recruiters will use the website to check the qualifications of candidates, she says.
This means that a resume that is not targeted may not even pass the first hurdle. McClain had a client who was a high-ranking military officer. Judging from his resume, he may have job opportunities in training and education, procurement, or arms sales. The best strategy, she says, is to create three different resumes using three different sets of keywords. Candidates also need to make sure their LinkedIn profile matches their resume—the vast majority of recruiters use the site to check candidates’ qualifications.
Passing the ATS stage may not be the jobhunter’s only technological barrier. Many companies, including Vodafone and Intel, use a video-interview service called HireVue. Candidates are quizzed while an artificial-intelligence (AI) program analyzes their facial expressions (maintaining eye contact with the camera is advisable) and language patterns (sounding confident is the trick). People who wave their arms about or slouch in their seat are likely to fail. Only if they pass that test will the applicants meet some humans.
ATS may not be the only technical hurdle job seekers face. Many companies, including Vodafone and Intel, have adopted a video interview service called HireVue. As candidates answer video questions, AI programs analyze their facial expressions (maintaining eye contact with the camera is recommended) and speech patterns (sounding confident is key). People who flail their arms or sit in a slouched posture are likely to fail. Only after passing this test can the job seeker meet with some interviewers.
You might expect AI programs to be able to avoid some of the biases of conventional recruitment methods—especially the tendency for interviewers to favor candidates who resemble the interviewer. Yet discrimination can show up in unexpected ways. Anja Lambrecht and Catherine Tucker, two economists, placed ads promoting jobs in science, technology, engineering and maths on Facebook. They found that the ads were less likely to be shown to women than to men.
Maybe you thought an AI program would be able to avoid some of the biases present in traditional recruiting methods, especially the tendency of interviewers to select candidates who are similar to themselves. Yet discrimination can show up in unexpected ways. Two economists, Anja Lambrecht and Catherine Tucker, posted ads on Facebook promoting job opportunities in science, technology, engineering and mathematics. They found that these ads were more likely to be served to men than to women.This was not due to a conscious bias on the part of the Facebook algorithm. Rather, young women are a more valuable demographic group on Facebook (because they control a high share of household spending) and thus ads targeting them are more expensive. The algorithms naturally targeted pages where the return on investment is highest: for men, not women.
This is not the result of conscious bias in Facebook’s algorithm. In contrast, young women are a more valuable group on Facebook (because they control a large portion of household spending), so ads targeting them are more expensive. These algorithms naturally target pages with the highest return on investment: men, not women.
In their book* on artificial intelligence, Ajay Agrawal, Joshua Gans and Avi Goldfarb of Toronto’s Rotman School of Management say that companies cannot simply dismiss such results as an unfortunate side-effect of the “black box” nature of algorithms. If they discover that the output of an AI system is discriminatory, they need to work out why, and then adjust the algorithm until the effect disappears.
Ajay Agrawal, Joshua Gans and Avi Goldfarb of the University of Toronto’s Rotman School of Management write in their co-author on artificial intelligence* that companies cannot simply dismiss such results as an unfortunate side effect of the “black box” nature of algorithms. If they find that the output of an AI system is discriminatory, they need to find out why and then adjust the algorithm until the impact disappears.
Worries about potential bias in AI systems have emerged in a wide range of areas, from criminal justice to insurance. In recruitment, too, companies will face a legal and reputational risk if their hiring methods turn out to be unfair. But they also need to consider whether the programs do more than just simplify the process. For instance, do successful candidates have long and productive careers? Staff churn, after all, is one of the biggest recruitment costs that firms face.
The potential for bias from AI systems has raised concerns in many areas, from criminal justice to insurance. The same is true for personnel recruitment. If companies use unfair recruitment methods, they will face legal and reputational risks. But they also need to consider whether these programs can do more than streamline the hiring process. For example, will a successful candidate remain with the company long-term and productively? After all, employee turnover is one of the biggest recruiting costs companies face.
There may also be an arms race as candidates learn how to adjust their CVs to pass the initial AI test, and algorithms adapt to screen out more candidates. This creates scope for another potential bias: candidates from better-off households (and from particular groups) may be quicker to update their CVs. In turn, this may require companies to adjust their algorithms again to avoid discrimination. The price of artificial intelligence seems likely to be eternal vigilance.
As candidates learn to tweak their resumes to pass the initial AI test, and the algorithms improve to filter out more applicants, it could spark an arms race. This creates room for another potential bias: Candidates from wealthier families (and certain groups) may be able to update their resumes more promptly. In turn, companies may need to adjust their algorithms again to avoid discrimination. The price of using artificial intelligence seems to be perpetual vigilance.
TIPS:
How to implement different arc sizes at different corners of the view
Cut all four right corners of the view into rounded corners:
//设置圆角半径值
self.view.layer.cornerRadius = 10.f;
//设置为遮罩，除非view有阴影，否则都要指定为YES的
self.view.layer.masksToBounds = YES;
- Cut a right angle of the view into a rounded corner:
//把 view2 的 左下角 和 右下角的直角切成圆角
UIView *view2 = [[UIView alloc] initWithFrame:CGRectMake(120,10,80,80)];
view2.backgroundColor = [UIColor redColor];
[self.view addSubview:view2];
//设置切哪个直角
// UIRectCornerTopLeft = 1 << 0, 左上角
// UIRectCornerTopRight = 1 << 1, 右上
// UIRectCornerBottomLeft = 1 << 2, 左下角
// UIRectCornerBottomRight = 1 << 3, 右下角
// UIRectCornerAllCorners = ~0UL 全部角
//得到view的遮罩路径
UIBezierPath *maskPath = [UIBezierPath bezierPathWithRoundedRect:view2.bounds byRoundingCorners:UIRectCornerBottomLeft | UIRectCornerBottomRight cornerRadii:CGSizeMake(10,10)];
//创建 layer
CAShapeLayer *maskLayer = [[CAShapeLayer alloc] init];
maskLayer.frame = view2.bounds;
//赋值
maskLayer.path = maskPath.CGPath;
The rounded corners set by the above method have the same arc for each rounded corner. So how to achieve four corners with different rounded corner sizes? The key to realizing the rounded corners above is the path of CAShapeLayer, so we only need to customize this path. The implementation is as follows:
- (void)setViewRadius:(UIView *)view{
CGFloat topLeftRadius = 50;
CGFloat topRightRadius = 60;
CGFloat bottomRightRadius = 40;
CGFloat bottomLeftRadius = 30;
CGFloat minx = CGRectGetMinX(view.bounds);
CGFloat miny = CGRectGetMinY(view.bounds);
CGFloat maxx = CGRectGetMaxX(view.bounds);
CGFloat maxy = CGRectGetMaxY(view.bounds);
UIBezierPath *path = [[UIBezierPath alloc] init];
[path moveToPoint:CGPointMake(minx + topLeftRadius, miny)];
[path addLineToPoint:CGPointMake(maxx - topRightRadius, miny)];
[path addArcWithCenter:CGPointMake(maxx - topRightRadius, miny + topRightRadius) radius: topRightRadius startAngle: 3 * M_PI_2 endAngle: 0 clockwise: YES];
[path addLineToPoint:CGPointMake(maxx, maxy - bottomRightRadius)];
[path addArcWithCenter:CGPointMake(maxx - bottomRightRadius, maxy - bottomRightRadius) radius: bottomRightRadius startAngle: 0 endAngle: M_PI_2 clockwise: YES];
[path addLineToPoint:CGPointMake(minx + bottomLeftRadius, maxy)];
[path addArcWithCenter:CGPointMake(minx + bottomLeftRadius, maxy - bottomLeftRadius) radius: bottomLeftRadius startAngle: M_PI_2 endAngle:M_PI clockwise: YES];
[path addLineToPoint:CGPointMake(minx, miny + topLeftRadius)];
[path addArcWithCenter:CGPointMake(minx + topLeftRadius, miny + topLeftRadius) radius: topLeftRadius startAngle: M_PI endAngle:3 * M_PI_2 clockwise: YES];
[path closePath];
CAShapeLayer *maskLayer = [[CAShapeLayer alloc] init];
maskLayer.path = path.CGPath;
view.layer.mask = maskLayer;
Give another demo of UIView to implement gradient color.
UIColor *frameColor = [UIColor colorWithHexString:@"#FFB300"];
UIColor *toColor = [UIColor colorWithHexString:@"#FF6100"];
CAGradientLayer *gradientLayer = [CAGradientLayer layer];
gradientLayer.locations = @[@0.0, @1.0];
gradientLayer.startPoint = CGPointMake(0, 0);
gradientLayer.endPoint = CGPointMake(1.0, 0);
gradientLayer.frame = _bgImageView.bounds;
gradientLayer.colors = @[(__bridge id)frameColor.CGColor, (__bridge id)toColor.CGColor];
[_bgImageView.layer insertSublayer:gradientLayer atIndex:0];
Share:
There is a Zhihu Q&A going viral today, ~~ Is Tencent’s technology construction currently (in 2018) lagging behind companies of the same size? ~~,yAn answer named toughguy became popular, but the author’s answer was deleted a day after it was posted. However, there is a backup online. If you are interested, you can search it.
Let me share my thoughts on this issue:
The article talks about poor technology, insufficient talent reserves, technology settlement, and relatively rigid internal rules and regulations within the company. The company I work for is actually like this. Many of the company’s systems are not conducive to the development of the company’s technology. Many of the company’s junior leaders are old people who have been in the company for more than 5 years. Their skills are average and they have survived. Some of them don’t even know Git and are still using SVN. No one dares to refactor the code because there are no test cases. If you correct the bug, you have to take responsibility. The attitude of the leader is that it can be used.
It can be said that the technical level of a team depends on the leadership of the team. If the leadership pattern is large enough and the ability is strong enough, the creativity of the entire team will be strong.
If a leader is complacent, pursues stability, and prevents others from using new technologies without making progress, then he is screwed and should leave as soon as possible.
In a large company, it is difficult for a grassroots programmer to change this situation. I think the only way to change this situation is from the leadership.
There is also the issue of overtime. In fact, a lot of overtime in large companies is not because the work cannot be completed, but because the company uses this as a standard to measure workload. In this way, no matter what happens, there must be enough overtime. Commonly known as face project.
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。