DCIS
BAN USERkeeping track of all intervals, adjusting them when a new interval falls in the current ones range
import java.util.*;
public class Question
{
public static void main(String[] args)
{
int[][] inputOne = {{1,4},{2,3}};
int[][] inputTwo = {{4,6},{1,2}};
int[][] inputThree = {{1,4},{7,8},{2,4},{7,9},{10,16}};
System.out.println("total time one: " + totalTime(inputOne));
System.out.println("total time two: " + totalTime(inputTwo));
System.out.println("total time three: " + totalTime(inputThree));
}
public static int totalTime(int[][] input){
if(input == null ||input.length == 0){
return 0;
}
int totalTime = 0;
ArrayList<int[]> totalIntervals = new ArrayList<int[]>();
int[] firstInterval = {input[0][0], input[0][1]};
totalIntervals.add(firstInterval);
for(int i = 1; i < input.length; i++){
boolean updatedInterval = false;
int index = 0;
while(!updatedInterval){
int[] currentInterval = totalIntervals.get(index);
if(input[i][0] >= currentInterval[0] && input[i][1] <= currentInterval[1]){
updatedInterval = true;
}else if(input[i][0] < currentInterval[0] && input[i][1] >= currentInterval[0]){
currentInterval[0] = input[i][0];
if(input[i][1] > currentInterval[1]){
currentInterval[1] = input[i][1];
}
updatedInterval = true;
}else if(input[i][1] > currentInterval[1] && input[i][0] <= currentInterval[1]){
currentInterval[1] = input[i][1];
if(input[i][0] < currentInterval[0]){
currentInterval[0] = input[i][0];
}
updatedInterval = true;
}else{
if(index < totalIntervals.size() - 1){
index++;
}else{
int[] newInterval = {input[i][0], input[i][1]};
totalIntervals.add(newInterval);
updatedInterval = true;
}
}
}
}
for(int i = 0; i < totalIntervals.size(); i++){
int[] currentInterval = totalIntervals.get(i);
totalTime += (currentInterval[1] - currentInterval[0]);
}
return totalTime;
}
}
Seems like a simple question
public class FacebookQuestion {
public static void main(String[] args)
{
int[] input = {1,3,5};
System.out.print("input array: {");
for(int i = 0; i < input.length; i++){
System.out.print(input[i]);
if(i < input.length - 1){
System.out.print(", ");
}
}
System.out.println("}");
int[] squareArray = squareArray(input);
System.out.print("squared array: {");
for(int i = 0; i < squareArray.length; i++){
System.out.print(squareArray[i]);
if(i < squareArray.length - 1){
System.out.print(", ");
}
}
System.out.println("}");
}
public static int[] squareArray(int[] input){
for(int i = 0; i < input.length; i++){
input[i] = input[i] * input[i];
}
return input;
}
}
public class UpdateList
{
public static void main(String[] args)
{
node head = new node(1);
node nOne = new node(2);
node nTwo = new node(3);
node nThree = new node(4);
node nfour = new node(5);
head.add(nOne);
nOne.add(nTwo);
nTwo.add(nThree);
nThree.add(nfour);
System.out.print("inital list: ");
node current = head;
while(current != null){
System.out.print(current.getVal());
if(current.getNext() != null){
System.out.print(" -> ");
}
current = current.getNext();
}
System.out.println();
head = reOrderList(head);
System.out.print("final list: ");
current = head;
while(current != null){
System.out.print(current.getVal());
if(current.getNext() != null){
System.out.print(" -> ");
}
current = current.getNext();
}
}
public static node reOrderList(node head){
node walker = head;
node runner = head;
// move walker to the middle of the list
while(walker.getNext() != null && runner.getNext() != null && runner.getNext().getNext() != null){
walker = walker.getNext();
runner = runner.getNext().getNext();
}
// set up nodes to reverse back half of list
node currentNode = walker;
node previousNode = null;
node nextNode = null;
// point walker to next element in halfway list
walker = walker.getNext();
// reverse list at midway point
while(currentNode != null){
nextNode = currentNode.getNext();
currentNode.add(previousNode);
previousNode = currentNode;
currentNode = nextNode;
}
// add reversed list to original list, swaping the first element of the reversed list
// with the last element of the original (non revsersed) list
node endOfOriginalList = head.getNext();
head.add(runner);
runner.add(endOfOriginalList);
endOfOriginalList.add(walker);
return head;
}
}
public class node{
private node next;
private int val;
public node(int val){
this.next = null;
this.val = val;
}
public void add(node n){
this.next = n;
}
public node getNext(){
return this.next;
}
public int getVal(){
return this.val;
}
}
import java.util.*;
public class DecodeStringQuestion
{
public static void main(String[] args)
{
String input = "3[a2[b3[X]d]g4[ef2[z]]h]";
System.out.println(decodeString(input));
}
public static String decodeString(String input){
char openBrace = '[';
char closeBrace = ']';
Stack<Integer> numStack = new Stack<Integer>();
Stack<String> stringStack = new Stack<String>();
int currentReplication = -1;
String currentString = "";
for(int i = 0; i < input.length(); i++){
if(input.charAt(i) == openBrace){
int newLimit = input.charAt(i - 1) -'0';
currentString = currentString.substring(0, currentString.length()-1);
if(currentReplication > -1){
numStack.push(currentReplication);
}
currentReplication = newLimit;
stringStack.push(currentString);
currentString = "";
}else if(input.charAt(i) == closeBrace){
System.out.println(Arrays.toString(stringStack.toArray()));
String startingString = stringStack.pop();
String finalString = "";
finalString += startingString;
// exited the current scope, pop up to next level
if(currentReplication == -1){
startingString += currentString;
currentString = startingString;
currentReplication = numStack.pop();
if(!stringStack.empty()){
finalString = stringStack.pop();
}
}
for(int j = 0; j < currentReplication; j++){
finalString += currentString;
}
currentReplication = -1;
currentString = "";
stringStack.push(finalString);
}else{
currentString += input.charAt(i);
}
}
return stringStack.pop();
}
}
/**
* While not explicitly stated in the problem, this solution assumes that the only valid meeting places are open spaces, or in rare instances, a house
* runTime O(n*h) where n is number of open spaces and h is number of houses (or h^2 in no open space case)
* memory O(n + h) two hashsets for houses and open spaces
**/
import java.lang.Math;
import java.util.*;
public class VillageMap
{
public static void main(String[] args)
{
String[][] testOne = {{"#","#","#","#","#"},
{"#","#","A"," ","#"},
{"#"," "," ","B","#"},
{"#"," "," "," ","#"},
{"#"," "," ","#","#"},
{"#"," ","C"," ","#"},
{"#","#","#","#","#"}};
String[][] testTwo = {{"#"}};
String[][] testThree = {{"A"}};
String[][] testFour = {{"#", " ", "#", " ", "#"},
{"#", " ", "#", " ", "#"}};
String[][] testFive = {{"A", "#","B"},
{"#", "C", "#"},
{"D", "#", "E"}};
// base case
int[] meetingPointTestOne = meetingPoint(testOne);
System.out.println(meetingPointTestOne[0] + ", " + meetingPointTestOne[1]);
// null input case
System.out.println(meetingPoint(null));
// 1x1 case, non house
System.out.println(meetingPoint(testTwo));
// 1x1 case, house
int[] meetingPointTestThree = meetingPoint(testThree);
System.out.println(meetingPointTestThree[0] + ", " + meetingPointTestThree[1]);
// no houses case
System.out.println(meetingPoint(testFour));
// no open spaces case
int[] meetingPointTestFive = meetingPoint(testFive);
System.out.println(meetingPointTestFive[0] + ", " + meetingPointTestFive[1]);
}
public static int[] meetingPoint(String[][] area){
// case where null input, there is no meeting place
if(area == null){
return null;
}
// case when area is 1x1 2d array
if(area.length == 1 && area[0].length == 1){
int[] response = null;
// if that one space is a house, we can meet in the house, else, there is no village and thus there is no meeting place
if(!area[0][0].equals("#") && !area[0][0].equals(" ")){
response = new int[2];
response[0] = response[1] = 0;
}
return response;
}
HashSet<int[]> houses = new HashSet<int[]>();
HashSet<int[]> meetingSpaces = new HashSet<int[]>();
for(int i =0; i < area.length; i++){
for(int j = 0; j < area[i].length; j++){
if(!area[i][j].equals("#")){
int[] location = {i, j};
if(area[i][j].equals(" ")){
meetingSpaces.add(location);
}else{
houses.add(location);
}
}
}
}
// case where there are no houses, there is no village so return null
if(houses.size() == 0){
return null;
}
// case where there is no open spaces, but there are houses, return the location of the closet house to all houses
if(meetingSpaces.size() == 0){
Iterator<int[]> it = houses.iterator();
int closestDistance = Integer.MAX_VALUE;
int[] meetingHouse = new int[2];
while(it.hasNext()){
int[] currentHouse = it.next();
int tempDistance = getTempDistance(houses, currentHouse);
if(closestDistance > tempDistance){
closestDistance = tempDistance;
meetingHouse[0] = currentHouse[0];
meetingHouse[1] = currentHouse[1];
}
}
return meetingHouse;
}
//base case, there is an area made up of houses, bushes and open spaces
int closestDistance = Integer.MAX_VALUE;
int[] meetingArea = new int[2];
for(int[] spot: meetingSpaces){
int tempDistance = getTempDistance(houses, spot);
if(closestDistance > tempDistance){
closestDistance = tempDistance;
meetingArea[0] = spot[0];
meetingArea[1] = spot[1];
}
}
return meetingArea;
}
private static int getTempDistance(HashSet<int[]> houses, int[] spot){
int tempDistance = 0;
for(int[] house: houses){
int xS = house[1] - spot[1];
int yS = house[0] - spot[0];
tempDistance += (int)Math.sqrt((xS*xS) + (yS*yS));
}
return tempDistance;
}
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.HashMap;
public class GoogleQuestionUnscambleASentence{
public static void main(String[] args)
{
String input = "elhloothtedrowl";
ArrayList<String> dictionary = new ArrayList<String>();
dictionary.add("hello");
dictionary.add("to");
dictionary.add("the");
dictionary.add("world");
System.out.println("the input is " + input);
System.out.print("our dictionary is ");
System.out.print(dictionary);
System.out.println("\nthe unscambled sentence is '" + unscrambleTheSentence(input, dictionary)+"'");
}
public static String unscrambleTheSentence(String input, ArrayList<String> dictionary){
HashMap<Character, HashSet<String>> characterToWord = new HashMap<Character, HashSet<String>>();
String finalSentence = "";
for(String word : dictionary){
for(int i = 0; i < word.length();i++){
char key = word.charAt(i);
if(characterToWord.containsKey(key)){
HashSet<String> wordsWithChar = characterToWord.get(key);
wordsWithChar.add(word);
}else{
HashSet<String> wordsWithChar = new HashSet<String>();
wordsWithChar.add(word);
characterToWord.put(key, wordsWithChar);
}
}
}
HashSet<String> currentWords = null;
int index = 0;
while(input.length() > 0){
char currentKey = input.charAt(index);
if(currentWords == null){
currentWords = characterToWord.get(currentKey);
}else{
if(currentWords.size() == 1){
String foundWord = currentWords.iterator().next();
input = input.substring(foundWord.length());
finalSentence += foundWord + " ";
index = -1;
currentWords = null;
}else{
currentWords.retainAll(characterToWord.get(currentKey));
}
}
index++;
}
return finalSentence;
}
}
Just need to keep track of the current min number
- DCIS February 21, 2017