NoOne
BAN USERLook at that link there? That is the language we have created.
 1of 1 vote
AnswerSuppose there is a function given to you that:
def get_friends( person_id ) { /* returns friends of person */ }
How you are now going to recommend friends to a person based on number of mutual friends? So, come up with the function:
 NoOne in Indiadef friend_reco( person_id, max_no_of_friends ){ }
 Report Duplicate  Flag  PURGE
Amazon SDE3 Algorithm  0of 0 votes
AnswersGiven billions of Identity cards of the form :
card : { my_id : "my id", "moms_id" : "mom id", "dad_id" : "dads id" }
If one gives you two Person's id, how can you tell if these 2 persons are blood related.
So, write a function that is:
 NoOne in Indiadef is_blood_related( person_id_1, person_id_2 ) // go on..
 Report Duplicate  Flag  PURGE
Amazon SDE3 Algorithm  2of 2 votes
AnswersGiven an unsorted array of integers, find the length of the longest consecutive elements sequence.
 NoOne in India
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4].
Return its length: 4.
Your algorithm should run in O(n) complexity. Report Duplicate  Flag  PURGE
Uber Senior Software Development Engineer Algorithm  1of 1 vote
AnswersThe stock exchanges work with price matching. A seller comes with a price, and a buyer, given asking for the exact same price are matched, and in quantity.
 NoOne in India
Design a system that works.
Considerations:
1. More than a million buy/sale happens in a second.
2. One needs to show a ticker prices  last sold price of a stock. Report Duplicate  Flag  PURGE
Myntra Software Architect Algorithm  0of 0 votes
AnswersCreate a data structure that stores integers, let then add, delete. It also should be be able to return the minimum diff value of the current integers.
 NoOne in India
That is,
min_diff = minimum (  x_i  x_j  )
Example:
1,3,4,10,11,11
min_diff = 0
1,3,4,10,11,14
min_diff = 1 Report Duplicate  Flag  PURGE
Uber Senior Software Development Engineer Algorithm  0of 0 votes
AnswersThe original question can be found from here :
 NoOne in India
franklinchen.com/blog/2011/12/08/revisitingknuthandmcilroyswordcountprograms/
Read a file of text, determine the *n* most frequently used words, and print out a sorted list of those words along with their frequencies.
In the same spirit of the history:
1. Do it using pure shell scripting
2. Do it in the favourite language of your choice
Try to minimise code and complexity. Report Duplicate  Flag  PURGE
Deshaw Inc Software Developer Algorithm  0of 0 votes
Answer1. If I say quick sort takes O(e^n ) on the average, would I be wrong?
 NoOne in India
2. Do you think O( f ) is a good idea for real engineering?
3.Given a choice, what other 'order of' measure would you propose to use ?
4. Do you see a real problem with the modified *order of* ?
5. If you were to sort 10 elements, what sorting method would you have used?
6. If you were to sort 1 trillion unicode characters, what sorting method you would have used? Report Duplicate  Flag  PURGE
Microsoft SDET Algorithm Math & Computation  0of 0 votes
AnswersThe actual problem from question?id=6289136497459200
Implement pow, with :// Assume C/C++, as of now double pow ( double x, double power )
No library functions allowed.
Should return : x^power
=== Edit ===
People took it a bit trivially, thus examples should help :
 NoOne in United Statesx = pow ( 4, 0.5 ) // x = 2.0 x = pow ( 8, 0.333333333 ) // 1.99999999986137069 x = pow ( 10.1 , 2.13 ) // 137.78582031242644
 Report Duplicate  Flag  PURGE
Microsoft SDET Algorithm  0of 0 votes
AnswersFrom here : question?id=5660692209205248
 NoOne in United States
Inorder traversal:
A>B>C>D>E>F>H>L>MP>R>S>T
Write a function (pseudocode is fine) that given a starting node, advances to the next inorder node in a binary tree.
Please also provide a datastructure definition of a node. Report Duplicate  Flag  PURGE
Arista Networks Software Developer Algorithm Trees and Graphs  0of 0 votes
AnswersApparently DESCO asked it. It was faulty, and I am fixing it. The physics was wrong. A mono pole is an abstract magnet with either the north or the south pole of the magnet.
[ en.wikipedia.org/wiki/Magnetic_monopole ]
Imagine you are given such *n* monopoles, all of the same type, say North type. Thus, all of these repel one another. The force of repulsion follows inverse square law :
[ en.wikipedia.org/wiki/Inversesquare_law ]
That is, given two such monopoles with a distance *r* between them, the force of repulsion between them is given by :F = ( 1.0 ) / ( r ** 2 )
Now, suppose you are also given an array of *n* number of positions over X axis, like : [ 0, 1, 4, 10 , 21 , .. ] where you need to place the monopoles ( imagine they are hold tight there, and do not move away ).
 NoOne in United States
After placement, you are given another monopole, of different type S, say. Find positions to place the monopole so that it is stable.
Fixes from the original question :
[geeksforgeeks.org/deshawinterviewexperienceset19oncampus/ ]
1. Monopoles exhibit inverse square law, not inverse law.
2. It is impossible to have stable configuration using same type monopole, so one must use another type, repulsion is not stable, attraction is.
( Terrible physics mistakes )
PS. Do not try to do binary search here. Binary search assumption is underlying linearity of the structure, thus, effectively there are proportionate elements in left and right. In the classic cases of sorted array, the expectation is 50/50. But here due to non linearity (inverse square) , it won't work. Report Duplicate  Flag  PURGE
Deshaw Inc Software Developer Algorithm  0of 0 votes
AnswersGiven a set of numbers, find out all subsets of the set such that
the sum of all the numbers in the subset is equal to a target number.s = [ 1, 2, 3, 4, 5 ] target = 5 op = [ [ 1,4 ] , [2,3] , [5] ]
Application: Given a fixed budget, and work items we are doing back filling to check what all we can attain with the budget.
Continuation. Imagine the set is actually a set of work items, with cost and utility involved :def work_item : { name : 'foo bar' , cost : 10 , utility : 14 }
Now, solve this to maximise utility.
Continuation. Imagine that the work items are related, so that, if work item w1 is already in the
subset of the work items selected, w2 's utility increases further!.
( Can you imagine how it can happen? Effectiveness of Mesi increases when he plays for Barca)
So, you are given a list like this :w1 > normal utility 14, with w2 20, ....
Now maximize payoff.
NOTE: Payoff is a matrix. This comes from game theory.
Hence, a payoff matrix looks like :w1 w2 w3 w4 .... w1 w1 w2 w2 w3 w3 w4 w4
A cell ( i,j) is filled up with if a list contains both wi and wj, then how much the payoff would be. It is a symmetric matrix.
 NoOne in United States Report Duplicate  Flag  PURGE
Amazon SDE3 Algorithm  0of 0 votes
AnswersWe tend to use computer to solve practical problems that actually earns or save dollars. Here is something that happens across the stock exchanges : people buy and sell stocks.
 NoOne in India
We generally use automated intelligent systems to buy and sell stocks. That part is too much mathematics, and beyond scope of this interview. There is another part. Suppose the system issues a buy order : buy 1000 Microsoft stock. Now, there are more than 1 ( in fact 10 ) active exchanges from where we can buy MSFT. There is a slight price delta, which keeps changing over time. There is another problem. In each stock exchange, prices are stacked, that is :
1. For first 100 stocks prices are 55$.
2. Next 200 stocks, prices are 55.2$.
... etc, and you got the idea. Even this stacks are changing over time.
Thus, here is the problem to solve. Design and implement a system such that one can buy n stocks with minimal price.
Also, in the same spirit, the same system should be able to sell n stocks with maximum payoff possible.
This is a non trivial problem, for Quant systems.
There are always k no of exchanges to hit. Report Duplicate  Flag  PURGE
Goldman Sachs Software Engineer / Developer Algorithm Cache Computer Architecture & Low Level Computer Science Distributed Computing Large Scale Computing Math & Computation Software Design  0of 0 votes
AnswersAs you know, Computers were invented to solve practical business problems, we tend to ask practical applied questions. One of the key areas where we want to apply computers is simulation. As most of the people working in software are Engineers, here is the problem. It is called 3 body problem.
 NoOne in India
3 Bodies with masses [ m1, m2, m3 ] are initially positioned in the 3 points in the space, thus, having positions [ P1, P2, P3 ].
Observe that each Pi is nothing but [ xi, yi, zi ].
Once the initial condition is set, definitely gravity would work and they would start falling against each other. Write code to simulate this problem. Imagine G, the constant of gravity as 1.
How do you go about simulating it?
Hint : feynmanlectures.caltech.edu/I_09.html see 9.5
Face to face. Pen and Paper. Panel Interview, 2 person Panel. 60 Minutes. For Engineers only, was specifically told about it. Report Duplicate  Flag  PURGE
Software Developer Algorithm Computer Science Graphics Math & Computation Programming Skills  0of 0 votes
AnswersGiven a convex polygon ( is planer as opposed to a polytope) and a point one had to tell if the point lies inside the polygon or outside the polygon.
 NoOne in India
To understand convexity : mathopenref.com/polygonconvex.html
Thus the question comprise of 3 sub problems :
1. How to store a polygon.
2. How to define inside and outside of a polygon.
3. How to solve the actual one, given 1,2 ? Report Duplicate  Flag  PURGE
Deshaw Inc Software Developer Algorithm  0of 0 votes
AnswersAs you guys know, C did not have,and does not have anything called class. C++ has them. Now, C++ was written using C. In fact, C++ initially was called C with classes.
 NoOne in India
Thus, here is the problem for you.
Given you have C, and you need to implement class like behaviour, how you would do it? Specifically, implement the following in C :
1. A Simple Hello class with hello() function printing "Hello, World" .
2. A new operator which enables creating this constructor less class.
3. A delete operator that deletes the pointer.
How would you do it? Report Duplicate  Flag  PURGE
Deshaw Inc SDET C  0of 0 votes
AnswersLinux has this nice command called *tree*.
 NoOne in India
If you did not use it, please take a look around.
You do not have to write one. BUT, you have to do something similar. Given a file name ( not a path ), and an initial directory, you have to list all the file paths, which matches the file name, case should not be considered.
Also allow regex match.
Again, the problem is non trivial.
It was expected to ask the right questions. Report Duplicate  Flag  PURGE
SDET Algorithm Operating System  0of 0 votes
AnswersThere is this nice tiny *nix utility called *wc*.
The idea here is :wc file_name
prints :
 NoOne in India
character count of the file.
Word count of the file.
Line count of the file.
You have to implement your own *wc* program.
NOTE: The problem is non trivial for 3 reasons.
It was expected to ask about the non triviality. Report Duplicate  Flag  PURGE
SDET Algorithm Operating System  0of 0 votes
AnswersNone actually understands how garbage collection works, albeit people ask this in the interviews. Nonetheless, we are going to ask you something very similar. Here is the problem.
Take an array of bytes, perhaps 1MB in size.
Implement these two operations:ptr_structure = alloc ( amount_of_storage ) freeed = free ( ptr_structure )
Now, here is your problem. alloc must allocate contiguous storage. If it is not possible, you need to compact ( defragment ) memory. So, you need to implicitly write a :
defragment() // defragments memory
Worse is coming. Even imagining you have written a stop the world defragmenter, after you reallocate, how the ptr_structures would actually work?
 NoOne in India
Solve this whole problem.
Time allocated was 1 hour. Face to face, panel with 2 interviewers. Report Duplicate  Flag  PURGE
SDET Algorithm Assembly Computer Architecture & Low Level Computer Science Data Structures  0of 0 votes
AnswersImagine there are brick boulders, all of integer size.
Their sizes are stored in an array.
The figure looks something like this :
peltiertech.com/Excel/pix2/Histogram2.gif
Now, suppose someone is pouring water into it till water starts spilling.
You have to answer how much water the boulders are holding up.
 NoOne in Indiadef water_holding( arr ) { /* answer this */ }
 Report Duplicate  Flag  PURGE
Deshaw Inc SDET Algorithm  0of 0 votes
AnswersXPATH implementation problem.
 NoOne in India
Here is the problem.
Implement XPATH expressions, given there is a DOM tree :
1. $x('//*[text() = "abc"])
How do you think it is implemented? Write code, imagine you have a general purpose tree.
2. $x('//span[text() = "abc"])
How do you think it is implemented? Write code, imagine you have a general purpose tree.
Now, explain which one would be faster, and why?
Explain from the design and the code you have written. Report Duplicate  Flag  PURGE
SDET Algorithm Application / UI Design  0of 0 votes
AnswerAs you know, every OS comes up with this tiny application called the calculator. It is good. Now, here is our problem. If we try to implement the function
def calculate( operand, operator, operand ) { /* Do Interviewers bidding here */ }
I have to write if upon if upon if upon if to do for all operators. Moreover, some operators are not even binary! Take example the abs() or say the negate()!
 NoOne in India
Bigger problem persists. With the if mode, we can not even add operators as we wish to without changing code!
But that is a sin. So, what do we do? That is question 1.
In question 2, as a software tester, how do you propose to test and automate the above? Writing more if than the developer is not allowed. Report Duplicate  Flag  PURGE
SDET Algorithm Data Structures Object Oriented Design Programming Skills Software Design  0of 0 votes
AnswersWe all know databases are very very slow. In fact they are so slow that very serious people who wants to do volumes of read operation and search operations write their own implementation. In this question, you would be asked to do the same, for a very limited operation  select.
Every item stored has this field called timestamp.
Now, here is the problem you need to solve :select items where time < some_time select items where time < some_time and time < another_time select items where time > some_time
Imagine you have millions of data rows. How to store it in HDD, and how to load, entirely your problem. None is going to insert anything on existing data  only read.
 NoOne in India
Write an algorithm that solves this problem, and a data structure that works as storage for the data. Report Duplicate  Flag  PURGE
SDET Algorithm Database  0of 0 votes
AnswersImagine you are given the instructions :
GOTO <LABEL> WHEN <CONDITION> NOP ; no operation
Implement the following using it:
 NoOne in India
1. If condition.
2. If else condition.
3. If else if else condition.
4. While loop
5. for loop. Report Duplicate  Flag  PURGE
SDET Assembly  0of 0 votes
AnswersGiven brackets, e.g. '(' and ')' as the only symbols, write a function that would generate : true, if the brackets are matching, false if the brackets are not matching.
 NoOne in India
Almost everyone can do the above.
Now, prove that it works.
Also tell which class of grammar the string belongs to.
Showcase why your algorithm is a language recogniser for the same. Report Duplicate  Flag  PURGE
SDET Automata  0of 0 votes
AnswersYou are given 20 questions to solve in 20 minutes.
 NoOne in India
If you successfully solve the question, you would receive 2 marks.
If you failed to solve the question, and you do not try it ( let it untouched ) , you would receive 0 marks. If you solve it wrong ( i.e. not the correct answer )  you would receive 1 ( negative) .
With the story, here are the problems:
1. Write an algorithm, which, given an input array ( set ) of questions, and varying probability ( 0 <= p <= 1 ) of can do and can not do per question, generates a strategy for solving the paper to generate maximum expected pay off.
2. Given the question paper is multiple choice, between 4 choices ( a,b,c,d ) do a bias analysis ( e.g. if more a's are coming than 'c's ), and decide if you would like to probabilistically take risk and mark some to increase pay off.
Obviously, you can get a maximum 40, and a minimum 20.
3. Now, put yourself in the position of the examiner, and try to ensure it is almost impossible to increase payoff by random selection over the questions. Try to negate the bias. That is question 3.
In all 3 cases write an algorithm. Face to face interview, time allocated was 60 minutes. Panel Interview. Report Duplicate  Flag  PURGE
unknown SDET Algorithm  0of 0 votes
AnswersFind the n'th Ugly no. An ugly no. is defined as a no. which are of the form :
n = ( 2 ** p ) * ( 3 ** q ) * ( 5 ** r )
with p,q,r >= 0 and are integers not all equal to zero.
 NoOne in United States
You must not memorise the whole sequence, as n can be really large.
Hint : use number theory to figure out the pattern of the increasing sequence. Report Duplicate  Flag  PURGE
Algorithm  0of 0 votes
AnswersGiven an array, move the smaller no to the left and the larger nos to the right. The relative positioning between the small no's and the relative positions between the large nos should not change.
The original ( ill formulated ) question can be found here :
question?id=5756583549075456.
Example :a = [ 6 4 5 0 2 1 11 1 ] after_a = [ 0 , 2, 1, 1, 6, 4, 5, 11 ]
Note, for lack of good explanation, please do not laugh at the poster in the solutions. After all, they are trying to help or get help.
 NoOne in United States Report Duplicate  Flag  PURGE
Arrays
/*
Observe that the problem is that of finding locations where
we can cut the string.
Given a string of length 's' has exact s1 locations where we can cut it
That s1 becomes the number of choices = n.
Clearly then the number of comma = k is the cut locations to be selected.
It is obvious that the order in which the cut was imposed does not matter.
Thus, the choices are C(n,k).
Thus, the problem is:
1. finding combinations of cut
2. Applying the cuts
3. Maintaining a max out of the cuts
*/
def do_fancy(string, k){
n = size(string)  1
range = [0:k+1]
max = 0
for ( t : comb(range,k) ){
start_inx = 0
words = list()
for ( i = 0; i < k ; i+= 1 ){
words += int( string[start_inx:t[i]] )
start_inx = t[i] + 1
}
words += int( string[start_inx:1] )
#(m,M) = minmax( words )
#(m,max) = minmax( max, M )
}
max // return
}
println( do_fancy( '89769957',3 ) )

NoOne
February 09, 2018 /*
Makarand is right.
The best way to handle it is O(nk), where:
n is the size of the dictionary
k is the average size of the words in the dictionary by unique characters
Observe the use of counter, what we are trying to do is multiset.
en.wikipedia.org/wiki/Multiset
Given zoomba defaults into multiset using mset()
and let's set operation ( subset ) over multisets
The problem becomes trivial code.
== Appendix : Multiset Subset Operation ==
Given a list/sequence, a multiset is M = { (key,count) }
Now, M1 is subset of M2, if and only if :
for all key in M1,
1. key exists in M2
2. count of key in M1 <= count of key in M2
==
And now the solution
*/
// step 1, load dictionary and make each entry multiset :: one time
md = list ( file('/BigPackages/words.txt') ) as { [ $.o, mset( $.o.toCharArray ) ] }
// get input word
input_word = 'makarand'
test_word = mset( input_word.toCharArray )
// where each word in md is a subset ( multiset sense ) of test_word O(n*k)
subset_words = select ( md ) where { $.o.1 <= test_word } as { $.o.0 }
// we are done
println( subset_words )
Yielding:
[ a,aa,aaa,aam,ad,adam,adar,adm,adman,ak,aka,akan,akra,am,ama,amadan,amar,amarna,amra,an,ana,anam,anama,and,anda,ankara,ar,ara,arad,arak,arank,ark,arm,armada,arn,arna,d,da,dak,dam,dama,daman,damar,damn,dan,dana,dank,dar,dark,darn,dk,dkm,dm,dn,dr,dram,drama,drank,,k,ka,kaama,kam,kama,kan,kana,kanara,kand,karanda,karma,karn,km,kn,knar,kr,kra,krama,kran,krna,m,ma,maad,maana,maar,mad,makar,makara,makran,man,mana,manada,manak,mand,mandar,mandra,mank,mar,mara,mark,marka,md,mk,mn,mna,mr,n,na,naa,naam,nad,nada,nak,nam,namda,nar,nard,nark,nd,nm,nr,r,ra,raad,rad,rada,radman,rakan,ram,ramada,ramadan,ran,rana,rand,rank,rd,rm,rn,rnd, ]

NoOne
October 22, 2017 /*
Step 1: Pick 5 numbers from 1...52. That is al combinations of C(52,5)
achivable using comb([1:53],5)
Now, pick any of these 4 ops [ +,,*,/] on these 5 numbers.
Use floating point to be exact
Each permutation has then 4^4 ways of assigning operators.
stringify it, do an eval.
Check it out if result is 42
*/
__OPS__ = { _'0' : '+' , _'1' : '' , _'2' : '*' , _'3' : '/' }
def do_facebook(){
total_ops = 4 ** 4
// create the operator varities
ops = list()
for ( k : [0:total_ops] ){
s = str(k,4)
s = '0' ** (4  size(s)) + s // left pad by '0'
ops += s
}
// select tuple from C(52,5) :: for demo.. we have to 8
for ( nums : comb( [1:8] , 5 ) ){
// select operators....
for ( op : ops ){
s = ''
for ( i = 0; i < 4; i+= 1 ){
s += ( str(nums[i]) + '.0' + __OPS__[ op[i] ] )
}
s += ( str(nums[4]) + '.0' )
// do eval ?
x = #'#{s}' // yes
if ( x == 42.0 ) {
// the answer to life, universe and everything...
println(s)
}
}
}
}
do_facebook()
Yields...
=====
1.0*3.0*4.0+5.0*6.0
1.0/2.0*3.0*4.0*7.0
1.0+2.0*3.0+5.0*7.0
1.0+2.0+4.0+5.0*7.0
1.0*3.0+4.0+5.0*7.0
1.0+2.03.0+6.0*7.0
1.0+2.0*4.0*6.07.0
1.0+3.04.0+6.0*7.0
2.0+3.0+5.0*6.0+7.0
2.0+3.05.0+6.0*7.0
1.0+4.0+5.0*6.0+7.0
1.0+4.05.0+6.0*7.0
=====
Analysis.
The problem is that of :
1 + 3 + 5 + ...
That is sum of n odd numbers.
That is known to be : 9math.com/book/sumfirstnoddnaturalnumbers
=> n^2.
Thus we are to find, if the number given is a perfectly square no. or not.
Now, given we do not want to use square root, which is
a terribly complex operation, we can do as follows:
[ careercup.com/question?id=14797683 ]
@milincjoshi :
You do not need to do recursion at all, to solve this sort of problem. Observe that the problem can be partitioned into two unrelated problems.
[1] Given a list of list, find which lists has the exact sum as S.
Now, if you were to think in terms of SQL, that will be :
select from whatever where sum( all columns ) == S
Which is a very neat and easy problem to solve.
[2]
Now, who generates this list of list? That is where the problem lies. The problem says, all possible subsets of a set. Ah. That is a power set. Google it up. There are many ways to generate a list of all possible subsets of a set, and one is clearly through recursion.
But that is the lamest way of doing it, computationally. Here, we can use Ramanujan's method. What is that?
Imagine for every item in the set ( list ) you can choose to take the item, and choose not to take the item. So, if the list is :
{ 1, 3, 4, 5, 6, 15 }.
You can say, for 1, 0 ( not select ) , for 3 : 0, ... for 15 0.
That would be : 00000 > 0.
That selects the subset, empty set.
In the same way :
00001 > 1. selects the subset { 15 }.
So, what did we learn? We learn that iterating over different binary representation of
0 to 2^n where n is the number of items in the list, we can generate a pattern
which can then be used to select the corresponding subset!
That concludes our problem [2]!
Now, anyone can easily solve the problem with much cleaner, and neater code.
def find_median_lazy( a, b ){
s = sset() // sorted set
s += a
s += b
l = list(s) // done, to get indexer up
len = size(l)
if ( len == 0 ) return null
// and now the rest
mid = len/2
if ( len % 2 == 0 ){
// even case, then
return (l[mid1] + l[mid])/2.0
}
return l[mid]
}
println( find_median_lazy( [1,2] , [3,4] ) )
println( find_median_lazy( [1,2,5] , [3,4] ) )
def _merge_(a,b){
l = list()
i_a = 0
l_a = size(a)
i_b = 0
l_b = size(b)
while ( i_a < l_a && i_b < l_b ){
if ( a[i_a] < b[i_b] ){
l += a[i_a]
i_a += 1
} else {
l += b[i_b]
i_b += 1
}
}
while ( i_a < l_a ){
l += a[i_a]
i_a += 1
}
while ( i_b < l_b ){
l += b[i_b]
i_b += 1
}
l // return
}
def find_median_with_unnecessary_work(a,b){
l = _merge_(a,b)
len = size(l)
if ( len == 0 ) return null
// and now the rest
mid = len/2
if ( len % 2 == 0 ){
// even case, then
return (l[mid1] + l[mid])/2.0
}
return l[mid]
}
println( find_median_with_unnecessary_work( [1,2] , [3,4] ) )
println( find_median_with_unnecessary_work( [1,2,5] , [3,4] ) )

NoOne
September 25, 2017 /*
'NORTH' +
'0EAST' +
'0WEST' +
'SOUTH'
===========
'EARTH'
2(H + T) % 10 = H // constraint 1
(2(T + S) + 2(H+T)/5) % 10 = T constraint 2
Solving these two reduces the problem from 10! into 7! Baam.
That is heavily reduced.
Now let's see how H, T, S are there.
*/
def is_valid( map ){
north = map.h + 10 * ( map.t + 10 * ( map.r + 10* ( map.o + 10 * map.n )))
east = map.t + 10 * ( map.s + 10 * ( map.a + 10* ( map.e ) ) )
west = map.t + 10 * ( map.s + 10 * ( map.e + 10* ( map.w ) ) )
south = map.h + 10 * ( map.t + 10 * ( map.u + 10* ( map.o + 10 * map.s ) ) )
earth = map.h + 10 * ( map.t + 10 * ( map.r + 10* ( map.a + 10 * map.e ) ) )
earth == ( north + east + west + south )
}
digits = [0:10].asList
// find constraint 1
c1_pairs = join(digits,digits) where { ($.l != $.r) && ( $.l == 2 * sum($.o) % 10 ) }
// get next set of constrant 2 ?
c2_tuples = join(digits,c1_pairs) where {
#(H,T) = $.r
S = $.l
S !@ $.r && ( ( 2 *( T + S ) + 2*(H+T)/10 ) % 10 == T )
} as { d = { 'h' : $.r.0 , 's' : $.l , 't' : $.r.1 } }
rest_of_lettrers = [ 'a' , 'e' , 'n', 'o', 'r', 'u' ,'w' ]
// now that we have established the 3 items,
// rest 7 has to be chosen who are not ... in the group
for ( t : c2_tuples ) {
other_digits = digits  t.values
// now permuatate the other_digits
for ( p : perm( other_digits ) ){
// assign into map
d = dict( rest_of_lettrers ) as { [ $.o, p[$.i] ] }
d = t // the whole map
if ( is_valid( d ) ){
println( d )
}
}
}
Producing...
{a=1, r=6, s=0, t=8, e=5, u=3, w=7, h=4, n=2, o=9}
{a=2, r=5, s=0, t=8, e=6, u=1, w=7, h=4, n=3, o=9}
{a=3, r=1, s=0, t=8, e=7, u=9, w=2, h=4, n=5, o=6}
{a=3, r=5, s=0, t=8, e=7, u=9, w=2, h=4, n=6, o=1}
{a=0, r=5, s=1, t=6, e=7, u=2, w=4, h=8, n=3, o=9}
{a=3, r=2, s=1, t=6, e=7, u=9, w=4, h=8, n=5, o=0}
{a=3, r=4, s=1, t=6, e=7, u=9, w=0, h=8, n=5, o=2}
{a=9, r=5, s=1, t=6, e=3, u=7, w=4, h=8, n=2, o=0}
{a=9, r=0, s=1, t=6, e=7, u=3, w=2, h=8, n=5, o=4}
{a=3, r=1, s=2, t=5, e=9, u=7, w=6, h=0, n=4, o=8}
{a=4, r=1, s=2, t=5, e=8, u=7, w=6, h=0, n=3, o=9}
{a=7, r=8, s=2, t=5, e=9, u=3, w=4, h=0, n=6, o=1}
{a=8, r=9, s=2, t=5, e=4, u=7, w=6, h=0, n=1, o=3}
{a=8, r=6, s=2, t=5, e=7, u=4, w=1, h=0, n=3, o=9}
{a=9, r=8, s=2, t=5, e=4, u=6, w=7, h=0, n=1, o=3}
{a=9, r=6, s=2, t=5, e=7, u=3, w=8, h=0, n=4, o=1}
{a=9, r=6, s=4, t=1, e=7, u=3, w=0, h=8, n=2, o=5}
{a=2, r=3, s=5, t=8, e=7, u=9, w=1, h=4, n=0, o=6}
{a=2, r=6, s=5, t=8, e=7, u=9, w=3, h=4, n=1, o=0}
{a=2, r=6, s=5, t=8, e=9, u=7, w=1, h=4, n=3, o=0}
{a=3, r=7, s=5, t=8, e=6, u=9, w=1, h=4, n=0, o=2}
{a=6, r=0, s=5, t=8, e=9, u=3, w=1, h=4, n=2, o=7}
{a=7, r=1, s=5, t=8, e=9, u=2, w=6, h=4, n=3, o=0}
{a=9, r=1, s=5, t=8, e=6, u=3, w=7, h=4, n=0, o=2}

NoOne
September 20, 2017 /* The recursive formulation is too easy
So, let's improve on that.
Observe the problem can be recursively formulated
as cardinal product of two lists, left one, is a conjugate
(items themselves may be list), while right ine is a primitive one.
Thus, simple for loop suffices, which then yields the left list
for the next iteration.
*/
def _cross_( conjugate, primitive ){
result = list()
for ( l : conjugate ){
for ( r : primitive ){
// concatenate these lists
row = list(l)
row += r
result.add(row)
}
}
result // return them
}
def cross( arr_of_arr ){
if ( size(arr_of_arr ) <= 0 ) return [] // fixed
cur_index = 0
// generate left list, conjugate
left_list = list ( arr_of_arr[cur_index] ) as { list( $.o ) }
cur_index += 1
while ( cur_index < size(arr_of_arr) ){
left_list = _cross_(left_list,arr_of_arr[cur_index] )
cur_index += 1
}
left_list // return... and we are good
}
// sample test case
a = [ [ 'a' , 'b' ] , [ 'c' , 'd' ] ]
r = cross( a )
println(r)

NoOne
September 16, 2017 // Globals are terribly bad...
// use closure instead
$state = 0
$even = true
def exit(){ $state >= 12 }
def func_0(){
while( !exit() ){
#atomic{
if ( 2 /? $state ){
printf(0)
$state += 1
$even = !$even
}
}
}
}
def func_even(){
n = 0
while( !exit() ){
#atomic{
if ( $state % 2 == 1 && $even ){
n += 2
printf(n)
$state += 1
}
}
}
}
def func_odd(){
n = 1
while( !exit() ){
#atomic{
if ( $state % 2 == 1 && !$even ){
n += 2
printf(n)
$state += 1
}
}
}
}
threads = [ thread() as { func_0() } , thread() as { func_even() } , thread() as { func_odd() } ]
while ( exists( threads ) where { $.o.alive } );
println()

NoOne
September 04, 2017 A graph.
yes. You heard that right. FileSystem is not a tree. Never was. The moment you invented the notion of [ askubuntu.com/questions/108771/whatisthedifferencebetweenahardlinkandasymboliclink ]  tree is dead. Long live the graph.
And we are done.
Well ordering principle suggests that the set of binary trees can actually be ordered, axiomatically. It is well known that the number of possible binary trees given node n, is
n'th Catalan Number : [ en.wikipedia.org/wiki/Catalan_number ].
C[n] is the number of rooted binary trees with n internal nodes (n + 1 leaves or external nodes).
Thus, the problem is about enumerating these configurations given *n* and then picking
one configuration at random.
Now, that means, *with equal probability* implies, a Random binary tree having n nodes,
therein generated must have a probability of 1/C[n] where C[n] is the n'th Catalan number.
In this formulation it is obvious that the problem is beyond trivial.
Unless, they are asking a random walk problem with equal probability
of having a { left node, right node, or both nodes. }, then it is very trivial.
The first problem is here :
[ tristaninterview.blogspot.in/2012/02/enumerateallpossiblebinarytrees.html ]
With the binary counting method, the problem is solved.
Again, the key issue is about the *equal probability*. They are certainly non trivial for non linear
expressions like this.
A pretty neat way is the recursive formulation as such:
def Node{
def $$(value, l=null, r=null){
$.value = value
$.children = [l,r]
}
def s_rep(){ // for string format
r_str = $.children[1] == null ? '' : $.children[1].s_rep()
l_str = $.children[0] == null ? '' : $.children[0].s_rep()
str( '(%s %s %s)', l_str, $.value, r_str )
}
}
// call it off
ll = new ( Node , 10 )
lr = new ( Node , 30 )
l = new ( Node , 100 ,ll, lr )
r = new ( Node , 130 )
root = new ( Node , 42 , l , r ) // root node
println( root.s_rep() )
Which produces :
((( 10 ) 100 ( 30 )) 42 ( 130 ))
From this, it is very easy to parse back into the tree.
The recursive formula of a any tree in this form is :
( ( left_sub_tree_rep ) my_value ( right_sub_tree_rep ) )

NoOne
August 23, 2017 There are at least two ways to solve it with O(n).
1. Sort using radix sort, and then linear search. Solved using Theta(k n ) where k = Log(max(arr),10) or rather any base.
2. The one I am posting down  much complex:
def max_contiguous_sub_seq( my_list ){
left = dict()
right = dict()
for ( x : my_list ){
prev = x  1
next = x + 1
merged = false
if ( prev @ right ){
merged = true
val = right[prev]
val += x
right = prev
right[x] = val
}
if ( next @ left ){
merged = true
val = left[next]
left = next
val.add(0,x)
left[x] = val
}
if ( !merged ){
// here, create one element guy
my_list = list( x )
left[x] = my_list
right[x] = my_list
}
}
// find the max length guy from left/right
#(min,max) = minmax( left ) where { size($.l.value ) < size($.r.value ) }
max.value // here we go
}
l = [ 1, 11, 102, 12, 32, 13, 80, 10 ]
sol = max_contiguous_sub_seq(l)
println(sol)

NoOne
August 22, 2017 The question has problem, the trivial solution is to have a substring with size 1. If we do ignore the substring of size 1, then :
def longest_repeated_substring( string ){
n = size( string )
if ( n <=1 ) return ''
counter = dict()
join ( [0:n], [0:n] ) where {
continue( $.1  $.0 <= 1 ) // when ( j  i > 1 ) for pairs
sub_string = string[$.0:$.1]
if ( sub_string @ counter ){
counter[sub_string] += 1
} else {
counter[sub_string] = 1
}
false // we do not want to add, at all
}
// find min, max
#(min,max) = minmax ( counter ) where { $.l.value < $.r.value }
max.key
}
println( longest_repeated_substring('banana') )

NoOne
August 22, 2017 def solve( my_list ){
// 0 is left partition, 1 is right partition
// a bit pattern of size(my_list) = n signifies the selection
// 0 1 0 1 0 > pick the 0 for left, 1 for right
// 1 2 3 4 5 > left : [1,3,5], right : [2,4]
// this is the bitmap trick
n = size(my_list)
N = 2 ** n
// infinity with null, lame!
min_diff = { 'value' : num('inf') , 'partitions' : null }
for ( my_num : [1:N] ){
string_rep = str(my_num,2) // in binary
// left pad 0
string_rep = '0' ** ( n  size(string_rep) ) + string_rep
// partition them using when 0 comes left, 1 comes right
#(left_items, right_items ) = partition ( [0:n] ) where { string_rep[$.o] == _'0' }
left_sum = sum ( left_items )
right_sum = sum ( right_items )
// this is pretty straight forward
diff = #left_sum  right_sum 
if ( diff < min_diff.value ){
min_diff.value = diff
min_diff.partitions = [ left_items, right_items]
}
}
min_diff // return
}
l = [1,2,3,4,5]
md = solve( l )
println( md )

NoOne
August 21, 2017 def find_node_with_value(root,node_value){
stack = list()
stack.push(root)
while ( !empty(stack) ){
node = stack.pop()
if ( node_value == node.value ){
return node
}
if ( node.left != null ){
stack.push(node.left)
}
if ( node.right != null ){
stack.push(node.right)
}
}
return null
}
// i have an implicit root
def find(x,y){
x_node = find_node_with_value(root ,x)
if ( x_node == null ) return false
y_node = find_node_with_value(x_node ,y)
y_node != null // return this
}

NoOne
August 16, 2017 In pure declarative form, using recursion  which can easily be removed:
def _recurse_(target,path){
if ( target == path[1] ){
println( path )
return
}
diff = target  path[1]
power_options = list([0:diff]) as { break( 2 ** $.o > diff) ; $.o }
for ( pow_2 : power_options ){
new_cur = path[1] + ( 2 ** pow_2 )
_recurse_ ( target, path + new_cur )
}
}
def print_paths(n){
_recurse_(n,[0])
}
print_paths(4)

NoOne
August 10, 2017 A much simpler approach using Java BigIntegers:
/* A clean solution using Java BigInteger.
We need to have N bulbs, so N binary digits we need
To have so, we must have a N+1 size integer.
*/
def Bulbs{
def $$(N){
s = str(2 ** ( N + 1 ))
$.underlying = new ( 'java.math.BigInteger' , s )
}
def is_on(i){
// tutorialspoint.com/java/math/biginteger_testbit.htm
$.underlying.testBit(i)
}
def toggle(start,end){
$.underlying = fold([start:end+1],$.underlying){
// tutorialspoint.com/java/math/biginteger_flipbit.htm
$.p.flipBit($.o)
}
}
}

NoOne
August 10, 2017 For the languages where the choice() function is available, @Fernando's solution is right. To use his solution one needs to :
if __name__ == '__main__':
func = gen_random(4,[2,1])
counter = dict()
for i in range(0,1000):
x = func.next()
if x not in counter:
counter[x] = 0
counter[x] += 1
print (counter)
However, for the languages which does not have a choice function, there is a way too  the precise thing @ahetuki is doing.
 NoOne July 31, 2017@ChrisK, ok now I get it. They want to generalise Rank :
[ people.csail.mit.edu/sanchez/papers/2016.model.hpca.pdf ] something like this.
Given a generic function, that can shuffle the order *completely*  I rather doubt there is any point  unless we specify what sort of property the ranking function has.
@funk :
===
Assuming the tasks need to be run in the order given, as per the example
==
No, not really. This is variant of task scheduling problem, and you can use any permutation of the tasks, such that when applied  the slots are minimal.
That would be the precise formulation.
@ChrisK:
approach 2:
===
approach 1 is fine, it works, but the HT will eventually grow large, consuming a lot of memory, whereas we actually only need the messages from unique user_ids from the last second, which I assume, is considerably less than the set of users over a longer period (mustn't be, but for most system it's a good assumption).
===
You were there, but then the question is why don't you expire the hashtable entries? :)
That is, of course another cleaner, meaner alternative approach.
Now the algorithm looks like:
def fire_func( iterator ){
map = dict()
while ( iterator.hasNext ){
item = iterator.next()
if ( item.user_id @ map ){
// i found it in map, so check old time
diff = item.timestamp  map[user_id].timestamp
if ( diff <= critical ){
// that is the requirement anyways
too_fast( map[user_id], item )
}
}
// new entry, store new time  always
map[user_id] = item
// now, expire items in the map ?
cur_time = int( time() )
// a base delay beyond which message will not come
critical_diff = diff * 10
map = dict ( map ) as {
continue( cur_time  $.value.timestamp > critical_diff )
$.o // else, preserve
}
}
}

NoOne
July 26, 2017 /*
There are three variations of the problem,
when I used to ask this.
1. A string is actually a sequence of chars.
Those makes whitespaces special.
1.1 'I am cool' > 'cool am I'
1.2 'cool am I'
2. 2.1 'cool am I'
People generally tend to solve the 2.1.
While, 1.1, and 1.2 are where the fun really is.
Now, I present 1 liners, fully declarative form.
*/
// 2.1. The easiest one
str( (tokens( string , '\\S+') ** 1 ), ' ')
/*
Blue is Sky The // String
*/
// 1.1 :: 'I am cool'
spaces = tokens( string , '\\s+')
words = tokens( string , '\\S+')
l = fold ( [size(spaces)1:1 ] , list(words[1]) ) as { $.p += (spaces[$.o] + words[$.o]) }
str(l,'')
// 1.2 trivial. left as exercise .

NoOne
July 24, 2017 See my comments above.
def _recurse_( root, node, path ){
if ( empty(root.children) ){
return ( root == node ? path : '')
}
for ( inx : [0: size(root.children) ] ){
path = _recurse_(root.children[inx], node, path + '/' + inx )
if ( !empty(path) ){
return path
}
}
return ''
}
def find_path(root, node){
_recurse_(root,node,'')
}
def apply_path( root, path ){
if ( empty(path) ) return null
indexes = path.split('/')
cur = root
for ( inx : indexes ){
cur = cur[inx] ?? null
if ( empty(cur) ) return null
}
cur // reuturn
}
def facebook_problem( root_orig, node_orig, root_deep_copy){
path = find_path(root_orig,node_orig)
apply_path( root_deep_copy, path )
}

NoOne
July 23, 2017 Observe the notional xpath as defined as :
index1/index2/index3/.... implies from root, go to the node with index index1, that child's index2 child, then that child's index3 child so on and so forth.
It is obvious that we can have a function :
String find_path(TreeNode root, TreeNode node)
// returns the path to node in root, empty string otherwise.
Once we have that, the deep copy guy must have the xpath. Apply the same xpath to the deep copy tree, and you find the deep copy node.
TreeNode apply_path(TreeNode root, String xPath)
// returns the node to the path in root, null otherwise.
Some smart developer, may, want to combine these two functionalities for optimisations sake  I do not blame them, but they are inherently two distinct functionalities.
Now that the problem is split into 3 more problems, I am good to go. Next comment will have all the answers.
It is better to avoid writing a single line of code, when you can write it in 2 lines.
[ stackoverflow.com/questions/618378/selectuniqueordistinctvaluesfromalistinunixshellscript ]
./yourscript_to_isolate_ip.sh  sort  uniq u
and this, will run no matter how less memory you have.
Aws guys actually run it, so does azure folks. I am pretty sure Apple will do the same.
There is another very neat alternative than creating a large boolean bucket array, radix sort.
// radix_sort is Theta(n)
def radix_sort(meetings){
// all of these, by definition will have same no digits :: max 4
no_digits = size ( meetings[0].start, 10 )
for ( inx : [no_digits1:1] ){
bucket = mset ( meetings ) as { int ( (str($.start))[inx] ?? 0 ) }
meetings = fold( [0:10] ,list() ) as {
continue( $.o !@ bucket )
$.p += bucket[$.o] }
}
meetings // return
}
def is_overlap(meetings){
meetings = radix_sort(meetings)
exists ( [1:size(meetings)] ) where {
meetings[$.o  1].end >= meetings[$.o].start
}
}

NoOne
July 21, 2017 @ChrisK is right, however, we can solve the problem by this too:
Start = [1,3,2,5]
End = [4,5,7, 10]
// there can be multiple in same time
starts = mset( Start )
ends = mset( End )
// sorted set of timings
timings = sset( Start )
timings += End
max = 0 ; cur = 0
for ( inx : timings ){
cur += (inx @ starts ? starts[inx] : 0)
cur = (inx @ ends ? ends[inx] : 0)
max = cur > max ? cur : max
}
println(max)

NoOne
July 19, 2017 Cheating using ZoomBA, avoiding all of recursion... and
movies = { "Shining" : [14, 15, 16],
"kill bill" : [14, 15],
"Pulp fiction": [14, 15] }
args = list ( movies.entries ) as { name = $.key ; list( $.value ) as { [ name, $.o ] } }
movie_size = size(movies)
all_sched = join( @ARGS = args ) where {
items = list ( $.o )
sorta ( items ) where { $.left[1] < $.right[1] }
!exists ( [1:movie_size] ) where { items[$.o][1]  items[$.o1][1] < 1 }
}
println(str(all_sched,'\n'))
And just to showcase that it did find the results, here are the results :
➜ wiki git:(master) ✗ zmb tmp.zm
@[ @[ Shining,16 ],@[ Pulp fiction,14 ],@[ kill bill,15 ] ]
@[ @[ Shining,16 ],@[ Pulp fiction,15 ],@[ kill bill,14 ] ]
➜ wiki git:(master) ✗

NoOne
July 16, 2017 Why make it more complex, this is clean, neat... and works.
def div_wo(a,b){
panic( b == 0 , 'Terrible parameter!')
printf('%d/%d%n', a,b)
sign_change = false
if ( a < 0 ){
sign_change = true
a = a
}
if ( b < 0 ){
sign_change ^= true
b = b
}
res = 0
while ( a >= b ){
res += 1
a = b
}
sign_change ? res : res
}
println( div_wo(0,1) )
println( div_wo(1,1) )
println( div_wo(1,2) )
println( div_wo(2,1) )
println( div_wo(2,1) )
println( div_wo(2,1) )
println( div_wo(2,1) )
println( div_wo(3,2) )

NoOne
July 16, 2017 This is a Directed Acyclic Graph, and the list given here is an adjacency list. Thus, standard BFS or DFS techniques work. There is no guarantee that it would be a tree ( there can be multiple managers to an employee ( what surprise) ). Matters not.
org_map = { 1: [2, 3, 4],
3: [5, 6, 7],
5: [8, 9, 10] }
def find_all_minions( gru ){
// gru before the minions ?
if ( !(gru @ org_map) ){ return [] }
minions = list()
// cool, let gru get's his groove back
despicable_me = list ( org_map[gru] )
while ( !empty(despicable_me) ){
// yes, bob was always faithful
bob = despicable_me.dequeue()
if ( bob @ org_map ){
// enqueue all the lesser minions
despicable_me += org_map[bob]
}
minions += bob // add bob the minions
}
minions // return value
}
printf( '%s > %s %n', 1, find_all_minions( 1 ) )
printf( '%s > %s %n', 2, find_all_minions( 2 ) )
printf( '%s > %s %n', 3, find_all_minions( 3 ) )

NoOne
July 15, 2017 There are cleaner solutions. Suitably change it into Java.
def reverse_vowels_declarative(word){
vowels = set( 'aeiou'.value ) // get into a set
vowels_in_word = select( word.value ) where { $.o @ vowels }
// put back
fold ( word.value , 1 ) as {
continue( !($.o @ vowels) )
word.value[$.i] = vowels_in_word[$.p]
$.p = 1
}
word
}
def reverse_vowels_imperative(word){
vowels = set( 'aeiou'.value ) // get into a set
lp = 0 ; rp = size(word)  1
while ( true ){
while ( lp < rp && !(word[lp] @ vowels) ){ lp += 1 }
while ( lp < rp && !(word[rp] @ vowels) ){ rp = 1 }
break(lp >= rp )
t = word[rp]
word.value[rp] = word[lp]
word.value[lp] = t
lp +=1 ; rp = 1
}
word // done
}
println( reverse_vowels_imperative('vowels') )

NoOne
July 11, 2017 The solution examples are obviously wrong.
Formally, the question can be any of these two :
1. Is a set x, subset of *any* of the sets contains in a list?
2. Is a set x, subset of *all* of the sets contains in a list?
If the question was [1], then "But checking for {1,2} in {1,5,6}, {2,3,1} should return false as {1,5,6} does not contain all elements of {1,2} 2 is missing" is wrong. Obviously.
If the question was [2], then "For example checking for set1 = {1,2} in {1,2,3}, {5,6} should return true" would be wrong.
The other fancy things I can think of are:
[3] Is a set x, subset of union of the sets contains in a list?
That would not work also.
See solutions...
To @ChrisK.
This should clear you out on what precisely ZoomBA is all about :
words = [ [3,2] , [4,3,2] , [4,1,1] , [1, 2] , [1, 1] ]
letters = words.flatten()
ms = mset(letters)
l = list( ms ) > { [$.key,$.value] }
sorta(l) :: { $.left[1] < $.right[1] }
alpha = list ( l ) >{ $.0 }
println(alpha)

NoOne
July 08, 2017 mix = { 'Cust1' : [ 'n3', 'n7', 'n5', 'n2' , 'n9' ],
'Cust2' : [ 'n5' ],
'Cust3' : [ 'n2' , 'n3' ],
'Cust4' : [ 'n4' ],
'Cust5' : [ 'n3' , 'n4' , 'n3' , 'n5' , 'n7' , 'n4' ] }
// what drinks serves who?
serving = fold( mix.keys , dict() ) as {
values = mix[$.o]
for ( v : values ){
if ( v @ $.p ){
$.p[v] += $.o
} else {
$.p[v] = set($.o)
}
}
$.p // return
}
// next, sort by no of customer a drink serves, and union off,
// go with greedy mode. if adding a drink does not increase customer base
// no need to add it.. thus...
l = list ( serving ) as { [ $.key , $.value ] }
sortd(l) where { size($.left[1]) < size($.right[1]) }
drinks = set( l[0][0] )
catered = set( l[0][1] )
n = size(catered)
i = 1
while ( n != size( mix ) ){
catered = l[i][1]
if ( size(catered) > n ){
n = size(catered)
drinks += l[i][0]
}
i += 1
}
println(drinks)
// caution, the problem is bin packing. Greedy is NOT a gurantee.
// en.wikipedia.org/wiki/Bin_packing_problem#Exact_algorithm
// A gurantee is, of course NP Hard.

NoOne
July 02, 2017 I was thinking about it for a long time. This is a classic case of discretisation making itself away into scale variance. What does that mean? Here is how it works out.
Here, I present two ways to solve the same problem [1].
Continuous Algorithm.
1. Make uniform distribution rain falling as in a point between [0,1].
2. Widen the point, to create an interval to [p  0.005, p + 0.005 ] to make the drop fall.
3. This way, we are creating intervals, and they are kept sorted  and then they are merged.
4. Continue till the intervals merged into a some intervals such that the total length is very close
to 1.000.
5. All while count the no of rain drops ( intervals ) fell.
> Observation, there is a clear mode near about 500 to 800.
Discrete Algorithm.
1. Create pixelated buckets with scale number of pixels per rain drop.
2. That makes the length L ( 1 m ) into 100 * scale.
3. Let the rain drop uniformly between [ 0, 99*scale + 1] , and then
4. Once the rain drop falls, in position pos, mark the buckets [pos, pos + scale) filled.
5. Check if all buckets are marked. That, gives you  whole road is wet.
Now, this is where fractal nature of world comes in. This simulation discretised the world, and thus, does not have a fixed mean, with scale, the mean increases.
Here are the codes.
This is for the discrete simulation. It is amazing how simply you can think about it after pixelation.
// This is discrete simulate
def discrete_simulate(){
scale = 10
count = 0
s = set()
max = 100 * scale
span = max  scale + 1
while ( size(s) != max ){
pos = random(span)
for ( [pos:pos + scale ] ){ s+= $ }
count += 1
}
count // return this
}
Here is *real* continuous one. Interestingly, these two distributions of number of rain drops will not match.
def merge2(slice1, slice2 ){
if ( slice1.x2 < slice2.x1  slice2.x2 < slice1.x1 ) {
return null // not overlap
}
if ( slice1.x1 <= slice2.x1 ){
#(min,max) = minmax( slice1.x2 , slice2.x2 )
return { 'x1' : slice1.x1 , 'x2' : max }
} else {
#(min,max) = minmax( slice1.x2 , slice2.x2 )
return { 'x1' : slice2.x1 , 'x2' : max }
}
}
def merge_into( new_slice, sorted_slices ){
if ( empty(sorted_slices) ){
sorted_slices += new_slice
return sorted_slices
}
// from left
i = index ( sorted_slices ) where { new_slice.x1 <= $.o.x2 }
if ( i < 0 ){
sorted_slices += new_slice
return sorted_slices
}
slice = merge2 ( new_slice, sorted_slices[i] )
if ( slice == null ){
sorted_slices.add(i, new_slice )
return sorted_slices
}
sorted_slices[i] = slice
if ( i + 1 < size(sorted_slices) ){
slice = merge2 ( sorted_slices[i], sorted_slices[i+1])
if ( slice != null ){
sorted_slices[i] = slice
sorted_slices.remove(i+1)
}
}
sorted_slices
}
def simulate(){
sorted_slices = list()
tot = 0.0
count = 0
while ( 1.0  tot > 0.0001 ){
pos = random(0.0)
x1 = pos  0.005
x1 = x1 < 0.0 ? 0.0 : x1
x2 = pos + 0.005
x2 = x2 > 1.0 ? 1.0 : x2
slice = { 'x1' : x1, 'x2' : x2 }
sorted_slices = merge_into( slice, sorted_slices )
//println(slice)
//println(sorted_slices)
//thread().sleep(10)
tot = sum( sorted_slices ) as { $.o.x2  $.o.x1 }
count += 1
//printf('>>>>> Count : %d Total %f %n', count, tot)
}
//println( sorted_slices )
return count // well
}
This is a pretty non trivial problem, and I see why PHD folks were asked this. The nature of simulation is, here, getting fractalised.
 NoOne June 27, 2017Open Chat in New Window
 NoOne March 05, 2018