jasmeet@iastate.edu
BAN USERHow would you know the pages are unique?
- jasmeet@iastate.edu January 15, 2013Store states of the progress in a stack.
- jasmeet@iastate.edu January 14, 2013explained it here - jasmeetsingh.net/wordpress/?p=55
- jasmeet@iastate.edu January 14, 2013If you know the distance from a to b and a to c, you don't need to store the distance from b to c
- jasmeet@iastate.edu January 14, 2013Space - O(n)
Time - O(n)
package strings;
import java.util.HashSet;
import java.util.Set;
public class CyclicSetOfStrings {
public CyclicSetOfStrings()
{
Set<String> s = new HashSet<String>();
s.add("aba");
s.add("cde");
s.add("eff");
s.add("gnj");
s.add("fgg");
s.add("jba");
s.add("abc");
checkCycle(s);
}
private void checkCycle(Set<String> s) {
HashSet<Character> first = new HashSet<Character>();
HashSet<Character> second = new HashSet<Character>();
boolean existsIn2nd = false;
boolean existsIn1st = false;
char f, l;
for(String str: s)
{
f = str.charAt(0);
l = str.charAt(str.length()-1);
if(second.contains(f))
{
existsIn2nd = true;
second.remove(f);
}
if(first.contains(l))
{
existsIn1st = true;
first.remove(l);
}
if(!existsIn2nd)
first.add(f);
if(!existsIn1st)
second.add(l);
existsIn2nd = false;
existsIn1st = false;
}
if(first.size() == 0)
System.out.println("Cycle found");
else System.out.println("No Cycle found");
}
}
package strings;
import java.util.ArrayList;
public class tupleSubstitute {
public tupleSubstitute() {
String tuple = "(a,b,c,d)";
ArrayList<String> out = new ArrayList<String>();
out.add("(*,*,*,*)");
String tmp;
int i =1;
int n =tuple.length() -2;
while(i<16)
{
for(int j =0; j< i; j++)
{
tmp = out.get(j);
tmp = tmp.substring(0,n) + tuple.charAt(n) + tmp.substring(n+1);
out.add(tmp);
}
i = out.size();
n -=2;
}
}
}
If frequency is just an additional value and not the key value, the in-order traversal will take place on the key value and not the frequency
- jasmeet@iastate.edu January 10, 2013This is a simple dynamic programming implementation.
Suppose our sentence = "words are shuffled"
input string = "swodsaerheldfsfu"
Start with the fist letter and see if it is in the dictionary(or its jumbled form). If not, move to the next letter and see if both first and second letter form a word. Suppose "sow" is in the dictionary. Now we move to the next letter and again try to find a word starting with this letter. If we form a sentence from the dictionary we stop(we can also keep looking for other sentences). If not, we go back to the previous word we found and mark it invalid. We now try to move forward in our usual manner and try to find another word.
Whenever you find a character sequence to be or not be in the dictionary, store it(and its jumpbled forms) in a hashMap. And before performing findJumpledWordInDictionary() operation, consult the hashMap for the word
If dictionary is small, preprocess the dictionary and sort the words and store in a hasSet, and while checking if a character sequence is in the dictionary, sort the character sequence and knock yourself out :)
This is a simple dynamic programming implementation.
Suppose our sentence = "words are shuffled"
input string = "swodsaerheldfsfu"
Start with the fist letter and see if it is in the dictionary(or its jumbled form). If not, move to the next letter and see if both first and second letter form a word. Suppose "sow" is in the dictionary. Now we move to the next letter and again try to find a word starting with this letter. If we form a sentence from the dictionary we stop(we can also keep looking for other sentences). If not, we go back to the previous word we found and mark it invalid. We now try to move forward in our usual manner and try to find another word.
Whenever you find a character sequence to be or not be in the dictionary, store it(and its jumpbled forms) in a hashMap. And before performing findJumpledWordInDictionary() operation, consult the hashMap for the word
Also found in - jasmeetsingh.net/wordpress/?p=36
/*
* Source: Wikipedia
*
* In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
T
*/
package BST;
public class MaxSubArray {
int arr[] = new int[]{-2, 1, -3, -4, -1, 2, 1, -5, 4};
public MaxSubArray() {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minPointer = 0;
int maxPointer = 0;
int subArrSum = 0;
for(int i =0;i<arr.length;i++)
{
subArrSum += arr[i];
if(subArrSum<min)
{
minPointer = i;
min = subArrSum;
}
if (subArrSum>max)
{
maxPointer = i;
max = subArrSum;
}
}
minPointer++;
if(minPointer >= maxPointer)
{
min = 0;
minPointer = 0;
}
System.out.println(max - min);
for(int i = minPointer; i<=maxPointer;i++)
{
System.out.print(arr[i] + " ");
}
}
}
/*A binary tree is given with left and right populated but the nextRight pointers in each node are not populated. Populate the nextRight pointer in each node.*/
package BST;
public class PopulateNextRight {
BST bst = new BST();
public PopulateNextRight() {
bst.createDummyBST();
bst.printBSTInOrder(bst);
populate(bst);
printLastRights(bst);
}
private void printLastRights(BST node) {
if(node == null)
return;
BST dummyNode = node;
while(dummyNode != null) {
System.out.print(dummyNode.data + " ");
dummyNode = dummyNode.nextRight;
}
System.out.println();
printLastRights(node.left);
printLastRights(node.right);
}
public void populate(BST node){
if(node == null) {
return;
}
if(node.right !=null && node.left !=null) {
node.left.nextRight = node.right;
assignNextRight(node.right,node.nextRight);
}
else if(node.right !=null) {
assignNextRight(node.right,node.nextRight);
}
else if(node.left !=null){
assignNextRight(node.left,node.nextRight);
}
populate(node.left);
populate(node.right);
}
void assignNextRight(BST node, BST uncle){
if(uncle == null)
return;
if(uncle.left !=null)
node.nextRight = uncle.left;
else if(uncle.right !=null)
node.nextRight = uncle.right;
else
assignNextRight(node, uncle.nextRight);
}
}
package BT;
import java.util.ArrayList;
public class DoubleArrayParentChildConfig {
public DoubleArrayParentChildConfig(){
BT bt = new BT();
bt.createDummyBT();
int[][] arr = new int[10][10];
calcArray(bt, null, arr);
bt = new BT();
}
private void calcArray(BT node, BT daddy, int[][] arr) {
if(node == null && daddy == null)
return;
else if(node == null)
{
return;
}
else if(daddy== null)
{
recursiveCallToCalcArray(node, node, arr);
}
else
{
recursiveCallToCalcArray(node, node, arr);
recursiveCallToCalcArray(node, daddy, arr);
}
}
private void recursiveCallToCalcArray(BT node, BT node2, int[][] arr) {
if(node.left !=null)
{
arr[node2.data][node.left.data] = 1;
calcArray(node.left, node2, arr);
}
if(node.right !=null)
{
arr[node2.data][node.right.data] = 1;
calcArray(node.right, node2, arr);
}
}
}
package Numbers;
import java.util.HashSet;
import java.util.Stack;
public class NextLargestInArray {
int[] arr;
Stack<Integer> stack = new Stack<Integer>();
public NextLargestInArray() {
arr = new int[] {1,9,5,3,4,12,7};
findNextLargest();
}
private void findNextLargest() {
int temp= 0;
for(int i :arr)
{
if(stack.isEmpty())
{
stack.push(i);
continue;
}
while(!stack.isEmpty())
{
temp = stack.peek();
if(i > temp)
{
System.out.println(temp + "->" + i);
stack.pop();
}
else break;
}
stack.push(i);
}
while(!stack.isEmpty())
{
System.out.println(stack.pop() + "->" + -1);
}
}
}
Actually, we got the question wrong.
- jasmeet@iastate.edu December 18, 2012use djikstra algo
- jasmeet@iastate.edu September 14, 2012solution(BT root)
{
root.data = sumandzero(root);
}
public static int sumandzero(BT root)
{
int k=root.data;
if(root==null)
return 0;
if(root.left==null&&root.right==null)
{
root.data=0;
return k;
}
k+=sumandzero(root.left);
k+=sumandzero(root.right);
return k;
}
Use Knade's algo
Store leftmost leaf's value in s0 and root in s1. if s0 + s1 < sum go to parent of leftmost leaf, else go towards root's child.
You need to use recursion.
Something like that, shouldn;t be hard to implement
I am not sure if the greedy approach always works..
- jasmeet@iastate.edu January 16, 2013Consider this example - you have to cater 98 cents and you have 50*1 , 20*2, 15*1, 10*1, 1*8... (n*m means you have m instances of n cents)
Greedy answer - 50 * 1 + 20 * 2 + 1 * 8. Total Coins = 11
DP answer - 50*1 + 20*1 + 15*1 + 10*1 + 1*3. Total Coins = 7