Booking.com Interview Question for Software Engineer / Developers


Team: perl backend
Country: neitherland




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

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;

public class main{
        private static int max = 0;
	private static HashMap<Character, Integer> histogram = new HashMap<Character, Integer>(){{
		for (int i=97; i<=122 ;i++){
			this.put((char)i, 0);
		}
	}};
	
	
    public static void readFile(String file) throws IOException {
        BufferedReader reader = new BufferedReader( new FileReader (file));
        String         line = null;
        char		   key;
        
        while( ( line = reader.readLine() ) != null ) {
        	for (int i=0;i<line.length();i++) {
        		key = Character.toLowerCase(line.charAt(i));
        		if (histogram.containsKey(key)){
            		      histogram.put(key, histogram.get(key)+1);
                              if  (histogram.get(key)>max){
                                    max=histogram.get(key);
                              }       			
        		}
        	}
        }
        reader.close();
    }
    
	public static void main (String []args){
		try {
			readFile("test.txt");
			for (int i=97; i<=122 ;i++){
				for(int j=0; j<((histogram.get((char)i)/max)*80);j++){
					System.out.print("*");
				}
				System.out.println((char)i);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
    }
}

Sorry, I didn't see that criteria of only printing up to 80, I updated the code to have a "max" value that each line is then divided by and multiplied by 80, to give a relative histogram.

- Jon.Koehmstedt March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This seems to satisfy all but the 80 character max. You could stop printing '*' after you've reached 80, but this does not produce a proper histogram. A character with 80 repeats will look identical as a character with 1000 repeats. You should store the max number of characters and use some algebra to calculate the # of '*' to print.

Ex. Max Number of repeats from all characters = 1000
Char 'n' is repeated 400 times

1000/80 = 400/x => 1000x = 32000 => 32000/1000 = 32.

Therefore, you should print '*' 32 times for the letter n. To generalize this we can say you would for a given ni (number of repeats for character i) and a given max number of repeats m, you would print '*' (ni*80)/m times.

- BenC March 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/bin/python


with open('file', 'r') as f:
        contents = f.readlines();

result = {}

#gather
for word in contents:
        for letter in word:
                if not result.has_key(letter):
                        result[letter] = 0;
                result[letter] = result[letter] + 1;

#represent 
maxval = result[max(result.keys(), key=lambda x: result[x])]

for key in sorted(result.keys()):
        ratio = int((float(result[key]) / float(maxval)) * 80);
        string = '';
        i = 0;
        for i in  xrange(ratio):
                string = string + '*';
                i = i + 1;

        print '%s%s' % (string, key)

- PT May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my %freq;
$input=~s/([a-zA-z])/$freq{$1}++;$1/ge;
foreach my $ch (sort {$a <=> $b} keys(%freq))
{
    next if $freq{$ch} <= 0;
    printf("\n%s%s",'*' x $freq{$ch},$ch);
}

- perl monk May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
#define MAX 80

int main()
{
  char c ;
  FILE *fp = NULL;
  char filename[80]; 
  int count[26];
  int i = 0 ;
  int spaces = 0 ;
  int start = 97;
  int j = 0;
  for(i = 0 ;i < 26 ; i++)
    count[i] = 0;
  
  printf("\nEnter a file name : ");
  scanf("%s",filename);
  printf("You have entered filename : %s",filename);
  fp = fopen(filename,"r");
  
  if(fp == NULL)
  {
    printf("Can not open specified file ... !!! Error.... ");
    exit(0);
  }
  
  while((c = fgetc(fp)) != EOF)
  {
	count[c%97]++;
  }  
  
  printf("\n------------------------------------histogram---------------------------------\n");
  for(i = 0 ; i < 26 && start <= 122; i++,start++)
  {
    for(j = 1;j <= count[i]; j++)
    {
      if(j % MAX == 0)
      {
	printf("*\n");
      }
      else
	printf("*");
      
    }
    
    spaces = MAX - (count[i]%MAX);
    for(j = 0 ; j < spaces ; j++)
    {
      printf(" ");
    }
    printf("%c\n",start);
  }
  
  printf("\n");
  return 0;
}

- Rajesh June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Histogram {
    public:
        Histogram(const std::string &content)
        {
            for (std::string::const_iterator it = content.begin(); it != content.end(); ++it) {
                std::map<const char, unsigned int>::iterator hit = data.find(*it);
                if (hit == data.end()) {
                    data[*it] = 0;
                } else {
                    hit->second++;
                }
            }
        }
        
        void PrintData(const int maxDots = 80)
        {
            /* find max */
            int max = std::max_element(data.begin(), data.end(), [](const std::pair<const char, unsigned int> &a, const std::pair<const char, unsigned int> &b){
                return a.second < b.second;
            })->second;
            std::cout << max << std::endl;
            
            /* display */
            std::for_each(data.begin(), data.end(), [=](const std::pair<const char, unsigned int> &p){
                int dots = p.second*maxDots/max;
                std::cout << p.first << " |";
                std::fill_n(std::ostream_iterator<char>(std::cout), dots, '+');
                std::cout << std::endl;
            });
        }
        
    private:
        std::map<const char, unsigned int> data;
    };
    
    void Solve(const std::string &content)
    {
        Histogram h(content);
        h.PrintData(80);
    }

- S November 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

lines = IO.readlines("test.txt")
maxHisto = 80

charCount = {}
lines.each do |word|
	word.chomp!
	word.downcase!
	word.each_char do |char|
		if !charCount.has_key?(char)
			charCount[char] = 0
		end
		charCount[char] = charCount[char] + 1
	end
end

# Checking for maximum count
maxCount = charCount.values.max
mustScale = maxCount > maxHisto

charCount.sort.each do |char, count|
	if mustScale
		count = ((count.to_f / maxCount) * maxHisto).round
	end
	print "#{count} "
	count.times {print "*"}
	print "#{char}\n"
end

- Camilo Martinez May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Histogram {

    private static TreeMap<Character, Integer> map = new TreeMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String line = sc.nextLine();
            process(line);
        }

        for(Map.Entry<Character,Integer> entry: map.entrySet()){
            int count = entry.getValue();
            String stars = new String(new char[count]).replace('\0', '*');
            System.out.println(stars + entry.getKey());
        }
    }

    private static void process(String line) {
        for (int i = 0; i < line.length(); i++) {
            char ch = line.charAt(i);
            Integer count = map.get(ch);
            if (count == null)
                count = 0;

            if (count <= 80)
                map.put(ch, count + 1);
        }
    }

}

- Shayan October 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Histogram {

    private static TreeMap<Character, Integer> map = new TreeMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String line = sc.nextLine();
            process(line);
        }

        for(Map.Entry<Character,Integer> entry: map.entrySet()){
            int count = entry.getValue();
            String stars = new String(new char[count]).replace('\0', '*');
            System.out.println(stars + entry.getKey());
        }
    }

    private static void process(String line) {
        for (int i = 0; i < line.length(); i++) {
            char ch = line.charAt(i);
            Integer count = map.get(ch);
            if (count == null)
                count = 0;

            if (count <= 80)
                map.put(ch, count + 1);
        }
    }
}

- Shayan October 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class CharacterHistogram {

	static class CharCount implements Comparable<CharCount> {
		private char c;
		private int count;

		@Override
		public int compareTo(CharCount o) {
			return o.count - this.count;
		}
	}

	public static void main(String[] args) {
		List<String> input = new ArrayList<String>();
		input.add("abactor");
		input.add("abaculus");
		input.add("abacus");
		input.add("Abadite");
		input.add("Zyrenian");

		Map<Character, CharCount> map = new TreeMap<Character, CharCount>();
		List<CharCount> list = new ArrayList<CharCount>();
		for (String str : input) {
			char[] ch = str.toCharArray();
			for (char c : ch) {
				CharCount obj = null;
				if (map.get(c) == null) {
					obj = new CharacterHistogram.CharCount();
					obj.c = c;
					obj.count = 1;
					map.put(c, obj);

				} else {
					obj = map.get(c);
					obj.count = obj.count + 1;
					map.put(c, obj);
				}
			
			}
		}
		System.out.println("Based On Character Sorting Order:");
		for (Entry<Character, CharCount> e : map.entrySet()) {
			for (int i = 0; i < e.getValue().count; i++) {
				System.out.print("*");
			}
			System.out.println(":"+e.getKey());
			list.add(e.getValue());
		}
		
		System.out.println("Based On Character Count:");
		
		Collections.sort(list);
		
		for(CharCount c : list){
			for (int i = 0; i < c.count; i++) {
				System.out.print("*");
			}
			System.out.println(":"+c.c);
		}
		
	}

}

- cpeeyush December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Solution {
	public static void main(String args[]) {
		String[] words = new String[] {"abactor" ,"abaculus", "abacus", "Abaditeuuu"};
		new Solution().solve(words);
	}
	private Map<Character, Integer> map;
	public Solution() {
		this.map = new HashMap<>();
	}
	private void add(String[] words) {
		for (String word: words)
			add(word);
	}
	private void add(String word) {
	word = word.toLowerCase();
		for (int i = 0 ;i < word.length() ; i++) {
			Character c = new Character(word.charAt(i));
			if (map.containsKey(c)) {
				map.put(c, map.get(c) + 1);
			}else{
				map.put(c, 1);
			}
		}
	}
	public void solve(String[] words) {
		add(words);
		Set<Character> set = map.keySet();
		Iterator<Character> iterator = set.iterator();
		while(iterator.hasNext()) {
			Character c = iterator.next();
			int value = this.map.get(c);
			queue.add(new Node(c.charValue(), value));
		}
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			for(int i = 0 ;i < node.value;i++)
				System.out.print("*");
			System.out.println(node.c);
		}
	}
	PriorityQueue<Node> queue = new PriorityQueue<>();
	private class Node implements Comparable<Node>{
		char c;
		int value;
		public Node(char c, int value) {
			this.c = c;
			this.value = value;
		}
		@Override
		public int compareTo(Node node) {
			if (this.c  < node.c)
					return -1;
			if (this.c > node.c)
				return 1;
			return 0;
		}
	}
}

- w.kinaan July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Tough question. I think it is NP-complete or Exp-hard.

- Anonymous March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm really no expert on this subject, but I'm pretty sure your statement is wrong. From what I remember an NP problem means it cannot be solved in polynomial time by a deterministic machine. So therefore it must be solved in exponential time by a deterministic machine. The above problem is being solved O(n) = O(n^1) (polynomial). Please correct me if I'm way off here, it's been a while.

- BenC March 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sarcastic comments about homework are best served with the name "Le snob".

- La Subburella. March 25, 2014 | Flag


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