Expedia Interview Question for Software Engineer / Developers


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

- John K April 19, 2017 | Flag Reply
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)

- Anonymous April 18, 2017 | Flag Reply
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)

- Brian M April 18, 2017 | Flag Reply
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;

	

}

- fred April 18, 2017 | Flag Reply
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

- NoOne April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Somebody plz write the logic instead of code

- Priyanka April 20, 2017 | Flag Reply
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

- Naman Dasot April 20, 2017 | Flag Reply
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};

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

}

}

- Vipul Agarwal April 22, 2017 | Flag Reply
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);
                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);
                   }
                }
            }
        }

    }
}

- Sihle April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

rgrg

- Sihle April 24, 2017 | Flag Reply
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()+" ");
                        }
                }

        }

- Kapil July 09, 2017 | Flag Reply
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))
                {
                    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);
                }
            }
        }

- gkr August 07, 2017 | Flag Reply
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)

- Vinita October 13, 2017 | Flag Reply
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(","))
}

- Suresh December 25, 2017 | Flag Reply
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(","))
}

- Suresh December 25, 2017 | Flag Reply
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(","))
}

- Suresh December 25, 2017 | Flag Reply
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);
	}
}

- galok7000 February 23, 2018 | Flag Reply
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;
};

- medard.zamble July 24, 2018 | Flag Reply
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++){
				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();
	}

}

- undefined June 01, 2017 | Flag Reply
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(","))
}

- Suresh December 25, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More