CareerCup

public static List<Contact> removeDuplicates(List<Contact> contacts){
Map<String, Integer> emailMap = new HashMap<String, Integer>();
List<Contact> contactUnique = new ArrayList<Contact>();
Iterator<Contact> it = contacts.iterator();

/*
* O(n) iterate over contacts and create email map
*/
while (it.hasNext()) {
Contact con = it.next();
Iterator<String> emailIt = con.getEmail().iterator();
while (emailIt.hasNext()) {
String email = emailIt.next();
if(emailMap.get(email) == null){
emailMap.put(email, 1);
}else{
Integer count = emailMap.get(email);
emailMap.put(email, ++count);
}
}
}

Iterator<Contact> it_1 = contacts.iterator();
while (it_1.hasNext()) {
Contact con = it_1.next();
Iterator<String> emailIt = con.getEmail().iterator();
Boolean isUnique = Boolean.TRUE;
while (emailIt.hasNext()) {
String email = emailIt.next();
if(emailMap.get(email) > 1){
isUnique = Boolean.FALSE;
break;
}
}
if(isUnique){
contactUnique.add(con);
}
}
return contactUnique;
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Q1_17_7_17 {


	public static void main(String[] args) {

		Set<Integer> set = new HashSet<Integer>();
		set.add(1);
		set.add(3);


		Set<Integer> set1 = new HashSet<Integer>();
		set1.add(1);
		set1.add(2);
		set1.add(3);
		Set<Integer> set2 = new HashSet<Integer>();
		set2.add(5);
		set2.add(6);

		List<Set<Integer>> list = new ArrayList<Set<Integer>>();

		list.add(set1);
		list.add(set2);

		System.out.println(validate(set, list));
	}


	private static boolean validate(Set<Integer> set, List<Set<Integer>> list){
		if(set == null || list == null){
			return false;
		}

		Boolean[] decisionArr = new Boolean[list.size()];
		int counter = 0;
		Iterator<Set<Integer>> it = list.iterator();

		//Iterate over the list of set
		while(it.hasNext()){
			Set<Integer> set_1 = it.next();
			boolean found = true;

			Iterator<Integer> it_1 = set.iterator();

			while(it_1.hasNext()){
				Integer i = it_1.next();
				if(!set_1.contains(i)){
					found  = false;
					break;
				}
			}

			if(found){
				decisionArr[counter++] = true;
			}else{
				decisionArr[counter++] = false;
			}

		}
		//Done iterating over the list of sets
		
		for (int i = 0; i < decisionArr.length; i++) {
			if(decisionArr[i]){
				return true;
			}
		}

		return false;
	}

}

@anandsh1990 : - This is normal linear search which runs in O(n) .... The question talks about a solution in less than O(n) .

We can do it in O(1) ... by using an extra space (map) and storing the number as key and frequency as value . But even this way first time the run time would be O(n) but subsequent finds will be run in O(1) ...

public class ArrayTest {


	public static void main(String[] args) {

		int[] arr = {3,15};
		int[] primes = {5};

		System.out.println(checkEquality(arr, primes));
	}

	public static boolean checkEquality(int[] arr,int[] primes){
		int max = arr[0];
		for(int i = 1;i< arr.length;i++){
			if(max < arr[i]){
				max = arr[i];
			}
		}
		//Iterating over elements array
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == max){
				continue;
			}
			//Iterating over primes array
			for (int j = 0; j < primes.length; j++) {
				int num = arr[i];
				boolean cont = false;
				for (int k = 1; k < 10; k++) {
					num *= primes[j];
					if(num == max){
						cont = true;
						break;
					}else if(num < max){
						continue;
					}else{
						if(j == primes.length -1){
							return false;
						}
						break;
					}
				}
				if(cont){
					break;
				}
			}
		}
		return true;
	}


}

package Stack;

public class Stack {

	private int capacity;
	private int[] baseArray;
	private int index = -1;
	private int size = 0;

	public Stack(int capacity) {
		this.capacity = capacity;
		baseArray = new int[capacity];
	}

	public void push(int data)throws StackFullException{
		if(this.isFull()){
			throw new StackFullException("Stack Full  ... Can't push more data");
		}
		baseArray[++index] = data;
		size++;
	}

	public int pop()throws StackEmptyException{
		if(this.isEmpty()){
			throw new StackEmptyException("Stack Empty ... Nothing to pop ");
		}
		size--;
		return baseArray[index--];
	}

	public int peek(){
		return baseArray[index];
	}

	public boolean isEmpty(){
		if(this.size() < 1){
			return true;
		}
		return false;
	}

	public boolean isFull(){
		if(this.size == this.capacity){
			return true;
		}
		return false;
	}

	public int size(){
		return this.size;
	}
}

package Stack;

public class StackImpl {
	public static void main(String[] args) throws Exception{

		Stack stack = new Stack(5);
		
		
		stack.push(10);
		stack.push(20);
		stack.push(30);
		stack.push(40);
		stack.push(50);
		
		
		while(!stack.isEmpty()){
			System.out.println(stack.pop());
		}
		
	}
}

public void flatten(Node head){
Node cur = head;
Node temp;
while(cur != null){
temp = cur.right;
Node down = cur.down;
while(down != null){
cur.right = down;
cur.down = null;
cur = down;
down = down.down;
}
cur.right = temp;
cur = temp;
}
}

public static void print2DArraySpirally(int arr[][]){
boolean flag = false;
for(int i = 0 ; i < arr.length; i++ ){
if(flag){
for(int j = arr[i].length - 1 ; j >= 0 ;j--){
System.out.print(arr[i][j]+" ");
}
}else{
for(int j = 0 ;j < arr[i].length ; j++){
System.out.print(arr[i][j]+" ");
}
}
flag = !flag;
System.out.println("");
}
}

This is a brute force approach,evaluating all numbers from 0 to N-1 : -

import java.util.ArrayList;
import java.util.List;

public class JumbledNumbers {

public static void main(String[] args) {
List<Integer> jumbledNumbers = new ArrayList<Integer>();
int N = 100;
for (int i = 0; i < N; i++) {
if(isJumbled(i)){
jumbledNumbers.add(i);
}
}
System.out.println(jumbledNumbers);
}

public static boolean isJumbled(int num){
if(num < 10){
return false;
}else{
String numVal = String.valueOf(num);
for (int i = 0; i < numVal.length() - 1 ; i++) {
int digit1 = Integer.valueOf(numVal.charAt(i)+"");
int digit2 = Integer.valueOf(numVal.charAt(i+1)+"");
if( ( digit1 - digit2 == 1) || (digit2 - digit1 == 1)){
continue;
}else{
return false;
}
}
return true;
}
}
}

We can create a hash map to store word and frequency , then create a tree map to store sorted frequency and list of words , then eventually dump the content into a array ... this way we can get highest and lowest frequency easily.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.TreeMap;

public class WordFrequency {

public static void main(String[] args) {


String sentence = "A word word has been been has A A A been bbb abbab bbb he he he is a good man";
String[] wordArray = sentence.split(" ");
HashMap<String, Integer> initialMap = new HashMap<String,Integer>();
TreeMap<Integer, List<String>> sortedMap = new TreeMap<Integer, List<String>>();
Object array[][];


// Create a map to store word and frequency
for (int i = 0; i < wordArray.length; i++) {
String word = wordArray[i];
Integer count = initialMap.get(word);
if(count == null){
initialMap.put(word, 1);
}else{
initialMap.put(word, ++count);
}
}

// Create a Tree map to store frequency and list of words
Iterator<String> it = initialMap.keySet().iterator();
while (it.hasNext()) {
String string = (String) it.next();
Integer count = initialMap.get(string);
List<String> list = sortedMap.get(count);
if(list == null){
list = new ArrayList<String>();
list.add(string);
sortedMap.put(count, list);
}else{
list.add(string);
sortedMap.put(count, list);
}
}

/*Store the tree map content into a 2d array
* now based on index you can easily find the word with highest and lowest frequency
*/
array = new Object[sortedMap.size()][3];

Iterator<Integer> it1 = sortedMap.keySet().iterator();
int i = 0;
while (it1.hasNext()) {
Integer integer = (Integer) it1.next();
List<String> list = sortedMap.get(integer);
array[i][0] = i;
array[i][1] = integer;
array[i][2] = list;
i++;
}

//System.out.println(sortedMap);


for (int j = 0; j < array.length; j++) {
for (int j2 = 0; j2 < array[j].length; j2++) {
System.out.print(array[j][j2]+" ");
}
System.out.println("");
}
}
}