Booking.com Interview Question Software Engineer / Developers
Team: perl backend
Country: neitherland
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.
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.
#!/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)
#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;
}
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);
}
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
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);
}
}
}
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);
}
}
}
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;
}
}
}
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.
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