puzzle-spotify

https://www.spotify.com/us/jobs/tech/

spotify.catvsdog.java

/*
 * spotify.catvsdog
 */

import java.util.ArrayList;
import java.util.Scanner;


public class Catvsdog {
    
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int numberOfTestcases = Integer.valueOf(scanner.nextLine());
		for(int testNum = 0; testNum < numberOfTestcases; testNum++){
			String[] numbers = scanner.nextLine().trim().split(" ");
			int numberOfVoters = Integer.valueOf(numbers[2]);
			
			/* generate users*/
			User[] users = new User[numberOfVoters];
			for(int i = 0; i < numberOfVoters; i++){
				String[] pro_con = scanner.nextLine().trim().split(" ");
				users[i] = new User(pro_con[0], pro_con[1]);
			}
			
			/* build a matrix to label the compatibility of users*/
			boolean[][] matrix = new boolean[numberOfVoters][numberOfVoters];
			for(int row = 0; row < numberOfVoters; row++){
				for(int column = 0; column < numberOfVoters; column++){
					if(!users[row].getPro().equals(users[column].getCon()) &&
							!users[row].getCon().equals(users[column].getPro())) matrix[row][column] = true;
				}
			}
			
			/* find the max compatible user combination*/
			int max = 0;
			for(int row = 0; row < numberOfVoters; row++){
				ArrayList<boolean[]> thisUserCompatity = new ArrayList<>();
				for(int column = 0; column < numberOfVoters; column++){
					if(matrix[row][column]) thisUserCompatity.add(matrix[column]);
				}
				int thisNumber = 0;
				for(int i = 0; i < thisUserCompatity.get(0).length; i++){
					int j = 0;
					for(; j < thisUserCompatity.size(); j++){
						if(!thisUserCompatity.get(j)[i]) break;
					}
					if(j == thisUserCompatity.size()) thisNumber++;
				}
				if(thisNumber > max) max = thisNumber;
			}
			System.out.println(max);
		}
		scanner.close();
	}

}

class User{
	private String pro;
	private String con;
	User(String pro, String con){
		this.pro = pro;
		this.con = con;
	}
	public String getPro(){
		return this.pro;
	}
	public String getCon(){
		return this.con;
	}
}

spotify.reversebinary.java

/*
 * spotify.reversebinary
 */
import java.util.Scanner;

public class Reversebinary {
    public static int reverse(int input){
		int result = 0;
		int count = 0;
		for(int i = 0; i < 32; i++){
			result <<= 1;
			result |= input & 0x1;
			if((input & 0x1) == 1) count = 0;
			else count++;
			input >>>= 1;
		}
		return result >>> count;
	}
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println(reverse(scanner.nextInt()));
		scanner.close();
	}
}

spotify.zipfsong.java

/*
 * spotify.zipfsong
 */

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Zipfsong {
    
	public static Song[] getHightQualitySongs(Song[] songs, int numberToSelect){
		/* generate Zipf's Law quality value for each song*/
		for(int i = 0; i < songs.length; i++){
			songs[i].setQuality((double) songs[i].getFrequency() / (songs[0].getFrequency() / (i + 1)));
		}
		
		/* use heap to get top k songs*/
		PriorityQueue<Song> heap = new PriorityQueue<>(numberToSelect, new Comparator<Song>(){
			public int compare(Song a, Song b){
				return Double.valueOf(a.getQuality()).compareTo(Double.valueOf(b.getQuality()));
			}
		});
		for(int i = 0; i < songs.length; i++){
			heap.offer(songs[i]);
			if(heap.size() > numberToSelect) heap.poll();
		}
		
		/* return the result*/
		Song[] result = new Song[numberToSelect];
		for(int i = 0; i < numberToSelect; i++){
			result[numberToSelect - 1 - i] = heap.poll();
		}
		return result;
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		/* get numbers */
		String[] numbers = scanner.nextLine().trim().split(" ");
		int numberOfSongs = Integer.valueOf(numbers[0]);
		int numberToSelect = Integer.valueOf(numbers[1]);
		
		/* generate songs node */
		Song[] songs = new Song[numberOfSongs];
		for(int i = 0; i < numberOfSongs; i++){
			String[] songLine = scanner.nextLine().trim().split(" ");
			songs[i] = new Song(Long.valueOf(songLine[0]), songLine[1]);
		}
		scanner.close();
		
		/* get high zipf's Law quality songs and print them */
		Song[] hightQualitySongs = getHightQualitySongs(songs, numberToSelect);
		for(int i = 0; i< hightQualitySongs.length; i++){
			System.out.println(hightQualitySongs[i].getName());
		}
	}
}

class Song{
	private String name;
	private long frequency;
	private double quality;
	Song(long frequency, String name){
		this.frequency = frequency;
		this.name = name;
		this.quality = 0;
	}
	public double getQuality(){
		return this.quality;
	}
	public void setQuality(double value){
		this.quality = value;
	}
	public long getFrequency(){
		return this.frequency;
	}
	public String getName(){
		return this.name;
	}
}