Vladislav Kudelin
BAN USER
I think the problem is "o(1) space complexity", so
int[] availableChars = new int[256];
above (etc.) doesn't quite solve it (stricktly speaking);
- maybe that's the catch? (YAISAQ).
- Fascinating thread!..:-).
Implementing rand7 (with bits manipulation or else) from 5 uniformly distributed numbers as they are is I think impossible.
Why? Basically, we deal with given probabilities:
... 1/5, 2/5, 2/5.
Solving this to get uniform 1/7 out of the above fractions: be my guest.
So,
"reject sampling" (as somebody above has called it) seems to be the only easy choice.
Here is how I did it:
a) from rand5(), take 4 and reject the 5th; get rand4();
b) from rand4(), build rand2() and rand8();
c) from rand8(), again take 7 and reject the 8th.
Here is the implementation:
def rand5():
...return random.randrange(5) # this is the only "real" random
def rand4():
...while(1):
......n = rand5()
......if n < 4:
.........return n
def rand2():
...return rand4() <2
def rand8():
...n4 = rand4()
...if rand2():
......n4 += 4
...return n4
def rand_5_7():
...while(1):
......n = rand8()
......if n < 7:
.........return n
A few takes (each one calls it 100000 times and stores the results):
:~> ./rand_5_7.py 100000
0: 14424; 1: 14114; 2: 14207; 3: 14517; 4: 14241; 5: 14250; 6: 14247;
:~> ./rand_5_7.py 100000
0: 14383; 1: 14195; 2: 14140; 3: 14265; 4: 14226; 5: 14389; 6: 14402;
:~> ./rand_5_7.py 100000
0: 14281; 1: 14195; 2: 14156; 3: 14287; 4: 14245; 5: 14531; 6: 14305;
:~>
Looks like random to me:-)...
The fefinition of the "union of rectangles" is accurate in the 1st post:
this is the smallest rectangle which includes both our rectangles within it.
Given:
R1: (x1,y1),(x2,y2);
R2: (x3,y3),(x4,y4);
No assumptions about their orientations and coordinate system is needed (i.e. x1>x2 or vise versa), still we have:
left: min(x1,x2,x3,x4);
right: max(x1,x2,x3,x4);
top: min(y1,y2,y3,y4);
bottom: max(y1,y2,y3,y4).
Union: (left,bottom), (right, top)
.
Thanks!
// To me, it was not clear that the [name] is a link... I am too old for CSS...:-).
- 10
RepDarshWilliams, abc at 8x8
Exceptionally dedicated and professional Academic Advisor with a superb record of student support and satisfaction. Read about dua to put ...
- 0
RepNinaHedge, Android Engineer at ABC TECH SUPPORT
Hello, I am a Book writer who uses their content creation and verbal skills to produce articles, blogs or professional ...
- 0
Repjasmineouzts765, Apple Phone Number available 24/7 for our Customers at 247quickbookshelp
JasmineOuzts and I am a web designer and freelance fashion blogger. I love writing about the latest trends in the ...
- 0
RepElijahMiller, abc at A9
I am highly organized with exceptional commitment to task completion and quality assurance when working with computer software programs. I ...
- 0
RepFreyaShaw, Attorney at 247quickbookshelp
Excellent verbal and written communication skills to aid in properly presenting positions, arguing cases, and getting positive outcomes for clients ...
- 50
Reptracyremly, Anesthesiologist at Ness
I am Tracy, working as an Anesthesiologist handles surgical patients and their pain relief during procedures.Rather than my job ...
- 0
RepAdaShipman, abc at 247quickbookshelp
During operation, determine all necessary adjustments to the printing press to maintain safety, quality and productivity standards and make such ...
- 0
RepHey, my name is DooreMee and I completed all my study from California. And Nowadays I am working as a ...
- 0
RepDedicated and professional insurance manager with many years of experience. I love my work here. I have learned many things ...
- 0
RepHelenBMartin, Android Engineer at ABC TECH SUPPORT
I am an avid reader and a leader and participant in a community book club. My reading Kamakhya Mandir Tantrik ...
- 0
RepBrianJones, Associate at ASAPInfosystemsPvtLtd
BrianJones a Secret Service special agent with 4 years experience . I am exploiting new tricks Black magic spells to break ...
- 0
RepRomilKazi, Member Technical Staff at AppNexus
Training Assistant with 6+ years of experience preparing flawless presentations, assembling progress reports, and providing support and training to secretarial ...
- 0
RepAchillesDiaz, Digital marketing Experinced at Jabong
I am working as a web administrator. I have a basic understanding of tools for testing HTML, CSS validation, Kerala ...
- 0
Repkayegoinsk, Cloud Support Associate at ABC TECH SUPPORT
Hello, I'm Kim Starns. I work as a Telephone service representative at the respected Sholl's Colonial Cafeteria. Part ...
- 0
Repreiviasmith, Malwarebytes customer service at ABC TECH SUPPORT
I am Reivia an outgoing and motivated Travel Consultant with over 5 years of experience in delivering professional travel related ...
- 0
RepHey, I am Ruth and I am working as an interviewer.I take too many Interviews For my Company and ...
- 0
Repcarlotamdaniel, abc at ADP
- 0
RepNirvedDavis, abc at 8x8
Professional lifeguard offering expertise in water safety. Worked for more than six years in guarding and controlling the safety of ...
- 0
RepMariaBJiles, Accountant at A9
I am working as a team leader in a development software company. I am creative in learning how to crochet ...
- 0
Repsuzikaily, Digital marketing freshers at ADP
Hi , I am Suzi , working as a dancer in the Rudo club . I have been working here since 2013 and ...
- 0
Repbrendaalfaro847, Computer Scientist at ABC TECH SUPPORT
Brenda Alfaro, and I am a Skills training coordinator and I love my work. Apart from this, today I am ...
- 0
Repjonej8821, Blockchain Developer at Alliance Global Servies
I am EbonyTuckson .I am a teacher who works in High school. I work during school hours but may also ...
- 0
RepZoeyUhl, abc at 247quickbookshelp
With a highly experienced law clerk, well respected and writing proficient, detail oriented and proficient in preparing legal memos of ...
- 0
RepAadavKiva, abc at 8x8
By profession I am a blogger and passionate about writing new and informative blog content who easily understand visitors. Nowaday ...
- 0
Repmargaratlonger, Talent Acquisition at Huawei
Hello, I am Margaret . I have been working with the company of Heilig-Meyers for the last 7 year. I guide ...
- 0
Repearlenecnicely77, Animator at 247quickbookshelp
Hey, I'm a Receiving clerk. And I love my work. Apart from this, I am doing some new experiments ...
- 0
RepHelanZelda, Consultant at Advent
HelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...
- 0
Repjacquelinejlopes48, Analyst at 247quickbookshelp
Hey, I am Jacqueline and I am a court reporter.I had heard a lot about Vashikaran Specialist,now I ...
- 0
Repjudithasmith175, Accountant at Akamai
Hey, my name is Terry and I completed all my study from California. And Nowadays I am working as a ...
- 0
Repdelioshorn, Member Technical Staff at Atmel
Attentive Teller Supervisor with 4 years of experience in assisting customers to meet financial needs and referring customers to partners ...
- 0
Repstephanielstokes45, Android Engineer at ABC TECH SUPPORT
Hey, my name is Stephanie and I completed all my study from California. And Nowadays I am working as a ...
- 0
Repzippy28943, Data Scientist at AppNexus
Maxine , a grant writer specializing in researching and analysing grant opportunities, creating funding plans, and conducting proposals and budgets. Last ...
It is a trick question. First of all, one must realize that solutions like "produce all anagrams..." / search for each in string2 are damn slow, even if we use Boyer-More / Robin Karp and all good stuff. So just forget about this path. Instead, there is a linear solution.
Notice that if any contiguous part of s2 contains contains all characters from s1 and in the same amount, it is an anagram of s1 by definition.
So here is the algo:
Walk s2, while current letter is in s1: count it otherwise (letter not in s1): it cannot belong to an anagram, so we have what we have ("if solution_found..." - great) otherwise start over ("h2 = {}") hoping for the best.This is algo O(N) (as dictionary operations are O(1))
Python implementation:
- Vladislav Kudelin October 07, 2017import collections # not to build counters by hand def solution_found(h1, h2): return ( all ( (k in h2) for k in h1 ) # all letters are present... and all (( h2[k] == h1[k] ) for k in h1) # ... and are present in the same amount! ) def anagram_is_substring(s1, s2): h1 = collections.Counter(s1) # for "abbc", it produces : {"a": 1, "b":2, "c":1} h2 = {} # current counters of letters from s1 in s2; for ch in s2: if solution_found(h1, h2): return True if not ch in h1: # this breaks the condition "all letters...", so: h2 = {} # start over else: if ch not in h2: h2[ch] = 0 h2[ch] += 1 return False