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
It is incredibly simple.
1. If the first char and last char are not "(" and ")"  then return the same string.
2. If they are, then,
2.1 get the substring "sub" from position 1 to len2 (0 based index ).
2.2. Verify if this string has matched parenthesis
2.3 If it has then return the "sub".
2.4 Else return the original string.
Here.
def bin_add( n1, n2 ){
/*
n1 digit, n2 digit, carry digit from previous >
carry, resulting digit
*/
RULES = { '000' : '00',
'001' : '01',
'010' : '01',
'011' : '10',
'100' : '01',
'101' : '10',
'110' : '10',
'111' : '11' }
min_size = size(n2)
max_size = size(n1)
if ( max_size < min_size ){
#(n2,n1) = [n1, n2] // swap
}
carry = '0'
result = ""
// when both are same size
i = min_size 1
j = max_size 1
while ( i >=0 ){
input = str("%s%s%s", n1[j],n2[i], carry)
i = 1
j = 1
output = RULES[input]
carry = output[0]
result = str( "%s%s", output[1], result )
}
while ( j >= 0) {
input = str("%s0%s", n1[j],carry)
j = 1
output = RULES[input]
carry = output[0]
result = str( "%s%s", output[1], result )
}
if ( carry == '1' ){
result = str("1%s", result)
}
result // return
}
println( bin_add('1101','1') )

NoOne
August 15, 2020 I am wondering, as an exSDEIII in amazon  where in Amazon people would build parser/interpreter  this is a case of that.
One good thing is  it is about pretty simple case of line by line parsing. So it is a line by line interpreter  that is good.
The bad is one line can be arbitrary complex expression.
Forget SDEIIs there are not many PE's who are capable of handling this problem.
/*
this function defines the weight between two vertices
we are looking at a directed graph,
where a>b and b>a will have different weights
*/
def min_click_path( ch_src, ch_dst ){
abs_delta = #ch_src  ch_dst  // this is done by using +/ channel button
dst_digits = size( ch_dst , 10 ) // this is the abs number press
#(m,M) = minmax( abs_delta, dst_digits )
m // minimal path from src to dst
}
/*
now just assume en.wikipedia.org/wiki/Dijkstra%27s_algorithm
from src to ch_dst
respond with the weight for ch_dst
*/

NoOne
May 18, 2020 I just wrote this .. and I believe it is beautiful. From elegance perspective. Hence, sharing.
def tail_function( file_name , n ) {
last_n_lines = list( [0:n] ) as { null }
cur_inx = 0
lc = 0
for ( line : file(file_name) ){
lc += 1
cur_inx %= n
last_n_lines[cur_inx] = line
cur_inx += 1
}
// print back the last_n_lines, imagining a circular buffer
start_inx = lc % n
for ( [start_inx:n] ){ (x = last_n_lines[$])  x == null  println(x) }
for ( [0:start_inx] ){ (x = last_n_lines[$])  x == null  println(x) }
}
tail_function( @ARGS[0] , @ARGS[1])

NoOne
May 05, 2020 /*
Of course there is a way to do it, with remembering
the last char and current char and proceed,
but that is not cool. That is too mundane.
So, I propose this insanely interesting strategy
*/
def reduce_string( some_string ) {
res = some_string
for ( c : some_string ){
regex_pattern = str("[%s]{2,}", c)
res = res.replaceAll(regex_pattern,"")
}
}
println( reduce_string( "aaaaacbbbbxxxdddddefghhg") )
Well, well. I am not entirely sure... but this seems to fit the bill. It was fun.
Can anyone break it?
We do not require sorting at all. No need. Using sorting, things are incredibly easy. There is a neat and fun way of solving this.
/*
If the precision of the meetings are in integers
that is 2:30 to 3:30, then we can simply quantize
the minimal value which is 30 mins meeting time min.
Then the problem becomes finding the time quantum of 30 mins
which contains the maximum overlap of meetings.
We encode the time 11:30 as 11.5 > 115 and take a 5 as 30 mins.
This can easily be done.
This can be solved in Theta(N). Observe:
*/
def find_min_rooms( list_of_meetings ) {
// simply carry on a counter ...
counter = dict()
for ( meeting : list_of_meetings ){
for ( s = meeting.start * 10 ; s <= meeting.end * 10 ; s+= 5 ){
counter[s] += 1 ?? counter[s] = 1
}
}
#(m,M) = minmax( counter.values )
return M
}

NoOne
April 23, 2020 N = 2
l = [ "geeks", "for", "geeks", "a", "portal", "to",
"learn", "can", "be", "computer", "science", "zoom",
"yup", "fire", "in", "be", "data", "geeks"]
counter = list ( mset(l) ) as { [ $.key, $.value ] }
// option 1 : not good using sorting  bad idea for large data set
result = sortd( counter ) where { sign($.l.1  $.r.1 ) }
println( str( [0:N] , "\n" ) as { str("%s > %d", result[$.o][0],result[$.o][1] ) } )
// option 2 : better use max heap
h = heap( N ) where { sign($.r.1  $.l.1 ) }
h += result
println( str( [N1:1] , "\n" ) as { str("%s > %d", h[$.o][0],h[$.o][1] ) } )

NoOne
November 29, 2019 This can be solved by inverting the Map which is genre map.
Once we invert the genre map, we know genre of each song, and now we can
traverse the song list of people while counting the genre of each song, and bingo!
This translates into :
people = {
"David": ["song1", "song2", "song3", "song4", "song8"],
"Emma": ["song5", "song6", "song7"] }
genres = {
"Rock": ["song1", "song3"],
"Dubstep": ["song7"],
"Techno": ["song2", "song4"],
"Pop": ["song5", "song6"],
"Jazz": ["song8", "song9"]
}
song_to_genre = fold( genres.entries , dict() ) as {
genre = $.key
song_list = $.value
for ( song : song_list ){
$.p[song] = genre
}
$.p // return
}
// now the trivial counting matter
for ( person : people.keys ){
persons_songs = people[person]
counter = dict()
for ( song : persons_songs ){
if ( song !@ counter ){
counter[song_to_genre[song]] = 0
}
counter[song_to_genre[song]] += 1
}
// find the genre with maximal count now?
#(min,Max) = minmax( counter.entries ) where { sign( $.left.value  $.right.value ) }
printf("Person : %s , Genre: %s %n", person, Max.key )
}

NoOne
November 25, 2019 Also, we can find out what point groups can not mutually create a circle. How? Simple, any 3 points on a plane can be made into a circle, unless all 3 of them form a line.
It is O(n^2) to check all points to find out all lines, at most.
So, we would have point groups which can not be used as circle.
That automatically should reduce a lot of points comparison.
They, might be possibly more optimisations, but am thinking still. Hence a comment, not an answer.
@Ankit Tomar's idea will not generally work  because arrays are not guaranteed to be unique. Of Course with unique array  where all elements are different it will work, but that is now as trivial as intersection and union of sets.
Solution to this problem is to imagine the generalised set operations.
Suppose an element valued "e" has count "count_a" in the "a" array or list, and "count_b" in the "b" array or list.
count of element "e" in the intersection of a,b will be defined as:
min( count_a, count_b)
count of element "e" in the union of a,b will be defined as:
max( count_a, count_b)
This generalised algorithm now can be used to Union/Intersection.You can generalised this to even find out set minus.
 NoOne October 04, 2019Actual problem can be solved, for all inputs this way , worthy of SDE 3 tag. Kudos Amazon.
/*
select domain of inversions,
and imagine starting with (0,0) which is sorted ascending.
*/
def find_if_whatever( array ){
N = size(array)
if ( N < 2 ) return true // boundary condition
// now, anything else.
domains = list()
domain = { 's' : 0, 'e' : 0 , 'st' : true }
for ( i : [ 1 : N ] ){
sorted = ( array[domain.e] <= array[i] )
if ( sorted == domain.st ){
// add to domain
domain.e = i
} else {
// end domain, create domain
domains += domain
domain = { 's' : i, 'e' : i , 'st' : sorted }
}
}
// now am done ...
domains += domain
println( jstr( domains ) ) // debug???
// now, well, well...
D = size( domains)
if ( D > 3 ) return false // no go... right?
// this is a clear go
if ( D == 1 ) return true
// now, when D=2, we have.. problems.. so
if ( D == 2 ){
if ( domains[0].st && !domains[1].st ) return array[domains[0].e] <= array[domains[1].s]
if ( !domains[0].st && domains[1].st ) return array[domains[0].s] <= array[domains[1].s]
return false
}
// now when D==3, so... larger problems...
if ( domains[0].st && domains[2].st ) {
return array[domains[0].e] <= array[domains[1].e] &&
array[domains[1].s] <= array[domains[2].s]
}
return false // done
}
println( find_if_whatever([ 1, 10,1 ]) )
println( find_if_whatever([ 1, 2,3,4,8,7,6,9 ]) )
println( find_if_whatever([ 1,2,3,50,40,90,10,23,99 ]) )

NoOne
July 31, 2019 /*
It can be done, in multiple linear traversals.
[1] Traverse to find out the min and max of the session ranges.
[2] Create a list of session count per time point, and keep on increasing
[3] Last traversal, find out the range which has max count.
We do not know (a,b) means both inclusive, or first inclusive 2nd exclusive.
It is assumed that (a,b) means user was live from a to b, that is, both inclusive
That does not match the sample output, obviously
*/
def get_max_session( session_list ){
seed = { 'm' : num('inf'), 'M' : num('inf') }
range = fold( session_list , seed ) as {
$.p.m = ( $.p.m > $.o[0] ) ? $.o[0] : $.p.m
$.p.M = ( $.p.m < $.o[1] ) ? $.o[1] : $.p.M
$.p // return
}
// now create a list, counters:
counters = list( [range.m : range.M + 1] ) as { 0 } // done
// next, increment counters...
for ( session : session_list ){
for ( offset : [ session[0] : session[1] + 1] ){
counters[ range.m  offset ] += 1 // incrementing sessions
}
}
// now, find out the range where max count exists
max_range = { 's' : range.m , 'e' : range.m , 'c' : counters[0] }
cur_range = { 's' : range.m , 'e' : range.m , 'c' : counters[0] }
for ( i : [ 0 : size(counters) ] ){
if ( cur_range.c != counters[i] ){
cur_range = { 's' : i + range.m , 'e' : i + range.m , 'c' : counters[i] }
if ( cur_range.c > max_range.c ){
// update max
max_range = { 's' : cur_range.s, 'e' : cur_range.e, 'c' : cur_range.c }
}
} else {
cur_range.e = i + range.m
}
}
// print max
println( max_range )
}
session_list = [ [2,5], [3,6], [8,10],[10,12], [9,20] ]
get_max_session( session_list )
result:
{s=13, c=3, e=13}

NoOne
July 06, 2019 L = [['abc', 10], ['def', 15], ['ghi', 10], ['abc', 12], ['xyz', 100]]
g = group( L ) as { $.o[0] } as { sum( $.value ) as { $.o[1] } }
l = list(g) as { [ $.key, $.value ] }
sortd( l ) where { sign( $.l[1]  $.r[1] ) }
println( str(l , "\n") as { str($.o, ">") } )
Produces:
xyz>100
abc>22
def>15
ghi>10

NoOne
July 05, 2019 Here you go.
/*
In here, we are abusing Java IO
*/
def abusing_java_print_count( path_string ){
if ( path_string #$ "/" ){
// remove trailing "/"
path_string = path_string[0:2]
}
words = path_string.split("/",1)
count = dict()
p = words[0]
f = file( p ).file.getCanonicalPath()
count[f] = 1
for ( i : [ 1 : size(words) ] ){
p += ("/" + words[i])
f = file( p ).file.getCanonicalPath()
if ( f !@ count ){
count[f] = 0
}
count[f] += 1
}
count // return
}
c = abusing_java_print_count( "a/../../../a")
println( jstr(c,true) )
The crucial thing is the abstract call to getCanonicalPath(), which one can now replace with
a custom impl. Here is how you get the response:
{
"\/Codes\/zoomba\/a":1,
"\/Codes":1,
"\/a":1,
"\/Codes\/zoomba":1,
"\/":1
}

NoOne
June 13, 2019 All answers are .. staggeringly wrong. Guys & Gals  it is a directory structure. I can destroy all these algorithms happiness by repeating same directory names in entirely different paths.
For example:
a/../../../a
Did you notice something interesting there? NO? Let me show you.
Suppose I am currently in the directory :
/home/dofus/
Now, the first bit will move me to
/home/dofus/a
Next 3 "../" will take me to :
/ # this is root!
And then next "a" will take me to:
/a # a directory under the root.
So, it is not as easy as it sounds. In fact, that is why the guys who write JDK has a special function for it called
[ docs.oracle.com/javase/10/docs/api/java/io/File.html#getCanonicalPath() ]
You have to normalise paths with respect to the starting or base directory.
And that is why it is an SDE3 question, not an SDE1/2 question.
Specifically:
visitCount("a/../../../a"); // null pointer exception
I will answer this in next post.
 NoOne June 13, 2019/* Find all perm.
Notice that the permutations are nothing but a mapping between
index sets  bitmaps into the list of items.
Observe, for a 3 member list {c : 3, b : 2 , a : 1 , '' : 0 }
...
Thus the problem is can be solved in 2 ways.
[1] Next higher permutation , when next is not there, increase number of digits
[2] Using the mthod of base 'k' numbers, when list is of size k  1
where digits do not repeat. We implement [2] here.
*/
def Permutations{
def $$( list_of_items ){ // constructor
$.items = list_of_items
$.base = size( $.items ) + 1
assert( $.base  1 == size( set( $.items) ), "Repeated items, I do not do those!" )
$.cur_number = 1 // nothing
}
def $next(){
next_num = $.cur_number
while ( true ){
next_num = next_num + 1
base_change_string = str( next_num , $.base )
//println( base_change_string )
// can not use any integer that is having '0' as digit
continue ( '0' @ base_change_string )
break ( size(base_change_string) > $.base )
// if no digits repeated, then ok ?
digits = set ( base_change_string.toCharArray )
break ( size( digits) == size(base_change_string) )
}
break ( size(base_change_string) > $.base )
$.cur_number = next_num
// now map it back with the items
list ( base_change_string.toCharArray ) as { idx = int( $.o )  1 ; $.$.items[ idx ] }
}
}
p = new ( Permutations, [ 'a' ,'b' , 'c' ] )
for ( x : p ){
println( x )
}

NoOne
June 02, 2019 def find_cut_point(some_string){
counter = 0
a_counter_list = list( some_string.toCharArray ) as {
// cumulative count of 'a' at index
( $.o == _'a' ) ? ( counter += 1 ) : counter
}
N = size(some_string)
A_count = a_counter_list[1]
B_count = N  A_count
exists( a_counter_list ) where {
// $.o is the current item
// $.i is the index of the item
current_b_count = $.i + 1  $.o
count_a_which_will_be_left = A_count  $.o
count_b_which_will_be_left = B_count  current_b_count
count_a_which_will_be_left == count_b_which_will_be_left
}
}
find_cut_point( "aaabbb" )

NoOne
May 20, 2019 def back_track( tmp, n ){
//println( str(tmp) )
if ( n == 0 ) {
println( str( tmp ) )
return
}
N = size( tmp )
for ( i = 0; i < N  n 1 ; i+= 1 ){
j = i + n + 1
continue( tmp[i] != 0  tmp[j] != 0 )
tmp_next = list(tmp) // deep copy
tmp_next[i] = tmp_next[j] = n
back_track( tmp_next, n1 )
}
}
def do_fb(n){
buf = list( [0:n * 2 ] ) as { 0 } // get the buf
back_track( buf , n )
}
N = 4
println( "== back tracking == ")
do_fb(N)

NoOne
May 09, 2019 I think the keep it simple, stupid works better here.
1. Construct a graph from the list ( it is a type of adj list anyways )
2. Check if the graph is a tree first.
2.1 In that case, there must be no cycle
2.2 and one clear node with null parent.
3. Do a preorder traversal on that "tree" and check at any point if there is any discrepancy
from the already given traversal.
/*
Problem is that:
swap_even() can permutate only even indices.
swap_odd() can permutate only odd indices.
That means that if someone breaks down the word into
two bag of characters with
Even [0] Bag for even indices ( 0 based indexing )
Odd [1] Bag of odd indices
Then, two words are equivalent if
for word w1 and w2
the bags ( Even and Odd ) are comprise of exact same
characters with exact same frequencies
that is the tuple ( char , count ) must be same
But on introspection, we can not compare this dictionary tuples.
So, what we do is create a sorted charset and then put a delimiter
to ensure that sorted_even_chars # sep # sorted_odd_chars
acts as key
Thus, we can create a hash function that is entirely reliant on that.
*/
def special_equivalent_hash_function( string ){
#(even, odd) = partition( string.toCharArray ) where { 2 /? $.i }
sorted_evens = str( sorta(even), '')
sorted_odds = str( sorta(odd), '')
sorted_evens + "#" + sorted_odds // return
}
def find_all_special_equivalents( list_of_strings ){
mset( list_of_strings ) as {
special_equivalent_hash_function( $.o )
}
}
res = find_all_special_equivalents( ["abcd", "cbad", "bacd" ] )
println( jstr(res,true) )
Produces :
{
"ac#bd":[
"abcd",
"cbad"
],
"bc#ad":[
"bacd"
]
}

NoOne
May 06, 2019 def Node : { val : null, left : null, right : null }
def Entry : { node : null, x : null, y : null }
def make_entries( entry_list, root , x_pos, y_pos ){
entry_list += new ( Entry, root, x_pos, y_pos )
if ( !empty( root.left ) ) { make_entries( entry_list, root.left, x_pos  1, y_pos + 1 ) }
if ( !empty( root.right ) ) { make_entries( entry_list, root.right, x_pos + 1, y_pos + 1 ) }
}
def visit_tree_column_and_row_wise( root ){
entries = make_entries( list(), root, 0, 0 )
// sort all entries by x_pos and then y_pos
sorta( entry_list ) where {
left_entry = $.l
right_entry = $.r
prec = sign( left_entry.x  right_entry.x )
if ( prec !=0 ) return prec
sign( left_entry.y  right_entry.y )
}
println( str( entry_list , "," ) as { $.node.val } )
}

NoOne
May 05, 2019 def cheat( some_arr ){
some_num = 1 + fold( some_arr, 0 ) as { $.p*10 + $.o }
ret_arr = list()
while ( some_num != 0 ){
ret_arr.add( 0 , some_num % 10 )
some_num /= 10
}
ret_arr
}
def non_cheat( some_arr ){
resp = rfold ( some_arr, { 'carry' : 1, 'result' : list() } ) as {
r = ( $.o + $.p.carry )
$.p.carry = r / 10
$.p.result.add ( 0, r % 10 )
$.p // return
}
resp.result // return
}
println( non_cheat( [1,4,3 ] ) )

NoOne
May 04, 2019 Imagine you are in the Point Origin with (0,0). Clearly, movement can be only X,Y. Thus, the way to handle it is simply keeping track of the coordinates in a set, and check if I have visited the point before or not.
If I did, I am inside a loop.
One more thing. The question is incomplete. It also should give the direction the robot is facing right now, is it N,E,W, S ?
/* quicksort */
def _partition_( arr, l, r ){
v = arr[r]
i = l
j = r  1
while ( true ){
while ( arr[i] < v ){ i += 1 }
while ( arr[j] > v ){ j = 1 }
break( i >= j )
t = arr[i] ; arr[i] = arr[j]; arr[j] = t
}
t = arr[i] ; arr[i] = arr[r]; arr[r] = t
i // return
}
def _qs_(arr, l, r ){
if ( l >= r ) return
// now here
i = _partition_(arr,l,r)
_qs_(arr,l,i1)
_qs_(arr,i+1,r)
}
def quicksort( arr ){
_qs_(arr, 0, size(arr)  1)
}
l = list( [0:13] ) as { random(100) }
println( l )
quicksort(l)
println(l)

NoOne
April 19, 2019 /*
look and say sequence
en.wikipedia.org/wiki/Lookandsay_sequence
*/
def look_and_say_next( cur_no ){
digits = str( cur_no ).toCharArray
count = 1
buf = ""
past_digit = digits[0]
for ( inx : [1:size(digits)] ){
cur_digit = digits[ inx ]
if ( cur_digit != past_digit ){
buf += ( str( count ) + str( past_digit) )
past_digit = cur_digit
count = 1
} else {
count += 1
}
}
buf += ( str( count ) + str( past_digit) )
int( buf )
}
las = list( 1 )
for ( inx : [0:10 ] ){
next = look_and_say_next( las[1] )
las += next
println( next )
}

NoOne
April 18, 2019 /* LIS */
def lis( input ){
if ( empty(input) ) return []
stacks = list( )
stacks.add( list( input[0] ) )
for ( inx : [1:size( input) ]){
added = false
for ( s : stacks ){
continue ( input[inx] <= s[0] ){
added = true
s += input[inx]
}
}
if ( !added ){ stacks.add( list( input[inx] ) ) }
}
println( size( stacks) )
// top elements of the stacks from left to right
// is the increasing sequence
println( str( stacks , ",") as { $.o[0] } )
}
a = [10, 22, 9, 33, 21, 50, 41, 60, 80]
lis( a )

NoOne
April 18, 2019 /* LIS */
def lis( input ){
if ( empty(input) ) return []
stacks = list( )
stacks.add( list( input[0] ) )
for ( inx : [1:size( input) ]){
added = false
for ( s : stacks ){
continue ( input[inx] <= s[0] ){
added = true
s += input[inx]
}
}
if ( !added ){ stacks.add( list( input[inx] ) ) }
}
println( size( stacks) )
// top elements of the stacks from left to right
// is the increasing sequence
println( str( stacks , ",") as { $.o[0] } )
}
a = [10, 22, 9, 33, 21, 50, 41, 60, 80]
lis( a )

NoOne
April 18, 2019 /*
Too much convolution in all the answers
Actual, things can be done much faster
*/
def UserActivity : {
user_id : "userid" ,
actions_at : [/* list of timestamps */ ]
}
def PageActivityForDay : {
page_id : "pageid" ,
day : "YYYMMdd" ,
user_activity : { /* map of User Activities keyed by userid */ }
}
// which pages has exactly 100 users in a day?
yo = select( list_of_page_activities_per_day ) where { size( $.user_activity ) == 100 }
// Which page was visited by only one user exactly 15 times in a day?
meh = select( list_of_page_activities_per_day ) where {
exists ( $.user_activity ) where { size( $.actions_at ) == 15 }
}
// Which page was visited by u3 more than 20 times in a day?
foo = select( list_of_page_activities_per_day ) where {
"u3" @ $.user_activity && size( $.user_activity["u3"].actions_at ) > 20
}

NoOne
April 17, 2019 Nearly optimal:
def merge_list_of_list( list_of_lists ){
iterators = list( list_of_lists ) as { $.o.iterator }
final_merge_list = list( )
added = true
while ( added ){
added = false
for ( it : iterators ){
added = it.hasNext
if ( added ){
final_merge_list += it.next // done
}
}
}
final_merge_list // return
}

NoOne
April 17, 2019 /*
In the current form, the question is ill posed.
It is as good as asking, given an array, find which indices
the maximal elements are  and return one at random.
More realistic and proper question would be:
Given a stream of integers, at any given time, if we were to ask
Give me a random index where the maximal element has appeared.
That would be worth interesting effort.
So we start.
*/
def bucket : { val : num('inf'), indices : list(1), cur_index : 1 }
def find_random_index( integer_iterator , bucket ){
if ( integer_iterator.hasNext ){
bucket.cur_index += 1
next_int = integer_iterator.next()
if ( next_int > bucket.val ){
bucket.val = next_int
bucket.indices = list( bucket.cur_index )
} else if ( next_int == bucket.val ){
bucket.indices += bucket.cur_index
}
}
random( bucket.indices ) // return a random value from collection
}

NoOne
April 12, 2019 Never reinvent the wheel. You are in Darwin, and you should simply use:
[ stackoverflow.com/questions/6637882/howcaniusegreptoshowjustfilenamesnoinlinematchesonlinux/6637894 ]
And yes, you can simply use grep.
[ digitalocean.com/community/tutorials/usinggrepregularexpressionstosearchfortextpatternsinlinux ]
Thus, the solution is really using regex in grep with "l" option.
/*
Observe the problem of cartesian product from arbitrary no.
of lists. Suppose the lists are : L1, L2, L3, ... Ln
with sizes s1, s2, s3, .. sn
Let the element in the i'th position of k'th list is Lk[i].
The configuration of such indices at any point is, then :
0 0 0 0 ... 0 // n times for the first tuple
0 0 0 0 ....1 // for the 2nd tuple...
...
0 0 0 0 ....(sn1) // for the sn Tuple.
After than, the first column will be reset, and carry will be generated,
so that the next tuple will be:
0 0 0 0 ...1 0 // for the ( sn + 1) Tuple.
Thus, generating next tuple's index is generating the carry, if any,
and resetting the indices from the index which generated the carry to the end,
and incrementing the index of the left one. This again can generate carry,
so it is a ripple effect from rightmost side to the left most side.
Thus, hasNext() is always possible, till the leftmost list is not exhausted by carry.
next() is the tricky one, where we need to define the carry and the ripple from right to left.
When there is no carry, we can stop having the ripple.
*/
def inc_iterator( some_list, cur_iterator ){
if ( cur_iterator.hasNext ){
return [ false , cur_iterator ]
} else {
return [ true, some_list.iterator ]
}
}
def cartesian ( list_of_list ){
iterators = list ( list_of_list ) as { $.o.iterator } // get the iterators
my_tuple = select( iterators ) where { $.o.hasNext() } as { $.o.next() }
if ( size( my_tuple) < size(list_of_list) ) return [] // empty tuple
println( my_tuple )
carry = false
while ( !carry ){
for ( i : [ size(list_of_list)  1 : 1 ] ){
#(carry,iter) = inc_iterator( list_of_list[i], iterators[i] )
if ( i == 0 && carry ) { return } // because now I am having carry to the left
iterators[i] = iter
my_tuple[i] = iter.next
break ( i != 0 && !carry )
}
println( my_tuple )
}
}
cartesian ( [ ['a','b', 'c'] , ['p', 'q' ], ['r','s' ] ] )

NoOne
March 11, 2018 There is no middle of anything when we are looking at a number. A number, rather more precisely integer is given by this regex (ignoring sign) :
N > [09]+
That would mean, in a context free way, it can be written as :
N > [09]* [09]? [09]*
That is how you should define middle. In this definition, of course middle becomes meaningless. Example: 34543 . What is the middle? My grammar of course is terribly ambiguous, but hope I did make the point.
Now, of course there are two problems.
1. Get all the factors of a number. This is not very interesting problem.
[ geeksforgeeks.org/finddivisorsnaturalnumberset1/ ]
2. A predicate to declare if a number is a special number. That is slightly more interesting.
But then fairly trivially done by (with proper collection minus and subset definition ):
special_digits = '356'.toCharArray
all_digits = ['0':'9'].string.toCharArray
drop_digits = all_digits  special_digits
def is_special_no( n ){
// set minus : to get the left over digits after subtracting drop_digits
left = set ( str(n).toCharArray )  drop_digits
// when left is non empty and is a proper subset of special_digits then true
!empty(left) && left <= special_digits
}
println( is_special_no(104) )
But the bigger question is, why write this way? It is terribly unoptimal !Clearly there are better way to do so? As it turned out, there is!!
special_digits = set ( '356'.toCharArray )
def is_special_no( n ){
!empty ( select ( str( n ).toCharArray ) where { $.o @ special_digits } )
}
println( is_special_no(134) )
Now this is cleaner, neater, and optimal. Now it is trivial to generate the appropriate imperative code.
 NoOne March 07, 2018Open Chat in New Window
 NoOne October 10, 2020