Java Code optimization- running out of time | Together Java | Page 1

orchid orioleBOT Dec 12, 2023, 6:37 PM

#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#

In order to optimize the code and improve its performance, you can consider the following suggestions:

Use more efficient data structures: Instead of using ArrayLists, consider using more efficient data structures such as LinkedList or HashSet, depending on your specific requirements. These data structures can provide faster insertion and retrieval times.
Preallocate ArrayList capacity: If you know the expected size of your ArrayLists in advance, use the ArrayList(int initialCapacity) constructor to preallocate memory for the lists. This can help avoid unnecessary resizing operations during insertion.
Use enhanced for loop: Instead of using traditional for loops with index variables, use enhanced for loops (also known as "for-each" loops) when iterating over collections. This can provide better performance and cleaner code.
Avoid unnecessary object creation: Be mindful of creating unnecessary objects within loops or methods that are called frequently. For example, if you don't need to modify the elements in your ArrayLists, consider using an immutable collection like Collections.unmodifiableList() instead.
Consider parallel processing: If your code allows it, consider using parallel processing techniques such as Java 8's parallel streams or multi-threading to process the ArrayLists concurrently. This can help leverage multiple CPU cores and improve overall performance.
Profile your code: Use a profiler tool to identify any bottlenecks or areas of improvement in your code. Profiling will help you pinpoint specific methods or operations that are consuming excessive time or resources.

Remember that optimization is a trade-off between speed and readability/maintainability of the code. Make sure to measure and test the performance improvements after implementing these suggestions to ensure they have a positive impact on your specific use case.

obtuse oasis Dec 12, 2023, 6:39 PM

#

I need help to optimise the code as this code is not passing the test cases, it is taking too long with larger data set.

Especially, I have 2 ArrayLists area and price which needs to be sent to a method (called isOutlier). However, before sending both the lists, I want to remove its first element and then send. In the second iteration, I want the first elements back in both the lists and this time I want to remove the second elements from both and then send. In the third iteration, I want the first two elements intact and I want to remove the third element and so on. That is why I have made a copy of the lists. But I think, making a copy in every iteration is using too much time.

Please please help me in optimising this code, the timer is running.

#

📎 message.txt

vital spruce Dec 12, 2023, 6:46 PM

#

"the timer is running"

#

What timer

obtuse oasis Dec 12, 2023, 6:47 PM

#

I have to submit this code

vital spruce Dec 12, 2023, 6:47 PM

#

When

obtuse oasis Dec 12, 2023, 6:47 PM

#

within 1 hour

vital spruce Dec 12, 2023, 6:48 PM

#

Is this an interview screening?

#

Or a school assignment

#

Also I'm maybe 15 minutes from my laptop

obtuse oasis Dec 12, 2023, 6:48 PM

#

there are 3 test hidden cases remaining which are not passing

#

school assignmnet

#

because of the optimisation, the compiler is stopping the code and I cant even see if the output is correct or not

#

rest 5 test cases have passed, so maybe if it is optimised

#

please help please

crisp pike Dec 12, 2023, 6:55 PM

#

obtuse oasis I need help to optimise the code as this code is not passing the test cases, it ...

So, u need what to be specific?

#

and try to code clean spoderman

strong glen Dec 12, 2023, 6:56 PM

#

so given a list of 10 elements, the first loop you want elements 2-10, 2nd time 1, 3-10, 3th time 1,2,4-10, ... ?

obtuse oasis Dec 12, 2023, 6:57 PM

#

strong glen so given a list of 10 elements, the first loop you want elements 2-10, 2nd time ...

yes exactly

#

I need to use some kind of efficient data structure for it

obtuse oasis Dec 12, 2023, 6:57 PM

#

crisp pike and try to code clean <:spoderman:910430588291407922>

Sorry

crisp pike Dec 12, 2023, 6:57 PM

#

ohh

#

u can just ignore that index

#

rather than copying into new

obtuse oasis Dec 12, 2023, 6:58 PM

#

Also, in general,(not only that removing number problem) the code needs to perform faster

crisp pike Dec 12, 2023, 6:59 PM

#

just pass the index into the func and skip it

#

can u share me full code and ur input, so i can debug it out?

#

and see where it taking much time

obtuse oasis Dec 12, 2023, 6:59 PM

#

that is the full code

crisp pike Dec 12, 2023, 7:00 PM

#

there is no main func?

obtuse oasis Dec 12, 2023, 7:00 PM

#

I dont have to edit the main part of the code, I can only edit the method

crisp pike Dec 12, 2023, 7:00 PM

#

gotcha

#

can u give me any input?

obtuse oasis Dec 12, 2023, 7:00 PM

#

wait I'll share the question

#

A real estate agent is advising a seller on the price to ask for a home. To do this, the agent will look at homes that have sold in the area and base the valuation on this data. The only factors that will be considered are square footage and sale price.
The agent starts by removing any outliers from the list of comparable homes. To determine the outliers:
• Select the home to test.
• Create a list of prices of other homes of the same size. It will be called compList in the examples.
• If there are no other homes of the same size, the house being tested is not an butlier.
• Otherwise:
• Calculate the mean price, P[m], and the standard deviation, o, for the homes compList.
° If | price[i] - P[m ]/ > 3 * o, the house is an outlier.

#

so, when I select a home to test for outlier, I dont have to consider that home, that is why I need to remove it from the list

crisp pike Dec 12, 2023, 7:02 PM

#

is there any link to check this problem online?

obtuse oasis Dec 12, 2023, 7:02 PM

#

No

#

I tried

crisp pike Dec 12, 2023, 7:03 PM

#

no input too?

#

is there any example to understand?

obtuse oasis Dec 12, 2023, 7:03 PM

#

yes, input I'll give

#

yes

#

1 minute

#

WhatsApp_Image_2023-12-13_at_00.34.32_3a634824.jpg

#

this is the example

#

the logic of the code is correct, but all the copying and removing is making it slow

crisp pike Dec 12, 2023, 7:07 PM

#

got it now

obtuse oasis Dec 12, 2023, 7:07 PM

#

please help me optimise it then

crisp pike Dec 12, 2023, 7:09 PM

#

give me some mins, lemme see if i can see anything

obtuse oasis Dec 12, 2023, 7:09 PM

#

sure

strong glen Dec 12, 2023, 7:09 PM

#

you could use a stream, and filter it based on the index

obtuse oasis Dec 12, 2023, 7:09 PM

#

how

#

but stream is also not very efficient, right?

crisp pike Dec 12, 2023, 7:12 PM

#

obtuse oasis A real estate agent is advising a seller on the price to ask for a home. To do t...

let say, we got the outliers, then?

#

nvm, i will just optimize this part of urs

strong glen Dec 12, 2023, 7:17 PM

#

Based on the question it also sounds like you don't need to remove a single element, but rather fetch houses of the same size?

obtuse oasis Dec 12, 2023, 7:17 PM

#

yes

#

that is what I'm doing in the isOuliers method

#

if there are 3 houses of 1200 area, of prices 15k, 16k and 17k respectively. When considering the first house, I need the 16k and 17k house. When considering the second house, i need the 15k and 17k house. but the problem is that prices are in different arraylist

crisp pike Dec 12, 2023, 7:20 PM

#

obtuse oasis that is what I'm doing in the isOuliers method

I don't know but ur code is giving different output for same thing peepo_java

obtuse oasis Dec 12, 2023, 7:21 PM

#

no, no it is working as intended

#

in the outliers method, it is only adding those houses as need, according to the example

#

need to find a better way of doing it

#

sorry for being nagging but please please hurry please

strong glen Dec 12, 2023, 7:25 PM

#

you should use area.get(i).equals(currentArea) by the way. You're using Long and not long.

crisp pike Dec 12, 2023, 7:26 PM

#

just optimizied a little, not much

📎 message.txt

orchid orioleBOT Dec 12, 2023, 7:26 PM

#

crisp pike just optimizied a little, not much

I uploaded your attachments as Gist.

obtuse oasis Dec 12, 2023, 7:27 PM

#

strong glen you should use area.get(i).equals(currentArea) by the way. You're using Long and...

corrected

obtuse oasis Dec 12, 2023, 7:30 PM

#

crisp pike just optimizied a little, not much

done the correction, but the code is still not passing the test case

#

😭

crisp pike Dec 12, 2023, 7:32 PM

#

wait, i can do more

#

this is it, i don't understand anything in if-else structure

orchid orioleBOT Dec 12, 2023, 7:34 PM

#

crisp pike this is it, i don't understand anything in if-else structure

I uploaded your attachments as Gist.

obtuse oasis Dec 12, 2023, 7:35 PM

#

still exceeding the time😭

crisp pike Dec 12, 2023, 7:36 PM

#

wow then, what u did after storing outliers?

obtuse oasis Dec 12, 2023, 7:36 PM

#

should I send the second half of the question?

crisp pike Dec 12, 2023, 7:36 PM

#

obtuse oasis should I send the second half of the question?

peepo_sad

#

yup and how much time remains?

#

u used many streams to calc something, which can be done inside any prev loops

obtuse oasis Dec 12, 2023, 7:38 PM

#

After removing outliers, The valuation is then calculated against the resulting list using the following:
If there are no houses in the list, use 1000 per square foot as the price.
• If there is only 1 house in the list, its square foot price is used.
• If there are 1 or more houses in the list with the exact square footage of the house to price, use the mean of those prices.
• If the required square footage is between the square footage of two houses in the list, interpolate the square foot price using the means of the closest higher, and

#

the required square footage is outside of the range of houses listed, extrapolate the price based on the means of the two square footage values that are closest to the home to value.In all cases, if the final price is less than 1000 or greater than 10^6, the price will be 103 and 106 , respectively. For any square footage, the square foot price is the mean of the prices at that square footage. Return an integer that represents the valuation of the seller's house.
For example, there are n = 6 houses with area = [1200, 1300, 1250, 1300, 1200,
2000], price = [12000, 24000, 14000, 22000, 13000, 30000] and the house to value has reqArea = 1500 square feet. The following table shows the test for.The 1300 square foot houses are both outliers, so they are discarded. The new
arrays are area' = [1200, 1200, 1200, 2000] and price' = [12000, 14000, 13000,
30000]. Interpolate the price between the two house sizes remaining. The interpolated price is 13000 + (30000 - 13000)/(2000-1200) * (1500-1200) =
19375.

crisp pike Dec 12, 2023, 7:38 PM

#

newArea.contains(reqArea)
You used this which is itself O(N)
u could have used set to do it in O(1)

#

there can be many optimizations possible

#

Now, if i change it to a hashset, i need to change it everywhere peepo_sad

obtuse oasis Dec 12, 2023, 7:40 PM

#

this is the entire question

obtuse oasis Dec 12, 2023, 7:41 PM

#

crisp pike ```newArea.contains(reqArea)``` You used this which is itself O(N) u could have ...

how O(1)?

crisp pike Dec 12, 2023, 7:41 PM

#

for(long val: newArea) if((secondMax<val) && (val<max)) secondMax=val;
Same here, u are looping around for calc secondMax, which could be calc in O(1) above

obtuse oasis Dec 12, 2023, 7:41 PM

#

crisp pike Now, if i change it to a hashset, i need to change it everywhere <:peepo_sad:871...

please do it😭

crisp pike Dec 12, 2023, 7:41 PM

#

obtuse oasis how O(1)?

set finds element in O(1)

#

u used list, which takes O(N) to find an element

obtuse oasis Dec 12, 2023, 7:42 PM

#

please do in sets😭

#

the main area and price will remain in Arraylist

#

please optimise it as much as possible, the last three test cases are not passing😭

crisp pike Dec 12, 2023, 7:48 PM

#

obtuse oasis please optimise it as much as possible, the last three test cases are not passin...

do u have input of those cases?

#

I am trying, there is so much to do thisisfine

#

            long closestMax=newArea.stream().filter(val->val>reqArea).min(Comparator.comparingLong(val->Math.abs(reqArea-val))).orElseThrow(NoSuchElementException::new);```

#

What is these two lines doing? can u explain it

obtuse oasis Dec 12, 2023, 7:49 PM

#

WhatsApp_Image_2023-12-13_at_01.19.17_2f34ce63.jpg

crisp pike Dec 12, 2023, 7:50 PM

#

ohh nearest ones

obtuse oasis Dec 12, 2023, 7:51 PM

#

crisp pike What is these two lines doing? can u explain it

for interpolation, I need to find the closest minimum and closest maximum value. for example the area[] is [1000, 1200, 1400, 1700, 2000] and the required area is 1500. Then closest minimum will give 1400 and closest maximum will give 1700

#

I also have loop for closest min and max, but I thought streams was efficient

#

for(int i=0; i< n; i++){
long val=newArea.get(i);
// long difference= Math.abs(reqArea-val);
if ((val< reqArea)&&((Math.abs(reqArea-val))< Math.abs(reqArea-closestMin))){
closestMin=val;
}
else if ((val>reqArea)&&(Math.abs(reqArea-val))< Math.abs(reqArea-closestMax)){
closestMax=val;
}

strong glen Dec 12, 2023, 7:52 PM

#

you're also looping an awfull lot over newArea

#

so maybe see if you can optimize that a bit

#

you could also set up a map<Long, List<Long>> <= where the key is area, and the latter is the list of prices

crisp pike Dec 12, 2023, 7:56 PM

#

obtuse oasis for interpolation, I need to find the closest minimum and closest maximum value....

Try this out, if not works, I have one more place to optimize

📎 message.txt

orchid orioleBOT Dec 12, 2023, 7:56 PM

#

crisp pike Try this out, if not works, I have one more place to optimize

I uploaded your attachments as Gist.

obtuse oasis Dec 12, 2023, 7:57 PM

#

give me 2 mins to implement and run the code

strong glen Dec 12, 2023, 7:57 PM

#

Also just a tip since I see a decent bit of min/maxing. As of Java 21 there's a Math.clamp function

crisp pike Dec 12, 2023, 7:58 PM

#

I am still running java 17 lol peepo_christ

#

can u give me constraints of the problem @obtuse oasis ??

#

is it more than 10^4 ?

#

I optimized it to run in O(N^2) now i guess, running it in lower complexing needs time to think then and its 2 am for me thisisfine

obtuse oasis Dec 12, 2023, 8:03 PM

#

WhatsApp_Image_2023-12-13_at_01.33.29_6a025d22.jpg

crisp pike Dec 12, 2023, 8:04 PM

#

obtuse oasis

bro, then this will not work, we need to do in O(N) or O(NlogN)

obtuse oasis Dec 12, 2023, 8:04 PM

#

oh

#

I'm sorry for troubling you so much

crisp pike Dec 12, 2023, 8:04 PM

#

I can do that, but I am not in my mind cause its midnight

obtuse oasis Dec 12, 2023, 8:05 PM

#

please

#

please

#

do it

#

it will take a couple of minutes for you

#

please

crisp pike Dec 12, 2023, 8:05 PM

#

obtuse oasis it will take a couple of minutes for you

nope peepo_sad

#

if i can somehow make outlier check func to be O(1), its solved

#

but the Q is... how?

obtuse oasis Dec 12, 2023, 8:07 PM

#

I tried my best to do it and you did a better job in 20 mins

crisp pike Dec 12, 2023, 8:07 PM

#

need to do some maths

#

long sd= Math.round(Math.sqrt(complist.stream().mapToDouble(val->Math.pow(val-mean,2)).sum()/(complist.size())));
Can u optimize it somehow, i will try other looop

obtuse oasis Dec 12, 2023, 8:08 PM

#

yes

crisp pike Dec 12, 2023, 8:09 PM

#

i will reduce mean

obtuse oasis Dec 12, 2023, 8:11 PM

#

private static long computeSd(List<Long> data) {
double sum = 0.0;
long mean = computeMean(data);

for (long val : data) {
    sum = sum + Math.pow(val - mean, 2);
}
return Math.round(Math.sqrt(sum / data.size()));

}

#

instead of calling the mean method, passing the value of mean would be better

crisp pike Dec 12, 2023, 8:11 PM

#

u need to implement it in O(1) for one

#

or O(N) for all

obtuse oasis Dec 12, 2023, 8:13 PM

#

but standard deviation will always be O(N)

#

yeah, that's what

obtuse oasis Dec 12, 2023, 8:15 PM

#

obtuse oasis private static long computeSd(List<Long> data) { double sum = 0.0; long ...

This is O(N)

crisp pike Dec 12, 2023, 8:17 PM

#

obtuse oasis This is O(N)

yeah

obtuse oasis Dec 12, 2023, 8:18 PM

#

crisp pike Try this out, if not works, I have one more place to optimize

what is distA and distB in this?

crisp pike Dec 12, 2023, 8:18 PM

#

but its giving O(N) for one value of list right, so for N values, there will be O(N*N) time

obtuse oasis Dec 12, 2023, 8:22 PM

#

crisp pike but its giving O(N) for one value of list right, so for N values, there will be ...

right

strong glen Dec 12, 2023, 8:23 PM

#

and this also doesn't help size wise: long closestMin=newArea.stream().filter(val->val<reqArea).min(Comparator.comparingLong(val->Math.abs(reqArea-val))).orElseThrow(NoSuchElementException::new);
long closestMax=newArea.stream().filter(val->val>reqArea).min(Comparator.comparingLong(val->Math.abs(reqArea-val))).orElseThrow(NoSuchElementException::new);

#

but also a tad late for me to rewrite that section

#

but try to reduce the amount of times you loop through your collections, try to group a bit. And indeed some things could be sets/hashmaps

obtuse oasis Dec 12, 2023, 8:25 PM

#

I'm trying to implement the code you sent last @crisp pike

#

and both distA and distB are not initialised, should I initialise them with MAX_VALUE?

crisp pike Dec 12, 2023, 8:26 PM

#

obtuse oasis and both distA and distB are not initialised, should I initialise them with MAX_...

i did that i guess

obtuse oasis Dec 12, 2023, 8:26 PM

#

oh yeah, sorry

crisp pike Dec 12, 2023, 8:29 PM

#


        Map<Long, Integer> map = new HashMap<>();
        Map<Long, Long> prices = new HashMap<>();

        for(int i=0; i<size; ++i) {
            map.put(area.get(i), map.getOrDefault(area.get(i), 0)+1);
            prices.put(area.get(i), prices.getOrDefault(area.get(i), 0L) + price.get(i));
        }

        for(int i=0; i<size; ++i)
            mean[i] = map.get(area.get(i)) == 1 ? 0 : Math.round((prices.get(area.get(i)) - price.get(i)) / (map.get(area.get(i))-1));```

orchid orioleBOT Dec 12, 2023, 8:29 PM

#

crisp pike ```long[] mean = new long[size]; Map<Long, Integer> map = new HashMap<>...

Detected code, here are some useful tools:

crisp pike Dec 12, 2023, 8:29 PM

#

I implemented and calc all mean in O(N) like this

#

now need to think about standard deviation

obtuse oasis Dec 12, 2023, 8:31 PM

#

ok

obtuse oasis Dec 12, 2023, 8:32 PM

#

crisp pike Try this out, if not works, I have one more place to optimize

this code failed 1 test case which was passing earlier

#

we are keeping the outlier method same?

obtuse oasis Dec 12, 2023, 8:34 PM

#

crisp pike ```long[] mean = new long[size]; Map<Long, Integer> map = new HashMap<>...

where will this code go?

crisp pike Dec 12, 2023, 8:35 PM

#

obtuse oasis where will this code go?

below distA and distB, but this is of no use if i can't find variance faster

#

my mind is not working peepo_sad

obtuse oasis Dec 12, 2023, 8:35 PM

#

please😭

crisp pike Dec 12, 2023, 8:35 PM

#

obtuse oasis this code failed 1 test case which was passing earlier

are u sure, I did not changed any logic?

obtuse oasis Dec 12, 2023, 8:36 PM

#

crisp pike are u sure, I did not changed any logic?

yes, you dont worry about logic, I will handle that, but please optimise the code

crisp pike Dec 12, 2023, 8:36 PM

#

i am thinking of optimizing the sd

#

but

#

mean is working good, i checked but sd .................... howwww peepoG

obtuse oasis Dec 12, 2023, 8:37 PM

#

I dont know😭 😭

#

I'll have a look at the logic

#

I got where the logic wrong

#

if the homes are of exact same area, we have to take mean of that

#

else if(newArea.contains(reqArea)){
// int c=0;
// double sum=0;
// for(int i=0; i<n;i++){
// if(newArea.get(i)==reqArea){
// c++;
// sum+= (newPrice.get(i));
// }
// }
// return Math.max(1000, Math.min(1000000, Math.round(sum/c)));
// }

#

this one

#

got that 1 test case back, but the three optimisation one's are still there😭 😭

#

@crisp pike

crisp pike Dec 12, 2023, 8:42 PM

#

i am trying to think but its 2:30 am now -_-

obtuse oasis Dec 12, 2023, 8:43 PM

#

please

#

please

#

please

#

only standard deviation for O(N) is left?

#

we are not making any changes to isOutlier method?

crisp pike Dec 12, 2023, 8:46 PM

#

obtuse oasis we are not making any changes to isOutlier method?

I am trying to come up with something

obtuse oasis Dec 12, 2023, 8:46 PM

#

okay, I'm waiting

crisp pike Dec 12, 2023, 8:52 PM

#

got an idea, lets test it

obtuse oasis Dec 12, 2023, 8:52 PM

#

yayyy

#

came up with something?

crisp pike Dec 12, 2023, 9:06 PM

#

obtuse oasis came up with something?

umm yeah

#

check this out!

📎 message.txt

orchid orioleBOT Dec 12, 2023, 9:06 PM

#

crisp pike check this out!

I uploaded your attachments as Gist.

crisp pike Dec 12, 2023, 9:06 PM

#

it should run in O(N)

#

i optimized the isOutlier() method to run in O(1)

obtuse oasis Dec 12, 2023, 9:07 PM

#

let me try and run it

crisp pike Dec 12, 2023, 9:07 PM

#

obtuse oasis got that 1 test case back, but the three optimisation one's are still there😭 😭

u can get that test case back

#

I don't think, there should be time problem now thisisfine

obtuse oasis Dec 12, 2023, 9:08 PM

#

just wait 5 mins

#

please

crisp pike Dec 12, 2023, 9:10 PM

#

There can be a wrong answer, but not time limit if i am right, optimized it too much!
I even ask, why ur school assignment needs too much of cleansing of code?

#

if this gives tle, I am ded for sure

obtuse oasis Dec 12, 2023, 9:13 PM

#

is there a 0L in the second line of first for loop of the program?

crisp pike Dec 12, 2023, 9:13 PM

#

yeah

#

second* loop

#

umm, imma go sleep now 🙂

obtuse oasis Dec 12, 2023, 9:21 PM

#

no no

#

wait

#

2 mins

#

I'm getting some small errors

#

let me run at altest once

#

please

crisp pike Dec 12, 2023, 9:23 PM

#

this won't give u tle, maybe wrong answer if i changed any logic in between, that u can change, like i removed round from mean and sd, u can do that

obtuse oasis Dec 12, 2023, 9:23 PM

#

wait

#

it says

#

method outlier cannot be aplied to given types

#

Oh i made a mistake

#

please stay up for 2 more mins

#

yes

#

wrong output

#

but no ttle

#

but idk anything about this code

#

how do i debug????

#

still 3 test cases remaining😭

#

@crisp pike

#

help me 1 last time

crisp pike Dec 12, 2023, 9:28 PM

#

obtuse oasis but no ttle

yup, We take it from O(n^3) to O(n)

#

so no tle

obtuse oasis Dec 12, 2023, 9:29 PM

#

there are 2 error in interpolation

#

@crisp pike

#

please help me one last time, i would have debug, but I dont understand the map part

#

or at least explain it to me, so I can debug

crisp pike Dec 12, 2023, 9:38 PM

#

obtuse oasis <@771765487797141504>

wait 5 mins

obtuse oasis Dec 12, 2023, 9:38 PM

#

sure

#

One of the test cases failing is not hidden, its this one

WhatsApp_Image_2023-12-13_at_03.09.40_dcbb5cca.jpg

#

the expected output is 30625, but the output is 31667

#

How do I find the complist ?

crisp pike Dec 12, 2023, 9:51 PM

#

try this one

📎 message.txt

orchid orioleBOT Dec 12, 2023, 9:51 PM

#

crisp pike try this one

I uploaded your attachments as Gist.

obtuse oasis Dec 12, 2023, 9:51 PM

#

okay

#

give me 2 mins

crisp pike Dec 12, 2023, 9:52 PM

#

obtuse oasis One of the test cases failing is not hidden, its this one

this is right answer on my latest one

crisp pike Dec 12, 2023, 9:52 PM

#

crisp pike try this one

right on this one

obtuse oasis Dec 12, 2023, 9:52 PM

#

fingers crossed

crisp pike Dec 12, 2023, 9:53 PM

#

if it works or does not works, I am going to sleep peepo_sad

obtuse oasis Dec 12, 2023, 9:54 PM

#

wait for 2 mins

crisp pike Dec 12, 2023, 9:56 PM

#

I shut my laptop down peepo_comfy

#

It's 3:26 am fat_laugh

obtuse oasis Dec 12, 2023, 9:58 PM

#

nooo

#

1 more min just

#

its doneeeeee

#

yayyyyyyyyy

crisp pike Dec 12, 2023, 9:59 PM

#

Correct?

obtuse oasis Dec 12, 2023, 9:59 PM

#

thank you sooooooo much

#

yeah

crisp pike Dec 12, 2023, 9:59 PM

#

Send me a ss

#

I wanna see

obtuse oasis Dec 12, 2023, 9:59 PM

#

yes

crisp pike Dec 12, 2023, 10:00 PM

#

I will explain this code then tomorrow okay? I will go to sleep u know peepo_heart

obtuse oasis Dec 12, 2023, 10:00 PM

#

WhatsApp_Image_2023-12-13_at_03.29.56_3f55a14e.jpg

#

yeah okay

crisp pike Dec 12, 2023, 10:00 PM

#

obtuse oasis

This is hackerrank peepo_think

obtuse oasis Dec 12, 2023, 10:00 PM

#

you came in the form of an angel please

crisp pike Dec 12, 2023, 10:01 PM

#

U know, the difficulty of this Q is around medium-hard

#

Why ur school needs this?

obtuse oasis Dec 12, 2023, 10:01 PM

#

crisp pike U know, the difficulty of this Q is around medium-hard

I saw

crisp pike Dec 12, 2023, 10:01 PM

#

Difficulty is that because of the optimisation

obtuse oasis Dec 12, 2023, 10:01 PM

#

yes, logic, I had sorted

crisp pike Dec 12, 2023, 10:01 PM

#

We implemented mean and variance in O(1) for every element like bruhh

obtuse oasis Dec 12, 2023, 10:01 PM

#

but optimisation, OMG

#

You're an expert

#

what do you do?

crisp pike Dec 12, 2023, 10:02 PM

#

Yup, ur logic was correct, I did not changed any logic.. nor i understand.. I just optimized lol pepekek

obtuse oasis Dec 12, 2023, 10:03 PM

#

😭 thank you so much

crisp pike Dec 12, 2023, 10:03 PM

#

obtuse oasis what do you do?

I am a student umm

obtuse oasis Dec 12, 2023, 10:03 PM

#

really?

#

where

crisp pike Dec 12, 2023, 10:03 PM

#

In an Asian University

obtuse oasis Dec 12, 2023, 10:04 PM

#

cool

crisp pike Dec 12, 2023, 10:04 PM

#

I guess so lol

obtuse oasis Dec 12, 2023, 10:04 PM

#

Well, thank you soooooooooooo much

crisp pike Dec 12, 2023, 10:04 PM

#

U did not answer my Q tho?

obtuse oasis Dec 12, 2023, 10:04 PM

#

my school?

#

huh

crisp pike Dec 12, 2023, 10:04 PM

#

Why ur school needs u to solve this hard prob?

obtuse oasis Dec 12, 2023, 10:05 PM

#

stupid teacher is challenging

crisp pike Dec 12, 2023, 10:05 PM

#

And are u in school for real? Or university?

obtuse oasis Dec 12, 2023, 10:05 PM

#

he taught big (o) from Sumita Arora book

#

school

#

DPS

crisp pike Dec 12, 2023, 10:06 PM

#

Wait, which country u are from?

obtuse oasis Dec 12, 2023, 10:06 PM

#

India

crisp pike Dec 12, 2023, 10:06 PM

#

obtuse oasis DPS

Wao bro 😂

obtuse oasis Dec 12, 2023, 10:06 PM

#

😂

crisp pike Dec 12, 2023, 10:06 PM

#

U do this stuff in dps ?

obtuse oasis Dec 12, 2023, 10:06 PM

#

what did you think?

crisp pike Dec 12, 2023, 10:06 PM

#

I thought u are like some American guy but u are just local to me

obtuse oasis Dec 12, 2023, 10:06 PM

#

crisp pike U do this stuff in dps ?

we dont do, but for internal marks, teachers make us do weird things

#

where are you from?

#

in india

crisp pike Dec 12, 2023, 10:07 PM

#

U should complain .. this is not a problem for school students

crisp pike Dec 12, 2023, 10:07 PM

#

obtuse oasis where are you from?

Jaipur, rajasthan

obtuse oasis Dec 12, 2023, 10:07 PM

#

crisp pike U should complain .. this is not a problem for school students

exactly !!

#

I think, I'll be the only one to do

crisp pike Dec 12, 2023, 10:07 PM

#

Well, it means this is also close to 4 am for u

#

pepekek

obtuse oasis Dec 12, 2023, 10:08 PM

#

yes

crisp pike Dec 12, 2023, 10:08 PM

#

Good night then peepo_heart

obtuse oasis Dec 12, 2023, 10:08 PM

#

Good night

#

and thanks again

crisp pike Dec 12, 2023, 10:08 PM

#

I will explain the code tomorrow, ping me again on this thread if I forget

obtuse oasis Dec 12, 2023, 10:08 PM

#

oki

#

byeeeeeee

#

thanksssss

crisp pike Dec 12, 2023, 10:09 PM

#

Byee peepo_comfy

#

peepo_heart

orchid orioleBOT Dec 12, 2023, 11:49 PM

#

Closed the thread.

crisp pike Dec 17, 2023, 8:09 AM

#

hey @obtuse oasis

obtuse oasis Dec 17, 2023, 8:10 AM

#

Hey

crisp pike Dec 17, 2023, 8:11 AM

#

here it is

📎 message.txt

orchid orioleBOT Dec 17, 2023, 8:11 AM

#

crisp pike here it is

I uploaded your attachments as Gist.

crisp pike Dec 17, 2023, 8:12 AM

#

So, lets see how i calculated mean without loop

#

at that time, i did many things lol, i need to see ur code first so i can see where i changed stuff lol

#

u did that hmm

📎 message.txt

orchid orioleBOT Dec 17, 2023, 8:14 AM

#

crisp pike u did that hmm

I uploaded your attachments as Gist.

crisp pike Dec 17, 2023, 8:16 AM

#

crisp pike u did that hmm

@obtuse oasis in the part, where u were calc mean in isOutlier function, u looped through array to add values in compList which are same as the currentArea and later sum them

#

So, what u are doing is... u were calc sum of all x num in the list... but not the x itself

#

x + x + x + x + ......... to (n-1) times

#

which can be calculated as x*(n-1) right?

crisp pike Dec 17, 2023, 8:19 AM

#

crisp pike here it is

So, using hashmap named "map" here, i store the freq count of an area, let say, i got from the hashmap thay currentArea came 7 times in the "area" list

obtuse oasis Dec 17, 2023, 8:19 AM

#

yes

#

okay

crisp pike Dec 17, 2023, 8:22 AM

#

In "prices" map, this includes, all the prices of that area came

#

but on "prices" map, any area will contains a list of prices from index 1, and at index 0, it contains all the sum of the total prices in this area

#

        Map<Long, List<Long>> prices = new HashMap<>();

        for(int i=0; i<size; ++i) {

            map.put(area.get(i), map.getOrDefault(area.get(i), 0)+1);

            if(prices.containsKey(area.get(i))) {
                prices.get(area.get(i)).add(price.get(i));
                prices.get(area.get(i)).set(0, prices.get(area.get(i)).get(0) + price.get(i));
            }
            else {
                List<Long> list = new ArrayList<>();
                list.add(price.get(i));
                list.add(price.get(i));

                prices.put(area.get(i), list);
            }
        }```

orchid orioleBOT Dec 17, 2023, 8:23 AM

#

crisp pike ```Map<Long, Integer> map = new HashMap<>(); Map<Long, List<Long>> price...

Detected code, here are some useful tools:

crisp pike Dec 17, 2023, 8:23 AM

#

Here, i am updating frequency or count of an area in "map"

#

and prices also, if it contains, add the new price, also put the current sum of whole on index 0

#

if not contains, make a new list with price of that on index 1, and on index 0, sum of all the prices in that area

#

Now, lets take an example!
area -> price
12 -> 100
13 -> 200
12 -> 300
12 -> 400
14 -> 500

#

Map -> [12, 3], [13, 1], [14, 1]

#

Prices -> [12, [800, 100, 300, 400]], [13, [200, 200]], [14, [500, 500]]

#

did u understand how, these maps filled? @obtuse oasis

#

lets say, for area 12, we need to find mean, then

#

mean = map.get(12) == 1 ? 0 : (prices.get(12).get(0) - (price[12])) / (map.get(12)-1);

#

it means, if the map only has one 12, then it means there are no more 12 other than 12, so out compList is empty and mean is 0

#

and if there is, then,
mean = sumOfAllOther12 / cntOfAllOther12

#

where

#

cntOfAllOther12 = cntOfAll12 - cntOfThis12(1) = 3 - 1 = 2
Hence, mean[0] = 700 / 2 = 350
mean[2] = (800-300)/(3-1) = 250```

orchid orioleBOT Dec 17, 2023, 8:32 AM

#

crisp pike ```sumOfAllOther12 = sumOfAll12 - sumOfThis12 = 800 - 100 = 700 cntOfAllOther12 ...

Detected code, here are some useful tools:

obtuse oasis Dec 17, 2023, 8:32 AM

#

1 min, I'm still trying to understand

crisp pike Dec 17, 2023, 8:33 AM

#

alr, take ur time

#

see example, u will get it, how i calc mean

obtuse oasis Dec 17, 2023, 8:34 AM

#

oki

obtuse oasis Dec 17, 2023, 8:37 AM

#

crisp pike ```Prices -> [12, [800, 100, 300, 400]], [13, [200, 200]], [14, [500, 500]]```

I did not understand this, how is 800 there?

crisp pike Dec 17, 2023, 8:37 AM

#

obtuse oasis I did not understand this, how is 800 there?

prices.get(area.get(i)).set(0, prices.get(area.get(i)).get(0) + price.get(i));

#

Using this, I am updating the sum of all prices for that area at index 0

obtuse oasis Dec 17, 2023, 8:38 AM

#

oh okayyy, and the first element is the sum

crisp pike Dec 17, 2023, 8:38 AM

#

yup!

obtuse oasis Dec 17, 2023, 8:39 AM

#

crisp pike and if there is, then, ```mean = sumOfAllOther12 / cntOfAllOther12```

the use of ternary operator here is so cool

#

okay understood till here

crisp pike Dec 17, 2023, 8:40 AM

#

So, now we can find mean in O(1) for every element of the array right?

obtuse oasis Dec 17, 2023, 8:41 AM

#

yep

#

and the standard deviation

crisp pike Dec 17, 2023, 8:48 AM

#

        
        // if there is only one element, then mean is 0, so this can't be an outlier so, return false, no need to check standard deviation
        if(map.get(currentArea) == 1)
            return false;
        
      // intializing sd and trev ( a variable which checks, if i traversed currentPrice or not, because we won't be adding it)
        double sd = 0;
        boolean trev = false;

        // traversing in map for currentArea (starting with index 1, cause index 0 is sum, not a individual price)
        for(int i = 1; i < prices.get(currentArea).size(); ++i) {
          
            // if i found a match, then put trev to true and we won't be adding it to sd
            if(prices.get(currentArea).get(i) == currentPrice && !trev) {
                trev = true;
                continue;
            }

            // standard deviation = summationOf(x - mean)^2 / n
            sd += Math.pow((prices.get(currentArea).get(i) - mean[index]), 2);
        }
        
        // Later dividing with numberOfN, which is stored in map ( but we are not taking the one with currentPrice, so map value -1 )
        sd /= (map.get(currentArea)-1);
        
        // Now we can check condition for outlier, where mean[index] is already calculated
        return (Math.abs(currentPrice-mean[index]) > (3*Math.sqrt(sd)));
    }```

```summationOf(x - mean)^2/n = ((x1 - mean)^2 + (x2 - mean)^2 + ........ (xn - mean)^2) / n```

orchid orioleBOT Dec 17, 2023, 8:48 AM

#

crisp pike ```private static boolean isOutlier(long currentArea, long currentPrice, int ind...

Detected code, here are some useful tools:

crisp pike Dec 17, 2023, 8:48 AM

#

obtuse oasis and the standard deviation

read this out

#

i change some things too, like u were looping around for calc max and min also second max, which i concluded in above loop

obtuse oasis Dec 17, 2023, 8:57 AM

#

Oki understood !!

#

took some time😅

#

so much for just checking if its an outlier or not

crisp pike Dec 17, 2023, 9:42 AM

#

obtuse oasis so much for just checking if its an outlier or not

yeah, but its optimized 😄

#Java Code optimization- running out of time