Relative Sorting — Asked in Google, Microsoft and Visa Interview

Problem Statement :

Given two arrays ‘ARR’ and ‘BRR’ of size ’N’ and ‘M’ respectively. Your task is to sort the elements of ‘ARR’ in such a way that the relative order among the elements will be the same as those are in ‘BRR’. For the elements not present in ‘BRR’, append them in the last in sorted order.

Note:

Elements of ‘BRR’ are non repeating.

Sample Input:

ARR = { 9, 5, 8, 4, 6, 5 } and BRR = { 8, 4, 5 }

Sample Output:

{ 8, 4, 5, 5, 6, 9 }

Approach :

Using a Map

  • The idea is to maintain a map frequencyMap of the elements ARR, for finding the count of occurrences of BRR elements in ARR.
  • Then, for each element of BRR, find its frequency by looking in frequencyMap. Say for any element B its frequency comes out to be A, then add B, A times in the RES array. Also erase the entry corresponding to B from the frequencyMap.
  • After the above step, the frequencyMap contains those elements whose corresponding elements do not lie in BRR. As the map contains elements in sorted order. So we simply iterate the rest of frequencyMap elements, and add them, its frequency times in our RES array.

Time Complexity : O(N*log(N)+M*log(N))
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Things They Don’t Teach Data Scientists

Freight Forwarders Essential for Medical Supplies | Logical Logistics

Datafication: The new oil and driver of progress

Clustering and Collaborative Filtering — Visualizing clusters using t-SNE

How NOT to learn Machine Learning

Analytics and Object Tracking

Logistic Regression and the Feature Scaling Ensemble

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Minimum Moves to Reach Target Score

Eggs and Building Puzzle

Google / Microsoft Interview Question — LeetCode 359

The Blind 75 Leetcode Series: Merge Two Sorted Lists