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 SDE-3 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 SDE-3 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/revisiting-knuth-and-mcilroys-word-count-programs/
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
In-order traversal:
A->B->C->D->E->F->H->L->M-P->R->S->T
Write a function (pseudo-code is fine) that given a starting node, advances to the next in-order node in a binary tree.
Please also provide a data-structure 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/Inverse-square_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/d-e-shaw-interview-experience-set-19-on-campus/ ]
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 SDE-3 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
Facebook, this time, asked I guess a meaningful question. What they do - this question makes sense from a practical point of view. If you are certain that your code works, then perhaps you missed this : [ dl.acm.org/citation.cfm?id=1377232 ]
I am not too sure though.
/*
This is where other we seriously do some awesome stuff
*/
def do_non_sense_using_thread(a,b,c,d){
t1 = thread()->{ println('I am in thread with id :' + $.i) ; a + b }
t1.join()
t2 = thread()->{ println('I am in thread with id :' + $.i) ; c + d }
t2.join()
t1.value * t2.value
}
println ( do_non_sense_using_thread( 1,2,3,4) )
/* The result : LOL
I am in thread with id :10
I am in thread with id :11
21
*/
/*
An edge - if hamming distance between two strings is 1
For this problem assume that the string lengths must be same.
Not an important aberration
A chain over a collection of strings :
Treat each string as a node.
Given a sequence of node exists :
1. such that no node repeats
2. each node is connected to previous by an edge
3. Span of the chain is the nodes connected by the chain
A complete chain over a collection of strings:
A chain exists that spans over the whole collection.
Thus, the problem : does a complete chain exist for a string collection?
We can solve it using ZoomBA's predefined permutations perm.
It will generate all possible tuples - and if we can have one that matches
what the description is - we catch it.
We are not saying it is optimal - we are saying it is cool!
*/
def is_dist_1(s1, s2){
// their length differs by max 1 ?
diff_len = #| #|s1| - #|s2| |
if ( diff_len != 0 ) return false
i = index( s1.value ) :: { s2[$.i] != $.o }
// diff is one char only
rindex( s1.value ) :: { s2[$.i] != $.o } == i
}
// this gets the chain up....
def possible_chain( strings ){
v = find( perm( strings ) ) :: {
p = $.o
!exists( p ) :: { $.i > 0 && !is_dist_1( p[$.i -1], p[$.i] ) }
}
v.nil?'nothing found' : v.value
}
A = [ "abc", "aba", "bba", "tbb", "cbb" ]
B = ["abc", "aba", "bba", "tbb", "cbb", "cba"]
C = ["abc", "bba", "bbt", "aba"]
println( possible_chain(A) ) // nothing found
println( possible_chain(B) ) // @[ abc,aba,bba,cba,cbb,tbb ]
println( possible_chain(C) ) // @[ abc,aba,bba,bbt ]
// we are less than 42 lines, even with so many comments!
I made it heavily documented - thus...
// fully declarative --> un-optimal
def k_distinct_d( string , k ){
// create a range
r = [ 0 : size(string) ]
// create combination pair
pairs = list ( comb( r , 2 ) )
// sort them by their size : end_index - start_index
sortd ( pairs ) :: { ( $.left.1 - $.left.0 ) < ( $.right.1 - $.right.0 ) }
// find a pair such that the distinct chars are exactly equal to k
v = find ( pairs ) :: { s = string[$.left:$.right] ; size(set(s.value)) == k }
// yep, we are good
v.nil?'nothing found':string[ v.value.0 : v.value.1 ]
}
s = k_distinct_d("asdfrttt", 3)
println(s)
// semi imperative : reasonably optimal
def k_distinct_i( string , k ){
// we need to generate pairs with larger size first..so
len = size(string)
r = [0:len]
MAX = [ '' ] // global is frowned upon, use side effect
res = join ( r, r.reverse ) :: {
continue( $.0 >= $.1 )
s = string[ $.0 : $.1 ]
continue( size( set(s.value) ) != k || size(s) <= size(MAX.0) )
MAX.0 = s // set max
false // do not collect
}
empty(MAX.0) ? 'nothing found' : MAX.0
}
s = k_distinct_i("asdfrttt", 3)
println(s)
I sincerely doubt that is possible. If the iterator does not generate an ordered sequence - this is not possible to crack it - an iterator does not traverse backward - unless it is ListIterator - and thus... we have a foundational problem with the question.
Given the iterators are generating ordered sequence - it is trivially same as the merge concept - and is highly doable - w/o any storage.
If not, I can not think of any solution.
I realize that my blessings does not mean much - I am not that blessed anyways - but this tool is seriously awesome. The point is - I wrote something close using Jsoup -- so I can well appreciate that. I will let my organization know about it - and I think you just have found a client. We definitely need this.
- NoOne February 03, 2017/*
Classic Kerninghan & Ritchie
Use states
- in_1s
- max_1s
- current_count of 1s
*/
def count_max_1s( arr ){
// max_1s , in_1s, current_count
#(max_1s,in_1s) = fold ( arr, [ 0, false ,0 ] ) -> {
#(max_1s , in_1s, current_count) = $.p
if ( $.o == 0 ){
if ( in_1s ){
if ( current_count > max_1s ){
max_1s = current_count
}
current_count = 0
in_1s = false
}
} else {
current_count += 1
in_1s = true
}
[ max_1s, in_1s, current_count ]
}
max_1s // return
}
arr = [0,0,1,1,0,0,0,1,0,0,1,1,1,0]
println ( count_max_1s(arr) )
There is a much much much simpler approach.
Observe the algorithm - ( ZoomBA : which works my the way ) :
def find_max_len( words, S ){
max_len = 0
result = ''
for ( w : words ){
// list contains comparision
if ( w.value <= S.value && size(w) > max_len ){
result = w ; max_len = size(w)
}
}
return result
}
S = 'abpcplea'
words = set( 'ale', 'apple', 'monkey', 'plea' )
println ( find_max_len(words,S) )
The only problem is how do you implement this <= operator?
That is simple, by simply implementing an mset comparison.
Convert an array of elements into multi-set where it is actually a dictionary of key-element against the value - no of items in the collection.
@ChrisK - the question says - ignore request more than 1 sec old. That would mean - it is using this whatever as the queuing mechanism for incoming requests. In fact I am not so sure about the response at all. Hence the proposition of a heap to keep most current at the top level - and then one separate thread can peacefully trim the heap...
- NoOne January 26, 2017ChrisK is correct - the question does not mean much. But given a max-heap data structure, where - the request timestamp stays at the max ( most recent request ) could be used to trim the structure anytime anyone wants to.
[ courses.cs.vt.edu/cs2604/spring02/Notes/C07.Heaps.pdf ]
/*
The idea is to isolate all pair of (start,end) indices
such that : length is >= alphabet
sort ascending by length
then find first match - that will ensure shortest.
There are other alternatives.
just find pairs, ignore all which are less than size of alphabet, and keep a min.
This avoids the sorting.
*/
def find_min_alpha_sub_str( string , alphabet ){
r = [0:size(string)]
max_len = size(alphabet)
pairs = join ( r , r ) :: { $.o.1 - $.o.0 + 1 >= max_len }
fold( pairs , string ) :: {
s = string[$.o.0:$.o.1]
// ignore when not a sub set or current size is >= min size
continue ( !( alphabet.value <= s.value && size(s) < size($.p) ) )
$.p = s // got the min one
}
}
s = find_min_alpha_sub_str ( "abbcac", "abc" )
println( s )
They stole my question. [question?id=5669859816898560 ]
But that is ok. Given none solved it there - it feels good to solve someone else's question.
The answer :
1. From the point P, connect every vertex-node ( triangulate it )
2. This would make n triangle. Sum those areas, call it : E
3. Use two of the existing nodes as base and triangulate the polygon.
4. Sum the triangles and then we have the area of the triangle call it - A
When A == E , we have the Point inside the Polygon.
If not - then, well... you know it is not.
Previous Kernel Team guy for Microsoft here. ( Had to pull the weight, because, simply otherwise none would take the comment seriously ).
If Ola, or Flipkart, or Oyo asks you these, even including Amazon, get out of the interview.
The guy asking it, has no idea what he is asking, and almost rarely people would implement a monster as such.
One more thing. When I was a kid, I developed my own filesystem, and an Unix - shell. Those things are non trivial and they don't need it.
But if you want it - it is here : [ github.com/google/jimfs ]
PS. Ola is not Google. We should politely tell them to get over it.
// ZoomBA
/*
Problem. We should think in terms of grammar rules.
Production Rules are :
G -> ( S )*
S -> <num> [ E+ ]
E -> S | <string>
There is no ambiguity, because Rule S starts with a number.
This is context free grammar.
I require a Stack/ But I would recurse
*/
def decode( encoded ){
cur_string = ''
inx = 0 ; len = size(encoded)
times = ''
while ( inx < len ){
switch ( encoded[inx] ){
case @$ @ '0123456789' :
// <num> rule
times += @$
case _'[' :
// inside recursive rule (S)
right_bra = inx
bra_count = 1
while ( bra_count != 0 ){
right_bra += 1
char = encoded[right_bra]
if ( char == _']' ){ bra_count -= 1 }
if ( char == _'[' ){ bra_count += 1 }
}
tmp = decode( encoded[ inx + 1 : right_bra -1 ] )
cur_string += ( tmp ** int( times ) )
times = ''
inx = right_bra
case @$:
// default case : we add up the string (<string>)
cur_string += @$
}
inx += 1
}
return cur_string
}
string = "3[abc2[ef]]"
println ( decode ( string ) )
// ZoomBA.
def has_sum( arr, K ){
/* create a dictionary where the key is K - current_item
and the value is the current items index */
subs = dict( arr ) -> { [ K - $.item , $.index ] }
/* You would expect that when an item in the array is present
as the key in the subs dictionary, you are good.
But you are wrong, what about :
there is an element e such that : K = e + 2 = 2e ?
In that case, we check i am not matching the same element again
as I am checking the index */
exists ( arr ) :: { $.item @ subs && subs[$.item] != $.index }
}
// no 2*e form
println( has_sum ( [1,0,4,10,12] , 14 ) )
// there is a 2*e form
println( has_sum ( [1,0,4,7,12] , 14 ) )
// 2* e form, but there is a duplicate so...
println( has_sum ( [1,0,4,7,7,12] , 14 ) )
Given the strings are non empty, ZoomBA has some awesome one liners:
a = [ 'hi am cool', 'boo hahah' ]
es = str(a,'_') -> { hash( 'e64' , $.o ) }
println ( es )
ds = tokens ( es , '[^_]+' ) -> { hash ( 'd64', $.o ) }
println ( ds )
In case the strings can be empty - we have to do something manually :
a = [ 'hi am cool', '' , 'boo hahah' , '' ]
es = str( a , '_' ) -> { empty( $.o ) ?'' : hash( 'e64', $.o ) }
println(es)
ds = list ( es.split('_',-1) ) -> { empty($.o) ? '' : hash('d64', $.o ) }
println ( ds )
This is the basic idea, observe the nested functions ( ZoomBA ) :
def find_all_pic_dir(dir='.',
pic_extensions=set('.jpg', '.png' , '.gif') ){
// nest it
def recurse(cur_dir){
d = file ( cur_dir )
if ( !d.file.directory ) return
pic_dir = exists ( d ) :: { file($.o).extension.toLowerCase @ pic_extensions }
if ( pic_dir ){ dir_paths += cur_dir }
for ( child : d ){
recurse( child.canonicalPath )
}
}
// set up and call
dir_paths = set()
recurse( file(dir).file.canonicalPath )
// return
return dir_paths
}
dirs = find_all_pic_dir ( "/" )
println( dirs )
Basic structure is this :
def spiral( m ){
bound = size(m) ; times = bound
row = 0 ; col = 0
while ( bound > 0 ){
while ( times != 0 ){ printf(' %d ', m[row][col]) ; col += 1 ; times -= 1 }
bound -= 1 ; times = bound ; col -= 1 ; row += 1
while ( times != 0 ){ printf(' %d ', m[row][col]) ; row += 1 ; times -= 1 }
times = bound ; col -= 1 ; row -= 1
while ( times != 0 ) { printf(' %d ', m[row][col]) ; col-= 1 ; times -= 1 }
bound -= 1 ; times = bound ; row = times ; col += 1
while ( times != 0 ) { printf(' %d ', m[row][col]) ; row-= 1 ; times -= 1 }
col += 1 ; row += 1 ; times = bound
}
println()
}
This is what should be done ( ZoomBA )
d = fold ( file( 'foo.txt') , sdict() ) -> {
line_no = $.i + 1
partial = $.p
line = $.o
tokens ( line , '\S+') -> {
word = $.o.toLowerCase
if ( word @ partial ){
partial[word] += line_no
} else {
partial[word] = list( line_no )
}
}
$.p // return the partial
}
// print the stuff
for ( d ) { printf('%s : %s\n', $.key , str( $.value , ' ' ) ) }
A very complex - and *tries to be smart* approach. Not entirely sure if it is worth it, I would suggest - NO.
num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
list([0:10]) -> { random(30) }
}
println ( ll )
// smarter approach
d = fold( ll, dict() ) -> {
for ( inx : [0:size(ll)] ){
l = ll[inx]
for ( item : l ){
if ( item @ $.p ){
$.p[item] += inx
} else {
$.p[item] = set(inx)
}
}
}
$.p
}
// find all items that existed in more than one lists
entries = select ( d ) :: { size( $.o.value ) >= 2 }
println ( entries )
// make pairwise
all_pairs = fold ( entries , dict() ) -> {
list_indices = $.o.value
// create pair from values
pair = comb( list_indices , 2 )
for ( p : pair ){
k_p = str(p,',')
if ( k_p @ $.p ){
$.p[k_p] += $.o.key
} else {
$.p[k_p] = list( $.o.key )
}
}
$.p
}
println ( all_pairs )
// select all entries with value length more than 2
valid_list_pairs = select ( all_pairs ) :: { size( $.o.value ) > 2 }
println ( valid_list_pairs )
This is how it looks like in ZoomBA :
num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
list([0:10]) -> { random(30) }
}
println ( ll )
// naive approach
pairs = join ( [0:num_lists], [0:num_lists] ) :: {
i = $.0 ; j = $.1
continue ( i >= j )
intersection = ll[i] & ll[j]
size( intersection ) >= 3 // that is the condition ?
}
println ( pairs )
In recursive mode, we can do cool in ZoomBA :
def do_join( tuple, arr, result ){
i = size(tuple)
if ( i == size(arr) ){
result.add ( tuple )
return
}
for ( item : arr[i] ){
do_join ( tuple + item, arr, result )
}
}
s1 = [0,1,2]
s2 = [true, false]
arr = [s1, s2]
result = list()
do_join( [], arr, result )
println ( result )
This is how you do it :
si = set(1,2,3)
sf = set(1.0,2.0,3.0)
sb = set( true, false )
// generate cross product? very well :
p = si * sf * sb
// not satisfied ?
p = join ( si, sf, sb )
// want to load from array ?
p = join ( @ARGS = [ si, sf, sb ] )
// so, you wan to seriously code? Not cool.
In that case, here is how ZoomBA implemented join operation :-) from ZoomBA with love:
// full iterative version, w/o any stack or recursion, should be good to watch...
static boolean next(Object[] tuple, List<Iterator> states, Iterable[] cc) {
boolean carry = true;
for (int i = cc.length - 1; i >= 0; i--) {
if (!carry) break;
Iterator iterator = states.get(i);
if (iterator.hasNext()) {
tuple[i] = iterator.next();
carry = false;
} else {
if (i == 0) return true;
carry = true;
iterator = cc[i].iterator();
tuple[i] = iterator.next();
states.set(i, iterator);
}
}
return false;
}
public static Collection join(Collection into, Function predicate, Function map, Iterable[] cc) {
if (cc.length < 2) return into;
int index = 0;
Object[] tuple = new Object[cc.length];
List<Iterator> myStates = new ArrayList<>();
for (int i = 0; i < cc.length; i++) {
Iterator iterator = cc[i].iterator();
if (!iterator.hasNext()) return into;
tuple[i] = iterator.next();
myStates.add(iterator);
}
boolean carry = false;
while (!carry) {
Function.MonadicContainer result = predicate.execute(index, tuple, cc, into);
if (!result.isNil() && ZTypes.bool(result.value(), false)) {
result = map.execute(index, tuple, cc, into);
extractResult( into, result, tuple );
}
if (result instanceof Break) {
extractResult( into, result, tuple );
break;
}
carry = next(tuple, myStates, cc);
index++;
}
return into;
}
In ZoomBA, or rather any other language, the logic should be clear like this :
// get file iterator - line by line
fi1 = file('large1.txt')
fi2 = file('large2.txt')
fo = open('merged' ,'w')
// when both are non empty - interleave
while ( fi1.hasNext && fi2.hasNext ){
fo.println( fi1.next )
fo.println( fi2.next )
}
// when one is leftover, find it and drop lines
if ( fi1.hasNext || fi2.hasNext ){
leftover = fi1.hasNext ? fi1 : fi2
while ( leftover.hasNext ){
fo.println( leftover.next )
}
}
// do not forget to close
fo.close()
Singly linked list, so you use auxiliary data store, a stack works, better, a string works with a special character for separator, like "#".
You simply traverse the linked list and push to the stack, or to the string with "#" , e.g
1 -> 2 -> 3 -> 42 -> 3 -> 2 -> 1
will be encoded as :
1#2#3#42#3#2#1
Now, traverse from left ( head ) again, pop the stack, and match the values.
In case you are using a String, then split the string and then traverse from right.
In case they match always, we have a solution.
Error out in case there is no match.
We can try to be clever and use some x,2x pointer to reach to the middle. But, as of now, that pointer game is pointless.
/*
One way, as Chris said,
for n chars, 2^n for sure,
but then sort these no.s such that
the comparison is how many 1's the binary string has.
Now, iterate and find the binary string with 1 means deletion of char
where the new word after deletion is into dictionary
*/
def find_word( word , dictionary ){
n = #|word|
l = list([1: 2 ** n ]) -> { s = str($.o, 2) ; '0' ** ( n - #|s|) + s }
sorta( l ) :: {
ls = sum( $.left.value ) -> { $.o == _'1' ? 1:0 }
rs = sum( $.right.value ) -> { $.o == _'1' ? 1:0 }
ls - rs
}
fold( l , null ) :: {
s = select ( $.o.value ) :: { $.o == _'0' } -> { word[$.i] }
w = str(s,'')
break ( w @ dictionary ){ w }
}
}
dictionary = set ( 'fellow' , 'hello' , 'one' , 'hell' , 'fhel' )
word = 'fhellowne'
println ( find_word( word, dictionary ) )
A much cleaner way in ZoomBA :
my_vals = [ 0, 1, 2, 3 ]
// minimizing use of English and more math
def power_set( arr ){
len = size( arr )
// this is why it is 2^n
list ( [0 : 2 ** len ] ) -> {
bs = str( $.o , 2 ) // binary string format
// to make it sized n binary digits
bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left
// select the index i's item when bs contains 1 at index i
select( bs.value ) :: { $.o == _'0' } -> { arr[$.i] }
}
}
println ( power_set( my_vals ) )
/*
ZoomBA powerset is simply done by
the following
*/
my_vals = [ 0, 1, 2, 3 ]
// sequences() function generates all possible sub sequences
// which is the power set :)
fold ( sequences(my_vals) ) -> { println($.o) }
// in a sensible way, this is how you can do the same
// also explains why it is Theta( 2^n )
def power_set( arr ){
len = size( arr )
n = 2 ** len
for ( bn : [0:n] ){ // this is why it is 2^n
bs = str( bn, 2 ) // binary string format
// to make it sized n binary digits
bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left
// select the index i's item when bs contains 1 at index i
subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
println ( subseq )
}
}
power_set( my_vals )
Sorting is not an entirely good idea here,
we do not need it. We can solve it w/o sorting, and in linear time.
Specifically, we can solve it in 2n, in fact, we can solve it in exact n, e.g. in a single traversal. But first, I would showcase 2n in ZoomBA :
data = [ [ 'Student1', 20, 40, 65],
[ 'Student2', 35, 40, 50],
[ 'Student3', 10, 55, 65] ]
// for 3 subjects... can be generalized ...
max = list([0:3]) -> { -1 } // hoping scores do not become -ve
max = fold ( data , max ) ->{
row = $.o ; max = $.p
for ( i = 1 ; i < 4 ; i += 1 ){
if ( row[i] > max[i-1] ){
max[i-1] = row[i]
}
}
max // return
}
// next, pick and group toppers student -> topped_in_sub_count
// select those who are topper in more than n subjects ?
n = 2
toppers = fold( data ) -> {
row = $.o
count = sum ( [1:4] ) -> { row[$.o] == max[$.i] ? 1 : 0 }
continue ( count < n ) // ignore when count is < n
[ row[0] , count ] // return
}
println( toppers )
I think ChrisK did a mistake this time, a rarity.
Suppose there are K options, then 3^K is correct.
But if the steps taken are n, then 3^n is wrong, why? Because set n = 1.
Clearly one can make only 1 step, 1 way.
If n = 2, then one can make 1 + 1 or 2, so 2 ways.
If n = 3, then one can make 1 + 1, 2 + 1, 1 + 2, 3 -> 4 ways.
Thus, the pattern is :
n < 1 : 1
n = 1 : 1
n = 2 : 2
n = 3 : 4
...
Giving: ( it is a rip off of Generalized Fibonacci like sequences )
S(n) = S(n-1) + S(n-2) + S(n-3)
=====
S(3) = S(2) + S(1) + S(0) = 4
S(4) = S(3) + S(2) + S(1) = 4 + 2 + 1 = 7
=== is it correct? Let's verify ? ====
1 + 1 + 1 + 1
1+1 + 2
1+ 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1
===> Yess! ( or I am totally wrong? )
// ZoomBA let's you use sequences
steps = seq( 1,1,2 ) -> { $.p[-1] + $.p[-2] + $.p[-3] }
n = 5
total = fold ( [3:n+1] ) -> { steps.next }
println( total )
In ZoomBA:
// returns -1 if does not go bye bye,
// else returns the index
will_bye_bye( n , J ){
// one liner in ZoomBA
r = [1:n+1]
for ( i = 0 ; i < size(J) ; i+=1 ){
// select those whose index is divisible by the item index
r = select ( r ) :: { J[i] /? ($.index + 1) }
if( empty(r) || r[-1] != n ){ return i }
}
return -1
}
In ZoomBA, this is how you write it :
def TreeNode : {
val : null , // value
child : list() // list of children
}
def find_parents( cur, nodes , map ){
// check if cur.child and nodes has intersection ?
children = cur.child & nodes
if ( !empty( children ) ){
// append to the map : key -> child, value -> parent
map |= dict( children ) -> { [ $.o , cur ] }
nodes -= children // remove parented children
}
for ( child : cur.child ){
find_parents ( child, nodes, )
}
}
def delete( root , nodes ){
parents = dict()
// populate parents
find_parents ( root, nodes, parents )
// populated now
for ( pair : parents ){
// remove the child
pair.value.child -= pair.key
// re-parent childs children into parent
pair.value.child += pair.key.child
}
}
srterpe very cleverly inverted the problem. I love the idea. Hats off.
Instead of finding all possible words (sub sequences)
a string can generate, which is my stupid idea,
srterpe is counting the no of characters on each word,
and is a word can be made by taking / loaning characters from the string.
Very very clever.
My code has no chance surviving in more then 24 letter strings - he will win hand down for any string with size more than 20 ish - which is the size of a dictionary ( 2^20 ) .
srterpe is slightly off on the complexity, my algo runs with a complexity of Theta(2^n) where n is the size of the input string, it is close to n! where srterpe is correct.
No matter how large the string becomes, srterpe's method would be on size of the dictionary * no of char in the word.
See more on [ en.wikipedia.org/wiki/Longest_word_in_English ]
Here is to srterpe :
DICT = [ "go","bat","me","eat","goal", "boy", "run" ]
list_of_msets = list ( DICT ) -> { [ mset( $.o.value ) , $.o ] }
LETTERS = [ _'e' , _'o' , _'b', _'a' , _'m', _'g' , _'l' ]
mset_letters = mset( LETTERS )
words = select( list_of_msets ) :: { $.left <= mset_letters } -> { $.right }
println( words )
Trick question.
Observe the string to counter mapping can be done by (ZoomBA):
strings = { "ab" : 0 , "aa" : 1 , "fff" : 2 , ... }
counters = [ 3, 2, 0, ...]
def increment_counter( s ){
idx = strings[ s ]
#atomic{
// make atomic operation : increment
counters[idx] += 1
}
}
Note that, there is no need to lock anything beyond the increment, as every index access are independent! Only access on the same index are not.
- NoOne December 07, 2016This problem can be imagined as a permutation problem.
Observe the following. Suppose the number *n* has no of decimal digit *d*.
The problem has no solution if d > 10. You can generalise it to any base now.
Now, start with generating permutations of :
*1* out of D = [ 0, 1, 2, ...., 8, 9 ].
Then, *2* out of D ( note for leading 0s )
Then *3* out of D ( note for leading 0s )
....
Finally *d* out of D, and there, we need to find how many of them are smaller then n.
One can theoretically reach that no, given a number.
So, let's solve it for 42.
Clearly for
d = 1 -> 1-9 ( 9 ) options
d = 2 -> There are total 10 * 9 options, out of which 9 has leading zeros.
That takes the toll to 81. How many of them are larger than 42 ?
Obvious,
There are [5,6,...9] for the first digit and [0,1,...,9] for the next.
Also there are 4 for first and [3,5,...9] for second digit.
Hence, there are 5 * 9 + 6 unique digited nos greater than 42.
Hence, the total is : 9 + 81 - 51 = 39
Now, let's verify with ZoomBA:
n = 42
t = sum ( [1: n + 1 ] ) -> {
x = str($.o)
#|set( x.value )| == #|x| ? 1 : 0
}
println( t )
In ZoomBA :
/*
1. we start with the values, and assigning them the keys from pattern
2. If we find a key whose value does not match the word, we failed
3. Else we have succeeded
*/
def matches( pattern , str_list ){
if ( size(pattern) != size(str_list) ) return false
keys = dict()
fold ( str_list , true ) -> {
key = pattern[$.i]
word = $.o
if ( key @ keys ){ // key exists
// if the value pointed by the key is the word?
// then ok, else fail
break ( keys[key] != word ) { false }
} else {
// this is new word, make a key,value out of it
keys[key] = word
}
$.p
}
}
pattern = [ 'a' , 'b', 'b' , 'a' ]
string = [ 'cat', 'dog', 'dog', 'cat' ]
println ( matches ( pattern, string ) )
Think in terms of automata. Every letter in the sample string is a state, which gets activated when a letter matches, and then it waits for the next state, which is the next letter.
Thus, for a sample string -> s[i] where s[i] denotes i'th letter, s[0] is the first letter, we have this automata in place ( axiomatic ) with s[-1] is the last letter :
( anything not s[0] ) * -> s[0] -> ( anything not s[1] ) * -> s[1] .... -> s[-1] -> end
We are confused about whether or not s[0] should be the first letter and s[-1] should be the last letter of the text string - but those are easy to adjust. Thus, the automata can be coded as (in ZoomBA):
def recognize( pattern_string , text_string ){
cur_pattern_index = 0
for ( char : text_string ){
continue ( char != pattern_string[ cur_pattern_index ] )
cur_pattern_index += 1 // matched, so move to next pattern letter
}
return cur_pattern_index == size( pattern_string )
}
println ( recognize('Rdd Waitn' , 'Redmond, Washington' ) )
println ( recognize('Rdd Waixtn' , 'Redmond, Washington' ) )
Here is something of help:
[ geeksforgeeks.org/count-set-bits-in-an-integer/ ]
1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count
- NoOne February 07, 2017