## Expedia Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````import 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;
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Somebody plz write the logic instead of code

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code :

``````a = [2,3,5,3,7,9,5,3,7]
b = {i : a.count(i) for i in set(a) }
c= sorted(b.items())
c = sorted(c,key=lambda x:x[1],reverse=1)
out = []
for p,q in c:
for i in xrange(q):
out.append(p)
print out``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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};

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 =
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);

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
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);
}
}
}
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

rgrg

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()+" ");
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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))
{
}
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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````e = [2,3,5,3,7,9,5,3,7]
d = {}
for v in e:
if v in d:
d[v] += 1
else:
d[v] = 1
res = []
for key, value in sorted(d.items(), key=lambda kv: (-kv[1], kv[0])):
res.extend([key]*value)
#print(key,value)
print(res)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(","))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(","))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(","))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

while(!pq.isEmpty())
{
int a=pq.peek();
for(int i=0;i<hash.get(a);i++)
{
}
}

System.out.print(new_arr);

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````// 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++){
}
}
}
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();
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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(","))
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.