blurred
BAN USERCode uses BST and uses Log(n) time. Can be done in contant time using hash tables, but will need extra space.
class RepeatedCount{
private static class BST{
private static class Node{
private int value;
private int count;
private Node left;
private Node right;
private Node(int val){
value = val;
count = 1;
}
}
private Node root = null;
private void put(int val){
root = put(root, val);
}
private Node put(Node rt, int val){
if(rt == null){
Node node = new Node(val);
return node;
}
if(val < rt.value){
rt.left = put(rt.left, val);
}
else if(val > rt.value){
rt.right = put(rt.right, val);
}
else if(val == rt.value){
rt.count++;
}
return rt;
}
private void traverse(){
traverse(root);
}
private void traverse(Node rt){
if(rt == null) return;
traverse(rt.left);
System.out.println("Value:" + rt.value + " present " + rt.count + "times");
traverse(rt.right);
}
}
public static void printRepeats(Integer[] arr){
System.out.println("printing repeats");
BST bst = new BST();
for(int x:arr){
bst.put(x);
}
bst.traverse();
}
}
class BinaryTree<K>{
private class Node{
K value;
Node left;
Node right;
Node(K val){
value = val;
left = null;
right = null;
}
}
/* Queue/Stack Implementation */
private class Queue{
private class NodeQ{
Node valNode;
NodeQ next;
NodeQ(Node val){
this.valNode = val;
}
}
private NodeQ HEAD = null;
private NodeQ TAIL = null;
private void enque(Node val){
if(val == null) return;
NodeQ nodeq = new NodeQ(val);
if(TAIL == null){
TAIL = nodeq;
HEAD = nodeq;
}
else{
TAIL.next = nodeq;
TAIL = nodeq;
}
}
private void push(Node val){
if(val == null) return;
NodeQ nodeq = new NodeQ(val);
if(HEAD == null){//empty queue
HEAD = nodeq;
TAIL = nodeq;
}
else{
nodeq.next = HEAD;
HEAD = nodeq;
}
}
private Node deque(){
if(HEAD == null)
return null;
Node retNode = HEAD.valNode;
HEAD = HEAD.next;
if(HEAD == null)
TAIL = null;//queue is empty
return retNode;
}
private boolean isEmpty(){
return (HEAD == null);
}
}
/* End of Queue implementation*/
private Node root;
/* Fill method in horizontal manner*/
public void put(K val){
Node node = new Node(val);
if(root == null){
root = node;
return;
}
Node rt = root;
Queue q = new Queue();
q.enque(rt);
while(!q.isEmpty()){
Node popped = q.deque();
if(popped.left == null){
popped.left = node;
return;
}
else
q.enque(popped.left);
if(popped.right == null){
popped.right = node;
return;
}
else
q.enque(popped.right);
}
}
/* In order traverse*/
public void inOrdertraverse(){
traverseIn(root);
}
private void traverseIn(Node r){
if(r == null) return;
traverseIn(r.left);
System.out.println(r.value);
traverseIn(r.right);
}
public void horizontalTraverse(){
Node rt = root;
Queue q = new Queue();
q.enque(rt);
while(!q.isEmpty()){
Node popped = q.deque();
System.out.println(popped.value);
if(popped.left != null){
q.enque(popped.left);
}
if(popped.right != null){
q.enque(popped.right);
}
}
}
public void zigzagTx(){
Queue queue = new Queue();
Node rt = root;
queue.enque(rt);
if(rt!= null)
System.out.println(rt.value);
boolean toggled = false;
while(true){
Queue Q1 = new Queue();//to carry fwd the process
Queue Q2 = new Queue();//for prints
while(!queue.isEmpty()){
Node x = queue.deque();
if(x.left != null){
Q1.enque(x.left);
if(!toggled)
Q2.enque(x.left);
else
Q2.push(x.left);
}
if(x.right != null){
Q1.enque(x.right);
if(!toggled)
Q2.enque(x.right);
else
Q2.push(x.right);
}
}
if(Q1.isEmpty()) break;
queue = Q1;
while(!Q2.isEmpty()){
System.out.println(Q2.deque().value);
}
if(toggled)
toggled = false;
else
toggled = true;
}
}
}
Implemented in C, a hashmap for <string, string> map. Used a chained hashing method
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define N 20
typedef struct X{
char* key;
char* value;
struct X* next;
}Node;
Node* hasharray[N] = {NULL};
int hashcalc(char* key){
int val = 0;
int count = 0;
while(*key != 0){
val = val*(*key) + *key + count;
count++;
key++;
}
if(val < 0) val *= -1;
val = val%N;
return val;
}
void put(char* key, char* value){
int hashval = hashcalc(key);
Node* nd = hasharray[hashval];
while(nd != NULL){
if(strcmp(nd->key, key) == 0){
nd->value = value;
return;
}
}
nd = (Node*) malloc(sizeof(Node));
nd->key = key;
nd->value = value;
nd->next = hasharray[hashval];
hasharray[hashval] = nd;
}
char* get(char* key){
int hashval = hashcalc(key);
Node* nd = hasharray[hashval];
while(nd != NULL){
if(strcmp(key, nd->key) == 0){
return nd->value;
}
}
}
void main(){
printf("%s\n", __func__);
put("alpha","bravo");
put("zero", "0");
put("alpha", "charlie");
printf("%s\n", get("alpha"));
printf("%s\n", get("zero"));
}
class CheckFormat{
public static boolean isNumber(String input){
char[] arr = input.toCharArray();
boolean isNumber = true;
boolean isDotted = false;
for(int n = 0; n < arr.length; n++){
if(arr[n] == '-' && n == 0)
continue;
else if(((arr[n] - '0') >= 0) && ((arr[n]-'0') <= 9))
continue;
else if(arr[n] == '.' && !isDotted){
isDotted = true;
continue;
}
else{
isNumber = false;
break;
}
}
if(isDotted && (arr[arr.length - 1] == '.'))
isNumber = false;
return isNumber;
}
}
#include<stdio.h>
typedef int (*simpleCompute) (int, int);
typedef struct{
simpleCompute fun;
} functionStruct;
int sum(int a, int b){
return a+b;
}
int prod(int a, int b){
return a*b;
}
void main(int args[])
{
printf("hello world\n");
functionStruct* ptr;
functionStruct obj1;
functionStruct obj2;
obj1.fun = sum;
obj2.fun = prod;
ptr = &obj1;
printf("caling fun using first assignment: %d\n", ptr->fun(2, 4));
ptr = &obj2;
printf("caling fun using first assignment: %d\n", ptr->fun(2, 4));
}
import java.util.ArrayList;
import java.util.List;
class SumToX{
static List<Integer> list = new ArrayList<>();
public static void printsums(int X, int[] arr){
sumToX(arr, X, 0, 0);
}
private static void sumToX(int[] arr, int X, int total, int index){
if(total > X) return;
if(total == X){
for(Integer y:list){
System.out.print(" " + y);
}
System.out.println("");
return;
}
for(int n = index; n <= X && n < arr.length; n++){
list.add(arr[n]);
sumToX(arr, X, total+arr[n], n+1);
list.remove((Integer)arr[n]);
}
}
}
import java.util.HashSet;
import java.util.*;
class Anagram1{
private static String inputStr;
private static Set<String> set=new HashSet<>();
public static void permute(String arg){
inputStr = new String(arg);
System.out.println("inputStr = " + inputStr + " len:" + inputStr.length());
permute("", 0, new boolean[inputStr.length()]);
for(String x:set){
System.out.println(x);
}
}
private static void permute(String str, int index, boolean[] used){
if(index == inputStr.length()){
set.add(str);
return;
}
else{
for(int n = 0; n < inputStr.length(); n++){
if(used[n]){
continue;
}
used[n] = true;
set.add(str);
permute(str + inputStr.charAt(n), index+1, used);
used[n] = false;
}
}
}
}
import java.util.ArrayDeque;
import java.util.Deque;
class RevChars{
public static String reverse(String input){
System.out.println("Input string is " + input);
Deque<Character> stack = new ArrayDeque<>();
String retStr = "";
if(input == null) return null;
for(Character x: input.toCharArray()){
if(x == ' '){
while(stack.size() != 0)
retStr = retStr + stack.pop();
retStr = retStr + x;
}
else{
stack.push(x);
}
}
while(stack.size() != 0)
retStr += stack.pop();
return retStr;
}
}
- blurred July 26, 2015