Expedia Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
def sortnums(lst):
output_lst = []
#sort freq using map
freq_map = getFrequency(lst)
#get all values and put in max heap (num and frequency)
max_heap = getMaxHeap(freq_map)
alt_max_heap = []
#pop each item one at a time
if len(max_heap) == 0:
return -1
item = max_heap.pop()
#check if next item has same frequency
while max_heap:
next_item = max_heap[0]
if item[1] == next_item[1]:
heapq.heappush(alt_max_heap, (-item[1], item[0]))
if len(max_heap) == 1:
next_item = heapq.heappop(max_heap)
for i in range(-next_item[0]):
output_lst.append(next_item[1])
else:
item = heapq.heappop(max_heap)
continue
else:
if len(alt_max_heap) > 0:
alt_item = heapq.heappop(alt_max_heap)
for i in range(alt_item[1]):
output_lst.append(-alt_item[0])
else:
reg_item = heapq.heappop(max_heap)
for i in range(-reg_item[0]):
output_lst.append(reg_item[1])
print output_lst
def getFrequency(lst):
freq = {}
for val in lst:
if val in freq:
freq[val] = freq[val]+1
else:
freq[val]=1
return freq
def getMaxHeap(freq_map):
max_heap = []
for key, val in freq_map.items():
heapq.heappush(max_heap,(-val, key))
return max_heap
input=[2,3,5,3,7,9,5,3,7]
sortnums(input)
def sortnums(lst):
output_lst = []
#sort freq using map
freq_map = getFrequency(lst)
#get all values and put in max heap (num and frequency)
max_heap = getMaxHeap(freq_map)
alt_max_heap = []
#pop each item one at a time
if len(max_heap) == 0:
return -1
item = max_heap.pop()
#check if next item has same frequency
while max_heap:
next_item = max_heap[0]
if item[1] == next_item[1]:
heapq.heappush(alt_max_heap, (-item[1], item[0]))
if len(max_heap) == 1:
next_item = heapq.heappop(max_heap)
for i in range(-next_item[0]):
output_lst.append(next_item[1])
else:
item = heapq.heappop(max_heap)
continue
else:
if len(alt_max_heap) > 0:
alt_item = heapq.heappop(alt_max_heap)
for i in range(alt_item[1]):
output_lst.append(-alt_item[0])
else:
reg_item = heapq.heappop(max_heap)
for i in range(-reg_item[0]):
output_lst.append(reg_item[1])
print output_lst
def getFrequency(lst):
freq = {}
for val in lst:
if val in freq:
freq[val] = freq[val]+1
else:
freq[val]=1
return freq
def getMaxHeap(freq_map):
max_heap = []
for key, val in freq_map.items():
heapq.heappush(max_heap,(-val, key))
return max_heap
input=[2,3,5,3,7,9,5,3,7]
sortnums(input)
std::vector<int>
crazy_sort(const std::vector<int> & input)
{
std::vector<int> input_cp(input.size() );
std::partial_sort_copy
(input.begin(),
input.end(),
input_cp.begin(),
input_cp.end() );
//run length encode;
using myPair = std::pair<int,int>;
std::vector<myPair> RLE;
for(auto it = input_cp.begin(); it != input_cp.end(); ){
auto val = *iter;
int count = 0;
while(it != input_cp.end() && *it == val){
++count;
++it
}
RLE.emplace_back(val,count);
}
std::stable_sort(RLE.begin(),
RLE.end(),
[](const myPair& a, const myPair& b)->bool
{
return a.second > b.second;
});
//"un" runlength encode RLE now.
//reuse input_cp;
auto result = &input_cp;
auto it = result.begin();
for(const auto & pr : RLE){
it = std::fill(it, pr.first, pr.second);
}
return result;
}
(zoomba)input=[2,3,5,3,7,9,5,3,7]
@[ 2,3,5,3,7,9,5,3,7 ] // ZArray
(zoomba)ms = mset(input)
{2=1, 3=3, 5=2, 7=2, 9=1} // HashMap
(zoomba)l = list(ms.entries)
[ 2=1,3=3,5=2,7=2,9=1 ] // ZList
(zoomba)sortd(l) :: { $.l.value < $.r.value }
true // Boolean
(zoomba)l
[ 3=3,5=2,7=2,2=1,9=1 ] // ZList
(zoomba)x = fold(l,list()) -> { for(i:[0:$.o.value] ){ $.p += $.o.key } }
[ 3,3,3,5,5,7,7,2,9 ] // ZList
public class DuplicateNumberFrequency {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] x ={2,3,5,3,7,9,5,3,7};
Map<Integer,Integer> map = new LinkedHashMap<Integer,Integer>();
for (int i = 0; i < x.length; i++) {
if(!map.containsKey(x[i])){
map.put(x[i], 1);
}
else {
map.put(x[i], map.get(x[i])+1);
}
}
System.out.println(map);
List<Map.Entry<Integer, Integer>> list =
new LinkedList<Map.Entry<Integer, Integer>>(map.entrySet());
System.out.println(list);
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> o1,
Map.Entry<Integer, Integer> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});
System.out.println(list);
}
}
namespace Pratise
{
static class Program
{
static void Main(string[] args)
{
int[] s = { 2,5, 3, 7, 4,5,9, 20,18,5, 3,3, 7 ,7,7,7,7,8,8,8,8};
Dictionary<int, int> acc = new Dictionary<int, int>();
for (int k = 0; k < s.Count(); k++)
{
Array.Sort(s);
acc.Add(k, s[k]);
}
Dictionary<int, int> dict = acc;
Dictionary<int, int> valCount = new Dictionary<int, int>();
foreach (int i in dict.Values)
{
if (valCount.ContainsKey(i))
{
valCount[i]++;
}
else
{
valCount[i] = 1;
}
}
List<KeyValuePair<int, int>> myList = valCount.ToList();
List<KeyValuePair<int, int>> myList1 = valCount.ToList();
myList.Sort(delegate(KeyValuePair<int, int> pair2, KeyValuePair<int, int> pair1) { return pair1.Value.CompareTo(pair2.Value); });
myList1.Sort(delegate(KeyValuePair<int, int> pair1, KeyValuePair<int, int> pair2) { return pair1.Value.CompareTo(pair2.Value); });
foreach(KeyValuePair<int, int> k in myList){
if (k.Value > 1)
{
for (int j = 0; j < k.Value; j++)
{
Console.WriteLine(k.Key);
}
}
}
foreach (KeyValuePair<int, int> l in myList1)
{
if (l.Value == 1)
{
for (int j = 0; j < l.Value; j++)
{
Console.WriteLine(l.Key);
}
}
}
}
}
}
Java Implementation Time Complexity (O(nLogn))
void function(int[] arr, int size) {
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int index = 0; index < size; index++) {
Integer elementFrquency = frequencyMap.get(arr[index]);
if (null != elementFrquency) {
elementFrquency += 1;
} else {
elementFrquency = 1;
}
frequencyMap.put(arr[index], elementFrquency);
}
List<Map.Entry<Integer, Integer>> frequencyMapElementList = new LinkedList<Map.Entry<Integer, Integer>>(
frequencyMap.entrySet());
Collections.sort(frequencyMapElementList, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
int compare = o1.getKey().compareTo(o2.getKey());
if (compare == 0) {
return o1.getValue().compareTo(o2.getValue());
}
return compare;
}
});
for(Map.Entry<Integer,Integer> entry : frequencyMapElementList) {
for(int index=0; index<entry.getValue(); index++) {
System.out.print(entry.getKey()+" ");
}
}
}
public static void SortByFrequency(int[] arr)
{
Dictionary<int, int> iDict = new Dictionary<int, int>();
Array.Sort(arr);
foreach (int i in arr)
{
if (!iDict.ContainsKey(i))
{
iDict.Add(i, 1);
}
else
{
iDict[i]++;
}
}
var sorted = iDict.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
foreach(KeyValuePair<int,int> keyValue in sorted)
{
for(int i =0; i<keyValue.Value; i++)
{
Console.WriteLine(keyValue.Key);
}
}
}
object DecreasingFrequency extends App {
/**
* You are given an array with duplicates. You have to sort the array with decreasing frequency of elements.
* If two elements have the same frequency, sort them by their actual value in increasing order.
* Ex: [2 3 5 3 7 9 5 3 7]
* Output: [3 3 3 5 5 7 7 2 9]
*/
case class NumberFrequency(value: Int, var frequency: Int) extends Ordered[NumberFrequency] {
def compare(that: NumberFrequency) = {
if (this.frequency == that.frequency)
this.value.compareTo(that.value)
else if (this.frequency < that.frequency)
1
else
-1
}
def incrementFrequency(): Unit = this.frequency += 1
def values: List[Int] = (1 to frequency).map(_ => value).toList
}
def sort(numbers: List[Int]): List[Int] = {
var frequencyMap: List[NumberFrequency] = List.empty[NumberFrequency]
for(outer <- 0 until numbers.size) {
val key = numbers(outer)
if (!frequencyMap.exists(_.value == key)) {
frequencyMap = frequencyMap :+ NumberFrequency(key, 1)
for (inner <- outer + 1 until numbers.size) {
if (numbers(inner) == key) {
frequencyMap.find(_.value == key).map(_.incrementFrequency())
}
}
} // end of inner
}
frequencyMap.sorted.map(_.values).flatten
}
val input = List(2, 3, 5, 3, 7, 9, 5, 3, 7)
println(sort(input).mkString(","))
}
object DecreasingFrequency extends App {
case class NumberFrequency(value: Int, var frequency: Int) extends Ordered[NumberFrequency] {
def compare(that: NumberFrequency) = {
if (this.frequency == that.frequency)
this.value.compareTo(that.value)
else if (this.frequency < that.frequency)
1
else
-1
}
def incrementFrequency(): Unit = this.frequency += 1
def values: List[Int] = (1 to frequency).map(_ => value).toList
}
def sort(numbers: List[Int]): List[Int] = {
var frequencyMap: List[NumberFrequency] = List.empty[NumberFrequency]
for(outer <- 0 until numbers.size) {
val key = numbers(outer)
if (!frequencyMap.exists(_.value == key)) {
frequencyMap = frequencyMap :+ NumberFrequency(key, 1)
for (inner <- outer + 1 until numbers.size) {
if (numbers(inner) == key) {
frequencyMap.find(_.value == key).map(_.incrementFrequency())
}
}
} // end of inner
}
frequencyMap.sorted.map(_.values).flatten
}
val input = List(2, 3, 5, 3, 7, 9, 5, 3, 7)
println(sort(input).mkString(","))
}
object DecreasingFrequency extends App {
case class NumberFrequency(value: Int, var frequency: Int) extends Ordered[NumberFrequency] {
def compare(that: NumberFrequency) = {
if (this.frequency == that.frequency)
this.value.compareTo(that.value)
else if (this.frequency < that.frequency)
1
else
-1
}
def incrementFrequency(): Unit = this.frequency += 1
def values: List[Int] = (1 to frequency).map(_ => value).toList
}
def sort(numbers: List[Int]): List[Int] = {
var frequencyMap: List[NumberFrequency] = List.empty[NumberFrequency]
for(outer <- 0 until numbers.size) {
val key = numbers(outer)
if (!frequencyMap.exists(_.value == key)) {
frequencyMap = frequencyMap :+ NumberFrequency(key, 1)
for (inner <- outer + 1 until numbers.size) {
if (numbers(inner) == key) {
frequencyMap.find(_.value == key).map(_.incrementFrequency())
}
}
} // end of inner
}
frequencyMap.sorted.map(_.values).flatten
}
val input = List(2, 3, 5, 3, 7, 9, 5, 3, 7)
println(sort(input).mkString(","))
}
void compute(vector<int> &nums) {
vector<pair<int,int> > v;
map<int,int> mp;
for(int i = 0; i < nums.size(); i++) mp[nums[i]]++;
for(map<int,int> :: iterator it = mp.begin(); it != mp.end(); it++) v.push_back({it->first, it->second});
sort(v.begin(), v.end(), [](pair<int,int> a, pair<int,int> b){
if(a.second == b.second) return a.first < b.first;
return a.second > b.second;
});
nums.clear();
for(int i = 0; i < v.size(); i++) {
for(int j = 1; j <= v[i].second; j++) nums.push_back(v[i].first);
}
}
function frequencySort(arr){
var arrObject = [], arrayOut = [];
if(arr.length===0) return arr;
// Sort ascending
arr.sort();
var startIndex = 0, endIndex = 1;
for(var i=0; i<arr.length; ++i){
if(arr[i] === arr[i+1]) ++endIndex;
else{
arrObject.push({
val: arr[i],
freq : Number(endIndex) - Number(startIndex)
});
startIndex++;
endIndex=startIndex+1;
}
}
for(var i=0; i<arrObject.length; i++){
var shouldRevert = false;
if(arrObject[i+1]){
if(arrObject[i+1].freq > arrObject[i].freq){
// deep copy arrObject[i]
const copy = Object.assign({}, arrObject[i]);
arrObject[i].val = arrObject[i+1].val;
arrObject[i].freq = arrObject[i+1].freq;
arrObject[i+1].val = copy.val
arrObject[i+1].freq = copy.freq;
}
}
}
for(var i=0; i<arrObject.length; i++){
for(var j=0; j<arrObject[i].freq; j++){
arrayOut.push(arrObject[i].val);
}
}
return arrayOut;
};
int arr[] =new int[]{2,3,5,3,7,9,5,3,7};
HashMap<Integer,Integer> hash=new HashMap<>();
ArrayList<Integer> new_arr=new ArrayList<>();
for(int c:arr)
{
hash.put(c,hash.getOrDefault(c, 0)+1);
}
PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->hash.get(b)-hash.get(a));
pq.addAll(hash.keySet());
while(!pq.isEmpty())
{
int a=pq.peek();
for(int i=0;i<hash.get(a);i++)
{
new_arr.add(a);
}
}
System.out.print(new_arr);
// The interface
import java.util.Map;
// The implementation of the Map interface, it allows us to have the Number with its frequency
import java.util.HashMap;
// We also need a Tree Map to sort the HashMap
import java.util.TreeMap;
// Usually a TreeMap comes along with a Comparator
import java.util.Comparator;
// The final array, it allows us to add duplicated elements
import java.util.ArrayList;
public class Frequencies {
// Initial input
private Map<Integer,Integer> frequency = new HashMap<Integer,Integer>();
// Input sorted
private Map<Integer,Integer> frequencySorted;
// Final output
private ArrayList<Integer> frequencyFinal = new ArrayList<Integer>();
private void fillFrequency(int[] elements){
for(int i=0; i<elements.length; i++){
int counter = 1;
if( frequency.get(elements[i])!= null ){
counter = frequency.get(elements[i]) + 1;
}
frequency.put(elements[i], counter);
}
}
/**
*
* @param order 0->Ascending, 1->Descending
*/
private void sortFrequency(int order){
Comparator<Integer> comparator = new Comparator<Integer>(){
public int compare(Integer key1, Integer key2){
int compare = 0;
if( order==0 ){ // Ascending order
compare = frequency.get(key1).compareTo(frequency.get(key2));
} else { // Descending order
compare = frequency.get(key2).compareTo(frequency.get(key1));
}
// On same values, do not move the element
if( compare == 0) {
return 1;
} else {
return compare;
}
}
};
frequencySorted = new TreeMap<Integer,Integer>(comparator);
frequencySorted.putAll(frequency);
}
private void fillFrequencyFinal(){
for(int elementId : frequencySorted.keySet() ){
for(int i = 0; i < frequency.get(elementId); i++){
frequencyFinal.add(elementId);
}
}
}
private void showFrequency(){
System.out.println("Frequency counter ===>");
for(int elementId : frequency.keySet() ){
System.out.println("Element->" + elementId + ", frequency->" + frequency.get(elementId) );
}
}
private void showFrequencySorted(){
System.out.println("Frequency counter sorted in descending order ===>");
// Explore our sorted TreeMap
for(int elementId : frequencySorted.keySet() ){
System.out.println("Element->" + elementId + ", frequency->" + frequency.get(elementId) );
}
}
private void showFrequencyFinal(){
System.out.println("Frequency final output ===>");
for(int elementId : frequencyFinal ){
System.out.println("Element->" + elementId);
}
}
/**
* The constructor
* @param int[] elements
*/
public Frequencies(int[] elements){
fillFrequency(elements);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] initialArray = { 2,3,5,3,7,9,5,3,7 };
// Create an instance of our class
Frequencies frequencies = new Frequencies(initialArray);
// Explore our frequency counter HashMap
frequencies.showFrequency();
// Sort frequencies in descending order
frequencies.sortFrequency(1);
// Show what we have so far
frequencies.showFrequencySorted();
// Fill our final output
frequencies.fillFrequencyFinal();
// Show our final list
frequencies.showFrequencyFinal();
}
}
object DecreasingFrequency extends App {
/**
* You are given an array with duplicates. You have to sort the array with decreasing frequency of elements.
* If two elements have the same frequency, sort them by their actual value in increasing order.
* Ex: [2 3 5 3 7 9 5 3 7]
* Output: [3 3 3 5 5 7 7 2 9]
*/
case class NumberFrequency(value: Int, var frequency: Int) extends Ordered[NumberFrequency] {
def compare(that: NumberFrequency) = {
if (this.frequency == that.frequency)
this.value.compareTo(that.value)
else if (this.frequency < that.frequency)
1
else
-1
}
def incrementFrequency(): Unit = this.frequency += 1
def values: List[Int] = (1 to frequency).map(_ => value).toList
}
def sort(numbers: List[Int]): List[Int] = {
var frequencyMap: List[NumberFrequency] = List.empty[NumberFrequency]
for(outer <- 0 until numbers.size) {
val key = numbers(outer)
if (!frequencyMap.exists(_.value == key)) {
frequencyMap = frequencyMap :+ NumberFrequency(key, 1)
for (inner <- outer + 1 until numbers.size) {
if (numbers(inner) == key) {
frequencyMap.find(_.value == key).map(_.incrementFrequency())
}
}
} // end of inner
}
frequencyMap.sorted.map(_.values).flatten
}
val input = List(2, 3, 5, 3, 7, 9, 5, 3, 7)
println(sort(input).mkString(","))
}
- John K April 19, 2017import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Map; public class SortByFrequency { public static void main(String[] args) { Integer[] input = new Integer[] { 2,3,5,3,7,9,5,3,7 }; // Sort the array using custom comparator Arrays.sort(input, new FrequencyComparator(input)); // Print the result for (Integer i : input) System.out.print(i + " "); } static class FrequencyComparator implements Comparator<Integer> { Map<Integer, Integer> frequencyMap = new HashMap<>(); public FrequencyComparator(Integer[] input) { for (Integer i : input) { frequencyMap.put(i, frequencyMap.get(i) != null ? frequencyMap.get(i) + 1 : 1); } } @Override public int compare(Integer i1, Integer i2) { // If frequencies are the same then compare the actual numbers if (frequencyMap.get(i1) == frequencyMap.get(i2)) return i1.compareTo(i2); return (frequencyMap.get(i1) < frequencyMap.get(i2)) ? 1 : -1; } } }