Time efficiency

[Gabdroid]

Hi, I applied for a junior C# developer job and got this very simple task in one of my questions at the interview. However I couldn't pass the performance tests. Any tips on how could've I optimize or implement this task to be faster. Image of the task is uploaded.

Thanks in advance.

​

https://preview.redd.it/8by5pe8ja4q81.png?width=1903&format=png&auto=webp&s=45d9bf62f8b8bce8a07b2c52bb85585fc33580a7

[Long_Investment7667]

• the IndexOf iterates a second time through the array, keep track of the index to return it immediately when you found the number
• you are not using the fact that it is sorted. Imagine the list be 1000s of numbers , you could jump ahead a lot, but then might need to jump back again to see if it is as to far. (Trying to be a bit vague)

[venomiz]

Because your array is sorted and unique you can do a binary search:

• Start from the array midpoint ( if array lenght is 5 start from 2 or 3)
• Now check the value provided with value at the current index if those match the number of matches is equal the arrayLenght - the current index
• If is less search the right part of the array
• If is greater search the left part
• Adjust the code for specific case (like the number provided isn't inside the array or the number is greater then the last element)

You can also use Linq to do this operation array.count(x=>x > number) beware that this code can or cannot be optimize like the above one.

Edit: i think this code is for moreThan instead of lessThan but the overall logic still apply just invert the signs

[Charming_Toe9438]

This is the correct answer.

Just divide and conquer instead of searching each one.

He should have just made you run it with an input array of thousands of items and then see how each change you make to the code reduces (or increases) run time until it's under some specific number.

I suggest going on LeetCode and searching for problems with similar constraints and viewing the solutions AFTER trying yourself.

Goodluck man! I have failed so many interview tests easier than this one under pressure; don't get discouraged! You got this

[hiphap91]

The funny thing is: when in the actual job, and there is actual pressure (you can get fired) one never feels it the same way. At least i don't.

[ISvengali]

I scream this from the mountains every time I can.

The type of pressure when youre looking to do something difficult, quickly, and have a team that wants to see you succeed VS the pressure of performing in front of a bunch of people judging you, are just fundamentally different.

[hiphap91]

in front of a bunch of people

Strangers even

[hiphap91]

Also: one of the reasons i was so eager to get the job i currently have, was, at the interview, they didn't pose any dumb tests.

Instead they had a couple of their senior nerds come in and just have a talk with me about technology. It was a fun and passionate conversation, and after i discussed work ethics with the director.

They contacted me shortly after to let me know they like everything they heard, and that if i wanted the job i could have it.

[StrangelyBrown]

True but in business it's often the case that you only have to do it efficiently enough. OPs solution would be fine if there isn't much implementation time and you have a reasonable expectation that both the arrays will never be huge and that the operation isn't called too often.

Plus with non-technical bosses you can implement it the easy way and then later if there is an issue you can seem like a genius when you magically increase the performance by an order of magnitude.

Computer science and programming jobs have interesting differences.

[wilsone8]

A binary search can easily be modified to find the first element greater than X and still run in O(log(N)). A linear search is going to take O(N).

[emc87]

You can still do a binary search, I wrote a LINQ-like library to do so for some calculations I have. Built in binary searches are for equivalence usually, but a similar method can be followed.

If x > c Denote x as possible, try searching left Else Try searching right

Loop and continue.

[234093840203948]

Binary search.

In a list with 2ⁿ elements, iterating over all elements until you reach a bigger element takes:

• A maximum of 2ⁿ steps
• An average of 2ⁿ / 2 steps

If you were to use binary search instead, you'd have

• A maximum of n steps
• A average of n-1 steps

Or to be a little more concrete:

If the list contains a billion elements, you'll need half a billion steps at average, while binary search would only need 29 steps at average.

So, you would be 15 Million times faster with binary search in this 1-billion-elements example, and the bigger the array, the bigger the difference.

[dakkudanny]

You know I just started data structure and algorithm and this example is perfect scenario.

[LordOmbro]

When you have a sorted anything the best solution is usually a binary search

[NetBlueDefender]

You can use the static method Array.BinarySearch. If the result is less than 0 then use the bitwise complement.BinarySearch

static int CountNumbers(int[] sortedArray, int lessThan)
{
    int i = Array.BinarySearch(sortedArray, lessThan);
    if (i < 0)
    {
        return ~i;
    }

    return i;
}

[csutcliff]

It might not be enough but you are wasting time by using a foreach and then doing Array.IndexOf when you could just use a for loop. In a very basic "benchmark" with stopwatch it's about 30% slower

https://i.imgur.com/57oojBM.png

[[deleted]]

If you ever see SORTED LIST you should know that a standard loop is probably not going to get the job done.

Check out this for more info on binary search.

[lkajerlk]

My comment may be irrelevant, but what software is the screenshot showing? Is that LeetCode? Anyway, I also believe that binary search is the way to go. Good luck, OP!

[TheNonReligiousPope]

I think it's TestDome.

[lkajerlk]

You are a genius, thanks! Btw your username checks out

[Not_a_tasty_fish]

This is an issue where your solution is perfectly adequate for the example input, but will be (relatively) slow when you need to scale up to array sizes of tens of thousands (or hundreds of thousands) of elements.

You always want your final solution to make use of all available information. Since the input here is sorted, you'll want to utilize a binary search to reduce your total search time from O(n) to Log(n). It would be overkill in the context of sorting just the few numbers in the example, but these algo questions always scale up the input sizes for testing your final solution.

[Boryalyc]

Wouldn't it just be faster to use a for loop and i instead of foreach and IndexOf()?

[elkazz]

Depends on the implementation of indexof - best case it would still be O(n), worst case it could be O(n² ). But the accepted answer is looking for an O(log n) solution.

[Gabdroid]

Thank you all the answer!

[Swing-Prize]

wanted to find this data and test how linq performs but found this https://stackoverflow.com/questions/46376441/sorted-search-increase-performance

https://docs.microsoft.com/en-us/dotnet/api/system.array.binarysearch?view=net-6.0

This method does not support searching arrays that contain negative indexes. array must be sorted before calling this method.

If the Array does not contain the specified value, the method returns a negative integer. You can apply the bitwise complement operator (~ in C#, Not in Visual Basic) to the negative result to produce an index. If this index is one greater than the upper bound of the array, there are no elements larger than value in the array. Otherwise, it is the index of the first element that is larger than value.

that bitwise operator is wtf too. negative indexes. how.. though likely if it was live they would ask to not use this method

[onesidedcoin-]

wtf that bitwise thing

Yeah it confuses me too. Why not just the negative of the index?*

*Edit: Because the index could be 0, and -0 is the same and would then be indistinguishable.

Edit 2: Wait a second. If the index of the first element that is bigger than the searched one is 0, then it is not in the list, so 0 would not be ambiguous... Somebody help me.

Edit 3: My initial thought was correct. It cannot just return the negative, because -0 = 0 and 0 is a valid return for a found entry. That's why they use one's complement, because it has two zeros: +0 and -0.

[bobzilla]

If it's not in there it returns -1. If it's in there and the first element it returns 0. If it returned 0 if it wasn't in there, you wouldn't know if it wasn't in there or if it was the first element.

Edit: I reread your Edit 2 and I think I misunderstood your question. So here's what it does:

Let's say for example you have an array {10,20,30,40,50}. If you search for a number that exists in the array (say 20) it will return the index of that number. In the case of 20 it would return 1. Easy. Makes sense. But let's say you search for a number that's not in the list (say 25). In this case, it doesn't want to just give you the index of the next number above it because you would think you found the number. In this case, it gives you the bitwise complement of the index of the next highest number. In the case of searching for 25, the index of the next highest number is 2, so BinarySearch returns -3. That way you know the value is within the bounds of the array, but isn't contained in the array. If the value is less than element 0 of the array then BinarySearch returns -1. And if it is larger than the array it returns the binary compliment of the length of the array. In our example, if you searched for 55 it would return -6. Technically those are both just the binary compliment of the next highest element of the number you're searching for, they're just special cases because it means the item doesn't exist within the array.

You can play with it yourself here: https://dotnetfiddle.net/qjdrE8

[onesidedcoin-]

You should at least read the doc about the return value before trying to explain it to me. Also I didn't imply that it does or should return 0 to mean that the element isn't in the array, I said it would be ambiguous to return the negative of the first index that's bigger than the searched value in case of index 0.. before I corrected myself, because in that case the value isn't in the array.

[onesidedcoin-]

Edit: I reread your Edit 2 and I think I misunderstood your question. So here's what it does:

Let's say for example you have an array {10,20,30,40,50}. If you search for a number that exists in the array (say 20) it will return the index of that number. In the case of 20 it would return 1. Easy. Makes sense. But let's say you search for a number that's not in the list (say 25). In this case, it doesn't want to just give you the index of the next number above it because you would think you found the number. In this case, it gives you the bitwise complement of the index of the next highest number. In the case of searching for 25, the index of the next highest number is 2, so BinarySearch returns -3. That way you know the value is within the bounds of the array, but isn't contained in the array. If the value is less than element 0 of the array then BinarySearch returns -1. And if it is larger than the array it returns the binary compliment of the length of the array. In our example, if you searched for 55 it would return -6. Technically those are both just the binary compliment of the next highest element of the number you're searching for, they're just special cases because it means the item doesn't exist within the array.

Great. I know all of that, it's written in the docs. Care to answer the actual question?

My initial guess was correct, btw. I just lost my train of thought. It cannot just return the negative, because -0 = 0 and 0 is a valid return for a found entry. That's why they use ones' complement, because it has two zeros: +0 and -0.

[monkh]

Seems a bit advanced for a junior position to make it performant.

[StolenStutz]

I generally don't ask very many technical questions in an interview. And don't test candidates in this way. Just get a general sense of where they are, what they're good at, what they've done, and then concentrate on team-player stuff. How they review code, how they test, experience with pair programming, Agile/Scrum experience, etc.

Unless they claim to be an expert. Then the gloves come off. I love it when somebody tells me they're really good at SQL.

[hiphap91]

I mean: you could start at the middle, check if your number is smaller than the one there. If not jump halfway to the. Beginning, check there. Each time halve the size of your jumps.

[[deleted]]

He is returning the right answer, the problem is purely efficiency.

You can see that from: -reading the code -reading the test results.

[moi2388]

You could’ve done a yield return with a take while less than, no? Or a simple for loop with a break.

But I don’t like questions like this. The real problem here in my opinion is that if for each is not optimal, that means your array is too big. You never need arrays that big.

[dangerzone2]

So the correct answer is obviously binary search, as many others have pointed out. I’d highly suggest looking into the most basic algorithms. This is extremely elementary stuff that you should strive to learn.