jsayyy
BAN USERO(s+k), where s is number of shards, k number of keys.
1) Iterate over the list of Shard
2) For current shard, iterate over List of Key until currentKey.start < currentShard.end
public List<Range> getRanges(List<Shard> shards, List<Key> keys){
List<Range> ranges = new ArrayList<>();
int shardP = 0;
int keyP = 0;
while(shardP < shards.size()){
Shard shard = shards.get(shardP);
Key key = keys.get(keyP);
while(keyP < keys.size() && keys.get(keyP).start < shard.end ){
keyP++;
}
int rangeEnd = Math.min(keys.get(keyP-1).end, shard.end);
int rangeStart = Math.max(key.start, shard.start);
Range range = new Range(rangeStart, rangeEnd);
ranges.add(range);
shardP++;
}
return ranges;
}
Iterative solution.
public ArrayList<String> getAllPaths(TreeNode<Integer> root){
if(root == null) return null;
Queue queue = new Queue();
queue.enqueue(root);
queue.enqueue(String.valueOf(root.getData()));
ArrayList<String> result = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode<Integer> currNode = (TreeNode<Integer>) queue.dequeue();
String currPath = (String) queue.dequeue();
if(currNode.isLeaf()){
result.add(currPath);
continue;
}
if(currNode.getLeft() != null){
TreeNode<Integer> leftNode = currNode.getLeft();
queue.enqueue(leftNode);
currPath += " -> " + String.valueOf(leftNode.getData());
queue.enqueue(currPath);
}
if(currNode.getRight() != null){
TreeNode<Integer> rightNode = currNode.getRight();
queue.enqueue(rightNode);
currPath += " -> " + String.valueOf(rightNode.getData());
queue.enqueue(currPath);
}
}
return result;
}
First, illuminate the lamps (preprocessing), so that new grid point lookup is constant time O(1).
public class LampIlluminationGrid {
private static class Lamp{
private int row;
private int col;
public Lamp(int row, int col){
this.row = row;
this.col = col;
}
}
private boolean[][] grid;
public LampIlluminationGrid(int n, Lamp[] lampsCoordinates){
grid = new boolean[n][n];
for(Lamp lamp : lampsCoordinates){
int targetRow = lamp.row;
int targetCol = lamp.col;
// illuminate row.
for(int c = 0; c < n; c++){
grid[targetRow][c] = true;
}
// illuminate col
for(int r = 0; r < n; r++){
grid[r][targetCol] = true;
}
// illuminate diagonal.
int r = targetRow;
int c = targetCol;
while(r >= 0 && c >=0){
grid[r][c] = true;
r--;
c--;
}
r = targetRow;
c = targetCol;
while(r < n && c < n){
grid[r][c] = true;
r++;
c++;
}
r = targetRow;
c = targetCol;
while(r >= 0 && c < n){
grid[r][c] = true;
r--;
c++;
}
r = targetRow;
c = targetCol;
while (r < n && c >= 0){
grid[r][c] = true;
r++;
c--;
}
}
}
public boolean isGridPointIlluminated(Lamp targetPoint){
if(targetPoint == null || targetPoint.row < 0 || targetPoint.col < 0
|| targetPoint.row >= grid.length || targetPoint.col >= grid.length){
throw new IllegalArgumentException();
}
return grid[targetPoint.row][targetPoint.col];
}
public static void main(String[] args) {
Lamp[] lamps = {new Lamp(2, 1)};
// , new Lamp(2, 2)};
int N = 5;
LampIlluminationGrid lampIlluminationGrid = new LampIlluminationGrid(N, lamps);
for(int row = 0; row < N; row++){
System.out.println(Arrays.toString(lampIlluminationGrid.grid[row]));
}
Lamp target = new Lamp(0,1);
System.out.println("targetPoint: "+lampIlluminationGrid.isGridPointIlluminated(target));
}
}
Note that n-ary tree is nothing but an acyclic Directed-Graph with a starting node given (root).
The longest sequence from leaf to leaf is the pair of longest two root-to-leaf paths. We will return the longest two paths in n-ary tree.
So, we use our own Directed-Graph data structure to solve this problem.
Output: [[1, 5, 15, 21, 19], [1, 2, 7, 9, 11, 25]], where 1 is the root.
// No weight of edges considered.
public class DiGraph<T>{
private class GraphNode<T>{
private T data;
private HashSet<GraphNode<T>> neighbors;
public GraphNode(T data){
this.data = data;
neighbors = new HashSet<>();
}
}
private HashMap<T, GraphNode<T>> allNodes;
}
public class LongestPathN_aryTree {
public ArrayList<ArrayList<Integer>> getLongestPath(GraphNode<Integer, Integer> startNode){
if(startNode == null) return null;
Queue queue = new Queue();
queue.enqueue(startNode);
ArrayList<Integer> list = new ArrayList<>();
list.add(startNode.getData());
queue.enqueue(list);
// We do not have to store all Paths and then find the longest two.
// We save/update the longest two paths each time a leaf node is met.
// init variables for referencing maxSizePath and secondMaxSizePath
int maxListSize = -1;
ArrayList<Integer> maxList = null;
int secondMaxListSize = -1;
ArrayList<Integer> secondMaxList = null;
while(!queue.isEmpty()){
GraphNode<Integer, Integer> currNode = (GraphNode<Integer, Integer>) queue.dequeue();
ArrayList<Integer> currPath = (ArrayList<Integer>)queue.dequeue();
int currPathSize = currPath.size();
if(currNode.getNeighbors().size() == 0){
if(maxListSize < currPathSize){
secondMaxListSize = maxListSize;
secondMaxList = maxList;
maxListSize = currPathSize;
maxList = currPath;
}else if(secondMaxListSize < currPathSize){
secondMaxListSize = currPathSize;
secondMaxList = currPath;
}
continue;
}
for(GraphNode<Integer, Integer> nbr : currNode.getNeighbors()){
ArrayList<Integer> currPathCopy = new ArrayList<>(currPath);
currPathCopy.add(nbr.getData());
queue.enqueue(nbr);
queue.enqueue(currPathCopy);
}
}
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
result.add(secondMaxList);
result.add(maxList);
return result;
}
public static void main(String[] args) {
DiGraph<Integer,Integer> graph = new DiGraph<>();
graph.addEdge(1, 2);
graph.addEdge(1, 5);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 7);
graph.addEdge(7, 9);
graph.addEdge(2, 10);
graph.addEdge(5, 15);
graph.addEdge(15, 21);
graph.addEdge(9, 11);
graph.addEdge(21, 19);
graph.addEdge(11, 25);
LongestPathN_aryTree longestPathN_aryTree = new LongestPathN_aryTree();
GraphNode<Integer, Integer> graphNode = graph.getNode(1);
ArrayList<ArrayList<Integer>> result = longestPathN_aryTree.getLongestPath(graphNode);
System.out.println(result);
}
}
Relatively simple problem. Using StringBuilder (or StringBuffer) is the key here.
public class StringFormatLengthK {
public String reformatString(String input, int k){
if(input == null || input.length() == 0){
return null;
}
String[] arr = input.split("-");
StringBuilder sbTemp = new StringBuilder();
for(String str : arr){
sbTemp.append(str);
}
String plainString = sbTemp.toString();
System.out.println("plainString: "+plainString);
int counter = 1;
StringBuilder sb = new StringBuilder();
for(int i = plainString.length()-1; i >= 0; i--){
String str = plainString.substring(i, i+1);
sb.append(str);
if(counter == k) {
sb.append("-");
counter = 0;
}
counter++;
}
String lastChar = sb.substring(sb.length()-1);
if("-".equals(lastChar)){
sb.deleteCharAt(sb.length()-1);
}
sb.reverse();
return sb.toString();
}
public static void main(String[] args) {
StringFormatLengthK stringFormatLengthK = new StringFormatLengthK();
String input = "2-4a0r7-4k";
String reformattedString = stringFormatLengthK.reformatString(input, 5);
System.out.println("reformatted: "+ reformattedString);
}
}
Here is one way to do it
1) Preprocess the dictionary (ArrayList<String>):
--- (a) for each word in the dictionary, generate all permutations (considering the fact that characters can repeat in dictionary words).
--- (b) add each of the permutation to a Trie (saves space for repeated permutations across all words in the dictionary).
2) Write a separate method in Trie where in, while searching, if a leaf node is reached before the input word ends, returns the length of the valid word (traversed till now). This mechanism can be used mainly for adding spaces to an input string (Re-Space problem).
3) Finally, for each suffix in the input sentence (substring starting at each index), search in the Trie using the new function defined above (the advantage here is, since we find a matching word in Trie, we can skip our iteration index by that length, thereby skipping all the suffixes in between).
class Trie{
private TrieNode root;
class TrieNode{
char c;
HashMap<Character, TrieNode> children;
boolean isLeaf;
}
/*
* Trie method as mentioned above in (2)
*/
public int getLengthOfMatchingWord(String word){
// If a leaf node is reached before word ends, then return the length of the valid word from Trie.
TrieNode node = root;
for(int i =0; i<word.length(); i++){
Character c = word.charAt(i);
node = node.getChildren().get(c);
if(node == null){
return -1;
}
if(node.isLeaf()){
return i;
}
}
// If word finishes before the Trie word/s
return -1;
}
}
public class UnscrambleInput {
private Trie trie;
private HashMap<String, String> permutationToValidWordMap;
public UnscrambleInput(){
trie = new Trie();
permutationToValidWordMap = new HashMap<>();
}
private ArrayList<String> getAllPermutations(String input){
if(input == null || input.length() == 0){
return null;
}
ArrayList<String> result = new ArrayList<>();
HashMap<Character, Integer> freqMap = new HashMap<>();
for(Character c : input.toCharArray()){
if(!freqMap.containsKey(c)){
freqMap.put(c, 0);
}
freqMap.put(c, 1+freqMap.get(c));
}
generatePermutations(result, freqMap, "", input.length(), input);
return result;
}
private void generatePermutations(ArrayList<String> result, HashMap<Character, Integer> freqMap,
String prefix, int remaining, String input){
if(remaining == 0){
result.add(prefix);
permutationToValidWordMap.put(prefix, input);
return;
}
for(Character c : freqMap.keySet()){
int count = freqMap.get(c);
if(count > 0){
freqMap.put(c, count-1);
generatePermutations(result, freqMap, prefix+c, remaining-1, input);
freqMap.put(c, count);
}
}
}
private void preprocess(ArrayList<String> dictionary){
for(String word : dictionary){
ArrayList<String> permutations = getAllPermutations(word);
for(String permutation : permutations){
trie.addWord(permutation);
}
}
}
public String unscrambleSentence(String inputSentence, ArrayList<String> dictionary){
if(inputSentence == null || inputSentence.length() == 0 || dictionary == null || dictionary.size() == 0){
return null;
}
preprocess(dictionary);
StringBuilder sb = new StringBuilder();
// from here, apply the logic that splits words (add spaces) in a sentence
for(int i = 0; i < inputSentence.length(); i++){
String currStr = inputSentence.substring(i);
int endIndex = trie.getLengthOfMatchingWord(currStr);
if(endIndex > 0){
String foundPermutation = inputSentence.substring(i, i + endIndex+1);
String validWord = permutationToValidWordMap.get(foundPermutation);
sb.append(validWord);
sb.append(" ");
i += endIndex-1;
}
}
return sb.toString();
}
public static void main(String[] args) {
ArrayList<String> dictionary = new ArrayList<>();
dictionary.add("these");
dictionary.add("the");
dictionary.add("to");
dictionary.add("together");
dictionary.add("much");
dictionary.add("hello");
dictionary.add("these");
dictionary.add("world");
dictionary.add("say");
dictionary.add("yes");
dictionary.add("jaffa");
UnscrambleInput unscrambleInput = new UnscrambleInput();
String unscrambled = unscrambleInput.unscrambleSentence("asyelhloeehtrgottohtedrowl", dictionary);
System.out.println("unscrambled: "+ unscrambled);
}
}
I believe this could be solved in O(1) Time, O(1) Space, using discharge rate.
Please correct if it is wrong.
1) Every row can be considered a a power of 11, meaning each digit in the power of 11, is the fill rate of the glass. Ex: row 5 is: 1 4 6 4 1 => end glasses in this row fill at (1/pow(2,4)) rate and glass 2 fills at 2*(1/pow(2,4)) and glass 3 fills at 6*(1/pow(2,4)) rate.
2) For a given amountX, and row i and glass j, we subtract the amount of water already consumed till the previous row and use the remaining water for current row by multiplying with the initialized discharge rate.
- jsayyy November 04, 2016