sLion
BAN USER- 2of 4 votes
AnswersGiven a complete binary tree, Find a Max element
- sLion in United States| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 2of 2 votes
AnswersWrite a function, for a given number, print out all possible way to make up that number eg: 2 - 1 1,2
- sLion in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
package interv.eBay;
public class CheckPerfectSquare {
public static void main(String[] args) {
// TODO Auto-generated method stub
CheckPerfectSquare cPS = new CheckPerfectSquare();
int input = 64;
System.out.println("Solution: Binary Search Version 1");
if (cPS.binarySearchCheck(input))
System.out.println("Yes the number is perfect square");
else
System.out.println("No the number is not a perfect square");
System.out.println("Solution: Binary Search Version 2");
if (cPS.binarySearchCheck2(input, 0, input))
System.out.println("Yes the number is perfect square");
else
System.out.println("No the number is not a perfect square");
System.out.println("Solution: Odd number Addition");
if (cPS.oddNumberAddition(input))
System.out.println("Yes the number is perfect square");
else
System.out.println("No the number is not a perfect square");
}
private boolean binarySearchCheck(int n) {
// TODO Auto-generated method stub
if (n == 1)
return true;
if (n < 4)
return false;
int min = 2;
int max = n / 2;
int div, res;
do {
div = (min + max) / 2;
res = n / div;
if (res * res == n)
return true;
else {
if (res < div) {
min = res;
max = div;
} else {
min = div;
max = res;
}
}
} while (max > (min + 1));
return false;
}
private boolean binarySearchCheck2(int n, int low, int high) {
// TODO Auto-generated method stub
if (low > high)
return false;
int mid = (low + high) / 2;
if (mid * mid == n)
return true;
else {
if ((mid * mid) > n)
return binarySearchCheck2(n, low, mid - 1);
else
return binarySearchCheck2(n, mid + 1, high);
}
}
private boolean oddNumberAddition(int n) {
// TODO Auto-generated method stub
int oddInteger = 1;
int squareValue = 1;
while(squareValue<=n){
if(squareValue==n)
return true;
else{
oddInteger=oddInteger+2;
squareValue = squareValue+oddInteger;
}
}
return false;
}
}
import java.util.Arrays;
import java.util.Hashtable;
public class FindLeaderInArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int inputArry[] = { 2, 2, 2, 5, 7 };
System.out.println("Hash Logic Leader: "
+ hashLogicFindLeader(inputArry));
Arrays.sort(inputArry);
System.out.println("Sort Logic Leader: "
+ sortedLogicFindLeader(inputArry));
}
private static int hashLogicFindLeader(int[] inputArry) {
// TODO Auto-generated method stub
if (inputArry.length <= 0)
return (-1);
Hashtable<Integer, Integer> arrayMap = new Hashtable<Integer, Integer>();
int candidate = -1;
;
for (int i = 0; i < inputArry.length; i++) {
if (arrayMap.containsKey(inputArry[i]))
arrayMap.put(inputArry[i], arrayMap.get(inputArry[i]) + 1);
else
arrayMap.put(inputArry[i], 1);
}
for (Integer i : arrayMap.keySet()) {
if ((2 * arrayMap.get(i)) > inputArry.length)
candidate = i;
}
return candidate;
}
private static int sortedLogicFindLeader(int[] inputArry) {
if (inputArry.length <= 0)
return (-1);
int n = inputArry.length;
int count = 0;
int pos = n / 2;
int candidate = inputArry[pos];
for (int i = 0; i < inputArry.length; i++) {
if (inputArry[i] == candidate)
count = count + 1;
}
if ((2 * count) > n)
return candidate;
return (-1);
}
}
import java.util.TreeMap;
public class RepeatedSubStringsOfMlength {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input1 = "ABCACBABC";
String input2 = "CABCAABC";
System.out.println(findRepeatedSubStr(input1, 3));
System.out.println(findRepeatedSubStr(input2, 2));
}
private static String findRepeatedSubStr(String input1, int m) {
// TODO Auto-generated method stub
if (input1 == null)
return null;
StringBuilder output = new StringBuilder();
TreeMap<String, Integer> stringMap = new TreeMap<String, Integer>();
for (int i = 0; i <= input1.length() - m; i++) {
if (stringMap.containsKey(input1.substring(i, i + m))) {
stringMap.put(input1.substring(i, i + m),
stringMap.get(input1.substring(i, i + m)) + 1);
} else
stringMap.put(input1.substring(i, i + m), 1);
}
for (String str : stringMap.keySet()) {
if (stringMap.get(str) > 1) {
output.append(str);
output.append(" ");
}
}
return output.toString();
}
}
private int findRangeNotSorted(ArrayList<ArrayList<Integer>> input) {
// TODO Auto-generated method stub
if (input == null)
return 0;
else {
TreeMap<Integer, ArrayList<Integer>> inputSortedMap = new TreeMap<Integer, ArrayList<Integer>>();
for (ArrayList<Integer> currentList : input) {
if (inputSortedMap.containsKey(currentList.get(0))) {
if (inputSortedMap.get(currentList.get(0)).get(1) < currentList
.get(1))
inputSortedMap.put(currentList.get(0), currentList);
} else
inputSortedMap.put(currentList.get(0), currentList);
}
int currentStart = Integer.MIN_VALUE, currentEnd = Integer.MIN_VALUE, range = 0;
boolean startFlag;
NavigableSet<Integer> sortedKeySet = inputSortedMap
.navigableKeySet();
for (Integer o : sortedKeySet) {
ArrayList<Integer> currentList = inputSortedMap.get(o);
if (currentList != null) {
startFlag = false;
for (Integer i : currentList) {
if (!startFlag) {
if (currentEnd < i) {
currentStart = i;
} else {
currentStart = currentEnd;
}
startFlag = true;
} else {
currentEnd = i;
if (currentStart < currentEnd) {
range += (currentEnd - currentStart);
}
break;
}
}
}
}
return range;
}
}
Ne[0] should be Math.min(1, inputArr[0]); or otherwise it will alter the result
for example { 2, -3, -2, -2, -40,-5};
Po[1] = 3 instead of just -3 as it takes the max of { -1*-3, -3, 2*-3} if Ne[0] =1
This will cause the result to be 2400 {3,-2, -2, -40, -5} instead of 960 {2, -3, -2, -2, -40}
public class PrintTreeByLevel {
public static void printTreeByLevel(TreeNode root) {
if (root == null)
return;
List<TreeNode> currentLevel = new List<TreeNode>();
currentLevel.add(root);
while(currentLevel.size>0){
List<TreeNode> parents= currentLevel;
currentLevel = new List<TreeNode>();
for (TreeNode node: parents){
System.out.print(node.value+" ");
if(node.left != null){
currentLevel .add(node.left);
}
if(node.right!= null){
currentLevel .add(node.right);
}
}
System.out.println();
}
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class FindSumByListFlattening {
@SuppressWarnings("unchecked")
public static int findSumByDepth(ArrayList<Object> inputList) {
int sum = 0;
int currentElementDepth = 1;
ListIterator<Object> listIterator = inputList.listIterator();
int currentPosition = 0;
int resetPoint = 0;
ArrayList<Object> tempList;
while (listIterator.hasNext()) {
Object i = listIterator.next();
if (!(i instanceof List)) {
if (resetPoint % 2 == 0)
currentElementDepth = 1;
else
resetPoint++;
sum += (currentElementDepth * (int) i);
currentPosition++;
} else {
tempList = (ArrayList<Object>) i;
listIterator.remove();
currentElementDepth++;
resetPoint++;
for (Object obj : tempList) {
listIterator.add(obj);
}
}
listIterator = inputList.listIterator(currentPosition);
}
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Object> inputList = new ArrayList<Object>();
ArrayList<Object> List1 = new ArrayList<Object>();
inputList.add(1);
List1.add(4);
ArrayList<Object> List2 = new ArrayList<Object>();
List2.add(6);
List1.add(List2);
inputList.add(List1);
// inputList.add(4);
for (Object obj : inputList) {
System.out.print(obj + " ");
}
System.out.println("Sum: " + findSumByDepth(inputList));
}
}
public class FindPowerOptimum {
private double power(double a, int b) {
// TODO Auto-generated method stub
if (b == 0)
return 1;
if (a == 0)
return 0;
double output = 1;
boolean isNegative = false;
if (b < 0) {
isNegative = true;
b = -b;
}
output = findPowerR(a, b);
if (isNegative) {
output = 1 / output;
}
return output;
}
private double findPowerR(double a, int n) {
// TODO Auto-generated method stub
if (n == 0)
return 1;
if (n == 1)
return a;
double output = 1;
output = findPowerR(a, n / 2);
if (n % 2 == 0)
return output * output;
else
return a * output * output;
}
public static void main(String[] args) {
FindPowerOptimum fp = new FindPowerOptimum();
System.out.println(fp.power(6, -6));
}
}
public class ExcludingProductArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 3,1,4,0,0 };
selfExcludingProduct(input);
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
}
private static void selfExcludingProduct(int[] input) {
// TODO Auto-generated method stub
int ArrayProduct = 1;
int zeroProduct = 1;
int zeroElementCount = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] != 0 && zeroElementCount < 2) {
zeroProduct *= input[i];
}
if (input[i] == 0) {
zeroElementCount++;
if (zeroElementCount > 1)
zeroProduct = 0;
}
ArrayProduct *= input[i];
}
for (int i = 0; i < input.length; i++) {
if (input[i] == 0)
input[i] = zeroProduct;
else
input[i] = (ArrayProduct / input[i]);
}
}
}
public class TestNumeric {
private boolean isNumeric(String input) {
// TODO Auto-generated method stub
try {
double number = Double.parseDouble(input);
} catch (NumberFormatException exception) {
return false;
}
return true;
}
public boolean isNumber(String toTest) {
toTest = toTest.trim();
// implement this
if (toTest == null)
return false;
else {
int i = 0;
if (toTest.charAt(i) == '-') {
i++;
}
int floatPointCounter = 0;
while (i < toTest.length()) {
if (toTest.charAt(i) == '.' && floatPointCounter < 1) {
floatPointCounter++;
} else if (toTest.charAt(i) > '9' || toTest.charAt(i) < '0'
|| floatPointCounter > 1) {
return false;
}
i++;
}
return true;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = " -5";
TestNumeric tN = new TestNumeric();
System.out.println("Numeric Status: " + tN.isNumeric(input));
System.out.println("Numeric Status: " + tN.isNumber(input));
}
}
public class FindShortestDistanceWords {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] inputArray = { "the", "quick", "brown", "fox", "summer",
"fox", "the", "brown", "fox", "summers", "quick", "quick",
"quick", "summer", "fox" };
System.out.println("Minimum Distance between (the) and (fox) "
+ findSDistance(inputArray, "the", "fox"));
System.out.println("Minimum Distance between (quick) and (fox) "
+ findSDistance(inputArray, "quick", "fox"));
}
private static int findSDistance(String[] inputArray, String string1,
String string2) {
// TODO Auto-generated method stub
int string1Index = -1;
int string2Index = -1;
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i].equals(string1)) {
string1Index = i;
}
if (inputArray[i].equals(string2)) {
string2Index = i;
}
if (minDistance > Math.abs(string1Index - string2Index)
&& (string1Index != -1 && string2Index != -1)) {
minDistance = Math.abs(string1Index - string2Index);
}
}
return minDistance;
}
}
public class PermuteCharsInString {
private String in;
StringBuilder out = new StringBuilder();
boolean[] used;
public void permutation(String str) {
in = str;
used = new boolean[in.length()];
permute();
}
public void permute() {
if (in.length() == out.length())
System.out.println(out.toString());
else {
for (int i = 0; i < in.length(); i++) {
if (used[i])
continue;
out.append(in.charAt(i));
used[i] = true;
permute();
used[i] = false;
out.setLength(out.length() - 1);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
PermuteCharsInString ps = new PermuteCharsInString();
char[] input = { 'a', 'b', 'c', 'd' };
String inp = new String(input);
ps.permutation(inp);
}
}
package ms.searching;
public class BinarySearchOnRotatedSortedArray {
private int search(int[] input, int low, int high, int key) {
// TODO Auto-generated method stub
if (low > high) {
return -1;
} else {
int mid = (low + high) / 2;
if (input[mid] == key)
return mid;
// left is ordered
else if (input[mid] > input[low]) {
if (key < input[mid] && key >= input[low])
return search(input, low, mid - 1, key);
else
return search(input, mid + 1, high, key);
} else if (input[mid] < input[high]) {
if (key > input[mid] && key <= input[high])
return search(input, mid + 1, high, key);
else
return search(input, low, mid - 1, key);
} else if (input[mid] == input[low]) {
if (input[mid] != input[high])
return search(input, mid + 1, high, key);
else {
int result = search(input, mid - 1, low, key);
if (result == -1) {
result = search(input, mid + 1, high, key);
}
return result;
}
}
}
return -1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 };
BinarySearchOnRotatedSortedArray bSRA = new BinarySearchOnRotatedSortedArray();
int resultIndex = bSRA.search(input, 0, input.length - 1, 14);
if (resultIndex != -1)
System.out.println("The key found at " + resultIndex);
else
System.out.println("The key not found");
}
}
package interv.linkedIn;
public class FindDuplicateRange {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 0, 2, 3, 3, 3, 10, 10 };
FindDuplicateRange fDR = new FindDuplicateRange();
fDR.findRange(input, 6);
}
public int binaryS(int[] input, int i, int j, int k) {
int low, high, mid, key;
low = i;
high = j;
key = k;
if (low > high)
return -1;
mid = (low + high) / 2;
if (input[mid] > key)
return binaryS(input, low, mid - 1, key);
else if (input[mid] < key)
return binaryS(input, mid + 1, high, key);
else
return mid;
}
private void findRange(int[] input, int key) {
// TODO Auto-generated method stub
if (input.length <= 0) {
System.out.println("Empty array");
return;
}
int startIndex = -1, endIndex = -1;
int keyIndex = binaryS(input, 0, input.length - 1, key);
if (keyIndex != -1) {
startIndex = keyIndex;
endIndex = keyIndex;
while (startIndex > 0) {
if (input[startIndex - 1] == key)
startIndex--;
else
break;
}
while (endIndex < input.length - 1) {
if (input[endIndex + 1] == key)
endIndex++;
else
break;
}
}
System.out.println("Start Index = " + startIndex + " End Index = "
+ endIndex);
}
}
1. Having counter variable initialized to 1
2. Store each character from start in hash map with key as the counter variable value
3. Insert this counter variable value into a min Heap
4. increment Counter variable
5. Before adding a character to a check if the character already exists in the the hash map, If it exists delete the character in the hashmap and delete the corresponding the counter variable value from the min heap and update the heap
6 once the stream is scanned completely, extract root of min heap and display the corresponding value from the hasp map
Little modification to the merge sort will work for this
1) Divide the input as we do in the merge sort
2) While merging use a variable which is incremented on every merge operation
3) Use ascending order condition for merging if it is even or descending order when it is odd
package ms.cc.alternatesorting;
public class AlternateSorting {
int[] inputArray = {3,5,7,8,4,1,2,12,15};
void mergeSort(int[] array)
{
int[] helper = new int[array.length];
mergesort(array, helper, 0 , array.length-1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private void mergesort(int[] array, int[] helper, int low, int high) {
if (low<high)
{
int middle= (low+high)/2;
mergesort(array, helper, low , middle);
mergesort(array, helper, middle+1 , high);
merge(array, helper,low, middle, high);
}
}
private void merge(int[] array, int[] helper, int low, int middle, int high) {
for (int i = low; i <= high; i++) {
helper[i]=array[i];
}
int helperLeft= low;
int counter=0;
int helperRight= middle+1;
int current=low;
while(helperLeft<=middle && helperRight<=high)
{
if(counter%2==0)
{
if(helper[helperLeft]<=helper[helperRight])
{
array[current]=helper[helperLeft];
helperLeft++;
}
else
{
array[current]=helper[helperRight];
helperRight++;
}
}
else
{
if(helper[helperLeft]>=helper[helperRight])
{
array[current]=helper[helperLeft];
helperLeft++;
}
else
{
array[current]=helper[helperRight];
helperRight++;
}
}
counter++;
current++;
}
int remaining = middle- helperLeft;
for(int i= 0; i<=remaining;i++)
{
array[current+i]= helper[helperLeft+i];
}
}
public static void main(String[] args) {
AlternateSorting i = new AlternateSorting();
i.mergeSort(i.inputArray);
}
}
- sLion September 02, 2014