CareerCup

This should be similar to link list loop finding problem

System.out.println(new BigDecimal(1 / Math.pow(2, 100)).toPlainString());

Java 8 one liner to group a list of strings according to anagrams

private static Collection<List<String>> getAnagrams(
    final List<String> words) {

    return words.stream()
        .collect(Collectors.groupingBy(s -> {
          final char[] sortedArray = s.toLowerCase().toCharArray();
          Arrays.sort(sortedArray);
          return new String(sortedArray).intern();
        })).values();
  }

Yes, this is due to the silly bug as pointed out by Omri Bashari above. Thanks Omri Bashari for pointing out this bug.

public class ParseFloat {

  public static int indexOf(final char[] s, final char c) {
    for (int i = 0; i < s.length; i++) {
      if (s[i] == c) {
        return i;
      }
    }
    return -1;
  }

  public static int ASCII_ZERO = 48;
  public static double PRECISION = 0.0000000001;

  public static double parse(final char[] s) {

    int decimalIndex = indexOf(s, '.');
    if (decimalIndex == -1) {
      decimalIndex = s.length;
    }

    double integer = 0.0D;
    for (int i = 0; i < decimalIndex; i++) {
      final int d = s[i] - ASCII_ZERO;
      integer = (integer * 10D) + d;
    }

    double frac = 0D;
    for (int i = s.length - 1; i > decimalIndex; i--) {
      final int d = s[i] - ASCII_ZERO;
      frac = ((frac * 0.1D) + (d * 0.1D));
    }

    return integer + frac;
  }

  public static String toString(final double d) {
    int integer = (int) d;
    final int numIntDigits = (integer / 10) + 1;
    double fraction = d - integer;

    final char[] s = new char[numIntDigits];
    for (int i = numIntDigits - 1; integer != 0; i--) {
      final int digit = integer % 10;
      integer = integer / 10;
      s[i] = (char) (digit + ASCII_ZERO);
    }

    String str = new String(s);
    if (fraction != 0) {
      str = str + ".";

      while (fraction > PRECISION) {
        fraction = fraction * 10;
        final int digit = (int) fraction;
        str = str + digit;
        fraction = fraction - digit;
      }
    }
    return str;
  }

  public static void main(final String[] args) {
    final double d = parse("12.108".toCharArray());
    System.out.println(d);
    System.out.println(toString(d));

  }
}

public static int getMinStones(final int a[], final int k) {

    if ((a.length < k)) {
      return -1;
    }

    Arrays.sort(a);

    // approach 1:
    final int mid = a[k - 1];
    int res1 = (mid * (a.length - k));
    for (int i = 0; i < k; i++) {
      res1 += a[i];
    }

    // approach 2
    int res2 = 0;
    for (int i = a.length - 1; i > (k - 1); i--) {
      res2 += a[i];
    }
    System.out.println("Approach 1 = " + res1 + " Approach 2 = " + res2);
    return Math.min(res1, res2);
  }

Optimized version:

For a range in 1 billion it takes around 36 ms

#!/usr/bin/python

import sys
import math
from time import sleep
import time


def num_gen(low, high):
    i = 1

    run = True
    while i < high and run:
        run = False
        d1 = i
        d2 = i
        num = d1

        while True:

            mul = max(10, math.pow(10, math.ceil(math.log(d2 + 1, 10))))
            num = num * mul + d2
            t = d2
            d2 = d1 + d2
            d1 = t

            #print num, mul, d1, d2

            if num < low:
                run = True
                continue
            if num > high:
                break
            run = True
            yield num
        i += 1


ms1 = int(round(time.time() * 1000))
j = 0
for i in num_gen(0, 1000000000):
    print i
    j += 1
print j
ms2 = int(round(time.time() * 1000))

print "Time taken = ", (ms2 - ms1)

Another python solution (not 100% optimized)

#!/usr/bin/python

import sys
import math
from time import sleep


def num_gen(low, high):
    i = 1
    while i < high:
        d1 = i
        d2 = i
        num = d1
        while True:

            mul = max(10, math.pow(10, math.ceil(math.log(d2 + 1, 10))))
            num = num * mul + d2
            t = d2
            d2 = d1 + d2
            d1 = t

            #print num, mul, d1, d2

            if num < low:
                continue
            if num > high:
                break
            yield num
        i += 1


for i in num_gen(100000, 1000000):
    print int(i)

Use Google Custom Search

In 7 byte ascii there could be 128 different characters hence you would require 128 bits. I guess using a simple it would result in overflow.

Do inorder traversal. Check if the traversed sequence is sorted or not.

Or use something like:

class HashObject {
       public Object obj;
       public long timestamp;
   }

Then have a global counter. Insert goes something like

void insert (Element e) {
       global_counter++;
       HashObject ho = new HashObject();
       ho.obj = e;
       ho.timestamp = global_counter;
       hashSet.add(ho);
   }

+1

As the string is ASCII we can easily use a bitmap to count the occurrence of each character. But as the question asks for uniqueness, counting is not required and one bit per element should be sufficient. Anyways here is the code for general count based bitmap solution

long[] bitmap = new long[256];
	
	public void printUniqChar(char[] s) {
		for(char c:s)
			bitmap[c]++;
		for(int i=0; i<bitmap.length; i++)
			if(bitmap[i] == 1)
				System.out.printf("UNIQUE = %c\n", i);
	}

We can optimize this further by memorizing all the results already produced,

private HashMap<Integer, ArrayList<String>> addSeqs = 
			new HashMap<Integer, ArrayList<String>>();
	
	public ArrayList<String> allAdds(int num) {
		ArrayList<String> ret = new ArrayList<String>();
		if(num == 1){
			ret.add(""+num);
			return ret;
		}
		for(int i = 1; i<num; i++) {
			ArrayList<String> all = addSeqs.get(num-i);
			if (all == null) {
				all = allAdds(num-i);
				addSeqs.put(num-i, all);
			}
			for(String j:all)
				ret.add(i+" + "+j);
		}
		ret.add(""+num);
		return ret;
	}

Another recursive solution here: (but I am not sure if the running time is acceptable)

public static ArrayList<String> allAdds(int num) {
		ArrayList<String> ret = new ArrayList<String>();
		if(num == 1){
			ret.add(""+num);
			return ret;
		}
		for(int i = 1; i<num; i++) {
			for(String j:allAdds(num-i))
				ret.add(i+" + "+j);
		}
		ret.add(""+num);
		return ret;
	}

You may start with the Google Big Table paper. It has various insights on designing a distributed column database. Apache HBASE is based on this paper.

The in-order representation is just the sorted sequence of the keys. Whatever be the structure of the tree, the in order readout will be same. It carries no extra information.

No. of possible binary tree structures given n distinct keys are (2n)!/((n+1)!*n!) which is also called the Catalan Number.

For a given tree structure and a set of keys there is only a single BST possible. As any other assignment of keys will change the in-order readout and the tree wont be a BST.

For a given set of keys every possible binary trees can be regarded as BST by assigning the keys properly to the nodes. Because, every possible binary tree can be traversed in-order and hence the keys can be assigned according to in-order traversal.

Hence the number of possible BST is same as the number of binary tree structures which is given by the Catalan Number.