Google Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
@loler, nicely done. I was thinking of:
- sorting the elements
- looping over the sorted list from each end
- adding the first and last element and checking whether the sum is divisible by k
But, your approach is better and eliminates the need to sort.
@Ben, if distinctive is needed, then the above approach can be altered slightly to use a hashset to remove duplicate pairs, while storing pairs such as (1,1).
@Prash: You might still use an approach similar to what you describe if k is large. Loler's solution is optimized for k being small. Also, I don't think dealing with the "distinct" condition, if indeed it was intended to be part of this problem, is that easy. You can't just not print duplicate pairs because the problem requires that you form n/2 pairs. You must form the pairs in such a way that none are duplicates.
@Prash: The mod operator is not reversible. So you actually haven't formed any pair to push to the hashset, only their residues. Check my answer below for a graph-based approach.
Awesome solution. But i did not understand usefulness of
if (k % 2 == 0) {
if (counts[k/2] %2 != 0) return false;
}
Can you please explain.
Right idea. I fixed two issues in the code, and made two optimizations.
static bool CheckPairable(int[] nums, int k)
{
int i, j;
int[] counts;
counts = new int[k];
for (i = 0 ; i < k ; i++)
{
counts[i] = 0;
}
foreach (int num in nums)
{
counts[num % k]++;
}
if ((counts[0] & 0x1) != 0)
return (false);
if ((k & 0x1) == 0)
{
if ((counts[k/2] & 0x1) != 0)
return false;
}
for (i = 1, j = k - 1 ; i < j ; i++, j--)
{
if (counts[i] != counts[j])
return (false);
}
return (true);
}
The time complexity of this idea is O(n + k).
This is a good idea when k < n.
But is this still a good idea when n is small (eq. 100) and k is large (eq. 100000000)?
@Alva0930: for that case, we could use a hash table instead of a bitset. This would still preserve the O(n) runtime (at least in terms of expected runtime). If we wanted worst-case guarantees we could store the remainders in a balanced tree and achieve a worst-case of O(n log n).
Code @loler solution in Python:
def pair_find(A, k):
assert(k > 0)
counts = [0] * k
for x in A:
counts[x % k] += 1
if counts[0] % 2 != 0:
return False
if k % 2 == 0 and counts[k / 2] % 2 != 0:
return False
for i in xrange(1, k / 2 + 1):
if counts[i] != counts[k - i]:
return False
return True
A = [0, 1, 2, 3]
assert(pair_find(A, 3))
A = [0, 1, 2, 2, 3, 4]
assert(pair_find(A, 3))
First idea:
Form a graph, joining number x to y if x+y is divisible by k.
Now run the matching algorithm on the graph.
On second thoughts, that is overkill.
Reduce each number to 0,1,.., k-1 (basically take remainder mod k).
Now an x can only be matched with k-x (or x if it is zero).
A greedy algorithm should work, it seems.
And since it is a decision problem, just maintain counts of 0, 1, ..., k-1 and checking if each is even should be enough.
Possible code (C# like)
bool checkPairable(List <int> nums, uint k) {
if (k == 0) throw ...;
int counts[k];
for (int i = 0; i < k; i++) {
counts[i] = 0;
}
foreach(int num in nums) {
counts[num %k]++;
}
for (int i = 0; i < k ; i++) {
if (counts[i] %2 != 0) {
return false;
}
}
return true;
}
If there are two numbers 6 and 6 and we have k as 5. Then sum count[1] will be 2 . I dont think it works in your case @lolo. It gices true as answer
Yes, we need to check if count[0] is even and if count[i] == count[k-i].
The code is messed up.
The above gets pretty complex if N is really really large.
Better solution find the sum of all numbers and then see if 'k' is a factor of the sum.
If the 'k' is less then sum of top to max from 'n' then we can create a n/2 pairs.
I tried a few examples and it works:
1, 2, 3, 4, 5, 6
we can have k=1,3,7
sum (5,6) = 11
1, 1, 2, 2, 3, 3
we can have k = 1, 2, 3, 4
sum (3, 3) = 6
Since 6 is a factors of sum of all n but is equal to sum (max two numbers).
@Simple Coder:
I'd like to start by pointing out that Loler's solution is O(n), which is optimal.
Your solution would have been O(n) as well, but unfortunately it's completely incorrect. Consider k=4 and 1 1 1 1 1 1 3 3. Sum divisible by 4? Yep. 3+3 > 4? Yep. But there is no way to do the splitting into pairs.
@eugene.yarovai and @loler:
how is it:
"we need to check if count[0] is even and if count[i] == count[k-i]".
I agree we need to check if count[i]==count[k-i]; but why to check if it is even or not? whats wrong with it being odd and equal (count[i] == count[k-i]. ??
I don't think Loier's strategy can be beaten. All you need to do is count the number of occurrences where mod(x) = 0 .. k-1, and then figure out if there are enough pairs.
There are two special cases to deal with while checking whether the pairing will work, which Loier did not pay specific attention to (but I am sure she meant it):
(a) When the modulus is 0
(b) When k is even and the modulus is k/2
In these cases, we need to check if there is an even number of occurrences rather than check the equality of occurrences with k-i.
{{
// ... rest of the code is ok.
for (int i = 0; i <= k/2 ; i++) {
if (i == 0 || (k%2=0 && i == k/2)) {
if (counts[i]%2 != 0)
return false;
}
if (counts[i] != counts[k-i]) return false;
}
}}
Oops. Loier has already done that in a later post of 9 Oct.
Not a mistake, but both checks (for counts[0] AND counts[k/2]) are not required ... one of them is enough, if we're assured that n is even.
The order of complexity is (n + k/2), and assuming k is a much smaller number than n, ~O(n).
If we assume that pair sums should not repeat, this could be little more involved that the matching algorithm
1 , 3 , 5 , 7 , 9 , 11 and k=12
#distinct sums = 1
The conditions listed earlier are necessary but not sufficient. You may want to look at
> find (i,j) such that xi+xj %k = 0, add a node for the sum and add a directed edge from (i,j) to sum, assume edge capacity 2
> add directed edges from sums to a sink node, assume edge capacity 2
> add directed edges from i to (i,j) and j to (i,j) assume edge capacity 1
> add directed edges of capacity 1 from a source node to i
Check if max flow from source to sink = n
Why are these questions (I literally mean questions. Solving comes later) so hard to understand? I get them eventually, but for most questions on career cup I see multiple interpretations possible and eventually arrive at one by process of elimination and/ or looking at answers.
Does anyone else feel the same way?
I suppose it is your responsibility to ask the interviewer to clarify if something is unclear. They are always trying to come up with new questions and are therefore not as clear for the person being interviewed as to the person who came up with the question.
Not to mention sometimes the question is ambiguous intentionally in order for interviewer to evaluate how good the candidate is in clarifying or negotiating the requirements. Then on top of that the person who posted the question on this website probably forgot some of the requirements or couldn't express well enough with English.
for each num
num = num%k;
each num is now between 0 and (k-1)
now count frequency of each x and k-x. they should be equal. don't check for zero at all. if for all x this is true then we are done. x varies from 1 to k/2.
O(n), using hash table
bool is_pairable(vector<int> &vec, int k){
if(k <=0) throw(0);
if(vec.size()%2 !=0) return false;
unordered_map<int, int> map;
for(auto &i:vec){
int rem = i%k;
if(map.find(rem) != map.end()){
map[rem] += 1;
}else
map[rem] = 1;
}
for(auto &i:map){
if(i.first == 0 && i.second%2 != 0)
return false;
int need = (k-i.first)%k;
if(map.find(need) == map.end())
return false;
else if(map[need] != i.second)
return false;
}
return true;
}
private void validate(List<Integer> input,int k){
getReducedElements(input,k);
Collections.sort(input);
boolean isPass = removeElements(input);
if(isPass)
isPass = checkForPairs(input,k);
if(!isPass){
System.out.println("We can not make pairs....");
System.exit(0);
}
System.out.println("We can make pairs....");
}
private boolean removeElements(List<Integer> nodes){
Iterator<Integer> it = nodes.iterator();
int count = 0;
while(it.hasNext()){
Integer n = it.next();
if(n == 0){
it.remove();
count++;
}
}
if(count%2 != 0){
return false;
}
return true;
}
private void getReducedElements(List<Integer> nodes,int k){
for(int i =0;i<nodes.size();i++){
Integer n = nodes.get(i);
nodes.set(i, n%k);
}
}
private boolean checkForPairs(List<Integer> nodes,int k){
while(!nodes.isEmpty() && nodes.size()%2==0){
if(nodes.get(0) + nodes.get(nodes.size()-1) == k){
nodes.remove(0);
nodes.remove(nodes.size()-1);
}else
return false;
}
if(nodes.isEmpty())
return true;
return false;
}
we can use graph,
take one vertex v[i], and divide by k to get remainder v[i]%k=r
iterate through the rest vertex by if((v[j]+r)%k==0) then mark both the vertex v[i] & v[j] as visited.
and proceed further till i reaches end.
I wish people who post solutions would stop to think about whether there's any rational reason that what they're proposing is correct.
Disagree with comments. @Jason is correct
For any pair (a, b) from given n number.
a%k = r1 and b%k = r2
for (a+b) to be divisible by k (r1 + r2) % k == 0.
If you generalize this for all n
a1, b1, a2, b2, .... an/2, bn/2 we get
sum of
r11, r12, r21, r22, .... r(n/2)1, r(n/2)2 % k == 0
which is exactly what Jason was saying in a simplified way,
@Anonymous: How about 1 1 1 1 1 1 3 3 and k=4? Sum is 12. 12 % 4 == 0, but you cannot form 4 pairs such that each will be divisible by k. So the condition Jason indicates is necessary but insufficient.
@eugene: you are right on that
@anonymous: as I posted the solution, you need to extend on the equation you reached,
for all non zero remainder let that be total of x
sum of all remainder <= x*K
if (sum of all remainder == x*K) then n/2 pairs exits
1, 1, 1, 1, 1, 1, 3, 3 and K=4
% 4 is
1, 1, 1, 1, 1, 1, 3, 3 here x = 8
(1 + 1 + 1+ 1+ 1+ 1+ 3 + 3) != 8*4
hence n/2 pairs dont exists
I wish people who claim an idea or code is incorrect would either provide a counter-example or explain briefly what's wrong with it. Sure it helps by telling the person he's wrong, but it would help even more if you would be nice enough to help him understand what's wrong.
@Sunny: not sure I understand you. I did provide an explicit counterexample above.
In any case, I believe the burden of proof falls on the person proposing the solution to justify its correctness, not on others to give counterexamples or dis-proofs. If this were not the case, we'd believe a great many false things. I'm usually happy to provide detailed feedback to people, but the person who posted this answer didn't even give any kind of justification or proof for the algorithm's correctness, so I can't really say where they went wrong because I don't know why they believed the algorithm to be correct in the first place.
@Eugene, oh I certainly wasn't talking about you. I was referring to the first few Anonymous who simply said that the solution was wrong etc without showing how. That sort of comment isn't that valuable to the user nor to the rest of us, but perhaps they did it intentionally since the person who proposed the solution was rather sloppy himself.
Sorry about the confusion. I read many of your comments on this website before and know you usually have something better to say :)
Form a graph, each node contains a unique number from the array and its count.
Connect node x and y if (x+y)%k == 0.
n/2 *distinctive* pairs can be formed if the graph is
(i) connected,
(ii) degree(x) >= count(x) for all x, and
(iii) the graph is a bigraph, and the total counts of both half are equal
Examples: k=5
{1,4,5,6} violates rule(i)
{1,1,4,4} forms a graph (value=1,count=2)------(value=4,count=2) or simply (1,2)---(4,2) violates rule (ii)
{1,1,4,4,6,6,9} violates rule (iii)
{1,1,4,4,6,6,9,9} forms the graph
(1,2)---(4,2)
\ /
x
/ \
(6,2)---(9,2)
which is OK, the distinct pairs are: (1,4), (1,9), (6,4), (6,9)
So how about k=4 and an input like 2 6 10 14? It seems that we can get 2 distinct pairs here, but the graph is not bipartite.
I think the graph doesn't need to be a bigraph, but instead, all of its connected components must satisfy (i), (ii) and:
(iii) the subgraph can be divided into 2 halves, whose total counts are equal.
So for k=4, {2 6 10 14} works
{2 6 10 14 18} doesn't,
and {2 2 6 10 14 18} works, since we can divide into the nodes
(2,2) (6,1) and (18,1) (10,1) (14,1) where total count of each half is 3.
And the final distinct pairs are: (2,18), (2,10), (6,14)
I think in common sense, distinct pairs can be interpreted as distinct sets of 2 numbers. Thus (6,8) != (7,7), but (6,8) == (8,6)
I don't see why the graph would need to be connected. Consider k=10 and 1 9 2 8 11 19. We can divide this into (1, 9), (11, 19), and (2, 8). However 2 and 8 is not connected to 1 or 9 or 11 or 19 in your approach.
Here is the second attempt (and I am guessing there will be more mistakes).
- Loler October 09, 2012bool checkPairable(List <int> nums, uint k) { if (k == 0) throw ... uint counts[k]; for(int i =0; i < k; i++) { counts[k] = 0; } foreach (int num in nums) { counts[num %k]++; } if (counts[0] % 2 != 0) return false; if (k % 2 == 0) { if (counts[k/2] %2 != 0) return false; } for (int i = 0; i <= k/2; i++) { if (counts[i] != counts[k-i]) return false; } return true; }