ruharish
BAN USERThis Java method will consider the characters that are repeated and then print them in sequential order. It does not consider the 'sorting' part, as it relies on HashTable and 'sorting' is not requirement per the question!
private void matchAlphaNumerals()
{
String input = "abdecadcszx";
//String input = "abcdefgh";
//String input = "aaaaaaaaaaa";
Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
for(int i=0, len=input.length(); i<len; i++)
{
char ch = input.charAt(i);
if(ht.get(ch + "") != null)
{
Integer count = ht.get(ch + "");
ht.put(ch + "", new Integer(count.intValue() + 1));
}
else
ht.put(ch + "", new Integer(1));
}
Set<String> chars = ht.keySet();
StringBuffer sequencedOutput = new StringBuffer();
Iterator<String> it = chars.iterator();
while(it.hasNext())
{
String currentChar = it.next();
for(int i=0, count=ht.get(currentChar).intValue(); i<count; i++)
sequencedOutput.append(currentChar);
}
System.out.println(sequencedOutput);
}
Do we have to calculate the sum of values from root to each leaf and then identify the path with maximum value? If so, Googler's solution seems to be in line, but seems to be working differently by the solution from yogi.rulzz. Or am I missing something here :(
- ruharish October 27, 2013Compiled Java code -
import java.util.Arrays;
public class SwapInThreeChunks {
public static void main(String[] args)
{
int[] input = {1,9,6,4,5,8,3,1,5,2,4,5};
for(int i=0, len=input.length; i<len; i++)
{
if(i+2 < len)
{
int temp = input[i];
input[i] = input[i+2];
input[i+2] = temp;
}
i += 2;
}
System.out.println(Arrays.toString(input));
}
}
You must override hashcode method, whenever you override equals method, as the best practice (though your program will get compiled & run, even without this). May be that's what the interviewer was expecting to hear back, as part of response to this question.
- ruharish October 25, 2013Here is a simple Java code to solve this puzzle. I've tried it with different inputs, which are commented in the source code.
/**
* An array of integer represents a bar graph, where index of array is X axis (width = 1) and Y axis represents height of the bar graph at X, find out how much water will retain if it rains infinite on the structure. Only portion of graph that retains water is enclosed area due to height difference of bar graph. You need to assume that each bar itself doesn't store any water.
e.g. {1,2,3} then no water is stored
{6,4,1} then no water is stored
{3,2,1, 5} then 3 unit water is stored between 3 & 5 (1 unit on 2 and 2 unit on 1)
* @author ruharish
*
*/
public class CollectedWaterOnBarGraph {
public static void main(String[] args)
{
/*
* This program follows a simple algo -
* 1. Iterate over each of the element, treating current element value as curValue.
* 2. Keep comparing with the elements on the left, till we reach beginning of the array or boundary of previous collection enclosure.
* 3. If any element is more than curValue, make it as the curMaxValue and continue searching.
* 4. If any element is equal to the curValue, make sure that there is at least one element in between, so that water can get collected there and continue searching for bigger numbers.
* 5. Keep comparing with the elements on the rgith, till we reach end of the array.
* 6. If any element is more than curValue, make it as the curMaxValue and continue searching.
* 7. If we have a non-zero lIndex & rIndex (found a enclosure where water can get collected), iterate over each of the element in between and measure the water collected.
*/
//int[] input = {1, 2, 3, 5};
//int[] input = {3, 2, 1 ,5};
int[] input = {4, 1, 6, 4, 1, 6, 3, 1, 4, 6};
//int[] input = {9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6};
//int[] input = {9, 4, 1, 6, 4, 1, 6, 3, 1, 4, 6, 8};
int totalQuantity = 0; //Total # of units of water collected
int prevRIndex = 0; //Used as the delimiter while searching to the left of the current index; right boundary of previous collection enclosure
//Iterate over each element of the input
for(int i=0, len=input.length; i<len; i++)
{
int lIndex = -1, rIndex = -1, curValue = input[i], curMaxValue = -1;
//Initialize the current max value to the value of current element
curMaxValue = input[i];
//Iterate to the left of current index i
for(int j=i-1; j>=prevRIndex; j--)
{
if(curMaxValue > input[j])
continue;
if(curMaxValue == input[j] && i-j > 1 && lIndex == -1)
lIndex = j;
if(curMaxValue < input[j])
{
lIndex = j;
curMaxValue = input[j];
}
}
//Initialize the current max value to the value of current element
curMaxValue = input[i];
//Iterate to the right of current index i
for(int k=i+1; lIndex > -1 && k<len; k++)
{
if(curMaxValue > input[k])
continue;
if(curMaxValue == input[k] && k-lIndex > 1 && rIndex == -1)
rIndex = k;
if(curMaxValue < input[k])
{
rIndex = k;
curMaxValue = input[k];
}
}
//Measure the water collected, if we find a enclosure enclosed
if(lIndex > -1 && rIndex > -1)
{
//Identify the smaller of #s at beginning or ending of the collection enclosure
int minValue = input[lIndex] < input[rIndex] ? input[lIndex]:input[rIndex];
System.out.print("Water gets stored between index " + lIndex + " and " + rIndex + ", at ");
for(int start = lIndex + 1; start < rIndex; start++)
{
if(start > lIndex + 1)
System.out.print(", ");
System.out.print("index " + start + " - " + (minValue - input[start]));
totalQuantity += minValue - input[start];
}
//Continue searching from the end of the current enclosure
i = rIndex - 1;
//Set the end of this enclosure as the boundary for next enclosure's start
prevRIndex = rIndex;
System.out.println();
}
}
System.out.println();
System.out.println("Total quantity stored - " + totalQuantity);
}
}
Optimal Java solution, with length checking and using arrays (for reduced memory footprint). I'm assuming that it's not overly complex like referring to Tree structures, etc.
public class MaxSubstrings {
public static void main(String[] args) {
String[] strs = {"rat", "cat", "abc", "xyz", "abcxyz", "ratcatabc", "xyzcatratabc", "abcx"};
int[] strSizes = new int[strs.length];
int[] strCounts = new int[strs.length];
for(int i=0, len=strs.length; i<len; i++)
{
strSizes[i] = strs[i].length();
strCounts[i] = 0;
}
for(int i=0, len=strs.length, wordLength=strs[i].length(); i<len; i++)
{
for(int j=0; j<len; j++)
{
if(i==j || wordLength > strs[j].length())
continue;
if(strs[j].contains(strs[i]))
strCounts[j]++;
}
}
int indexMaxCount = -1, maxCount = 0;
for(int i=0, len=strs.length; i<len; i++)
if(strCounts[i] > maxCount)
{
maxCount = strCounts[i];
indexMaxCount = i;
}
System.out.println(strs[indexMaxCount]);
}
}
This can be recursively printed with this method -
public class ArrayInSpiralOrder {
public static void main(String[] args) {
int array[][] = {
{ 0, 1, 2, 3, 4},
{15, 16, 17, 18, 5},
{14, 23, 24, 19, 6},
{13, 22, 21, 20, 7},
{12, 11, 10, 9, 8}};
printMatrixRecursive(array, 0, 0, 4, 4);
}
public static void printMatrixRecursive(int array[][], int startRow, int startCol, int endRow, int endCol)
{
if(startRow > endRow || startCol > endCol)
return;
for(int i=startRow, j=startCol; j<endCol; j++)
System.out.println(array[i][j] + " ");
for(int i=startRow, j=endCol; i<=endRow; i++)
System.out.println(array[i][j] + " ");
for(int i=endRow, j=endCol - 1; j>startCol; j--)
System.out.println(array[i][j] + " ");
for(int i=endRow, j=startCol; i>startRow; i--)
System.out.println(array[i][j] + " ");
printMatrixRecursive(array, startRow+1, startCol+1, endRow-1, endCol-1);
}
}
This can be achieved in Java, with simple code like this -
public class AlphabetCount {
public static void main(String[] args) {
String str = "AAAABCCDDD";
//String str = "ABCD";
//String str = "AAAA";
//String str = "";
StringBuffer sb = new StringBuffer(str), sbTarget = new StringBuffer();
char prevChar = ' ', currentChar = ' ';
int prevCharCount = 0;
for(int i=0, len=sb.length(); i<len; i++)
{
currentChar = sb.charAt(i);
if(currentChar != prevChar)
{
if(prevCharCount > 1)
sbTarget.append(prevCharCount);
sbTarget.append(currentChar);
prevCharCount = 1;
prevChar = currentChar;
}
else
prevCharCount++;
}
if(prevCharCount > 1)
sbTarget.append(prevCharCount);
System.out.println(sbTarget);
}
}
This simple non-recursive Java method works for 2d arrays of different rows & columns # too (need not be a 4x4, 5x5, but can be 4x5, 5x6, etc too)-
public class ArrayInSpiralOrder {
public static void main(String[] args) {
int array[][] = {
{ 0, 1, 2, 3, 4},
{15, 16, 17, 18, 5},
{14, 23, 24, 19, 6},
{13, 22, 21, 20, 7},
{12, 11, 10, 9, 8}};
printMatrixNonRecursive(array, 5, 5);
}
public static void printMatrixNonRecursive(int array[][], int rows, int cols){
int nCurrentLevel = 0;
int min = (rows < cols) ? rows:cols;
while(nCurrentLevel <= min/2){
for(int j = nCurrentLevel; j < cols - nCurrentLevel - 1; j++){
System.out.print(array[nCurrentLevel][j] + " ");
}
for(int i = nCurrentLevel; i < rows - nCurrentLevel - 1; i++) {
System.out.print(array[i][cols - nCurrentLevel - 1] + " ");
}
for(int j = cols - nCurrentLevel - 1; j > nCurrentLevel; j--){
System.out.print(array[rows - nCurrentLevel - 1][j] + " ");
}
for(int i = rows - nCurrentLevel - 1; i > nCurrentLevel; i-- ){
System.out.print(array[i][nCurrentLevel] + " ");
}
nCurrentLevel++;
}
}
}
RepShastri Ji is well known hindi and tamil vashikaran specialist. He will give you effective and simple totke to control ...
Java code for the same algo - thanks to @thelineofcode
- ruharish December 31, 2013