akkhil2012
BAN USER
int thirdLargest(int[] arr,int k){
return createMaxHeap(arr,k);
}
int createMaxHeap(int[] arr,int k){
Heap h = new Heap(arr.length);
for(int i=0;i<arr.length;i++){
h.insert(arr[i]);
}
int max = 0;
int i = 0;
while(i < k-1){
max = h.extractMax();
i++;
}
return max;
}
class Heap{
private int[] heapArray;
private int currentSize;
private int maxSize;
private int FRONT = 1;
Heap(int maxSize){
this.maxSize = maxSize;
this.currentSize = 0;
this.heapArray = new int[maxSize];
}
public boolean insert(int key){
if(currentSize==maxSize)return false;
heapArray[currentSize] = key;
tickleUp(currentSize++);
return false;
}
public int extractMax(){
if(currentSize==0)
return Integer.MAX_VALUE;
int root = heapArray[0];
if(currentSize>1){
heapArray[0] = heapArray[currentSize-1];
maxHeapify(0);
}
currentSize--;
return root;
}
public void maxHeapify(int i){
int l = 2*i+1;
int r = 2*i+2;
int largest = i;
if(l < currentSize && heapArray[i] < heapArray[l] )
largest = l;
if(r < currentSize && heapArray[i] < heapArray[r] )
largest = r;
if(largest != i){
int t = heapArray[i];
heapArray[i] =heapArray[largest];
heapArray[largest] = t;
maxHeapify(largest);
}
}
Could you please explain the logic behind this
- akkhil2012 January 04, 2016Using two TreeMap
package com.amazon.arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
public class FindMostRepeatedWords {
Map<String, Integer> wordsMap = new TreeMap<String, Integer>();
public void getRepeated(String[] arr, int count) {
Integer val;
for (String s : arr) {
if (wordsMap.containsKey(s)) {
val = wordsMap.get(s);
val++;
wordsMap.put(s, val);
} else {
wordsMap.put(s, 1);
}
}
List<String> st = new LinkedList<String>();
Map<Integer, List<String>> countMap = new TreeMap<Integer, List<String>>()
.descendingMap();
for (Map.Entry<String, Integer> m : wordsMap.entrySet()) {
if (countMap.containsKey(m.getValue())) {
st = countMap.get(m.getValue());
st.add(m.getKey());
} else {
st = new LinkedList<String>();
st.add(m.getKey());
countMap.put(m.getValue(), st);
}
System.out.println(" ");
}
System.out.println(" Count Map ");
int number = 0;
for (Map.Entry<Integer, List<String>> m : countMap.entrySet()) {
System.out.println(" -->>>>" + m.getKey() + " ");
List<String> word = m.getValue();
Iterator<String> itr = word.iterator();
while (itr.hasNext()) {
System.out.println(" " + itr.next());
number++;
if (number == count)
break;
}
if (number == count)
break;
}
return;
}
public static void main(String args[]) {
String[] arr = { " akkhil", "kumar", "gupta", "testCase", " akkhil",
"kumar", "kumar", "kumar", "kumar", "kumar", "kumar", "kumar",
"kumar", "kumar", "kumar", "gupta", "gupta", "gupta" };
new FindMostRepeatedWords().getRepeated(arr, 4);
}
}
private static boolean checkIfListIsPalindrome(Node<String> first){
StringBuffer firstBuffer = new StringBuffer();
StringBuffer secBuffer = new StringBuffer();
Node<String> current = first;
Node<String> faster = first;
Node<String> dummy = null;
while(faster!=null && faster.next!=null){
dummy = faster.next;
faster = faster.next.next;
current = current.next;
}
boolean flag = true;
System.out.println(" ");
String middle = current.nData;
System.out.print(" Middle--->>> "+ current.nData);
if(faster==null)
System.out.println(" end is : even case "+ dummy.nData);
else{
System.out.println(" end is: odd case "+ faster.nData);
flag = false;
}
System.out.print(" First half : ");
Node<String> firstHead = first;
while(firstHead.nData != current.next.nData){
firstBuffer.append(firstHead.nData.trim());
System.out.print(" "+ firstHead.nData);
firstHead = firstHead.next;
}
/**
* reverse the second half
*/
Node<String> prev = null;
Node<String> nextNode = null;
Node<String> newHead = current;
current = newHead;
while(current!=null){
nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
while(current!=null){
System.out.print(" "+ current.nData);
secBuffer.append(new StringBuffer(current.nData).reverse().toString());
current = current.next;
}
if(flag){
secBuffer.append(new StringBuffer(middle).reverse());
}
/*
*
* compare first and second half
*/
if(firstBuffer.toString().equals(secBuffer.toString()))
return true;
return false;
}
Improved time complexity of O(n)
public static int findMaxDiff(int[] arr) {
int max = arr[0];
int min = arr[0];
int minIndex = 0;
int maxIndex = 0;
int diff = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
maxIndex = i;
}
if (arr[i] < min) {
min = arr[i];
minIndex = i;
}
if (maxIndex > minIndex && diff < Math.abs(max - min))
diff = max - min;
}
return diff;
}
Using the HashMap and Dequeue as the DS
public void printSpiralInwards(Node root){
Map<Integer,ArrayList<Node>> mp = new HashMap<Integer, ArrayList<Node>>();
ArrayList<Node> arrayList = null;
ArrayList<Node> arrayList1 = null;
int i = 0;
if(root == null)
return;
Deque<Node> queue = new LinkedList<Node>();
queue.add(root);
queue.add(null);
while(queue.size()>1){
Node temp = queue.peekFirst();
arrayList = new ArrayList<Node>();
while(temp!=null){
temp = queue.pollFirst();
arrayList.add(temp);
System.out.println(" "+ temp.data );
if(temp.left!=null)
queue.offerLast(temp.left);
if(temp.right!=null)
queue.offerLast(temp.right);
temp = queue.peekFirst();
}
mp.put(i++, arrayList);
temp = queue.peekLast();
arrayList1 = new ArrayList<Node>();
while(temp!=null){
temp = queue.pollLast();
arrayList1.add(temp);
System.out.println(" "+ temp.data );
if(temp.right!=null)
queue.offerFirst(temp.right);
if(temp.left!=null)
queue.offerFirst(temp.left);
temp = queue.peekLast();
}
mp.put(i++, arrayList1);
}
Deque<ArrayList<Node>> de = new LinkedList<ArrayList<Node>>();
de.addAll(mp.values());
while(!de.isEmpty()){
System.out.println(" ");
ArrayList<Node> first = de.pollFirst();
Iterator<Node> itr = first.iterator();
while(itr.hasNext()){
System.out.print(" "+itr.next().data);
}
System.out.println(" ");
ArrayList<Node> sec = de.pollLast();
Iterator<Node> itr1 = sec.iterator();
while(itr1.hasNext()){
System.out.print(" "+itr1.next().data);
}
}
}
package com.dynamic;
public class MaximumRob {
public int getMaximum(int[] arr) {
int excl = 0;
int incl = arr[0];
int newExcl;
for (int i = 1; i < arr.length; i++) {
newExcl = (excl > incl) ? excl : incl;
incl = excl + arr[i];
excl = newExcl;
}
return (excl > incl) ? excl : incl;
}
public static void main(String args[]) {
int[] arr = { 10, 2, 3, 5, 7, 8 };
System.out.println(" Maximum sum is "
+ new MaximumRob().getMaximum(arr));
}
}
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
/**
* Created by akhil on 12/13/2015.
*/
public class SortStringList {
public static void sortString(List<String> lst) {
Set<String> st = new TreeSet<String>(lst);
for (String s : st)
System.out.print(s);
}
public static void main(String arg[]) {
List<String> lst = new LinkedList<String>();
lst.add("akhil");
lst.add("kumar");
lst.add("gupta");
lst.add("nidhi");
lst.add("mahajan");
lst.add("cinema");
sortString(lst);
}
}
/**
* Created by akhil on 12/13/2015.
*/
public class DiffBetweenIndices {
public static int difBetween(int[] arr, int a, int b) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = sum + arr[i];
sum = arr[i];
}
for (int i : arr) {
System.out.print(" " + i + " ");
}
return arr[b] - arr[a];
}
public static void main(String args[]) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// difBetween(arr,0,4);
System.out.print(" Diff is " + difBetween(arr, 0, 4));
}
}
/**
* Created by akhil on 12/13/2015.
*/
public class RowWithMaxVal {
public static int getmaxValRow(int[][] mat) {
int max = 0;
int rowNo = 0;
int row = mat.length;
int col = mat[0].length;
int temp = 0;
int k;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
k = col - j;
temp += mat[i][j] * 2 ^ k;
}
if (temp > max) {
max = temp;
rowNo = i;
}
temp = 0;
}
System.out.print(" max is " + max);
return rowNo;
}
public static int getMax(int[][] mat) {
int max = 0;
int row = mat.length;
int col = mat[0].length;
int temp = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.println(" to " + mat[i][j]);
int t = mat[i][j] << col - 1 - j;
System.out.println(" now " + t);
temp |= t;
System.out.println(" final" + temp);
}
}
return 0;
}
public static void main(String args[]) {
int[][] mat = {{0, 1, 0},
{1, 1, 0},
{1, 0, 1}
};
//getMax(mat);
System.out.println("--" + getmaxValRow(mat));
}
}
/**
* Created by akhil on 12/13/2015.
*/
public class RepeatedNumberCount {
public static int getCount(int[] arr, int num) {
int n = getNumber(arr, 0, arr.length - 1, num);
return n;
}
private static int getNumber(int[] arr, int low, int high, int num) {
int mid = 0;
int count = 0;
while (low <= high && num != arr[mid]) {
mid = (high + low) / 2;
if (num < arr[mid]) {
high = mid - 1;
} else if (num > arr[mid]) {
low = mid + 1;
}
}
if (num == arr[mid])
System.out.println(" Element is present " + count++);
for (int i = mid; i < arr.length - 1; i++) {
if (num == arr[i + 1]) count++;
// break;
}
for (int i = mid; i > 0; i--) {
if (num == arr[i - 1]) {
count++;
//continue;
}// break;
}
System.out.println(" count " + count);
return count;
}
public static void main(String args[]) {
int[] arr = {1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6, 6};
System.out.println(" Number of times a number is repeated " + getCount(arr, 1));
}
}
import java.util.ArrayList;
/**
* Created by akhil on 12/13/2015.
*/
class Heap {
private int[] hArray;
private int maxSize;
private int currentSize;
public Heap(int maxSize) {
this.maxSize = maxSize;
this.currentSize = currentSize;
hArray = new int[maxSize];
}
public int insert(int data, int n) {
if (currentSize == maxSize)
return 0;
hArray[currentSize] = data;
// if(hArray.length<n)return 0;
trickleUp(currentSize++, n);
return hArray[0];
}
public void trickleUp(int index, int n) {
int parent = (index - 1) / 2;
int bottom = hArray[index];
while (index > 0 && hArray[parent] > bottom) {
hArray[index] = hArray[parent];
index = parent;
parent = (parent - 1) / 2;
}
hArray[index] = bottom;
int count = 0;
for (int i = 0; i < n; i++) {
System.out.println(" " + hArray[i]);
}
System.out.println("------------");
}
}
public class StreamMin {
public static void findMin(Heap hp, ArrayList<Integer> lst, int number, int n) {
lst.add(number);
hp.insert(number, n);
}
public static int findMinOfStream(ArrayList<Integer> stream) {
int minVal = 0;
return minVal;
}
public static void main(String args[]) {
final ArrayList<Integer> lst = new ArrayList<Integer>();
final Heap hp = new Heap(20);
Thread t = new Thread() {
public void run() {
for (int i = 0; i < 20; i++) {
findMin(hp, lst, i, 5);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
}
}
}
};
t.start();
}
}
{ /**
* Created by akhil on 12/13/2015.
*/
public class FindMaDifference {
public static int findDiff(int[] arr) {
int diff = 0;
int maxDiff = 0;
int first = 0;
int sec = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - arr[j] > maxDiff) {
maxDiff = arr[i] - arr[j];
first = arr[i];
sec = arr[j];
}
}
}
System.out.println(" first " + first + " " + "sec " + sec);
return maxDiff;
}
public static void main(String args[]) {
int[] arr = {10, 15, 90, 200, 110};
System.out.println(" Maximum diff is " + findDiff(arr));
}
}
package com.amazon.arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/*
*
*
* Alternative: To use MinHeap
*/
class AmazonItems {
public Item getIthItem(List<Item> lst, int k) {
Item item = null;
Map<Item, Integer> itemsMap = new TreeMap<Item, Integer>(
new MyComparator());
Iterator<Item> it = lst.iterator();
while (it.hasNext()) {
Item nextItem = it.next();
itemsMap.put(nextItem, nextItem.getQuantitySold());
}
Item[] itemArray = new Item[lst.size() + 1];
int i = 1;
for (Map.Entry<Item, Integer> items : itemsMap.entrySet()) {
itemArray[i++] = items.getKey();
}
return itemArray[k];
}
}
class MyComparator implements Comparator<Item> {
public int compare(Item o1, Item o2) {
if (o1.getQuantitySold() > o2.getQuantitySold())
return -1;
else if (o1.getQuantitySold() < o2.getQuantitySold())
return 1;
return 0;
}
}
class Item {
private String itemId;
private int quantitySold;
public String getItemId() {
return itemId;
}
public void setItemId(String itemId) {
this.itemId = itemId;
}
public int getQuantitySold() {
return quantitySold;
}
public void setQuantitySold(int quantitySold) {
this.quantitySold = quantitySold;
}
public Item(String itemId, int quantitySold) {
this.itemId = itemId;
this.quantitySold = quantitySold;
}
}
public class ArrayPopularItem {
public static void main(String args[]) {
List<Item> lst = new LinkedList<Item>();
lst.add(new Item("first", 100));
lst.add(new Item("sec", 1000));
lst.add(new Item("third", 200));
lst.add(new Item("fourth", 400));
lst.add(new Item("fifth", 700));
lst.add(new Item("six", 4700));
lst.add(new Item("seven", 11700));
/* new AmazonItems().getIthItem(lst,3); */
System.out.println(" K th item is "
+ new AmazonItems().getIthItem(lst, 5).getQuantitySold());
}
}
1
This problem is a version of finding the least common ancestor but for N-array tree
- akkhil2012 December 05, 2015package com.amazon.arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class ArraysListSorted {
public static void mergerLists(List<int[]> lst){
Map<Integer,int[]> m = new TreeMap<Integer, int[]>();
Iterator<int[]> itr = lst.iterator();
while (itr.hasNext()) {
int[] is = (int[]) itr.next();
m.put(is[is.length-1], is);
}
LinkedList<int[]> fList = new LinkedList<int[]>();
for(Map.Entry<Integer, int[]> s : m.entrySet()){
fList.add(s.getValue());
}
Iterator<int[]> itrtr = fList.iterator();
while (itrtr.hasNext()) {
int[] temp = itrtr.next();
for(int t : temp){
System.out.print(" "+t+" ");
}
}
}
public static void main(String args[]) {
int[] first = {31,32,33,34,35};
int[] sec = {11,22,33,44,55};
int[] third = {1,2};
int[] fourth = {45,56};
List<int[]> lst = new LinkedList<int[]>();
lst.add(first);
lst.add(sec);
lst.add(third);
lst.add(fourth);
mergerLists(lst);
}
}
Since sorting using bubble sort will be in O(nK) while using min Heap will be NLogK
- akkhil2012 April 18, 2016so prefer MinHeap to BubbleSort