effy
BAN USER- 0of 0 votes
AnswersGiven a set of ranges:
- effy in United States
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}.
And given a target range R (e.g. R = (3, 13) - meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.| Report Duplicate | Flag | PURGE
Facebook
public class PutZerosAtEnd {
public static void main(String[] args) {
int[] arr = { 1, 3, 5, 1, 5, 1, 0 ,3, 81, 32, 0, 12, 91, 0, 1, 0};
zerosToEnd(arr);
System.out.print("{ ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("}");
}
public static void zerosToEnd(int[] arr) {
//Sets position to swap to at the
//end of the array.
int swapPos = arr.length - 1;
//continue moving backwards until it is not
//equal to 0.
while (swapPos > -1 && arr[swapPos] == 0)
swapPos--;
//Go forward in the array until swapPos
for (int i = 0; i < swapPos; i++) {
//If an element is 0, swap it with
//the element at swapPose.
if (arr[i] == 0) {
int temp = arr[swapPos];
arr[swapPos] = arr[i];
arr[i] = temp;
// decrement swapPos until not pointing
// to a 0.
while (swapPos > -1 && arr[swapPos] == 0)
swapPos--;
}
}
}
}
output:
{ 1 3 5 1 5 1 1 3 81 32 91 12 0 0 0 0 }
static boolean doesSumToTarget(int arr[], int target) {
if (arr[0] == target) return true;
if (arr.length < 2) return false;
int left = 0, right = 1, sum = arr[0];
while (right < arr.length + 1) {
if (sum < target) {
if (right < arr.length)
sum += arr[right++];
}
else if (sum > target) {
sum -= arr[left++];
if (left == right && right < arr.length)
sum += arr[right++];
}
else {
System.out.print("{ ");
for (int i = left; i < right; i++)
System.out.print(String.valueOf(arr[i]) + " ");
System.out.println("}");
return true;
}
}
return false;
}
input:
int[] arr = {1, 2, 3, 4, 5};
System.out.println(doesSumToTarget(arr, 7));
output:
{ 3 4 }
true
Store the dictionary as a graph. Have it set up so that you have vertices with labels 1, 2, 3, etc (these represent the number of letters in the word). From each of these, create complete-subgraphs, where every node (representing a word) with n characters, is connected to every other node with n characters. Every edge from a node is given by the letter that is changed, and the position of that new character.
Assume your classes appear as follows:
public class Vertex {
// Adjacency list, where the key is the index of the letter to change, and the value is
// another map, where the key is the character to change, and the value is the
// vertex of the new word
Hashmap<Integer, Hashmap<Character, Vertex>> adj =
new Hashmap<Integer, Hashmap<Character, Vertex>>();
String data;
public Vertex getAdjacentVertex(int index, char letter) {
if (!adj.containsKey(index))
return null;
return ajd.get(index).get(letter);
}
}
Then you can find the number of steps it takes to get there with the following:
public Integer numSteps(Vertex word, String target) {
if (word == null) return null;
if word.data.equals(target) return 0;
Map<Integer, Character> wordMap = new HashMap<Integer, Character>();
for (int i = 0; i < target.length(); i++) {
wordMap.put(i, target.charAt(i));
}
int numSteps = 0;
while (!wordMap.empty() && !target.equals(word.data)) {
Iterator<Integer> wordKeys = wordMap.keySet().iterator();
boolean foundEdge = false;
while (wordKeys.hasNext()) {
Integer wordKey = wordKeys.next();
if (word.getAdjacentVertex(wordKey, wordMap.get(wordKey)) != null) {
word = word.getAdjacentVertex(wordKey, wordMap.get(wordKey));
wordMap.remove(wordKey);
foundEdge = true;
numSteps++;
break;
}
}
if (!foundEdge)
return null;
}
return numSteps;
}
This solution would run in O(n) time, but use O(n^2) space.
- effy October 28, 2015O(n) time, O(1) space.
static void becomeABillionaire(int arr[]) {
int i = 0, buy = 0, sell = 0, min = 0, profit = 0;
for (i = 0; i < arr.length; i++) {
if (arr[i] < arr[min])
min = i;
else if (arr[i] - arr[min] > profit) {
buy = min;
sell = i;
profit = arr[i] - arr[min];
}
}
System.out.println("We will buy at : " + arr[buy] + " sell at " + arr[sell] +
" and become billionaires worth " + profit );
}
Implemented using two stacks. Runs in O(n), but also has a space complexity of O(n).
public static boolean isMatch(String str, String regex) {
//If the regex is just a * it's always a match
if (regex.equals("*")) return true;
//Create 2 stacks. One for the characters of the
//regular expression, and the other for the string
Stack<Character> strStack = new Stack<Character>();
Stack<Character> regStack = new Stack<Character>();
//Push the characters from each onto their corresponding stacks
for (int i = 0; i < str.length(); i++) {
strStack.push(str.charAt(i));
}
for (int i = 0; i < regex.length(); i++) {
regStack.push(regex.charAt(i));
}
//As long as at least one of the stack is not empty
while (!strStack.empty() || !regStack.empty()) {
//Get the next letter from the string (or null)
char strChar = (strStack.empty()) ? '\0' : strStack.peek();
//Get the next letter from the regex (or null)
char regChar = (regStack.empty()) ? '\0' : regStack.peek();
//If the character is a star, get the letter in the regex
//that is under (proceding in the string) the star (denoted L),
//and continue popping from strStack until the top letter no
//longer equals L.
if (regChar == '*') {
regStack.pop();
regChar = regStack.pop();
while (!strStack.empty() && strStack.peek() == regChar)
strStack.pop();
}
//If the two characters match, pop them off the stack
else if (strChar == regChar) {
strStack.pop();
regStack.pop();
}
//If they don't, and one isn't a star, return false.
else return false;
}
return true;
}
The following is a spin-off of the Kadane algorithm. It runs in O(n) time, and uses O(1) space.
public static void findPairs(int[] arr, int k) {
//This implementation will be similar to the Kadane algorithm
//If there is only one element, return
if (arr.length < 2) return;
//Otherwise, initialize two indices to positions 0 and 1
int lefti = 0;
int righti = 1;
//As long as we haven't reached the end yet
while (lefti < arr.length && righti < arr.length) {
//Find the difference (since it's sorted, this will
//always be positive.
int diff = arr[righti] - arr[lefti];
//If the difference is k, this is a pair, so print it out.
//Then increment both indices by one.
//The reason for this is because if you only incremented the
//left index, the next difference will ALWAYS be smaller
//and if you only incremented the right index, the next
//difference would ALWAYS be larger (because the array
//is sorted) So we increment both.
if (diff == k) {
System.out.println(arr[lefti] + ", " + arr[righti]);
lefti++;
righti++;
}
//If the difference is smaller, increment the right
//index (because it's sorted, we know doing that will
//increase the difference)
else if (diff < k) righti++;
//Otherwise (meaning the difference is smaller) increment
//the left index (because it's sorted, we know doing that
//will decrease the difference)
else {
lefti++;
//The next line is because we never want the two indices
//pointing to the same spot
if (lefti == righti) righti++;
}
}
}
This should run in O(nlogn) time. The bottleneck is in sorting the array. The rest of the algorithm runs in O(n).
- effy November 02, 2015