Test job - Split Array

readme.md

The task from interview. There are two versions of this script written in php and python.

An integer X and a non-empty zero-indexed array A consisting of N integers are given. We are interested in which elements of A are equal to X and which are different from X. The goal is to split array A into two parts, such that the number of elements equal to X in the first part is the same as the number of elements different from X in the other part. More formally, we are looking for an index K such that: 0 ≤ K < N and the number of elements equal to X in A[0..K−1] is the same as the number of elements different from X in A[K..N−1]. For K = 0, A[0..K−1] does not contain any elements.

For example, given integer X = 5 and array A such that:

A = [5, 5, 1, 7, 2, 3, 5]

K equals 4, because: two of the elements of A[0..3] are equal to X, namely A[0] = A[1] = X, and two of the elements of A[4..6] are different from X, namely A[4] and A[5].

Write a function solution($X, $A); that, given an integer X and a non-empty zero-indexed array A consisting of N integers, returns the value of index K satisfying the above conditions. If more than one index K satisfies the above conditions, your function may return any of them. If there is no such index, the function should return −1.

For example, given integer X and array A as above, the function should return 4, as explained above.

Assume that: N is an integer within the range [1..100,000]; X is an integer within the range [0..100,000]; Each element of array A is an integer within the range [0..100,000].

Complexity: Expected worst-case time complexity is O(N); Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments); Elements of input arrays can be modified.

ArraySplitter.php

<?php

class ArraySplitter
{
    public $x; //the X
    public $a; //array
    public $n; //count of all elements
    public $k; //index of searching
    public $left; //count of $x in left part
    public $right; //count of !$x in right part

    public function __construct($x, $a)
    {
        try {
            $this->validation($x, $a);
        } catch (Exception $e) {
            echo "Exception: " . $e->getMessage() . "\n";
            die();
        }
        $this->x = $x;
        $this->a = $a;
        $this->n = count($a);
        if ($this->n > 2) {
            $this->k = round($this->n/2); //start to find from middle
        } else {
            $this->k = 0; //start to find from begining
        }
    }

    public function validation($x, $a)
    {
        if ($x < 0 || $x > 100000 || !is_int($x)) {
            throw new Exception("The X must be integer, 0 < X < 100000\n");
        }
        if (count($a) < 1) {
            throw new Exception("The count of array must be > 1", 1);
        }
        foreach ($a as $value) {
            if ($value < 0 || $value > 100000 || !is_int($value)) {
                throw new Exception("Each element of array must be integer and > 0 and <100000\n");
            }
        }
        if (!in_array($x, $a)) {
            throw new Exception("No one element from array is equal to X\n");
        }
    }

    public function toSplit($isEqual = false)
    {
        for ($i = 0; $i < $this->n; $i++) {
            $isEqual = $this->checkParts($this->k);
            if ($isEqual) {
                echo "Splitted at index = $this->k \n";
                var_dump(array_slice($this->a, 0, $this->k+1, true));
                var_dump(array_slice($this->a, $this->k+1, $this->n));
                return $this->k;
            }
            if ($this->left > $this->right) {
                $this->k -= ($this->left - $this->right);
            } elseif ($this->left < $this->right) {
                $this->k += ($this->right - $this->left);
            }
        }
        echo "Can't to split the array \n";
        return false;
    }

    public function checkParts($index)
    {
        //check left part of $a
        $left = 0;
        for ($i = 0; $i < $index; $i++) {
            if ($this->a[$i] === $this->x) {
                $left++;
            }
        }
        //check right part of $a
        $right = 0;
        for ($i = $index+1; $i < count($this->a); $i++) {
            if ($this->a[$i] != $this->x) {
                $right++;
            }
        }
        //check parts
        if ($left === $right) {
            return true;
        } else {
            $this->left = $left;
            $this->right = $right;
            return false;
        }
    }
}

$x = 5;
$a = [5, 5, 1, 7, 2, 3, 5];

$model = new ArraySplitter($x, $a);

echo "X = $model->x \n";
echo "N = $model->n \n";
var_dump($model->a);

$model->toSplit();

ArraySplitter.py

class ArraySplitter:
    def __init__(self, x, a):
        self.validation(x, a)
        self.x = x
        self.a = a
        self.left = 0
        self.right = 0
        self.n = len(a)
        if self.n > 2:
            self.k = round(self.n/2)
        else:
            self.k = 0

    def validation(self, x, a):
        if not(0 < x < 100000) or not int(x):
            raise ValueError('Oops! That was not valid number.')
        if len(a) < 1:
            raise ValueError('Oops! That was not valid array')
        if not a.count(x):
            raise ValueError('Oops! No one element from array is equal to X.')
        for item in a:
            if not(0 < item < 100000) or not int(item):
                raise ValueError('Oops! That was not valid array')

    def to_split(self, is_equal = False):
        for i in range(self.n):
            is_equal = self.check_parts(self.k)
            if is_equal:
                print("Splitted at index = " + str(self.k))
                return self.k
            if self.left > self.right:
                self.k -= self.left - self.right
            elif self.left < self.right:
                self.k += self.right - self.left
        print("Can't to split the array")
        return False

    def check_parts(self, index):
        left = 0
        for i in range(index):
            if self.a[i] == self.x:
                left += 1
        right = 0
        for i in range(index + 1, len(self.a)):
            if self.a[i] != self.x:
                right += 1
        if left == right:
            return True
        else:
            self.left = left
            self.right = right
            return False

x = 5
a = [5, 5, 1, 7, 2, 3, 5]

model = ArraySplitter(x, a)

print(model.x, model.a)
print(model.n, model.k)

model.to_split()

left = {}
right = {}
for (key, value) in enumerate(model.a):
    if key in range(0, model.k + 1):
        left[key] = value
    else:
        right[key] = value
print(left)
print(right)

I've recently faced the same task. If you don't mind here's the solution that I believe meets all the requirements: https://github.com/Jarosh/Exercises/wiki/Split-array-into-two-parts,-such-that-the-number-of-elements-equal-to-X-in-the-first-part-is-the-same-as-the-number-of-elements-different-from-X-in-the-other-part