₦airaland Forum

Yep you do need maths, how much maths depends on what you want to specialize in. The best programmers I've met are good at maths even though some don't really enjoy it. Generally the more maths you know the better, especially when things like DSA and discrete maths come into play, and these are the backbones of really good programmers.
You'll here a lot of folks talk about logical thinking, thing is there is no way you can be good at logical thinking and be bad at maths, even if you don't like maths.
The good news is you can still learn maths, especially the fundamentals. I'll recommend Khanacademy.

GREATIGBOMAN:
Basic challenge for beginners

Fine if that's how you see it.

excanny:
Did it in C#. I put the data into a hashmap, ordered the values and put the keys back into as a new sorted array. But space complexicity was crazy. Had to initiate about 3 memory allocations. What's the expected time and space complexity for the problem?

The expected time and space complexity are both O(n). My approach is almost same as yours, I did only 2 memory allocations though. Nice one .

GREATIGBOMAN:
Oh shoot

Just saw that now lol.
That was have happened when I tried pasting on nairaland.
I've modified

Noted.

For those interested, here's my code.

So a beginner in one of the coding communities I'm in posted this mini-project description. Unsurprisingly he was looking for help, I think It's from one of those high profile introductory computer science courses.
Normally a project like this would be basic for me, I decided to make things a bit more involving by trying to code it fast as I could, and time it.

If you're interested, these are the challenge rules;
# I'll post the project description. Do not read the project description for now, skimming is ok.
# Make a "5_letter_words.txt" file and type in some random 5 letter words. Do not time this.
# Open your code editor and start the timer. Time all these only; Reading project description, Coding, Testing and debugging.

I finished in about 26 minutes, let's see if you can beat that .

GREATIGBOMAN:
I didn't I didn't want to create a duplicate array hence why I used short hand

I think sorting in JavaScript in an in place operation, e.g;
// arr.sort();
I may be wrong though.

Chuukwudi:

import collections
def SortMe(lst):
	counts = collections.Counter(lst)
	return set(sorted(lst, key=lambda x: -counts[x]))

Your solution is incorrect, does not pass the test cases, take a look at the description, you must've missed something.

gistray:
i forgot his question, just strolled back and decide to continue short solution lol.... i didnt care for time complexity or anything.

function SortArrayFrequency(arr){

// set number to one
var num = 1
let finalArray=[]
let arrayByFrequency = []

// auto sorting given array & Iterate through;
arr.sort();
for(let i=0; i<arr.length; i++){

// if next sorted array item matches previous add 1 to num;
if(arr[i]==arr[i+1]){
num++
}
else{
//else push the item to sorted array by frequecy and set num back to 1
arrayByFrequency.push([arr[i],num])
num=1
}
}

// Now sort arrayByfrequecy, reverse it and then add to final array and return
arrayByFrequency.sort(function(a, b) {
return a[1] - b[1];
}).reverse().forEach((item)=>{
finalArray.push(item[0])
})
return finalArray

}

SortArrayFrequency([1,2,6,2,3,7,7,5,7,6,2,7])
(6) [7, 2, 6, 5, 3, 1]

Works well, time complexity of O(n log n), nice one.
You should've sort the array outside the for loop though.

Ever since I took the redpill, the word "crush" no longer exists in my dictionary. IMO, It's Ok to admire some girls here and there, but having a crush on girl, that's simply simping.

fattprince:
Bros!!!! It's been agreed never to quote her. Trust me she's dumber than she sounds even as she sound dumb.

Noted.

MJBOLT:

A simp and his money are soon....... abeg complete am

Y'all should stop engaging trolls you can always read and ignore @ namikaze

Noted sire.

Tranquility2345:
Please how is this a win for all men Will you get a cent from the settlement? Why do Nigerians leave their third world problems and concern themselves with problems of developed countries that are totally not applicable to their lives? I just don’t get it…

Must a win be about money?
What is you yourself doing about these "third world" problems?I'd like to know.

DieRich5:
yes ooo and she's paying $13 millions on top it

I just hope this act send a great message to those female who's trying to shit a man's life

Yeah, pretty sure he doesn't care much about the money, though some extra won't hurt lol.
This is a win for all men, and them feminists must be if sifia pains right now, I like it.

omohayek:
God, you're dumber than a post! This "typical Nigerian" has turned down offers by the very......garbage

Bye bye.

omohayek:
You couldn't have made a dumber reply if you tried. How exactly are you going to output the "array sorted by the frequencies of it's [sic] elements" without sorting the frequencies, which is exactly what I said? Given your lack of English comprehension skills, it's no wonder a trivial question like this would strike you as the sort of thing a "senior software developer" would be asked as anything more than a screener.

Ah shit here we go again, typical Nigerian, you said "it's precisely those frequencies that you want to output in reverse-sorted order", which doesn't apply in the context of this problem. Like I said, you're a typical Nigerian, take your frustrations elsewhere.

salvationproject:
Looks simple but demands some kinda deep thinking... Here is the solution in JavaScript,

function sort(arr){
let pre_sorted_arr = {}, sorted_arr = [];
for (i = 0; i < arr.length; i++){
if (pre_sorted_arr[arr[i]] === undefined)
{
pre_sorted_arr[arr[i]] = 1;
}
else
{
pre_sorted_arr[arr[i]] += 1;
}
}

while (Object.keys(pre_sorted_arr).length > 0)
{
for (x in pre_sorted_arr)
{
let j = 1;
for (i in pre_sorted_arr)
{
if (pre_sorted_arr[x] != pre_sorted_arr[i] && pre_sorted_arr[x] < pre_sorted_arr[i])
{
j = 0;
}
}
if (j == 1)
{
sorted_arr.push(x);
delete pre_sorted_arr[x];
}
}
}

return sorted_arr;
}

alert(sort([1,2,6,2,3,7,7,5,7,6,2,7])); //OUTPUTS: 7,2,6,1,3,5

Works well, nice one, do you mind explaining your approach?

omohayek:
I disagree. There's no point sorting the array before counting the frequencies, as it's precisely those frequencies that you want to output in reverse-sorted order. Why do two sorts when you only need one? Scanning through all the items and putting them in the hashtable takes O(n) time, while the sort of the counts at the end will take O(n log n) time, but now the n is a much smaller value.

In any case, this sort of trivial question is not the sort of thing one should expect when applying for a "senior developer" position. At best it's useful as a means of weeding out the totally hopeless before wasting any time giving them personal interviews. This is just a slightly fancier "FizzBuzz" question.

Nope it's not the frequencies, it's the input array sorted by the frequencies of it's elements, you missed the whole point of the question, so he's not wrong.

Deicide:
That would not be difficult for you to do ryt? Cause the answer already shows in the key, I don't have strength for extra steps

Yeah it's in the keys but it's not as straightforward as you make it seem. It is not me you will torture with C++ , the lord shall be your strength lol.

MeMiTi:
Sorting will take nlogn time and priority queue will also take nlogn time since every insertion and deletion takes logn.

I think this might be the best solution, since you'll have to sort it one way or the other.

Yeah for the priority queue approach it's O(n log n), however it's not strictly O(n log n) for the other one.
In the worst case where all input array elements are unique then we'd be sorting an array of size n, so nlogn. The best case would be an input array of the same element then we'd be sorting an array of size 1, so O(n).
On average the input array would consist of both unique and repeated numbers, mostly repeated numbers, so we assume a time complexity of O(n) amortized.

Deicide:
did you include the required library?

#include <iostream>
#include <functional>
#include <unordered_map>
using namespace std;

You also have to be on c++ 17 + to run the code.

Now it compiles, but the output is just a key - value pair of numbers and counts, you'd have to return an array/vector that satisfies the problem description.

JoyousFurnitire:

 const numArr : number[] = [1,2,6,2,3,7,7,5,7,6,2,7];

 const reNumArr : number[] = [...new Set(numArr.reverse())];

 console.log(reNumArr);
 

^^^ This doesn't check most repeated.

Well It should check the repetition, that's what the question is really about.

Deicide:
Sort the Array in descending number first, then use unordered_map to prevent resorting.

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  vector<int> temp = {1,2,6,2,3,7,7,5,7,6,2,7};
  sort(begin(temp), end(temp), greater<>());
  unordered_map<int, int> freq;
  for(auto i : temp) ++freq[i];
  for(auto[key,value] : freq) cout<<key<<" -> "<<value<<endl;
}

@seun abeg add beta code format feature for this Nairaland.

It did not compile, plus output should be an array.

stanliwise:
Stop playing petty tricks. You’re the “senior developer” that can’t solve it

What tricks? there's a source up there bro if you want to verify. I'm only posting this cause I and others in the group were able to solve what a supposed "senior" developer a member interviewed could not, I'm still a junior myself.

Grandlord:
What were the time and space complexities of your solution?

The space complexity would be 0(n).
The time complexity is a little bit different, in the worst case scenario, i.e where all array elements are unique, it would be O(n log n) since we're sorting the key-value pairs, but it could also be O(n) if the inputs are mostly duplicates.

tensazangetsu20:
The second one is actually easy to do in JavaScript you should call object.entries on the object and you can then sort and push those elements to a new array.

Yeah this is what I did in my solution, though there's no "Object.entries" in python, nice.

Grandlord:
Sure a map can't be directly sorted. What I meant was sorting it's keys/counts extracted into an ArrayList.

Oh my bad, this was my approach too.

Grandlord:
Sort the map based on the keys. Then proceed to extract corresponding values into the output array, in that order.

This should work, but a map cannot be sorted, we would have to use some sort of ordered map.

tensazangetsu20:
Oh yeah that's true I thought it was duplicates getting removed. Well with each element in the map. We would need to create a form of queue and then push to that queue from largest count to the lowest count and we can sort that address issue.

Exactly, a priority queue would work here, we use the counts of the numbers as the priority and so the numbers with the highest priorities gets dequeued first.
We could also create a value-key pair from the hashmap and store in an array,i.e [[3,7], [2,2], [2, 6]...] and sort the array in descending order, finally we iterate through this array and push the second element of each array element into a new array.

tensazangetsu20:
Just use a hashmap. If the elements in the array are more than once increase the count on the hashmap to 2. Loop through the map and then push to a new array the elements that have a count of more than 1.

This addresses the first part of the problem only, remember, even elements with a count of 1 should be in the output array, also hashmaps are not ordered by default so you'd have to address that too.

Deicide:
Who is the senior software developer? Make Una stop to day lie

Take a look at the source. Fair enough any developer interviewing for a senior role would simply be a senior in that context.