algorithmor
BAN USERI like to study algorithms
Use Radix Sort for better performance
- algorithmor December 02, 2015This is quite a complex problem, depending upon the type of data a node stores. For a node containing value that can be represented as a string a pre-order traversal can be stored, with null values represented as a special character that is guaranteed to not occur as a node value.
The following working code is for a binary search tree, but the concept should ideally work on any binary tree. To verify, a bst is serialized and then deserialised. The deserialized tree is again serialized to see if the serialized strings are the same.
import java.util.StringTokenizer;
public class SerializableBinarySearchTree<K extends Comparable<K>>{
private static final long serialVersionUID = -8047345267967142073L;
private Node<K> root;
public Node<K> getRoot() {
return root;
}
public void add(K key){
root = add(root,key);
}
private Node<K> add(Node<K> node,K key){
if(node == null){
return new Node<K>(key);
}
int compare = key.compareTo(node.key);
if(compare < 0){
// progress in left sub-tree
node.left = add(node.left,key);
}else if(compare > 0){
// progress in right sub-tree
node.right = add(node.right,key);
}else{
// key-match. Overwrite value
node.key = key;
}
return node;
}
public Node<K> getNode(K key){
Node<K> n = root;
while(n != null){
int compare = key.compareTo(n.key);
if(compare < 0){
// progress in left sub-tree
n = n.left;
}else if(compare > 0){
// progress in right sub-tree
n = n.right;
}else{
// key-match. return node
return n;
}
}
// the node is not found in tree with this key
return null;
}
public K min(){
if(root.left == null){
return root.key;
}else{
return min(root.left).key;
}
}
private Node<K> min(Node<K> root){
if(root.left == null){
return root;
}else{
return min(root);
}
}
public K max(){
if(root.right == null){
return root.key;
}else{
return max(root.right).key;
}
}
private Node<K> max(Node<K> root){
if(root.right == null){
return root;
}else{
return max(root);
}
}
public void delete(Key<K> key){
//TODO
}
public boolean isInOrderSame(Node<K> root1, Node<K> root2){
boolean same = true;
if(root1 == null && root2 == null){
return same;
}else if((root1 == null && root2!=null)||(root1!= null && root2 == null)){
same = false;
return same;
}else{
if(root1.key.equals(root2.key)){
same &= isInOrderSame(root1.left,root2.left);
same &= isInOrderSame(root1.right,root2.right);
}else{
same = false;
return same;
}
}
return same;
}
public String serialize(){
StringBuilder sb = new StringBuilder();
recursiveSerialize(root,sb);
return sb.toString();
}
private void recursiveSerialize(Node root,StringBuilder sb){
if(root == null){
sb.append("#").append(',');
}else{
sb.append(root.key).append(',');
recursiveSerialize(root.left,sb);
recursiveSerialize(root.right,sb);
}
}
private SerializableBinarySearchTree<K> deserialize(String sTree){
SerializableBinarySearchTree<K> bst = new SerializableBinarySearchTree<K>();
StringTokenizer st = new StringTokenizer(sTree,",");
SerializableBinarySearchTree<K>.Node<K> node = recursiveDeserialize(st);
bst.root = node;
return bst;
}
private Node<K> recursiveDeserialize(StringTokenizer st){
Node<K> returnNode = null;
if(st.hasMoreTokens()){
String token = st.nextToken();
if(!token.equals("#")){
returnNode = new Node((K)token);
returnNode.left = recursiveDeserialize(st);
returnNode.right = recursiveDeserialize(st);
}
}
return returnNode;
}
class Node<T extends Comparable<T>>{
T key;
Node<T> left,right;
public Node(T key){
this.key = key;
this.left = null;
this.right = null;
}
public Node(T key,Node<T> left, Node<T> right){
this.key = key;
this.left = left;
this.right = right;
}
}
public static void main(String[] args) {
SerializableBinarySearchTree<String> bst1 = new SerializableBinarySearchTree<String>();
bst1.add("D");
bst1.add("B");
bst1.add("F");
bst1.add("A");
bst1.add("C");
bst1.add("E");
//System.out.println(bst1.isInOrderSame(bst1.getRoot(), bst2.getRoot()));
String bst1Serialize = bst1.serialize();
System.out.println(bst1Serialize);
SerializableBinarySearchTree<String> bst2 = bst1.deserialize(bst1Serialize);
String bst2Serialize = bst2.serialize();
System.out.println(bst2Serialize);
}
}
public static String maxUniqueSubstring(String s){
int strlen = s.length();
StringBuilder sb = new StringBuilder(strlen); // Use StringBuilder to save memory.
String previousMax = ""; // The previous Max substring encountered
String max = ""; // The current max substring
boolean updateFlag = false; // Should max be updated from the StringBuilder
Map<Character,Integer> fMap = new HashMap<Character,Integer>();
for(int i=0;i<strlen;i++){
Character nextChar = s.charAt(i);
if(fMap.containsKey(nextChar)){ //character already present in current max
// check whether to update max
if(updateFlag){
max = sb.toString();
updateFlag=false;
}
sb = new StringBuilder(); // reset the StringBuilder
sb.append(nextChar);
fMap.clear();
fMap.put(nextChar,1);
// update previousMax if current max is longer
if(max.length()>previousMax.length()){
previousMax = max;
}
}else{
// keep adding character to the builder
sb = sb.append(nextChar);
fMap.put(nextChar,1);
if(max.length() < sb.length() && updateFlag==false){
updateFlag=true; // Set the flag to update max when a duplicate occurs
}
}
}
// choose the maximum between previousMax and max
if(previousMax.length()>max.length()){
max = previousMax;
}
return max;
}
Based upon the approach mentioned by CT in the first comment this is a class in Java
public class DoubleLinkListUsingStack<E> {
private Stack<E> h = new Stack<E>();
private Stack<E> t = new Stack<E>();
private int size = 0;
/*
* Returns number of elements in the list
*/
public int size(){
return size;
}
/*
* Inserts the specified element at the beginning of this list.
*/
public void addFirst(E element){
if(h.empty()){
h.push(element);
}else{
while(!h.empty()){
t.push(h.pop());
}
h.push(element);
}
size++;
}
/*
* Inserts the specified element at the end of this list.
*/
public void addLast(E element){
if(t.empty()){
t.push(element);
}else{
while(!t.empty()){
h.push(t.pop());
}
t.push(element);
}
size++;
}
/*
* Inserts the specified element at the specified index
*/
public void add(int index, E element){
if(index > size){
// Can't insert
System.out.println("Index out of bounds");
}else{
if(h.size() > index){
while(h.size()>index){
t.push(h.pop());
}
h.push(element);
size++;
}else{
while(h.size()<= index){
h.push(t.pop());
}
h.push(element);
size++;
}
}
}
/*
* Returns the index of the first occurrence of the specified element in this list,
* or -1 if this list does not contain the element.
*/
public int indexOf(E element){
while(!h.empty()){
t.push(h.pop());
}
while(t.peek()!= element){
h.push(t.pop());
}
if(t.empty()){
return -1;
}else{
return h.size();
}
}
/*
* Returns true if this list contains the specified element.
*/
public boolean contains(E element){
return indexOf(element) >= 0;
}
/*
* Replaces the element at the specified position in this list with the specified element.
*/
public void set(int index,E element){
if(index > size){
// Can't insert
System.out.println("Index out of bounds");
}else{
if(h.size() > index+1){
while(h.size() > index){
t.push(h.pop());
}
h.pop();
h.push(element);
}else{
while(h.size()<= index){
h.push(t.pop());
}
t.pop();
h.push(element);
}
}
}
/*
* Removes first occurrence of element in the list
*/
public void removeFirst(E element){
if(size == 0){
System.out.println("Stack Empty. Nothing to remove");
}else{
while(!h.empty()){
t.push(h.pop());
}
while(t.peek() != element){
h.push(t.pop());
}
if(!t.empty()){
t.pop();
}
size--;
}
}
/*
* Removes last occurrence of the element in the list
*/
public void removeLast(E element){
if(size == 0){
System.out.println("Stack Empty. Nothing to remove");
}else{
while(!t.empty()){
h.push(t.pop());
}
while(h.peek() != element){
t.push(h.pop());
}
if(!h.empty()){
h.pop();
}
size--;
}
}
/*
* Gets the first value in the List
*/
public E getFirst(){
while(h.size() > 1){
t.push(h.pop());
}
return h.peek();
}
/*
* Returns the last value in the list
*/
public E getLast(){
while(t.size() > 1){
h.push(t.pop());
}
return t.peek();
}
/*
* Returns the value at the specified index
*/
public E get(int index){
E val = null;
if(index > size-1){
return null; // index out of bounds
}else{
if(h.empty()){
// pop index number of times from t to h and then peek()
while(h.size() < index){
h.push(t.pop());
}
val = t.peek();
}else if(t.empty()){
// pop from h to t till index comes to top
while(h.size() > index+1){
t.push(h.pop());
}
val = h.peek();
}else if(index < h.size()){
// element is in stack h
while(h.size() > index+1){
t.push(h.pop());
}
val = h.peek();
}else{
// element is in stack t
while(h.size() < index){
h.push(t.pop());
}
val = t.peek();
}
}
return val;
}
}
Note: This might contain bugs as this has not been tested much.
- algorithmor January 26, 2015posting the contents here:
You can use the java.lang.instrument package
Compile and put this class in a JAR:
import java.lang.instrument.Instrumentation;
public class ObjectSizeFetcher {
private static Instrumentation instrumentation;
public static void premain(String args, Instrumentation inst) {
instrumentation = inst;
}
public static long getObjectSize(Object o) {
return instrumentation.getObjectSize(o);
}
}
Add the following to your MANIFEST.MF:
Premain-Class: ObjectSizeFetcher
Use getObjectSize:
public class C {
private int x;
private int y;
public static void main(String [] args) {
System.out.println(ObjectSizeFetcher.getObjectSize(new C()));
}
}
Invoke with:
java -javaagent:ObjectSizeFetcherAgent.jar C
His concept is similar to Memory mapped files, but he is just not able to express it in the actual way it is supposed to be done.
- algorithmor November 04, 2014Use MappedByteBuffer. It is used in existing trading applications and offers low latency.
- algorithmor November 04, 2014Sorry! This is not the right code. Please ignore this.
- algorithmor June 06, 2014Just the quick and dirty recursive version here:
public void subDivide(int num, int min, String prefix) {
for (int i = 1; i <= num/2 && i >= min; i++) {
// We need to iterate only till Math.floor(num/2) and division in java by default rounds to the lower value, so not using the function here.
if("".equals(prefix)){
System.out.println(""+(num - i)+"+"+i);
prefix += i;
}
else{
System.out.println(""+(num - i)+"+"+i+"+"+prefix);
prefix += "+"+i;
}
subDivide(num-i,i, prefix);
}
}
The initial call say, for 5 would be subDivide(5,0,"");
Due to lots of String concatenations this is not efficient, and a Stringbuilder should be used ideally.
Note : This does not print the original input number again, as its just seemed redundant, but that can be done by printing the input number before making the function call.
So, let's start by first analyzing how Truecaller works
- algorithmor February 03, 2018Case 1 : If a user has truecaller installed in his phone and he sets his profile name then his number is directly mapped to his username and that will be displayed whenever he calls someone who has truecaller installed
Case 2 : This is the interesting case as this shows the true utility of Truecaller. Truecaller also had access to contacts and so uploads all the contacts saved by people to their servers. Now, they calculate the name for a number by calculating the highest frequency of exact or matching words used for a particular phone number.
So, we need a centralized service that syncs contacts for each user. Then, a periodic backend job that keeps updating the internal directory or map of contacts for our Truecaller or whatever we choose to name our app.