fuleying
3/3/2018 - 10:05 AM

## codility tests

codility tests

``````// 第一题：
// Whole Square: (Codility)
// An integer P is a whole square if it is a square of some integer Q; i.e. if P = Q^2.
// Write a function:
//     class Solution { public int solution(int A, int B); }
// that, given two integers A and B, returns the number of whole squares within the interval [A..B] (both ends included).
// For example, given A = 4 and B = 17, the function should return 3,
// because there are three squares of integers in the interval [4..17], namely 4 = 2^2, 9 = 3^2 and 16 = 4^2.
// Assume that:
//     * A and B are integers within the range [-2,147,483,648...2,147,483,647];
//     * A <= B.
// Complexity:
//     * expected worst-case time complexity is O(sqrt(abs(B)));
//     * expected worst-case space complexity is O(1).

public static int solution(int A, int B) {
if(A > B) {
return 0;
}

int current = A;
int squareCount = 0;

while(current <= B) {
int sqrt = (int) Math.sqrt(current);
if(sqrt * sqrt == current) {
squareCount++;
}
current++;
}
return squareCount;
}

// 第二题：
// Determine whether a single swap is sufficient to sort an array of integers.
// Solution is to
// 1. find the first left incorrect position
// 2. Find first right side incorrect position
// 3. swap elements
// 4. Check if array is sorted , if not, return false;
// 5. restore elements by swaping previously swapped elements in step 3
// Time Complexity : O(N)

#include <algorithm>
bool solution(vector<int> &A) {
int left_index = -1;
for (size_t i = 0; i < A.size() - 1; ++i) {
if (A[i] > A[i + 1]) {
left_index = i;
}
}

if (left_index == -1)
return true;

int right_index = -1;

for (size_t i = A.size() - 1; i > 0; i--) {
if (A[i] < A[i - 1]) {
right_index = A[i];
}
}

std::swap(A[left_index], A[right_index]);
bool is_sorted = std::is_sorted(A.begin(), A.end());
std::swap(A[right_index], A[left_index]);
return is_sorted;
}

// 第三题：
// Count of index pairs with equal elements in an array
// Given an array of n elements.
// The task is to count the total number of indices (i, j) such that arr[i] = arr[j] and i != j

#include <unordered_map>

int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::unordered_map<int, int> un_mp;
for (int i=0; i < A.size(); i++) {
un_mp[A[i]]++;
}

int count = 0;
for(auto iter=un_mp.begin(); iter != un_mp.end(); iter++) {
int num = iter->second;
count += (num * (num - 1)) / 2;
}
return count;
}

// 第四题：
// given a zero indexed array A of N integers, returns the minimum cost of  dividing the chain into three parts.
// The problem is as follows:
// An array contains N integers.
// Index starts from 0.
// We have to break this array into 3 parts at breakpoints P and Q, where: 0 < P < Q < N-1.
// P and Q cannot be adjacent, that is: Q-P > 1.
// The cost of this breaking is arr[P]+arr[Q].
// An array can be broken in many ways using various legal combinations of P and Q, each having its own cost

#include <algorithm>
int solution(vector<int> &A) {
int p = 1;
int result= 1000000000;
for (int q=3; q < A.size()-1; q++) {
result = std::min(result, A[p] + A[q]);
if (A[p] > A[q-1]) {
// //Update min only with the last element to maintain the constraint P - Q > 1
p = q -1;
}
}
return result;
}``````