tomahawk
BAN USERpublic List<int[]> getTriplets(int[] arr){
//First sort the array O(NlogN)
List<int[]> result = new ArrayList();
for(int i=0; i<arr.length; ++i){
if(i > 0 && arr[i] == arr[i-1]) continue; // Avoid duplicates
int left = i+1, right = arr.length - 1;
while(left < right){
int sum = arr[i] + arr[left] + arr[right];
if(sum < 0) l++;
else if(sum > 0) r--;
else{
result.add(new int[]{i, left, right});
while(left < right && arr[left] == arr[left + 1]) left++;
while(left < right && arr[right] == arr[right - 1]) right++;
left++;
right--;
}
}
return result;
}
public int[] product(int[] arr){
int[] res = new int[arr.length];
int nonZeroProduct = 1;
int zeroCount = 0;
for(int a : arr){
if(a == 0){
zeroCount++;
if(zeroCount > 1){
//No chance to have a non zero res for any element
return res;
}
continue;
}
| nonZeroProduct *= a;
}
for(int i=0; i<res.length; ++i){
int curr = res[i];
if(curr == 0){
res[i] = nonZeroProduct;
}else{
res[i] = nonZeroProduct / curr;
}
}
return res;
}
public StringBuilder decode(char [] str, int[] start){
StringBuilder res = new StringBuilder("");
int multi = 0;
for(int i=0; i<str.length; ++i){
char c = str[i];
int multiDigit = 0;
while(c <= '9' && c >= '0' && i<str.length){
int n = Character.getNumericValue(c);
int multi = (int)Math.pow(10, multiDigit++) * n + multi;
++i;
}
if(cn >= 'a' && cn <= 'Z'){
for(int cn=0; cn<multi; ++cn){
res.append(cn);
}
multi = 0;
}
if(c == '['){
StringBuilder sub = decode(str, i+1);
int bracketCount = 1;
while(bracketCount > 0){
++i;
c = str[i];
if(c == '['){
bracketCount++;
}else if(c == ']'){
bracketCount--;
}
}
for(int cn=0; cn<multi; ++cn){
res.append(cn);
}
multi = 0;
}
if(c == ']'){
return res;
}
}
return res;
}
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(new Codechef().getNoWays(29));
}
public int getNoWays(int length){
return getNoWays(length, false);
}
private Map<Integer, Integer> cache = new HashMap();
private int getNoWays(int length, boolean isLowerOccupied ){
if(cache.containsKey(length))
return cache.get(length);
if(length == 0 || length == 1){
cache.put(length, 1);
return 1;
}
int noWays = 0;
if(isLowerOccupied){
noWays = getNoWays(length-2, false);
}
else{
noWays = getNoWays(length-1, false) + getNoWays(length, true);
System.out.println("Evaluated for " + length + " - " + noWays);
cache.put(length, noWays);
}
return noWays;
}
}
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
Set<String> dict = new HashSet();
public Main(){
dict.add("app");
dict.add("apple");
dict.add("applet");
dict.add("t");
dict.add("a");
dict.add("let");
}
public static void main (String[] args) throws java.lang.Exception{
Main c = new Main();
System.out.println(c.getSentences(""));
}
public List<List<String>> getSentences(String str){
return getSentences(str, 0);
}
private List<List<String>> getSentences(String str, int start){
List<List<String>> res = null;
if(start >= str.length()){
res = new ArrayList<List<String>>();
res.add(new ArrayList<String>());
return res;
}
for(int i=start; i<str.length(); ++i){
String subStr = str.substring(start, i+1);
//System.out.println("Sub " + subStr);
if(!dict.contains(subStr)){
continue;
}
else{
//System.out.println("word " + subStr);
List<List<String>> subRes = getSentences(str, i+1);
if(subRes == null){
continue;
}
if(res == null){
res = new ArrayList<List<String>>();
}
for(List<String> sentence : subRes){
List<String> currSentence = new ArrayList<String>();
currSentence.add(subStr);
currSentence.addAll(sentence);
res.add(currSentence);
}
}
}
return res;
}
}
This looks like a variation of Longest subsequence. Instead of doing it on a single array, we are doing it on each path of the tree from root to leaf.
While traversing through the tree(DFS should work) we need to keep track of the continuous sequence ending at that node.
Also need to keep track of the max subsequence and its length until that point in the traversal.
public int getLongest(Node root, List<Node> longestSoFar, List<Node> currentSequence){
if(root == null)
return 0;
for(Node child : root.childen){
//Check if the child not 1 greater than the root. Start new sequence
if(child.value != 1 + root.value){
currentSequence = new ArrayList();
}
currentSequence.add(child);
//Check if the length of sequence ending at this node is greater than the largest sequence found so far. If yes, we have a new longest.
if(currentSequence.size() > longestSoFar.size()){
longestSoFar = currentSequence;
}
getLongest(ch, longestSoFar, currentSequence);
}
//remove current node from sequence before returning up the stack
currentSequence.remove(currentSequence.get(currentSequence.size()-1));
return longestSoFar.size();
public class Test{
public String getWord(int length){
Map<Character, GraphNode> nodes = new HashSet<Character, GrapNode>();
do{
char[] triplet = Util.getTriplets();
for(int i=0; i<3; ++i){
char from = triplet[i];
for(int j=i+1; j<3; ++j){
char to = triplet[j];
if(nodes.containsKey(from)){
nodes.get(from).goingOut.add(to);
}else{
nodes.put(from, new GraphNode(from));
nodes.get(from).goingOut.add(to);
}
if(nodes.containsKey(to)){
nodes.get(to).comingIn.add(from);
}else{
nodes.put(to, new GraphNode(to));
nodes.get(to).goincomingInOut.add(from);
}
}
}
}while(nodes.size() < length && isMoreThanOneNodeHavingNoIncoming(nodes))
}
private boolean isMoreThanOneNodeHavingNoIncoming(nodes){
int noIncomingCount = 0;
for(char c : nodes.keySet()){
if(nodes.get(c).incoming.size() == 0)
noIncoming++;
if(noIncoming > 1)
return true;
}
}
}
class GraphNode{
Set<GraphNode> comingIn, goingOut;//Also, Initialize them
char value;
//Make sure you override equals and hashCode for value;
}
public class Test{
public int ASCII_CODING_DIFF = 67;
private Map<String, Character> codes = new HashMap<String, Character>();
public Test(){
for(char c = 'a'; c<='z'; c++){
int code = c - ASCII_CODING_DIFF + 1;//67
codes.put(code, c);
}
}
public List<StringBuilder> getCombos(String str, int start){
List<StringBuilder> combos = new ArrayList<StringBuidler>();
if(start >= str.length)
combos;
int end = start + 1;
String firstChar = str.subString(start, end+1);//check the javadoc for subString() for what start and end should be. Could be off by 1 here.
while(codes.contains(firstChar)){
Character code = codes.get(firstChar);
List<StringBuilder> subCombos = getCombos(str, end);
for(StringBuilder subCombo : subCombos){
combos.add(code + subCombo);
}
}
return combos;
}
}
public class Test{
public boolean isSumSeq(int[] arr, int sum){
Queue<Integer> seqQ= new PriorityQueue<Integer>();
int currSum = 0;
for(int i : arr){
currSum += i;
if(currSum == sum)
return true;
if(currSum > sum){
while(currSum > sum){
int last = seqQ.pop();
currSum -= last;
}
}
if(currSum == sum)
return true;
}
return false;
}
}
For the first part of finding number of ponds:
public class Pond {
public static final int WATER = 0;
public static final int LAND = 1;
public int[][] matrix;
public Pond(int [][] matrix){
this.matrix = matrix;
}
public int getNoOfPonds(){
boolean [][]visitedPond = new boolean[this.matrix.length][this.matrix[0].length];
//initialize visitedPond
for(int row=0; row<visitedPond.length; row++)
for(int col=0; col<visitedPond[0].length; col++)
visitedPond[row][col] = false;
int noOfPonds = 0;
for(int row=0; row<matrix.length; row++){
for(int col=0; col<matrix[0].length; col++){
if(matrix[row][col] == WATER && visitedPond[row][col] == false){
noOfPonds++;
traversePond(visitedPond, row, col);
}
}
}
return 0;
}
private void traversePond(boolean [][]visited, int row, int col){
//If already visited
if(visited[row][col] == true)
return;
//Check out of bounds
if(row < 0 || row+1 > this.matrix.length || col < 0 || col+1 > this.matrix[0].length)
return;
//Check if we are on land
if(this.matrix[row][col] == LAND)
return;
visited[row][col] = true;
//left
traversePond(visited, row, col-1);
//right
traversePond(visited, row, col+1);
//bottom
traversePond(visited, row+1, col);
//up
traversePond(visited, row-1, col);
}
}
public class Algos {
private Map<Integer, List<List<Integer>>> _cache = new HashMap();
public List<List<Integer>> getSequence(int steps, int maxStep){
if(_cache.containsKey(steps))
return _cache.get(steps);
List<List<Integer>> list = new ArrayList();
if(maxStep > steps )
return list;
if(steps == 1 && maxStep <= steps){
if(_cache.containsKey(1))
return _cache.get(1);
list.add(Arrays.asList(1));
_cache.put(1, list);
return list;
}
if(steps == 0){
return list;
}
for(int firstStep = 1; firstStep <= maxStep; firstStep++){
List<List<Integer>> subList = getSequence(steps - firstStep, maxStep);
for(List<Integer> sequence : subList){
sequence.add(firstStep);
}
list.addAll(subList);
}
_cache.put(steps, list);
return list;
}
}
public int[] getMagicSort(int[] a){
int firstNeg=0;
for(int start=0; start < a.length; start++){
while(firstNeg < a.lenght){
if(a[firstNeg] < 0){
break;
}
firstNeg++;
}
percolate(a, start, firstNeg);
}
}
private void percolate(int[] a, int sI, int eI){
if(eI <= sT)
return;
int temp = a[eI-1];
a[eI-1] = a[eI];
a[eI] = temp;
percolate(int a, sI, eI-1);
}
public Triple<Integer, Integer, Integer> getMinRange(List<Integer> l1, List<Integer> l2, List<Integer> l3){
Tripe<Integer, Integer, Integer> mT = Create.newTriple();
int min = Integer.MAXIMUM;
for(int e1 : l1){
for(int e2 : l2){
if(mod(e1, e2) > min){
if(e2 >= e1){
break;
}
continue;
}
for(e3 : l3){
int min12 = Math.min(e1, e2);
if(mod(e3, min12) > min){
if(e3 > min12){
break;
}
continue;
}
mT = new Triple(e1, e2, e3);
min = mod(min12, e3);
}
}
}
return mT;
}
// Worst case complexity O(mno)
// But average case is much less
- tomahawk August 07, 2017