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``

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.

Simple stuffz


Remember my days at leetcode.


I just add identical values in the arrays to a new array

Later check the length of each array then form a new array depending on which is longer

Let me solve it without using any array methods

GREATIGBOMAN:
Simple stuffz


Remember my days at leetcode.


I just add identical values in the arrays to a new array

Later check the length of each array then form a new array depending on which is longer

That's an interesting way to look at it, looking forward to your solution.

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

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.

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.

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.

GREATIGBOMAN:
Simple stuffz


Remember my days at leetcode.


I just add identical values in the arrays to a new array

Later check the length of each array then form a new array depending on which is longer

I guess the dictionary or hashmap solution above would be more efficient than this method if you consider space complexity.
Your approach would require creating a new array for every new value but you could just use a
dictionary once and for all.

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.

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.

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.

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

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.

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.

namikaze:

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

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

namikaze:

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.

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.

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.

namikaze:

Oh my bad, this was my approach too.

What were the time and space complexities of your solution?

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:


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.

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.

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``

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

I hate live coding because 70% of real problems are solved through googling.

Even though I must have studied how to do this, I still don't recollect until I google.

---

My TypeScript solution after googling how to reverse an array and eliminate duplicate numbers in array.

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.

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.

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.

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.

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.

Is it possible to solve it in O(n) time?

MeMiTi:

Is it possible to solve it in O(n) time?

Yeah definitely both solutions will run in o(n) time

tensazangetsu20:


Yeah definitely both solutions will run in o(n) time

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:

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

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.

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.

Oh yeah I completely forgot about this. Thanks for the correction.

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.