Sidhu
BAN USER
Time Complexity: O(n)
Space Complexity: O(n)
package ds;
import java.util.concurrent.atomic.AtomicInteger;
public class surpass {
public static void main(String a[]) {
int[] aa = {2,7, 5, 5, 2, 7, 0, 8, 1};
System.out.print(maxSurpass(aa)) ;
}
public static int maxSurpass(int[] a) {
int max = 0;
Node[] surpass = new Node[a.length];
for (int i = 0; i < a.length ; i ++) {
if (surpass[i] == null)
surpass[i] = new Node(a[i]);
for ( int j = 0; j < i; j++)
if (surpass[j].getData() < a[i])
surpass[j].incrementSurpass();
}
for (int j=0; j < surpass.length; j++)
if (surpass[j].getSurpass().get() > max)
max = surpass[j].getSurpass().get();
return max;
}
}
class Node {
private int data;
private Node next;
private AtomicInteger surpass;
Node(int d){
this.data = d;
this.surpass = new AtomicInteger(0);
}
Node(int d, Node n) {
this.data = d;
this.next = n;
}
public void incrementSurpass() {
this.surpass.getAndIncrement();
}
public int getData() {
return data;
}
public Node getNext() {
return next;
}
public AtomicInteger getSurpass() {
return surpass;
}
public String toString() {
return "[ Data: "+ getData() + "; surpass: " + getSurpass().get() + "]";
}
}
I am not sure if you read the code carefully, so let me put things in clear perspective for you:
1) The timer object is of type "java.util.Timer" and not the timer time() class which the author mentions in the question. So they are two separate entities. java.util.Timer is a class under the java.lang package. [See: docs.oracle.com/javase/1.5.0/docs/api/java/util/Timer.html].
2) My assumption of using the milli sec doesn't make any difference in the output required / expected. If there were say 1,000 ticks happening in 100 nano seconds then from my logic they would appear to happen in 0 millisec ( they actually happened in 0.000100 millisec). Since we are only concerned with the number of ticks (or number of times increment was called) so the code would still return 1000 ticks. which is the response expected here.
3) The problem also states that the space usage shouldn't grow depending on the number of call backs to increment(), since the API has methods defined only till the getCountInLastDay() so I am clearing any timers or calls which happened more than 24 hours ago will not only put a cap on the storage but also remove any data which is stored but never used or read anymore.
4) You still haven't explained why you have used 10^9 multiplication factor here. The question says "timer time()" has nano second precision so that "just" means if there were say 10,000 ticks happened in 100 nano seconds then you will be able to differentiate the difference in the timings of the individual ticks to the nano second level. It has nothing to do with the address space or how much memory will be consumed. (fyi : the default precision level is till microseconds so nano second isn't that far either :P )
5) Assuming you took some basic programming course :P at some level in your life, let me ask you on what basis do you have your "wild" assumption of using 32 "bytes" per message, what programming language uses that much memory to store information for primitive or non primitive variables. Please enlighten me. :) I may have still let you go if you had used "32 bits" NOT "32 bytes" to store information. With these two corrections I am sure your claim of using petabytes of memory will come down.
class A implements RealTimeCounter {
private volatile ArrayList<Long> timers = new ArrayList<Long>();
private static java.util.Timer timer = new Timer();
private static TimerTask task = new TimerTask() {
public void run(){
// query for today's date
removeEntriesLongerThanDay();
}
};
static {
// run once every day say 10pm, you can change this to any other time or any frequency.
DateTime now = new DateTime(DateTimeZone.forID("US/Eastern"));
DateTime fivePM = now.withTime(22,00,0,0);
timer.scheduleAtFixedRate(task, fivePM.toDate(), 1000*60*60*24);
}
public void increment() {
timers.add (System.currentTimeMillis()) ;
}
private int getCounters(long n) {
int count = 0;
long currentTime = System.currentTimeMillis();
for (Long val:timers) {
if ( (( currentTime - val )/ n) > 0 )
count ++;
}
return count;
}
public int getCountInLastSecond() {
return getCounters(1000) ;
}
public int getCountInLastMinute() {
return getCounters (60*1000) ;
}
public int getCountInLastHour() {
return getCounters (60*60*1000) ;
}
public int getCountInLastDay() {
return getCounters (24*60*60*1000) ;
}
/**
* Removes the entries which are older than day,
* this will make sure the ArrayList 'timers' doesn't
* grow very very long as we are cleaning up entries eventually.
* @param null
* @return null
*/
private void removeEntriesLongerThanDay() {
if (getCountInLastDay() <= 0 )
return;
long currentTime = System.currentTimeMillis();
ArrayList<Long> removalIndexes = new ArrayList<Long>();
long n = 24* 60 * 60 * 1000; // Number of sec in 1 day.
for (int i = 0; i < timers.size(); i++) {
if ( (( currentTime - timers.get(i) )/ n) > 0 ) {
removalIndexes.add((long) i);
}
}
synchronized(timers){
for (Long index:removalIndexes)
timers.remove(index);
}
}
}
I think this solution will be much easier and simpler.
As the formula to find the sum of consecutive n numbers is [(n(n + 1) )/ 2]
the sum of numbers from 1 to 9 is 45.
So in my approach I add each of the n rows and check if the sum is less than 45 or not if there is a row whose sum is less that 45 than the algorithm stops and I output the row number as the error row if all the rows add upto 45 then I add each of the columns separately if the sum is less than 45 you stop and return with the column number (or false as exit status) else if all the columns also add upto 45 then exit as null (or true as success).
In addition to this, we can further enhance the solution as follows so that any malicious user can't enter fake numbers to add them to 45 and pass the check.
1.) If we find a row or a column whose sum is less than 45 or more than 45 then we can iterate through the elements of the array and find out the missing/duplicated element.
2.) if all the rows and columns add upto 45, then we can use this approach:
Hashtable<Integer,Integer> count = new Hashtable <Integer,Integer>();
iterate through all the elements and add them to the hashtable if the element doesn't exist then add as
count.put(element,1);
if the element exists then add as
count.put(element,count.get(element)+1));
Once all the elements are inside the hashtable then iterate through all the hash keys and check if the count == 9 or not, if not then STOP and output as FAILURE else SUCCESS, also if any element is higher than 9 or less than 1 than again you STOP and return FAILURE. The hashtable keySet MUST HAVE all the numbers between 1 to 9 and hence no solution like 555 555 555 is acceptable.
Running time analysis:
To sum up all the rows will take constant time O(c1)
To sum up all the columns will again take constant time O(c2)
now if we were to go further even then
iterating through all the elements inside the sudoku will take constant time O(c3) and hashtable operation is O(1) time (assuming no one over thinks the problems to implement a superior hash function :P ).
so the total is: O(c1) + O(c2) + O(c3) + (constant time to access hash table entries) = linear time.
I can think of the following approach, not sure if this is the best way to do it:
Lets say the target is T, and array given is 'a' having 'n' elements
Sort the array by any sorting algorithm say merge sort or quick sort - that will take (n (log n)) as the total time, now if a is sorted where a[0] is the smallest element, if a[0] < T then return false and exit
If a[0] > T then, I will use a random approach now,
Pick any element in the array a, say element x, now you know the value of a[x], so we have the following equation
a[x] + y = T, and we can find out y using this, this will take a constant time,
now we can quickly scan the array to see if y exists or not, that will take n-1 comparisons, if we find 'y' then return true and exit, if we don't then we continue scanning the remaining n-1 elements , the worst case is that we scan all the elements and don't find a match so this will take O(n2) time,
so the worst case time will be O(n2)
and the best case is n log n
Can't think of a better solution. any comments highly appreciated.
Python implementation
def missing(r): # R is a string of numbers if not r: return -1 check_missing, inc, start, missing = True, 1, 0, -1 seq = inc while (check_missing): x, y, z = int( r[start:start+inc] or 0), int( r[start+inc:start+2*inc] or 0 ), int( r[start+2*inc:start+3*inc] or 0 ) if (((x+1) == y and (y+1)== z) or ((x+2) == y and (y+1)==z) or ((x+1) == y and (y+2)==z) or ((x+2) == y) ): seq, check_missing = inc, False else: inc = inc + 1 if check_missing and ((start+3*inc) > len(r)): raise ValueError("No sequence") find_missing, f = True, 0 while(find_missing): if (int(r[f:f+seq])+2==int(r[f+seq:(f+2*seq)])): missing, find_missing = int(r[f:f+seq])+1, False else: f = f+seq if ((f+seq) >= len(r)): find_missing = False return missingI tried a few test cases as well.
class MyTests(unittest.TestCase): def get_val(self, myseq): return mycode.test.missing(myseq) def test_missing_no_missing(self): self.assertEqual(self.get_val("121314151617181920212223242526272829303132"), -1, "Values don't match.") def test_missing_start(self): self.assertEqual(self.get_val("57"), 6, "Values don't match.") def test_missing_last(self): self.assertEqual(self.get_val("55565759"), 58, "Values don't match.") def test_missing_triple(self): self.assertEqual(self.get_val("596597598600601602"), 599, "Values don't match.") def test_missing_single(self): self.assertEqual(self.get_val("568910"), 7, "Values don't match.")Reviews appreciated.
- Sidhu August 28, 2016