Maximize a number by deleting a repeated number.

For eg:

Question : 223336226

Answer: 23336226

Other removal of numbers possible: 22336226, 22333626

Code:

int solution(int X){ 
   int max=1,val=X; 
   while(val/10!=0){ 
     max*=10; 
     val/=10; 
   } 
   boolean del=true; 
   int pos=-1,cur=-1,rep=0,max1=max; 
   val=X; 
   while(del && max!=0){ 
     int new_cur=val/max; 
     if(rep==1 && new_cur > cur){ 
       pos=max*10; 
       del=false; 
     } 
     else if(new_cur==cur){ 
       pos=max; 
     } 
     if(new_cur==cur) 
       rep = 1; 
     else 
       rep = 0; 
     val=val%max; 
     max=max/10; 
     cur=new_cur; 
   } 
   int new_num=0,max_new=max1/10; 
   val=X; 
   while(max1!=0){ 
     if(max1==pos){ 
       max1/=10; 
       continue; 
     } 
     int num=(val/max1)%10; 
     new_num+=max_new*num; 
     max_new/=10; 
     max1/=10; 
   } 
   return new_num; 
} 

Prisoners and hats puzzle

According to the story, four prisoners are arrested for a crime, but the jail is full and the jailor has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailor puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats. The jailor explains that there are two black hats, and two white hats; that each prisoner is wearing one of the hats; and that each of the prisoners only see the hats in front of him but not on himself or behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication among the prisoners is allowed.

If any prisoner can figure out and say to the jailor what color hat he has on his head with 100% certainty (without guessing) all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape, regardless of how the jailer distributes the hats.

import java.util.ArrayList;

public class Solution {

 public static void main(String[] args) {
  int members = 10;
  ArrayList<String> list = new ArrayList<String>();
  int blackCount = 0;
  for (int i = 1; i <= members; i++) {
   String val = (getRandom(1, 2) == 1) ? "white" : "black";
   list.add(val);
   if (val.equals("black"))
    blackCount++;
  }
  if (list.get(members - 1).equals("black"))
   blackCount--;
  System.out.println(list);

  int prevC = blackCount;
  String prevB = printStatus(blackCount % 2 != 0);

  for (int i = 8; i >= 0; i--) {
   if (list.get(i).equals("black"))
    blackCount--;
   boolean prevOdd;
   prevOdd = (prevB.equals("white")) ? (prevC == blackCount) ? true
     : false
     : (prevB.equals("black") && prevC == blackCount) ? true
       : false;
   prevB = printStatus(prevOdd);
   prevC = blackCount;
  }
 }

 private static String printStatus(boolean prevOdd) {
  String prevB;
  if (prevOdd) {
   System.out.print("white ");
   prevB = "white";
  } else {
   System.out.print("black ");
   prevB = "black";
  }
  return prevB;
 }

 public static int getRandom(int minimum, int maximum) {
  return minimum + (int) (Math.random() * maximum);
 }

}

Result:
From 1 to N: [white, white, black, black, black, white, white, white, white, white]
Last person to first telling their colors: white white white white white black black black white white 

Median of Medians Java implementation, kth element in array

Median of Median algorithm implementation in Java. It also provides Kth element in array after sorting. This algorithm runs in O(n) time.

Please leave comments below for more questions and remarks.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
 public static void main(String[] args) {
  Solution s = new Solution();
  List<Integer> a = Arrays.asList(88, 30, 11, 17, 22, 16, 39, 8, 31, 55,
    29, 63, 77, 69, 99, 90, 81, 2, 20, 53, 62, 5, 88, 33, 44, 6);
  System.out.println(s.findKthElement(a, 18));
  Collections.sort(a);
  System.out.println(a);
  System.out.println(a.get(18));
 }

 public int findKthElement(List<Integer> a, int k) {
  if (a.size() < 10) {
   Collections.sort(a);
   return a.get(k);
  }
  ArrayList<Integer> medians = new ArrayList<Integer>();
  for (int i = 0; i < a.size() - a.size() % 5; i = i + 5)
   medians.add(getMedian(a.subList(i, i + 5)));
  int v = getMedian(medians);

  ArrayList<Integer> left = getPartition(a, v, true);
  ArrayList<Integer> right = getPartition(a, v, false);

  return (left.size() + 1 == k) ? v : (left.size() > k) ? findKthElement(
    left, k) : findKthElement(right, k - left.size());
 }

 public int getMedian(List<Integer> a) {
  Collections.sort(a);
  return a.get(a.size() / 2);
 }

 public ArrayList<Integer> getPartition(List<Integer> a, int v,
   boolean isLessThan) {
  ArrayList<Integer> res = new ArrayList<Integer>();
  for (int val : a)
   if (isLessThan && val < v)
    res.add(val);
   else if (!isLessThan && val >= v)
    res.add(val);
  return res;
 }
}

Output:
62 ( value returned from algorithm)
[2, 5, 6, 8, 11, 16, 17, 20, 22, 29, 30, 31, 33, 39, 44, 53, 55, 62, 63, 69, 77, 81, 88, 88, 90, 99]
62 (kth value after sorting)

Arrangements/Combination of a elements in n positions

This method helps in arranging any type of objects in given number of positions. It is brut-force method of getting all type of combinations.

Please leave comments below for more questions and remarks.

public class Solution {
    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1, 2);
        System.out.println(getArrangements(a, 4));
    }
    public static <T> List<List<T>> getArrangements
               (List<T> numbers, int n) {
        List<List<T>> result = new ArrayList<List<T>>();
        int itr = (int) Math.pow(n, numbers.size());
        for (int i = 0; i < itr; i++) {
            List<T> comb = new ArrayList<T>();
            for (int j = 0; j < n; j++) {
                int pos = (int) Math.pow(numbers.size(),
      (n - j - 1));
                int element = (i / pos) % (numbers.size());
                comb.add(numbers.get(element));
            }
            result.add(comb);
        }
        return result;
    }
}

Results:

Input1:[ 'A','B','C','D'] & 2 positions
output1: [[A, A], [A, B], [A, C], [A, D], [B, A], [B, B], [B, C], [B, D], [C, A], [C, B], [C, C], [C, D], [D, A], [D, B], [D, C], [D, D]]


Input2: [1,2] & 4 positions

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2], [1, 2, 1, 1], [1, 2, 1, 2], [1, 2, 2, 1], [1, 2, 2, 2], [2, 1, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 2, 2], [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 2, 1], [2, 2, 2, 2]]

Palindrome

Palindrome problem:

Given : string

Output: An integer

Give product of lengths of two non overlapping palindromes from the string.

For ex:

"abcadad"

String1: "aba"
String2: "dad"

Product : 9

Good resources for preparation for coding interview

1. https://sites.google.com/site/mytechnicalcollection/algorithms/data-structures

2. hackerrank.com

3. codility.com

4. codefights.com