微软笔试题

1. Write a function solution that, given an array A of N integers, returnsthe largest integer K>0 such that both values K and -K(the oppositenumber)exist in array A. If there is no such integer, the function should return 0.

Examples:

1. Given A=[3, 2, -2 5, -3], the function should return 3(both 3 and-3exist in array A)

2. Given A=[1, 1, 2, -1, 2, -1], the function should return 1(both 1 and-1exist in array A)

3. Given A=[1, 2, 3, -4], the function should return 0(there is no such K for which both values K and-k exist in array A)

Write an efficient algorithm for the following assumptions N is an integer within the range [1..100, 000),each element of array A is an integer within the range [-1,000,000000.100000000]

#include 
#include 
#include 
using namespace std;

int solution(vector arr) {
    unordered_set hash;
    int ans=0;
    for (auto a : arr) {
        if (hash.count(0-a)!=0) {
            ans=max(ans, max(a, 0-a));
        }
        hash.insert(a);
    }
    return ans;
}
int main()
{
	cout< 
2. A string is called balanced when every letter occurring in the string ,appears both in upper-and lowercase . For example , the string "Catattac" is balanced ( 'a', 'c', 't' occur in both cases ) , but "Madam" is not ( 'd' and 'a' appear only in lowercase ) . Note that the number of occurrences does not matter.
 
Write a function :
 
 
 
int solution ( string &S) ;
 
 
that , given a string S of length N , returns the length of the shortest balanced fragment of S. If S does not contain any balanced fragments ,the function should return -1.
 
Examples :
 
1 . Given S = "azABaabza" the function should return 5 . The shortest balanced fragment of S is "Abaab".
 
2 . Given S = "TacoCat" the function should return-1 . There is no balanced fragment
 
3 . Given S = "AcZCbaBz" the function should return 8 . The shortestbalanced fragment is the whole string
 
4 . Given S = abcdefghijklmnopqrstuvwxyz" , the function should return -1
 
Assume that:
 
N is an integer within the range [1...200]
 
string S consists only of letters ( a-z and / or A-Z )
 
In your solution , focus on correctness . The performance of your solution will not be the focus of the assessment.
 
#include 
#include 
#include 
using namespace std;
bool fun(string str, int l, int r) {
	unordered_set hash;
	for (int i=l; i<=r; i++) {
		hash.insert(str[i]);
	}
	for (auto ch : hash) {
		if (ch>='a' && ch<='z') {
			if (hash.count('A'+(ch-'a'))==0)	return false;
		}else {
			if (hash.count('a'+(ch-'A'))==0)	return false;
		}
	}
	return true;
}
int solution(string str) {
	int ans=0;
	for (int k=2; k<=str.size(); k++) {
		for (int i=0; i<=str.size()-k; i++) {
			if (fun(str, i, i+k-1)){
				ans=max(ans, k);
			}
		}
	}
	return ans==0 ? -1 : ans;
}

int main()
{
	cout<