A programming algorithms Huawei interview questions

Friend sent today a very special topic:

Topics:There are two array a,b,Size n,Any of the values of the array elements,Disorder;
Requirements:Through the exchange of a,Elements in the b,Elements of array a and b elements in the array, and the difference between the minimum。

I feel familiar at first glance the problem ... ... And domestic c exams almost,But a closer look seems to be a bit more difficult,Do not look like that has a clue what the problem。Ok,I asked to know,This is Huawei's interview questions。

Is, after all, interviews,So it is a little difficult。--But domestic ... ... This topic is really enough respect to the old Tan。Taking into account the main test is the algorithm,Then-and language-independent,I will use my most familiar with Swift to complete it。

In fact, this question is misleading,It deliberately stresses the "disorder" and "swap" makes you think about how to calculate--,Just disrupt rearrangement--pay attention to the length of the array to be fixed--I think this is why the size of the array to the same n。Also says that complex,Purpose is to say the figures add up in the two arrays to be as close as possible to,So,I wrote a function that sums the counting group backup:

This function accepts an array to loop through the summation,And then return the results。

Then what,I set up two arrays of the same length:

Here we have the default numeric type is plastic,Because a good calculation,Algorithms can also be used with decimal,This problem did not give clear instructions,But taking into account possible c language implementation,We don't blow the generic。

First of all,We wrote a function to handle the two arrays,Return a tuple with two arrays。The tuple contains two interchangeable elements in an array of,And they should be as close as possible--that is, as far as possible equal to zero。

then,Not compare and exchange--it's not the sort – well,In fact some sort of sense it is,We just pooled break array,Then removed from big to small in the two arrays in a。

Array in turn assigned

Array in turn assigned

But then I found this method a bug! That's what if I'm not the average of the array? Such as the one in the array has a maximum,That result is not so good:

If there is a significant number or minimum number of time

If there is a significant number or minimum number of time

And the results we expect is a great number of side is a smaller number filled,And the other side is left as large numbers as possible to fill,The difference between them is minimal:

This is the expected result

This is the expected result

So how to tell? We just need to determine the array (the sum of the elements) which is the biggest little not on the line? We seek not just before writing a function of sum of array elements,It's not used:)

So now we just need to realize broke up the passed array sorting into the Pool would be nice!

Here I use a structure to make a stack,Throw sort an array of,This is intuitive--you can use arrays,Just don't look too good just。

Then,Meet stack,Our function should look like this:

and many more,This seems wrong ... ... Run is the:

Haha,Looks like we need a variable to keep track of the length of the array,Or minutes are missing!

So,If the length of the array is different,So our function should not perform,Then we add a judge,If the parameter is incorrect(In other words,Enter two arrays of different lengths),Function is not performed,Avoid an array out of bounds。

Then,Function is the end result of this is the:

Such,We have the final code:

Code execution results:


Original article written by Gerber drop-off:R0uter's Blog » A programming algorithms Huawei interview questions

Reproduced Please keep the source and description link:https://www.logcg.com/archives/1461.html

About the Author

R0uter's Blog

The non-declaration,I have written articles are original,Reproduced, please indicate the link on this page and my name。

Leave a Reply

Your email address will not be published.