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.

namikaze:

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.

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.

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

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.

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

namikaze:

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.

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.

namikaze:

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.

omohayek:

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

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]

namikaze:

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

namikaze:
Apparently a senior software developer could not solve this coding interview problem, can you?

Given an array of numbers, list them in the order of most repeated. I.e:
[1,2,6,2,3,7,7,5,7,6,2,7] => [7,2,6,5,3,1]

source: ``https://www./programmer.nullposting/permalink/1456356328162617/?app=fbl``

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

Chuukwudi:

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

GREATIGBOMAN:





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

namikaze:

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

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;



for(let i=0; i<arr.sort().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]

GREATIGBOMAN:
Oh shoot

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

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?

namikaze:

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 .

Deicide:
if you sorting then the time complexity is not O(n)

namikaze:

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.

truthsayer009:


You can use TreeMaps which are ordered, you can also sort the maps after your logic. This problem is an easy one to be fair, if i see this type of problem in an interview. I will be praising the name of the Lord.

namikaze:
My solution:

def sort_by_frequency(arr):
   fmap = {}
   for num in arr:
     fmap[num] = fmap.get(num, 0) + 1
   arr = [ (v,k) for k,v in fmap.items() ]
   arr.sort(reverse=True)
   return [ b for a,b in arr ]

Let's see yours.

a = [1,2,6,2,3,7,7,5,7,6,2,7]
from collections import Counter
list(list(zip(*Counter(a).most_common()))[0])

Guontey:


You can write it in one line of code if you can import Counter

a = [1,2,6,2,3,7,7,5,7,6,2,7]
from collections import Counter
list(list(zip(*Counter(a).most_common()))[0])

obimerchant:
I am really wowed by all this I am seeing here...
really thought I was a good developer but nah....
can't even understand all this things you all are posting here

obimerchant:
I am really wowed by all this I am seeing here...
really thought I was a good developer but nah....
can't even understand all this things you all are posting here