http://groups.google.com/group/comp.lang.c++?hl=en
comp.lang.c++@googlegroups.com
Today's topics:
* map vs list performance - 3 messages, 2 authors
http://groups.google.com/group/comp.lang.c++/t/f0b7f86d78b91416?hl=en
* Writing good articles that have much better chance to be seen by others - 2
messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/ddbe20a354342370?hl=en
* Math/CompSci Interview Question - Thoughts? - 2 messages, 2 authors
http://groups.google.com/group/comp.lang.c++/t/a1cffd71c99a2dd0?hl=en
* output - 2 messages, 2 authors
http://groups.google.com/group/comp.lang.c++/t/b9723ac6c0efc610?hl=en
* Gigantic Class - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/b3756783d92fd56a?hl=en
* Constructor problem - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/d528665531d6d939?hl=en
==============================================================================
TOPIC: map vs list performance
http://groups.google.com/group/comp.lang.c++/t/f0b7f86d78b91416?hl=en
==============================================================================
== 1 of 3 ==
Date: Thurs, Dec 31 2009 3:37 pm
From: Daniel Pitts
Branimir Maksimovic wrote:
> Lars Tetzlaff wrote:
>> i get:
>>
>> List: 1780000 150
>> Map: 10000 150
>>
>> so map is 178 times faster than map!
>>
>> Testet on Linux with gcc 4.3.2, -O3 option, processor at a fixed clock.
>
> n^2 algorithm have to be slower than nlogn, no matter what ;)
Your statement is not true.
If an algorithm is O(f(n)) then the number of operations can be k*f(n) +
g(n), where g(n) contributes less than f(n) for large n. so, for small
N, an O(nlogn) algorithm may be slower than an N^2 algorithm. For
example, compare heap-sort to merge-sort on a list of 3 elements.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
== 2 of 3 ==
Date: Thurs, Dec 31 2009 3:40 pm
From: Branimir Maksimovic
Daniel Pitts wrote:
> Branimir Maksimovic wrote:
>> Lars Tetzlaff wrote:
>>> i get:
>>>
>>> List: 1780000 150
>>> Map: 10000 150
>>>
>>> so map is 178 times faster than map!
>>>
>>> Testet on Linux with gcc 4.3.2, -O3 option, processor at a fixed clock.
>>
>> n^2 algorithm have to be slower than nlogn, no matter what ;)
> Your statement is not true.
>
> If an algorithm is O(f(n)) then the number of operations can be k*f(n) +
> g(n), where g(n) contributes less than f(n) for large n. so, for small
> N, an O(nlogn) algorithm may be slower than an N^2 algorithm. For
> example, compare heap-sort to merge-sort on a list of 3 elements.
>
>
Agreed. btw happy new year ;)
Greets
== 3 of 3 ==
Date: Thurs, Dec 31 2009 3:42 pm
From: Daniel Pitts
Branimir Maksimovic wrote:
> Daniel Pitts wrote:
>> Branimir Maksimovic wrote:
>>> Lars Tetzlaff wrote:
>>>> i get:
>>>>
>>>> List: 1780000 150
>>>> Map: 10000 150
>>>>
>>>> so map is 178 times faster than map!
>>>>
>>>> Testet on Linux with gcc 4.3.2, -O3 option, processor at a fixed clock.
>>>
>>> n^2 algorithm have to be slower than nlogn, no matter what ;)
>> Your statement is not true.
>>
>> If an algorithm is O(f(n)) then the number of operations can be k*f(n)
>> + g(n), where g(n) contributes less than f(n) for large n. so, for
>> small N, an O(nlogn) algorithm may be slower than an N^2 algorithm.
>> For example, compare heap-sort to merge-sort on a list of 3 elements.
>>
>>
>
> Agreed. btw happy new year ;)
Yes, Happy New Year to you too.
Happy New Year to everyone.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
==============================================================================
TOPIC: Writing good articles that have much better chance to be seen by others
http://groups.google.com/group/comp.lang.c++/t/ddbe20a354342370?hl=en
==============================================================================
== 1 of 2 ==
Date: Thurs, Dec 31 2009 6:16 pm
From: tanix@mongo.net (tanix)
In article <3vcv07-54n.ln1@invalid.net>, stan <smoore@exis.net> wrote:
>tanix wrote:
>> In article
> <4a6b5487-5f11-4845-8335-d46653060270@a21g2000yqc.googlegroups.com>, James
> Kanze <james.kanze@gmail.com> wrote:
>>>On 30 Dec, 04:21, ta...@mongo.net (tanix) wrote:
>>>> In article <20091229152640....@gmail.com>, Kaz Kylheku <kkylh...@gmail.com>
>>> wrote:
>>>> >On 2009-12-24, tanix <ta...@mongo.net> wrote:
>>>> >> So, from this standpoint, try to keep the context of the
>>>> >> article intact. No not delete some section of the article
>>>> >> you are following upon because you think it is
>>>> >> "insignificant" in YOUR opinion.
>>>
>>>> >In my opinion, it is bad netiquette not to trim the quoted
>>>> >article as much as possible.
>>>
>>>> Just the other way around.
>
>Actually Emily Postnews covered this long before you got to usenet.
Well, it is a new year time so I'll give you a special discount
by replying to this stuff. It is not worth replying, but we'll do that.
Now, who is Emily Postnews as far as usenet goes?
Well, NOBODY.
Simple as that.
Because the 1st individual in the history of Usenet was David Lawrence
and his buddy, Russ Allbery. Both of them were associated with ISC
(Internet Software Consortium), being sponsored in part by DISA
(Defense Information Systems Agency).
ISC is sponsored by the biggest and baddest of them all.
But if you ask what IS this thing called ISC and what is its
purpose, you might have your ear drums sightly popping if you
hear ANY response.
That was creation of what is now known as Usenet,
and, from the very first step, it was Usenet biggest disaster.
From then on, Usenet was taken over by dictators via trick, known
as "big reorg", and that is, the net.* hierarchy was split and
8 hierarchies were created instead, known as "big-8".
There was also alt.* hierarchy in this scheme.
The alt hierarcy was hierarchy of "anarchy" as these dictators
represented it. But it was just a plain democratic process in
reality. The voice of people, and not the voice of totalitarian
dicators as this disgusting totalitarian machine called big-8 was.
From the very start, David Lawrence and Russ Allbery started working
on tools and mechanisms that would allow them, and via ISC, to
allow DISA to effectively OWN Usenet.
How so?
Well, they created the PGP signature idea.
Articles or control messages, signed with the PGP key,
were made to be called "official".
Since Russ Allbery was a maintainer of the most popular news server,
INN, he wired in the mechanisms to "authorise" the most critical
parts of usenet dynamics, called newgroup, and rmgroup.
Newgroup message, at least according to the "standard", RFC 1038,
was the type of message to be automatically recognized by the
NNTP servers as a group creation message. That is ALL you have
to do to create some group.
Furthermore, the way these dictators and conmen designed it,
the default INN configuration would come with the facility,
allowing the autmoatic recognition if THEIR PGP key as an "official",
even though these individuals could not be recognized as officials
under no circumstances.
Every single newer revision of the INN server had more and more
severe mathods of dominating Usenet servers via ALL sorts of
dictatorial rules, wired into the server configuration.
The decision was made in totalitarian fasion.
No one voted for it. Usenet at large was not even aware of it,
and not that many people even realized the extent of this ugly
totalitarian perversion that allowed a small group of dictators
to LITERALLY own the whole thing, and via them, to make Usenet
totally controllable by the US military and intelligence apparatus.
Do you realize that the whole usenet can be removed
and within SECONDS, even at this very junction, you smart farts,
running your mealy mouhts, having no clue whatsoever of what
are you blabbering about?
:--}
As a result, usenet was totally controlled by these utterly
dishonest and utterly perverted dictators since day one.
They created the whole torturing procedure for those, who were
interested in creating some group. It was call the RFD process
(Request For Discussion) and CFV (Call For Votes), which is the
final and most disgusting procedure to torture the group proponents
and insult them in the most disgusting ways.
There was a whole gang of perverted sadists, called "news groupies".
Those people apparently were so profoundly uncreative that about the
only joy in life, even though a perverted one, was to forever enjoy
torturing the group proponents, insulting their intelligence,
accusing them in ALL sorts of things they have never done, just like
here, in this hole.
These sadists, called "news groupies" would "vote" as a block, and
they would vote with whatever the dictators wanted, hoping to get
promoted to the top of the heap one day and also become the "elite".
Uggggh. Disgusting to even look at this stuff.
The most disgusting "rule" was created in order to control Usenet
in the most drastic ways. It was called a 100 "vote" rule.
What it meant that even if there is "sufficient interest",
and there are HUNDREDS of people that supported creation of
some group, the end result of "discovery of interest" scam,
was that the block "vote" by these sick perverts, called
"news groupies" would be substracted from the number of
proponent votes, and the total result of "yes" "votes"
would be reduced by the number of "no" votes.
Now what is "no" votes in the process of discovering INTEREST
in creation of some group?
Well, nothing more than a procedure to sabotage the creation
of ANY group.
Because "no" "votes", by definition do NOT represent interest
in some group and could not be logically considered as appropriate.
Just because that some of you are not interested in some group,
does it mean there are not people that ARE interested in it?
What is YOUR busines in someone elses group if you are not
interested in it?
How could it POSSIBLY be taken into consideration.
By the same logic, ANY group you do not participate in,
could be considered as "no" vote by you, and, therefore,
VAST majority of the groups on Usenet would not even exist.
Clear enough for the intellectual giants of your kind and grade?
:--}
The most perverted sicko among the "news groupies" was Jay Denebeim,
a total nazi, who did and said some of the most destructive things
in the whole history of usenet.
He was in bed with that clique of self apoointed dictators
in this grand disgrace called big-8.
These dictators were not elected via democratic process.
They were self-appointed, or rather appointed by DISA, owned
gun stock and barrel by the US military and intelligence apparatus,
and the whole idea of effectively taking over the biggest,
fully distributed and most resilient information system called
Usenet, is probably the instructions given to them by DISA.
For one thing, the big-8 is the most propagated set of hierarchies
there is. Every single server in the world would carry ALL the
groups from big-8. But the alt.* hierarchy was never carried
by such a large number of servers.
So, by TOTALLY controlling the most significan part of usenet,
the only thing you had to do is to create the groups that coould
be easily supervised and loggeed in an organized manner by the
US military and intelligence in this Electronic Warfare game,
most of you are probably not aware of.
What you are dealing with Usenet is a project by the evilest,
totally anti-democratic forces int he most perverted circles
of the HIGEST caliber, who, for hundreds of years are working
on this so called NWO thing, a police state, where there are
only two classes of citizens left, the "elite" and the "slaves".
The same exact idea as Nazi ideology,
the ideology of black and white, "good" and "bad",
you are forever zombified with any place you look, from morning
to night, since your craddle.
Haven't you noticed?
:--}
There is another set of hierarchies, called alt.*, and it was not
a subject to these totalitarian dictates and the PGP key did not
apply to them. So people could create any group they want with
a single control message and the group was created instantly.
The big-8 dictators did not appreciate such a situation and they
have chosen that ultra Nazi, Jay Denebeim, as their hit man.
What he would do is to concoct some disgusting "justifications"
to remove some group, and then, based on his own concoction,
as "justification", he would issue the control messages to remove
ANY group they wanted, thus trying to destroy the most vital
parts of alt.* hierarchy.
This Nazi sicko would remove HUNDREDS of groups every single day,
365 days a year for YEARS on. He would waste most of his time,
insulting the group proponents in the most disgusting,
arrogant and blatant ways, all with silent support of dictators.
They would conduct the behnind the back email communications
to discuss the issues of PUBLIC interest and decide what they
want to do with Usenet next, quite likely being guided along
the way by the Electronic Warfare figure heads.
That was probably the most disgusting part of this criminally
minded setup.
So, since the day one, the Usenet was being literally suffocated
by these servants of the US military and intelligence apparatus,
and ISC was being paid millions by DISA in form of "sponsorship"
money and some of that money went into the pockets of these
disgusting degenerates, David Lawrence and Russ Allbery. Ask them.
And they WERE asked, and not only once.
And the result?
:--}
Guess, sire!
There are ALL sorts of interesting things about Usenet, and the
consequences to the entire mankind are simply mind boggling.
But Emily Postnews is not one of them.
Not even in the picture.
One more time:
Usenet is the ONLY remaining system of democratic commuintions
and the global information exchance on any conceivable subject.
All other approaches are totally conrolled and dominated
via all sorts of perverted "moderation" tricks.
All the blogs are "moderated".
All the forums are "moderated"
EVERYTHING you know of is "moderated".
They even tried to make the whole Usenet to be TOTALLY
"moderated" and those "moderators" happen to be the MOST
immoderate Nazis you can possibly hope to find.
First of all, if you are software guy, why would you even BOTHER
about things like trying to "moderate" some group?
For what?
And what is the guarantee that your "moderation" is going to be
unbiased?
Do you know what happened to one of the OLDEST groups on usenet,
actualy preceeding the usenet as such, called comp.ai, the very
ROOT of entire AI hierarchy?
Well, it was taken over by David Kinny, a self-admitted Nazi.
That was a pretty vibrant group with plenty of participants.
But this intellectuall pigmey, whose "research" work at the
University Of Sidney, Australia, was such a pathetic pile of
garbage of the lowest grade, that no printing press would
printing press would print if it was given a choice.
He started a campaign of lies, using some utterly bizzare
excuse, trying to justify his lust for power. Eventually,
he was able to convince a few power hungry fools to support him
He wrote the RFD, just like this sucky RFC we are talking about
here, and he promised everyone a virtual paradise and the
most democratic thing conceivable.
Then they were supported by these sickos, "news groupies",
because it was one of the central obscessions of that dictator
Russ Allbery, who was HIGLY interested in taking over usenet
via trick of "moderation".
That pathetic, mouth foaming Nazi even tried to replace the
Usenet with his totally dictatorial Usenet 2 idea, where every
single hierarchy and every single group would be "moderated",
by "tzars", LITERALLY speaking, appointed by Herr Fuehrer,
Russ Allbery, the grandfather of brainwashing and zombification.
ALL this information is on the record.
Yes, some of it you may not be able to find because it was
removed from Google archives and places like that.
But you can still find plenty.
>>>Not according to the official documents. Quoting RFC 1855:
>>>
>>> If you are sending a reply to a message or a posting be sure
>>> you summarize the original at the top of the message, or
>>> include just enough text of the original to give a context.
>>>
>>>It's not a question of opinion. It happens to be part of an
>>>official standard.
>>
>> I would expect THIS kind of response from you, personally.
>> I think your brain functions much better than this.
>>
>> Ok, lemme spend a couple of minutes on this.
>>
>> You see, "official standard" can ONLY be applied to technical
>> issues, not the posting style or personal preferences.
>
>Says who? Can you cite a reference or is this simply your opinion?
>
>> Those are CONTENT issues.
>> You can not "standartize" the content issues.
>
>Yet, netiquette rules were developed from lessons learned before the
>internet even existed.
You mean like do not use UPPER case to ACCENTUATE something,
but use all sorts of perversions like *blah* or _blah_, or /blah/?
Is THAT what you call netti-fetti-betti?
Well, to me it is probably the MOST idiotic zombification procedure.
First of all, how do I know what YOU imply by *blah* versus
_blah_?
The semantics of it are totally unclrear.
Secondly, if you want to ACCENTUATE something, why don't you use that,
which was SPECIFICALLY designed for it?
After all, you DO want to accentuate something, no matter in which
totally idiotic and perverted way you end up doing it.
ALL that happens at the end is YOU suppressing YOURSELF
by submitting to someone elses zombification propaganda,
and it is YOU, no one less, that is going to suffer the conseques
of it, as those things, that you suppressed, start accumulating
inside of you and eventually become poison and violence.
So, being the perverts you are, and MANY of you are, you start
conspiring in herds and work as a pack of volves, not to insult
the volves, trying to destroy someone, who does not buy into
the zombification procedure that is running YOUR life.
Do you see ANYTHING?
> Back then the goal
WHOSE goal?
> was to hopefully educate the unwashed ignorant masses
Here ya go, Dr. Mengele.
That IS the very nature of fascism and totalitarian dictate
by some "elite", the "blue blooded" onese, like you, sicko
present here.
> that flooded newsgroups
What is this?
Do you mind people walk on the street?
> every September when
>school started.
UTTER garbage. UTTER fabrication.
There exist no such statistics I know of.
> By the end of the first semester, things usually got
>better as the clueless started to see that the rules worked and were a
>good thing.
You ARE just a disgusting Nazi.
Simple as that.
:--}
Enough of this Nazi propaganda!
>Back then, the unwashed were capable of learning that the rules were
>based on sound principles and worked because the principles were in
>fact correct. They accepted that there was a possibility that there
>were people who might just know something they didn't.
>
>Contrast that description with today's consistently uncivilized,
>arrogant, rude (in other words petty and juvenile) behavior and you
>get a glimpse at how the world has changed.
>
>> So, to me, personally, if some fools start writing THESE kinds
>> of things into standards, then those very standards have little,
>> if not less, significance.
>
> Voluntary rules for civilized behavior are always significant, it's
> just that many are not capable of seeing why. Many can't or won't see
> the consequences of noncompliance; to them it feels better to be
> independent and rebellious. Anarchy is rarely enjoyable.
>
>I think you confuse significance with consequences.
>
>> It is like a programmer deciding to dictate others how to do
>> business or diplomacy.
>>
>> Simply does not make sense.
>
>To whom? Exactly what part is confusing? Cooperation and consequences
>maybe?
>
>Just a thought but your description of your work experiences and your
>behavior and attitude regarding netiquette seem to show a common
>thread and pattern. Cause and effect? Consequences?
>
>> Secondly, things like these, even if written into standards,
>> only mean an agreement between the members of the "board".
>
>You really don't understand usenet.
>
>Reading usenet from a web interface is like driving a motorcycle from
>a sidecar; a very distorted and unnatural experience. For those who
>prefer the web, they should stick to forums. Forums are different and
>have different principles apply to meet those differences. Use the
>right tool for the job is a lesson many learned as children; some swim
>upstream into adulthood and even old age unfortunately.
>
>Your thoughts seem appropriate for forums but they are ineffective for
>usenet.
>
>Let me ask. There was a time when the best people in the computer
>field participated in usenet and you could easily and often find help
>and interesting conversations. Does that sound like this group today?
>It does not seem that way to me. I watched many top people leave and
>many explained why they could no longer endure usenet.
>
>For at least a token effort at something remotely related to C, does anyone
>know what the M in Dennis M Ritchie stands for?
--
Programmer's Goldmine collections:
Tens of thousands of code examples and expert discussions on
C++, MFC, VC, ATL, STL, templates, Java, Python, Javascript,
organized by major topics of language, tools, methods, techniques.
== 2 of 2 ==
Date: Thurs, Dec 31 2009 6:17 pm
From: tanix@mongo.net (tanix)
In article <snjv07-ccn.ln1@invalid.net>, stan <smoore@exis.net> wrote:
>tanix wrote:
>
>> In article <lKGdnWijGeJ8VqHWnZ2dnUVZ8sydnZ2d@eclipse.net.uk>, Andy Champ
> <no.way@nospam.invalid> wrote:
>>>tanix wrote:
>>>>
>>>> My humble friend, I understand Usenet better than you,
>>>> probably an order of magnitude better.
>>>
>>>James has been providing useful replies on this group for at least three
>>>years.
>>
>> So what? What does it have to do with ANYTHING, even remotely
>> related to the subject of this thread or even group for that matter?
>
>Goes to claims of understanding.
>
><snip>
>
>> You see, what you have done is to strip the ENTIRE context
>> and left a SINGLE statement. Why did you do that?
>
>Good manners, common courtesy, spirit of cooperation, demonstration of
>understanding, etc ...
Nope.
Guilt manipulating lies and fabrications.
PROVE that your "manners" are "good"!
Prove that you are something to even bother about?
This ugly concoction is simply sick.
Enough.
>> One more time: VAST majority of article views happen via web,
>> where all that people see is a single article, just like you see
>> it via google. You do not even have a thread to look at.
>
>The claim is simply wrong. It's not a vast or even a simple
>majority. With a typical newsreader it's possible to simply filter out
>every post from the big web portals. Besides losing a vast amount of
>spam you improve the signal to noise greatly and you lose nothing like
>a vast majority of posts.
>
>Now if you count all the spam sent through google then you might
>approach half of some groups, but if you disregard spambots the
>numbers are more realistic.
>
>> First of all RFC are NOT "standards".
>> They literally mean Request For Comment or Clarification.
>>
>> Do you understand?
>
>Why do you ask? Do you claim understanding of the organization and
>governance of usenet?
>
>> They are NOT ANY kind of "standard". Yes, when there is some real
>> RFC, where a group a people worked for years on some technical
>> system and designed something that works and reconciles, that is a
>> different matter. The other people simply decide to go with it and
>> it becomes a "standard" by implication.
>>
>> But to have THIS kind of obsenity and to even conceive of an idea to
>> use it as some kind of argument, trying to make someone GUILTY of
>> something, that is not only ugly, not only PROFOUNDLY dishonest, but
>> is simply rotten to the bone and marrow.
>
>How many people besides you have to disagree to prevent something from
>becoming standard? Are you that powerful by yourself or is there some
>minimum number of others required?
>
>For the RFC's that existed before you discovered the internet, can you
>invalidate those by simple disagreement too or is there a time limit
>to your power?
>
><snip>
>
>> Do you understand the BASIC human rights, as signed by VAST majority
>> of countries in the world?
>
>Again with the "vast"; your understanding of the state of human rights
>in the international context is underwhelming. It's hard to find a
>topic with more fundamental disagreement globally.
>
>< snip>
>
>> There is such a right as freedom of expression. Do you understand?
>
>Rights never stand alone, they are paired with responsibility.
>
>Freedom of expression comes with responsibility and limits. There is a
>clear limit that prevents expression that causes harm to others. You
>can't falsely yell fire in a crowded theater or knowingly say false
>things to harm another. Those limits derive from the burden to act
>responsibly and consequences based on civil law.
>
>> It does not say "you have freedom of expression" if you sit on some
>> group for more than 3 years and you do NOT have such freedom if you
>> are there for onoy a month.
>
>Where did you read or hear this? I can't find anything that promises
>freedom of expression on usenet with or without qualifications.
>
>> Do I have to chew things like THESE to the software developers,
>> and not only software developers but LANGUAGE developers?
>
>Is there someone there threatening you? Do you need help?
--
Programmer's Goldmine collections:
Tens of thousands of code examples and expert discussions on
C++, MFC, VC, ATL, STL, templates, Java, Python, Javascript,
organized by major topics of language, tools, methods, techniques.
==============================================================================
TOPIC: Math/CompSci Interview Question - Thoughts?
http://groups.google.com/group/comp.lang.c++/t/a1cffd71c99a2dd0?hl=en
==============================================================================
== 1 of 2 ==
Date: Thurs, Dec 31 2009 6:38 pm
From: Andrew Tomazos
On Dec 23 2009, 3:48 am, "Ostap S. B. M. Bender Jr."
<ostap_bender_1...@hotmail.com> wrote:
> On Nov 21, 8:12 am, Andrew Tomazos <and...@tomazos.com> wrote:
>
>
>
> > I was posed the following question in a technical interview for a
> > Software Engineering position by a major multinational NASDAQ company:
>
> > [Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
> > One int value x occurs 500,001 times or more in the array. Specify an
> > algorithm to determine x."
>
> > The assumption being extra points for efficiency.
>
> > I initially came up with a linear space, linear time solution. With
> > some prompting and hints from the interviewer we worked our way to a
> > smaller constant space and linear time algorithm. That being
> > basically:
>
> > int findmode(int* p, int n)
> > {
> > int count[32];
> > for(int i = 0; i < 32; i++)
> > count[i] = 0;
>
> > for (int i = 0; i < n; i++)
> > for (int j = 0; j < 32; j++)
> > if (p[i] & (1 << j)) // if bit j is on
> > count[j]++;
> > else
> > count[j]--;
>
> > int x = 0;
> > for (int i = 0; i < 32; i++)
> > if (count[i] > 0)
> > x = x | (1 << i);
>
> > return x;
>
> > }
>
> > The idea here is to count the frequency of each of the 32 bits in the
> > array separately, knowing that these bit counts will be dominated by
> > the mode.
>
> > The interviewer already knew the answer, so I can only assume the test
> > was based on how much help he had to give me to arrive at it.
>
> > My question about this is as follows. I, perhaps boldly, claim to
> > employers to have a "masters-equivilant" experience/knowledge of
> > computer science and math. Should I have been able to come up with
> > this solution without prompting or help?
>
> > Would you expect someone with a CompSci Masters or PhD from some major
> > ivy league university to be able to come up with this solution without
> > help?
>
> > If so in what course or from which book would you expect to learn the
> > required knowledge to come up with the above solution?
>
> > Is the skill to be able to come up with such an algorithm something
> > that is learned by studying lots of algorithms and being able to mix
> > and match the "tricks"? If so, what is a similar commonly known
> > algorithm(s) on which the above solution could have been based?
>
> > Or, is the ability to invent such a solution simply a matter of IQ?
> > Some people have the talent to solve the puzzle, see the pattern and
> > come up with the solution - and some just don't?
>
> How badly would the following simple algorithm work:
>
> Look at the first column. Determine which digit occurs more - 0 or 1 -
> among the 1,000,000 integers, and mark those integers, that don't have
> this digit, as "R" (for "rejects")
This requires linear O(n) space to store these reject marks. The two
previously discussed algorithms only require constant O(1) space.
-Andrew.
== 2 of 2 ==
Date: Thurs, Dec 31 2009 7:23 pm
From: "Ostap S. B. M. Bender Jr."
On Dec 31, 6:38 pm, Andrew Tomazos <and...@tomazos.com> wrote:
> On Dec 23 2009, 3:48 am, "Ostap S. B. M. Bender Jr."
>
>
>
> <ostap_bender_1...@hotmail.com> wrote:
> > On Nov 21, 8:12 am, Andrew Tomazos <and...@tomazos.com> wrote:
>
> > > I was posed the following question in a technical interview for a
> > > Software Engineering position by a major multinational NASDAQ company:
>
> > > [Paraphrasing] "You are given an array of 1,000,000 32-bit integers.
> > > One int value x occurs 500,001 times or more in the array. Specify an
> > > algorithm to determine x."
>
> > > The assumption being extra points for efficiency.
>
> > > I initially came up with a linear space, linear time solution. With
> > > some prompting and hints from the interviewer we worked our way to a
> > > smaller constant space and linear time algorithm. That being
> > > basically:
>
> > > int findmode(int* p, int n)
> > > {
> > > int count[32];
> > > for(int i = 0; i < 32; i++)
> > > count[i] = 0;
>
> > > for (int i = 0; i < n; i++)
> > > for (int j = 0; j < 32; j++)
> > > if (p[i] & (1 << j)) // if bit j is on
> > > count[j]++;
> > > else
> > > count[j]--;
>
> > > int x = 0;
> > > for (int i = 0; i < 32; i++)
> > > if (count[i] > 0)
> > > x = x | (1 << i);
>
> > > return x;
>
> > > }
>
> > > The idea here is to count the frequency of each of the 32 bits in the
> > > array separately, knowing that these bit counts will be dominated by
> > > the mode.
>
> > > The interviewer already knew the answer, so I can only assume the test
> > > was based on how much help he had to give me to arrive at it.
>
> > > My question about this is as follows. I, perhaps boldly, claim to
> > > employers to have a "masters-equivilant" experience/knowledge of
> > > computer science and math. Should I have been able to come up with
> > > this solution without prompting or help?
>
> > > Would you expect someone with a CompSci Masters or PhD from some major
> > > ivy league university to be able to come up with this solution without
> > > help?
>
> > > If so in what course or from which book would you expect to learn the
> > > required knowledge to come up with the above solution?
>
> > > Is the skill to be able to come up with such an algorithm something
> > > that is learned by studying lots of algorithms and being able to mix
> > > and match the "tricks"? If so, what is a similar commonly known
> > > algorithm(s) on which the above solution could have been based?
>
> > > Or, is the ability to invent such a solution simply a matter of IQ?
> > > Some people have the talent to solve the puzzle, see the pattern and
> > > come up with the solution - and some just don't?
>
> > How badly would the following simple algorithm work:
>
> > Look at the first column. Determine which digit occurs more - 0 or 1 -
> > among the 1,000,000 integers, and mark those integers, that don't have
> > this digit, as "R" (for "rejects")
>
> This requires linear O(n) space to store these reject marks. The two
> previously discussed algorithms only require constant O(1) space.
>
Do you mean this:
int findmode(int* p, int n)
{
int count[32];
for(int i = 0; i < 32; i++)
count[i] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 32; j++)
if (p[i] & (1 << j)) // if bit j is on
count[j]++;
else
count[j]--;
int x = 0;
for (int i = 0; i < 32; i++)
if (count[i] > 0)
x = x | (1 << i);
return x;
}
Doesn't count[j] require O(log n) space?
But of course O(log n) is still better than O(n)
==============================================================================
TOPIC: output
http://groups.google.com/group/comp.lang.c++/t/b9723ac6c0efc610?hl=en
==============================================================================
== 1 of 2 ==
Date: Thurs, Dec 31 2009 7:25 pm
From: arunix
hello
here is code from "The C++ Programming langauge" by Bjarne Stroustrup.
the code is working but not showing the output when press ctrl+c it
shows only interrupt and first input.
wht's wrong with this code.
thnaks .
here is the code
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Pair{ string name; double val;};
vector<Pair> pairs;
double& value(const string& s)
{
for(unsigned int i=0; i < pairs.size(); i++)
if(s==pairs[i].name) return pairs[i].val;
Pair p={s,0};
pairs.push_back(p);
return pairs[pairs.size()-1].val;
}
int main()
{
string buf;
while(cin>>buf) value(buf)++;
for(vector<Pair> :: const_iterator p= pairs.begin(); p != pairs.end
();++p)
cout <<p->name << " : "<<p->val <<"\n";
return 0;
}
== 2 of 2 ==
Date: Thurs, Dec 31 2009 7:54 pm
From: Sam
arunix writes:
> hello
> here is code from "The C++ Programming langauge" by Bjarne Stroustrup.
> the code is working but not showing the output when press ctrl+c it
> shows only interrupt and first input.
> wht's wrong with this code.
There's nothing wrong with it. Press CTRL-D instead of CTRL-C.
==============================================================================
TOPIC: Gigantic Class
http://groups.google.com/group/comp.lang.c++/t/b3756783d92fd56a?hl=en
==============================================================================
== 1 of 1 ==
Date: Fri, Jan 1 2010 12:23 am
From: "io_x"
"Michael Tsang" <miklcct@gmail.com> ha scritto nel messaggio
news:hhfb04$aos$1@news.eternal-september.org...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> io_x wrote:
>
>>
>> "Immortal Nephi" <Immortal_Nephi@hotmail.com> ha scritto nel messaggio
>> news:dcc957fe-3558-4f5b-a7a0-4c819a003d52@u1g2000pre.googlegroups.com...
>>>I consider to use either object-based programming or object-oriental
>> ...
>> i find the word "private" and "protected" not useful
>> like the word "const".
>> in my code where is the problem?
>
> Have you ever used the words "private" and "const" ?!
yes i used them ("private", "const", "protected");
> Do you know the meaning of them?
not 100%, but i know how use them (with some help of the compiler)
> Do you know that using "const" can help the compiler to do
> better optimizations?
no i don't know it...
it seems i find problem in remember in general,
big languages standards in particular.
i prefer speak in the beginning from runnable example
(the runnable example i have some problem to find (cause to few imagination?))
and do some analisys on it for see if i find some way better for
not using these above words ("private", "const", "protected");
for "const" i'm 99% sure is not useful
==============================================================================
TOPIC: Constructor problem
http://groups.google.com/group/comp.lang.c++/t/d528665531d6d939?hl=en
==============================================================================
== 1 of 1 ==
Date: Fri, Jan 1 2010 12:23 am
From: "io_x"
"Robert" <watkinsdev@hotmail.com> ha scritto nel messaggio
news:5dcb4b84-5d57-4f31-8a7a-ffc542f6bb58@k19g2000yqc.googlegroups.com...
i speak for me:
your exmple not show any indentation, the code not compile too.
so if you have some problem with one part of code it is better
you cut the most little peace of it that compile, run,
and self-show the problem.
when you tell something in a programming group,
do it preferibily in few words (it has not matter if they are
not spell perfect (at last for me)).
==============================================================================
You received this message because you are subscribed to the Google Groups "comp.lang.c++"
group.
To post to this group, visit http://groups.google.com/group/comp.lang.c++?hl=en
To unsubscribe from this group, send email to comp.lang.c+++unsubscribe@googlegroups.com
To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.lang.c++/subscribe?hl=en
To report abuse, send email explaining the problem to abuse@googlegroups.com
==============================================================================
Google Groups: http://groups.google.com/?hl=en
No comments:
Post a Comment