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
Non trivial code. Absolutely non trivial. Here is one part of it, when the dates are larger than 1970 Jan 01 :
MS_IN_NORMAL_YEAR = 365 * 24* 60 * 60 * 1000
MS_IN_LEAP_YEAR = 366 * 24 * 60 * 60 * 1000
DAYS_IN_MONTH = [ 0, 31, 28 , 31, 30, 31, 30, 31, 31, 30, 31 , 30, 31 ]
def is_leap_year( year ){
return ( ( 400 /? year )  ( !( 100 /? year ) && ( 4 /? year ) ) )
}
def get_ms_in_month( month, is_leap ){
if ( is_leap && month == 2 ) return 29 * 24 * 60 * 60 * 1000
return DAYS_IN_MONTH[month] * 24 * 60 * 60 * 1000
}
def date( millisec ){
year = 1970 // *nix inception year
is_leap = is_leap_year( year )
ms_in_year = ( is_leap ? MS_IN_LEAP_YEAR : MS_IN_NORMAL_YEAR )
while ( millisec > ms_in_year ){
millisec = ms_in_year
year +=1
is_leap = is_leap_year( year )
ms_in_year = ( is_leap ? MS_IN_LEAP_YEAR : MS_IN_NORMAL_YEAR )
}
println ( year )
// at this point, we have found the years, now add months
month = 1
ms_in_month = get_ms_in_month ( month, is_leap )
while ( millisec > ms_in_month ){
millisec = ms_in_month
month +=1
ms_in_month = get_ms_in_month ( month, is_leap )
}
days = (millisec / ( 24 * 60 * 60 * 1000 )) + 1
[ days, month, year ]
}
res = date ( 1476615214741 )
println( res )

NoOne
October 16, 2016 Dumbo Strategy. Not smart but does the job.
Suppose the graph has K pair of nodes, which are not connected.
We are not considering en.wikipedia.org/wiki/Multigraph.
In that case we need to add to these pairs all pairs having edge length more than 2.
Now, the problem becomes :
find_min ( start, end, [ original , modified_1, modified_2, ...modified_k ] )
That is, finding individual shortest path in the original graph, and then modifying the graph by joining the first pair and then continuing the same.
This surely solves the problem.
But let's take a look around this a bit more.
Suppose we do this :
find_min ( start, end, [ original_graph ] )
and find the path P.
Now, if we go through the path verices by vertices, edge by edge,
can we not calculate if replacing 3 of the verices by a 2 ( by inserting the virtual edge )
reduces the min value or not?
Thus, we may solve the problem by :
1. Finding min path
2. Check if directly connecting start to end solves it or not? If not, then proceed to [2]
3. For each 3 verices in 2 edges, we check if adding a virtual edge reduces the min or not.
4. Continue storing the previous min and go to [3].
Proof Of Correctness: NONE.
As of now, this can go wrong drastically.
1. Have a credit card cache, partitioned into good and fraud.
2. When a card belong to any of the above, then do due diligence.
3. When a card belongs to neither, call the website and get the latest fraud card list.
4. Update the card cache, move from good to fraud.
5. Now, if the card is still in neither, then add the card to the good card cache.
Issue : with [2]. But it can never be fixed, really.
s = [ "IBM cognitive computing" , 'IBM "cognitive" computing is a revolution' ,
"ibm cognitive computing" , "'IBM Cognitive Computing' is a revolution?" ]
// shows the power of full declarative framework
#(full,final) = fold ( s , [ '' , '' ] ) > {
// token splitting of the current statement, basing the rules
words = tokens( $.item.toLowerCase , '[az09]+')
key = str( words , ' ' ) // preserve single whitespace if need be
previous_key = $.previous.0 // the fold structure
previous_value = $.previous.1 // unwinding
continue ( !(previous_key @ key) 
( previous_key == key && #$.item > #previous_value ) )
// when the continue did not happen, return the current as the latest
[ key, $.item ]
}
println( final )
Explanation. We note that the statements can be mapped to a key.
A key that is to be used for comparison. Obviously, if key1 is contains in key2, we need to pick key2. That is inscribed in the code.
// ZoomBA
mapping = dict()
// the basic mapping is created using this
def traverse( node , cur_x, cur_y ){
if ( !(cur_x @ mapping) ){ mapping[cur_x] = list() }
// append :store both y co ordinate as well as value
mapping[cur_x].add ( [ cur_y , node.value ])
// change the x to left, so one minus, and level one down
if ( !empty( node.left) ) { traverse( node.left, cur_x  1, cur_y + 1 ) }
// change the x to right, so one plus, and level one down
if ( !empty( node.right) ) { traverse( node.right, cur_x + 1, cur_y + 1 ) }
}
traverse( root, 0, 0 ) // basis
// sort the keys based on x coordinate
keys = sorta ( list ( mapping.keySet ) )
fold ( keys ) >{
values = mapping[$.item] // get the pair values in that key
// sort the values based on the pairs left item, e.g. y coordinate
sorta( values ) :: { $.item[0][0] < $.item[1][0] }
// now, simply print all the values : the right value
printf ( '%s', str( values , ' ') >{ $.item[1] } )
}
// end with a newline
println()

NoOne
October 14, 2016 // ZoomBA
def left_right( a ){
len = #a
odd = !(2 /? len)
left_heap = fold( a , heap( len/2 + 1 ) ) > { $.partial += $.item }
#(l,r) = fold( a, [list(),list()] ) > {
if ( $.item < left_heap.max ){ $.partial.0 += $.item }
if ( $.item > left_heap.max ){ $.partial.1 += $.item }
if ( !odd && $.item == left_heap.max ) { $.partial.1 += $.item }
$.partial
}
println ( l + (odd ? left_heap.max : []) + r )
}
a = [ 6, 4, 5, 0, 2, 1, 11 , 1 ]
left_right(a)
a = [ 6, 4, 5, 0, 2, 1, 11 , 1, 9 ]
left_right(a)

NoOne
October 14, 2016 //ZoomBA
s = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))"
def simplified_solution(s){
// observe that every ')' previous to that is the word to add, so :
cur = 0
len = #s
words = list()
while ( cur < len ){
r = index ( [cur: len] ) :: { s[$.item] == ')' } + cur
break ( r >= len )
l = rindex ( [ cur:r ] ) :: { s[$.item] == ' ' } + cur
break ( l >= len )
w = s[l+1:r1]
if ( !empty( w.trim() ) ) { words += w }
cur = r + 1
}
println ( str ( words , ' ' ) )
}
simplified_solution( s )
A much faster and alternative  to do it directly from string rep.
 NoOne October 13, 2016// ZoomBA
tree = { "NP" : [ { "DT" : "a" } , { "NN" : "boy" } ] }
def traverse( node , s ){
names = list( node.keySet )
name = names.0 // yes, we did it ourselves
value = node[name]
if ( value isa [ ] ){
for ( child : value ){
traverse ( child , s )
}
}else{
s += value
}
}
s = list()
traverse ( tree, s )
println( str(s, ' ') )
Here, we are forced to use minimal dictionary ( json ) format to store the parse tree.
Observe that the ordering does not matter at all for the nodes, because of the format chosen. Order is implicit in the list.
// ZoomBA
// whole string
def reverse( string , si, ei ){
fold( [ si : (si + ei + 1)/2 ] ) >{
t = string.value[ $.item ]
string.value[ $.item ] = string.value[ ei  $.index ]
string.value[ ei  $.index ] = t
}
}
// If you want to reverse the words,
def reverse_words( string ){
reverse( string , 0, #string  1 )
si = 0 ; ei = 0
len = #string
while ( true ){
while ( si < len && string[si] ==' ' ) { si += 1 }
break ( si >= len )
ei = si
while ( ei < len && string[ei] !=' ' ) { ei += 1 }
break ( ei >= len ){ reverse( string, si, len1 )}
reverse( string, si, ei  1 )
si = ei
}
}

NoOne
October 13, 2016 // ZoomBA
node = { 'id' : 0 , 'children' : list() }
visited_nodes = set()
def post_order(node){
// awesomeness of ZoomBA is linear error handling mechanism
// if condition is true, panic is raised with the message
panic ( node.id @ visited_nodes , 'I have visited this node before!' )
visited_nodes += node.id // appends it
for ( child : node.children ){
post_order( child )
}
println ( node ) // visits it
}

NoOne
October 13, 2016 1. Make a graph, from your string[] bank.
All strings become nodes.
A node is connected to another if they have a single edit distance, that is ,
a single mutation can transform one string to another. Thus, making the graph is hard affair.
Linear solution on the strings lengths exists, see below ZoomBA code.
2. Once that graph building is done, search for the node.
Keep a hashmap/trie whatever you want.
Get the start and end node. Now, apply any standard path finding mechanism to
reach from start to the end node, in the shortest path. The weight of the path is the mutation distance.
// ZoomBA
def is_edit_distance_1( string1, string2 ){
n1 = #string1 ; n2 = #string2
if ( #n1  n2 > 1 ) return false
if ( n1 == n2 ) return test_same_length( string1, string2 )
if ( n1 > n2 ) return test_one_more ( string1 , string2 )
return test_one_more ( string2 , string2 )
}
def test_same_length( string1, string2 ){
n = #string2
( lfold ( [0:n] , 0 ) >{
$.partial += (string1[$.o] == string2[$.o] ? 0 : 1 )
break ( $.partial > 1 )
$.partial
} ) == 1
}
def test_one_more( large, small ){
n = #small
first_diff = index( [0:n] ) :: {
small[ $.o ] != large[ $.o ]
}
if ( first_diff < 0 ) return true
// match the suffixes
! exists ( [ first_diff : n ] ) :: {
large[$.o+1] != small[$.o]
}
}

NoOne
October 12, 2016 // ZoomBA
def classify( string ){
// please do some menial work and list all consonants, to ensure that
// we do not false miss stuff not in [az]
// =~ is the matches operator
if ( string =~ '.*[^aeiou]{5,}.*.*[aeiou]{3,}.*' ) return 'bad'
if ( string =~ '.*[\?aeiou]{3,}.*.*(\?[^aeiou]){5,}.*' ) return 'mixed'
return 'good'
}
This is very lazy, using regex, and bad matching on them. But generally gives you the idea.
The fall back *order* is essential.
As you can see, the *left* half has all the small elements while the *right* half has all the large elements. Thus, the problem is partition the array into two halves of equal sizes, left contains all the small elements ( w/o violating the order ) and right has the large ones.
Thus, for odd sized array the middle element would be the median.
For lack of editing capability, posting as comment.
// ZoomBA
def careercup(path, x, y, M, N){
if ( x > M  y > N ) return 0
if ( x == M && y == N ) {
println( path )
return 1
}
result = ( careercup( path + str('(%s,%s)', x+1,y) , x + 1, y , M, N) +
careercup( path + str('(%s,%s)', x,y+1) , x, y + 1 , M, N) +
careercup( path + str('(%s,%s)', x+1,y+1) , x + 1, y + 1, M, N) )
}
println ( careercup('(0,0)', 0, 0, 2, 2) )

NoOne
October 11, 2016 You probably just want to replace the factorial function with something like this :
// ZoomBA
FACTORIALS = list(1,1,2,6,24)
def factorial ( n ){
if ( n <= size(FACTORIALS) ) return FACTORIALS[n]
for ( [size(FACTORIALS):n+1] ){
FACTORIALS += FACTORIALS[1] * $
}
FACTORIALS[n]
}
println( factorial(10) )

NoOne
October 11, 2016 // ZoomBA
def ways_to_dist( target_value ){
count = 0
q = list() // create a queue
q.enqueue ( [0,0,list(0)] ) // add to it
// now the loop
while ( !empty(q) ){
#( prev_inc , cur_sum , path ) = q.dequeue()
continue ( cur_sum > target_value ) // obvious, nothing else can do
continue ( cur_sum == target_value ) {
println( path ) // for debug diagnostic
count +=1 // increment possible scenarios
}
for ( inc : [1,5,10,25 ] ){
if ( inc >= prev_inc ){ // ensure sorted path
q.enqueue( [ inc , cur_sum + inc , path + inc ] )
}
}
}
return count
}
println ( ways_to_dist( 42 ))

NoOne
October 10, 2016 // ZoomBA
def ways_to_dist( target_value ){
count = 0
q = list() // create a queue
q.enqueue ( [0,0,list(0)] ) // add to it
// now the loop
while ( !empty(q) ){
#( prev_inc , cur_sum , path ) = q.dequeue()
continue ( cur_sum > target_value ) // obvious, nothing else can do
continue ( cur_sum == target_value ) {
println( path ) // for debug diagnostic
count +=1 // increment possible scenarios
}
for ( inc : [1,5,10,25 ] ){
if ( inc >= prev_inc ){ // ensure sorted path
q.enqueue( [ inc , cur_sum + inc , path + inc ] )
}
}
}
return count
}
println ( ways_to_dist( 42 ))
This is now a non recursive solution.
 NoOne October 10, 2016// ZoomBA
def ways_to_dist( path, cur_sum , target_value ){
if ( cur_sum > target_value ) return 0
if ( cur_sum == target_value ) {
println( path )
return 1
}
cnt = 0
for ( inc : [1,5,10,25 ] ){
if ( inc >= path[1] ){
cnt += ways_to_dist ( path + inc, cur_sum + inc, target_value)
}
}
return cnt
}
println ( ways_to_dist( list(0), 0, 42 ) )
We tried a bit sanity here. BUT, we are not sure, we are going to optimize it further.
 NoOne October 10, 2016// ZoomBA
def print_pattern( n ){
if ( n < 2 ) { println ( n ) ; return }
// create n * n matrix
m = list( [0:n] ) > { list() }
// 0 , n1, 1, n  2 ...
row_indices = lfold ( [ 1:n1], list(0,n1) ) >{
$.partial += ( $.partial[2] + ( (1) ** $.index) )
}
count = 1
for ( row : row_indices ){
for ( [0:n ] ){
m[row] += count
count +=1
}
}
lfold(m) > { println ( str( $.item, ' * ' ) ) }
}
// use it
print_pattern ( 3 )

NoOne
October 10, 2016 // ZoomBA
s = 'abbbbcdddefffg'
seed = { 'cur' : '', 'count' : 0, 'max' : '', 'max_count' : 0 }
seed = lfold( s.value, seed ) > {
if ( $.o != $.p.cur ){
if ( $.p.count > $.p.max_count ){
$.p.max = $.p.cur
$.p.max_count = $.p.count
}
$.p.cur = $.o
$.p.count = 1
}else{
$.p.count +=1
}
$.p
}
printf('%s > %d\n', seed.max , seed.max_count )

NoOne
October 09, 2016 Guys, you did not read.
=======
write a program to Generating Random Integer numbers without repetition
======
You need a GUID generator, not any random no generator. Any computerised random generator are bound to repeat, not because they are not random, but because they have a finite integer range.
The idea is :
1. Factorize the no *n* into prime factors.
2. Now a factorisation is a list of ( prime, multiplicity ) pair. Check that if all the multiplicity values has a GCD >1.
See the code from here : [question?id=5742470735331328]
// ZoomBA
def gcd( a,b ){ // copied from wikipedia
while ( b != 0 ){
t = b ; b = a % b ; a = t
}
return a
}
def is_expressible( n ){
multiplicities = select ( lfold ( [2:n+1] , dict() ) > {
continue ( exists ( $.p.keySet ) :: { $.o /? $.$.o } )
$.p[$.o] = 0
for ( x = n ; $.o /? x ; x/= $.o ){ $.p[$.o] += 1 }
$.p
} ) :: { $.o.value > 0 } > { $.o.value }
// calculate gcd of all the multiplicities
final_gcd = reduce ( multiplicities ) > { gcd( $.p , $.o ) }
final_gcd > 1 // for a non trivial solution
}

NoOne
October 09, 2016 // ZoomBA
def count_more_char( string ){
m = mset ( string.value )
// find all chars with odd frequency
odds = select ( m ) :: { $.o.value % 2 != 0 }
len = size(odds)
// every char freq is even means
//can be shuffled into a palindrome
if ( 0 == len ) return 0
// because only one odd freq can be allowed
//for palindrome, rest needs to be made into even
len  1
}
Based on expansion of WilOzil's idea.
 NoOne October 09, 2016// ZoomBA
$count = 0
def count_stais( cur,path, max ){
if ( cur > max ) return
if ( cur == max ){
println( path ) ; $count += 1
return
}
count_stais( cur + 1 , path + '>1' , max )
count_stais( cur + 2 , path + '>2' , max )
}
count_stais( 0 , '' , 4 )
println ( $count )
You can look at the recursive code, and decide the same!
 NoOne October 09, 2016bogdan.zima is of course correct. A better way to prove is this identity.
suppose the no of ways you can take step n is defined by a function step(n).
Now, clearly, as only 1 or 2 step at a time are allowed, you could have reached step(n)
by :
one step + take rest of (n1) OR two steps + take rest of (n2) steps.
Tow independent count of choices, and thus must get added up.
Hence:
step(n) = step(n1) + step(n2) // this gives Fibonacci sequence.
You can generalize it.
// ZoomBA
def prime_factors( n ){
select ( lfold ( [2:n+1] , dict() ) > {
continue ( exists ( $.p.keySet ) :: { $.o /? $.$.o } )
$.p[$.o] = 0
for ( x = n ; $.o /? x ; x/= $.o ){ $.p[$.o] += 1 }
$.p
} ) :: { $.o.value > 0 }
}
println( prime_factors ( 36 ) )
Making it inhuman, and thus lovers of succinct syntax should like it.
 NoOne October 09, 2016// ZoomBA
def prime_factors( n ){
#( primes, factors ) = lfold ( [2:n+1] , [ list() , dict() ] ) > {
cur = $.o ; partial_primes = $.p.0 ; partial_factors = $.p.1
is_prime_cur = !exists ( partial_primes ) :: { $.o /? cur }
continue ( !is_prime_cur )
partial_primes += cur
multiplicty = 0
for ( x = n ; cur /? x ; x/= cur ){ multiplicty += 1 }
if ( multiplicty > 0 ){ partial_factors[cur] = multiplicty }
$.p
}
factors
}
println( prime_factors ( 36 ) )
We have made it a bit human readable. Feedback of inhuman came.
Next post, we would optimize it for math lovers.
Guys, and gals, you have been tricked. O(1) is a misnomer, it basically suggests that there exists a fixed constant C, and the total no of operations would be less than that constant, at most. Thus, given the integer bit size known ( it is known for most languages ) and is constant, a fixed sized loop on the integer bit size (K) is indeed O(K) and is O(1).
 NoOne October 09, 2016// ZoomBA
nums = [ 2,3,1,0, 4,3,2 ]
def do_yahoo( nums ){
#(num_zeros, product) = lfold ( nums ,[0, 1] ) > {
if ( $.o == 0 ){ $.p.0 += 1 } else { $.p.1 *= $.o }
$.p
}
product = num_zeros > 1 ? 0 : product
for ( nums ) {
println ( $ == 0 ? product : (product/$) )
}
}
do_yahoo ( nums )
Note the handling of zeros. Obviously, if there is one zero, the problem is non trivial. For multiple zeros, the problem is trivial again.
 NoOne October 09, 2016// From ZoomBA with love
def parition_int( n ){
num_cuts = #str(n,2)
// to cut or not to cut
lfold ( [ 1 : 2 ** num_cuts ] , set() ) > {
bs = str( $.o, 2)
bs = '0' ** ( num_cuts  #bs ) + bs
p = list() ; start = 0
for ( i : [0:num_cuts] ){
if ( bs[i] == '1' ){
p += ( i  start + 1 )
start = i+1
}
}
p += ( num_cuts  start + 1)
sorta(p) ; $.p.add(p)
$.p
}
}
pi = parition_int(4)
println( pi )

NoOne
October 08, 2016 // From ZoomBA , with Love
def len_of_max_subset_palindrome( a ){
m = mset( a )
has_odd = [ false ]
sum( m ) > {
count = $.o.value
even = ( 2 /? count ) // 2 divides value ?
if( !even ){
has_odd.0 = true
count =1
}
count
} + (has_odd.0 ? 1:0 ) // adds 1 for the max odd guy
}

NoOne
October 08, 2016 // From ZoomBA , with Love
def not_sorted( a ){
select ( mset( a ) ) :: { $.o.value == 1 } > { $.o.key }
}
def sorted_imp( a ){
lfold ([0: #a ], [ a[0] , 1 , list() ] ) > {
if ( $.p.0 == a[$.o] ){
$.p.1 += 1
} else{
if ( $.p.1 == 1 ) { $.p.2 += $.p.0 }
$.p.0 = a[$.o]
$.p.1 = 1
}
$.p
}

NoOne
October 08, 2016 // ZoomBA
a = [ 1,2,3,4,4,4,5,5,7,8 ]
def bin_search( a, n, i, j ){
while ( i <= j ){
mid = ( i + j )/2
if( a[mid] < n ){
i = mid + 1
}else if( a[mid] > n ){
j = mid  1
}else{
return mid
}
}
return 1
}
def find_l_r( a, n ){
inx = bin_search( a , n , 0 , #a  1 )
if ( inx < 0 ) return [ 1, 1 ]
l = inx ; r = inx
while ( inx >= 0 ){
l = inx
inx = bin_search ( a , n, 0, inx 1 )
}
inx = r
while ( inx >= 0 ){
r = inx
inx = bin_search ( a, n , inx + 1 , #a  1 )
}
[ l, r ]
}
println( find_l_r ( a, 5 ) )

NoOne
October 08, 2016 Open Chat in New Window
 NoOne October 16, 2016