FredCycle
BAN USERThis was just having fun and answering quickly. Linked list sure is a nice soln though.
public class MaxStockPriceSpan {
/**
Max span is number of days before this day that the price was lower than todays.
I/P is an array of prices ordered by days.
*/
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
int[] in = {2, 4 ,6 ,9, 5, 1};
List<Integer> out = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
for (int n : in) {
while (!minHeap.isEmpty() && minHeap.peek() < n) {
int temp = minHeap.poll();
stack.push(temp);
}
minHeap.offer(n);
if (stack.isEmpty()) {
out.add(-1);
}
else {
out.add(stack.size());
while (!stack.isEmpty()) {
int temp = stack.pop();
minHeap.offer(temp);
}
}
}
System.out.println("The min span array for " + Arrays.toString(in) + " is " + Arrays.toString(out.toArray()) + ".");
}
}
I also think the balanced search tree idea deserves a look. Seems like it would make sense since what we're looking for is a data struct that's always sorted and which gives you the index of a member on request -- like the linked list solution does "manually."
- FredCycle May 08, 2014Maintain separate indices for both arrays and do a "merge" without merging -- just keeping track of the current highest value (and prev in case arrays are same size and we need to compute mean as average of the middle two elements).
import java.util.Arrays;
public class TwoArrayMedian {
/**
* Find the median of two sorted arrays of 8 bit ints.
*/
public static void main(String[] args) {
byte[] a = {1, 3, 5, 7, 9, 11};
byte[] b = {2, 4, 6, 8, 10, 12};
int len = a.length + b.length;
int aIndex = 0;
int bIndex = 0;
boolean evenCount = (len % 2) == 0;
int mid = len / 2;
if (evenCount) mid += 1;
int curr = 0;
int prev = 0;
for (int i = 0; i < mid; i++) {
prev = curr;
if (aIndex > a.length || a[aIndex] > b[bIndex]) {
curr = b[bIndex++];
}
else {
curr = a[aIndex++];
}
}
double median;
if (evenCount) {
median = (curr + prev) / 2.0;
}
else {
median = curr;
}
System.out.println("Median of " + Arrays.toString(a) + " and " + Arrays.toString(b) + " is " + median + ".");
}
}
Rune time is closer to n/2 -> O(n) where n is combined length of both arrays.
- FredCycle May 07, 2014Look up "Hawstien"s solutions for the "Cracking the Coding Interview" in C++ on GIT. He solved this very nicely.
git... /Hawstein/cracking-the-coding-interview/blob/master/9.3.cpp
I like this solution better than the one in the book. It makes a lot more sense to me.
I took a different direction. The properties of the points of all four points of the square are covered by checking min/max x/y. So, multipass through the points.
1. Pass 1: Get all mins and maxes.
2. Create an array of 4 bools and check for all four points.
3. Check to make sure all 4 bools are set. If someone rants about the cost of scanning an array of 4 items, I'll laugh. If a programming language is that bad, why use it?
I'm kinda into maintainable and readable over compact. That took ten minutes to write and test.
import java.awt.Point;
import java.util.Arrays;
public class PointsAreSquare {
/**
given 4 points, whose x and y coordinates are both integers.
they are all different. write a function to check if they form a square.
i forgot to point out that the points can be given in any order
*/
public static void main(String[] args) {
Point[] points = new Point[4];
points[0] = new Point(3, 1);
points[1] = new Point(-1, 1);
points[2] = new Point(3, -2);
points[3] = new Point(-1, -2);
int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
// Find min/max x/y
for (Point p : points ) {
minX = Math.min(minX, p.x);
maxX = Math.max(maxX, p.x);
minY = Math.min(minY, p.y);
maxY = Math.max(maxY, p.y);
}
// Array of booleans to mark if
// we find points in cc direction starting at UL
boolean[] found = new boolean[4];
for (Point p : points) {
//UL:minX, maxY
if (p.x == minX && p.y == maxY) found[0] = true;
//UR:maxX, maxY
if (p.x == maxX && p.y == maxY) found[1] = true;
//LR:maxX, minY
if (p.x == maxX && p.y == minY) found[2] = true;
//LL:minX, minY
if (p.x == minX && p.y == minY) found[3] = true;
}
for (boolean b : found) {
if (!b) {
System.out.println("Points don't represent a square.");
return;
}
}
System.out.println("Points " + Arrays.toString(points) + " are a square.");
}
}
That was a great article. Here's a java version of the "efficient" version of that code:
public class IndicesMaxDiff {
/*
Yahoo!:
Given an Array A[], find the maximum j - i such that A[j] > A[i].
For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1)
Time Complexity should be less then O(n^2)
*/
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
public static int maxIndexDiff(int[] arr)
{
int maxDiff;
int i, j;
int n = arr.length;
int[] LMin = new int[n];
int[] RMax = new int[n];
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for (i = 1; i < n; ++i)
LMin[i] = Math.min(arr[i], LMin[i-1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n-1] = arr[n-1];
for (j = n-2; j >= 0; --j)
RMax[j] = Math.max(arr[j], RMax[j+1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0;
j = 0;
maxDiff = -1;
while (j < n && i < n)
{
if (LMin[i] < RMax[j])
{
maxDiff = Math.max(maxDiff, j-i);
j = j + 1;
}
else
i = i+1;
}
return maxDiff;
}
/* Driver program to test above functions */
public static void main(String[] args) {
int[] arr = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
int maxDiff = maxIndexDiff(arr);
System.out.println("Max diff for " + Arrays.toString(arr) + " is " + maxDiff + ".");
return;
}
To whoever said that solution is O(n^2), I'd love to hear more of an explanation. I'm with nperez who points out that it's 4 passes that are at most n long which is still O(n)
- FredCycle March 27, 2014import java.util.Arrays;
public class SlidingWindowMin {
/**
* @param args
*/
public static void main(String[] args) {
/*
* Given an array of integer, find the minimum in the sliding window of size 4, in most optimal way.
* ex [2,1,3,4,6,3,8,9,10,12,56]
* Output : [1,1,3,3,3,3,8.....]
*/
int[] a = {2,1,3,4,6,3,8,9,10,12,56};
int window = 4;
int min = Integer.MAX_VALUE;
int[] ret = new int[a.length - window + 1];
if (window > a.length) System.exit(-1);
for (int i = window - 1; i < a.length; i++) {
min = Integer.MAX_VALUE;
for (int j = i - window + 1; j <= i; j++) {
if (a[j] < min) min = a[j];
}
ret[i - window + 1] = min;
}
System.out.println("In: " + Arrays.toString(a) + ", out: " + Arrays.toString(ret));
}
}
Better to just count as if you were merging, but just don't merge.
public class KthElementTwoSortedArrays {
public static void main(String[] args) {
int[] b = {2,3,4,5,6,7,8,9};
int[] a = {10,11,12,13,14,15,16,17,18,19};
int k = 14;
int count = 1;
int i = 0;
int j = 0;
while (i < a.length || j < b.length) {
int n;
if (i < a.length && (j > b.length - 1 || a[i] < b[j])) {
n = a[i];
i++;
}
else {
n = b[j];
j++;
}
if (count == k) {
System.out.println("Kth entry (K = " + k + ") in merged array would be: " + n + ".");
break;
}
count++;
}
}
}
public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;
for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a[0]);
continue;
}
next = a[i];
if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();
while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}
/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}
/* push next to stack so that we can
find next greater for it */
s.push(next);
}
while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}
public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}
public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));
System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}
/*
* Works...
* crazyforcode.com/greater-element-array/
* Plus I added the hash table to fill the output array.
*/
public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;
for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a[0]);
continue;
}
next = a[i];
if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();
while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}
/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}
/* push next to stack so that we can
find next greater for it */
s.push(next);
}
while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}
/*
* mycppexperiments.blogspot.com/2013/02/reorder-array-elements-with-1next dot html
*/
public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}
public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));
System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}
Seems there's a lot of confusion around two common, but different problems.
Next GreatER Element is the hard one that wants to use fancy stack algorithms.
Replace each element with the next element in the array greater than this one.
Next GreatEST Element:
Replace each element with the greatest element to it's right.
This one seems straightforward with the most common solutions I found just being O(n) solutions which track a maximum and run from right to left. This is a combination of some great code I found plus my additions to make sure it got what I thought was the right answer:
/*
* crazyforcode.com/greater-element-array/
* Plus I added the hash table to fill the output array.
*/
public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;
for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a[0]);
continue;
}
next = a[i];
if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();
while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}
/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}
/* push next to stack so that we can
find next greater for it */
s.push(next);
}
while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}
/*
* url mycppexperiments.blogspot.com/2013/02/reorder-array-elements-with-1next.html
*/
public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}
public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));
System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}
This would have been my interview response -- best I could think of with no prep or lookup...
Not the most efficient solution out there, but a college kid could maintain it.
- FredCycle May 08, 2014