Thanks for posting a link to your 13 ball solution. But your method does not answer the second part of the question - whether the odd ball is lighter or heavier - in all cases.
Not DEC. (Not Digital Research, either, as someone else guessed.) Seattle Computer Products. And, according to some histories, not Bill Gates, but Paul Allen. (It did imitate CPM from DR, which in turn imitated RSX-22 from DEC.)
They should be able to name an efficient sort algorithm (bubble sort)
Ouch! Bubble sort, at O(n^3), is just about the least efficient determinstic sort possible. Ideally a move-based sort should move each item at most once - to the correct position. Bubble sort will move an item at most one position closer to the right spot with each exchange. You could be more inefficent only if you were to move items in the wrong direction! Use bubble sort in school if you must, but never thereafter.
1. How do you make a Nazi Cross with five matches? 2. A hole is drilled through the center of a sphere. The height of the resulting object (former sphere) is 6 inches. What is its volume?
Neither of these is particularly useful in an interview; (1) is an old joke (Ans: Stick four of them in his ear and light them with the fifth) and (2), though interesting to solve, doesn't really reveal aptitude, IMO. But they're still two of my favorites.
3. Given 12 balls - 11 identical and 1 either heavier or lighter than the others - and a balance beam, determine in as few weighings as possible which is the odd ball, and whether it is heavier or lighter.
This one is getting a bit too well-known - I first heard it perhaps 20 years ago. But if someone can explain their answer they might have some aptitude for information theory and problem solving.
4. Write a binary search.
Anyone who can do this cold, with no boundary errors, gets a gold star.
5. Find as many errors as you can in [some code]. Feel free to critique the style as well.
The interviewer should provide code salted with her favorite bugs, whatever they may be.
MDI stands for "Multiple Document Interface" - a single program presenting two or more documents at the same time. You can do it with tabs, split-screen, multiple windows,...
The idea has been around for ages (emacs, for instance). The MDI initialism appeared in the late 80's courtesy of the late IBM/Microsoft GUI alliance.
Wireless on the train has been done, sort of. Amtrak Acela (northeast corridor), Hiawathas (Chicago) and Capitols (SF Bay Area) provide wireless internet access. But only with their computers, not yours.
[Switching to "serious" mode, temporarily] The "toothless" characterization was an attempt to point out the silliness - or at least the weirdness - of legislating a 20-year goal. How many current office-holders are going to be around to pass the budget bills that see it through, besides Strom Thurmond?
Twenty-year goals aren't really bad, I suppose. (Notwithstanding the dismal Soviet experience with five-year plans.) At least they show some foresight. But if I had to pick one, it wouldn't flying someone to Mars to plant a flag and collect a few rocks. Unless things go really badly for NASA we should already have some (recently acquired) Martian rocks by then.
Redundant: In 1969, Vice-President Spiro Agnew committed the United States to a manned Mars mission by the year 2000. That beats this bill by 22 years. [As a side note, the Vice-President has traditionally been the administration's point person for space activity. That is why Apollo mission responsibility shifted from the Kennedy Space Center in Florida to Mission Control in Texas (Lyndon Johnson's home state) as soon as the Saturn V cleared the launch tower.]
Toothless: There are no penalties for failure to execute. If the mission is not completed on schedule, NASA bosses should be looking at some hard prison time. Otherwise, what's the point?
Still, it gets me down when people imply that VMware is some goofy hack that happens to work with Windows and Linux.
I hope you don't mean my post; I didn't intend to imply that. I agree that the list is impressive. The set of OSes you can't (or don't choose to) support does not reflect badly on VMWare, it just shows the difficulty of the problem.
As an impartial(?) observer, I say "congratulations, good work."
In the Unix world, however, processes are not created.
Processes spring magically into existence and start to run when their contexts are loaded.
As a result, most Unix CPUs have hardware context management allowing them to completely switch processes within one instruction cycle -- or even to run more than one instruction stream concurrently.
I'll grant the point of the paragraph - that UNIX process/destruction occurs more often that MVS address space creation or even task creation.
And I'll buy that some "UNIX CPUs" can handle multiple instruction streams.
But have any really implemented a single-cycle context switch?
VPC/Win cannot simply "shove [instructions] at the actual processor" as the original post suggested. A VPC/Win OS runs in user mode, while a "bare metal" OS runs in privileged mode. In x86, some instructions work (do not cause a fault) in both modes, but *do different things.* In order to properly run a guest OS, a host (like VPC/Win or VMWare) needs to scan the instruction stream and emulate those problematic instructions. The guys at VMWare figured out how to do this(*) with almost zero overhead. But it is not easy, especially with variable length instructions such as pervade the x86.
(*) Well, I figured it out also, but only after VMWare had shown that it could be done. Before that I would not have tried; I would have written it off as "impossible."
> Does anyone know an OS (for x86 architecture) that does not run under VMware?
VMWare only claims to support Windows, DOS 6.0, some Linuxes and FreeBSD as guests. Caldera Linux is noticeably absent from the list of supported guests. (It is supported as a host.) No mention of OS/2 or VxWorks that I can see. Maybe they work, but VMWare won't say so. Newsgroup messages say that VMWare had OS/2 "mostly working" as a guest. But if they were able to fully emulate a PC, it swould have simply worked.
The spec sheet for ESX server does say that other OSes "may be supported; please contact VMWare with any specific requirements." I don't fault VMWare for such a tentative position. A self-virtualizing x86 is like a singing pig. The wonder is that it exists at all.
The sad part is that x86 self-virtualization is so difficult in the first place. It would be much easier if user-mode accesses to control registers were disallowed. How hard could that be for Intel? Or for AMD?
Several other (less popular architectures) are much easier to virtualize: S/370, M680x0 and PowerPC e.g. Motorola just missed the target with the original 68000 - eight privileged status bits were user-readable. They fixed that in the M68010.
The x86 situation benefits only VMWare, which figured out how to virtualize x86 despite Intel. And VMWare still has trouble; it can handle only specific OSes in guest machines. By contrast VM/370 (or whatever IBM is calling it these days) can handle virtually any guest OS.
I can only assume that Internet Explorer is now fully integrated with Finder. The existence of a separate IE in Mac was always a liability in the DOJ case.:-)
In the late 70s or early 80s ACM's "Computing Surverys" ran an article on Soviet computing. Here's what I remember:
The Soviets said that military computers were generally original designs.
Most of the commercial computers were either IBM 360/370 models diverted through 3rd countries (direct exports were prohibited) or the Soviet "Ryad" line. Ryads were 360/370 copies. Not having to worry about copyright andd patent issues, the East copied IBM mainframes directly. IBM engineers recognized an I/O problem with one Soviet model, since the IBM original had the same problem. Just as the 360 model development was split among groups in Poughkeepsie and Endicott, different Soviet Bloc countries were assigned development/manufacturiing responsibility for the copies.
Software was, of course, pirated OS/360. (Back in those days, software came with source.)
(Saga which I read in Science magazine many years ago.)
The 1975 Viking Mars lander was expected to last only a few months on the Mars surface; battery life was the limiting factor. The battery lasted longer than expected, but eventually the Sun would come between Earth and Mars. With the lander fully powered the battery would be dead by the time Earth came back into view.
NASA (or maybe it was JPL) thought of reprogramming the Viking controller to power down, wait a few months, then power back up. (The power-up had to be automatic; in power-down mode there was no communication with Earth.)
Viking had reprogrammable firmware, but only for pre-flight programming. Reprogramming during the mission hadn't been anticipated, so the diagnostic bus through which the ROM was reprogrammed was removable. There was no record of whether the Viking which NASA had sent to Mars had that bus or not! Nor was there a way to detect bus presence.
On the chance that the bus was installed, new code was tested on an Earth-bound copy of the Viking which had the bus, then uploaded. The Mars lander did have the bus, the code worked, and NASA got several additional months of operation from Viking.
The article has a bunch of technical "fudges", but the reporter used them to create an article - in a few parapraphs - which fairly represented the RISC/CISC debate in an intelligible manner. Itanium architecture *is* intended to enable greater parallelism. And the article does include AMD's counter-argument that CISC has adopted the RISC techniques.
But you don't need 2 processors for multiprocessing. "Barrel processors" had one core with multiple contexts (register sets). The contexts would use the execution unit in round-robin fashion. Barrel processors were controlling I/O, where mainframes needed parallelism but not speed. I think CDC PP's and Amdahl channels used them.
Same thing happened to Ernst & Young, the accounting firm which hosts the kids money site moneyopolis.com. They lost.org through a bureacratic snafu, and a pornographer picked it up. This was written up in the NY Times of 10/26/2001; search on "Moneyopolis".
Their situation was a bit more dire, since a published book directs kids to the hijacked site! I've always felt funny about seeing cyberspace addresses in printed material, and I suppose that incident highlights part of the problem. Books last a long time, while URLs have yet to demonstrate staying power. You can date any publiciation with Cue Cat to within a couple of years. How long for URLs? Ten years? Twenty?
The first 5,000 copies will be personally signed by Steve Ballmer himself! (Actually, his administrative assistant did the honors. But you'll never know.)
Itanium to x86 backwards compatibility is handled mostly in hardware, so you can credit Intel more than Microsoft for that.
Apple's support for 68K application under POWER must have been done in software, because POWER has no 68K emulation mode. (Although POWER and its predecessors have a long history of software emulation tools. In addition to the 68K, there are at least two POWER-based x86 emulators, and a POWER predecessor had a S/370 emulator.)
"Their most convincing argument is that programming is a job. It's work, and it can be hard work at times. But if all software is free, then who pays the programmers?"
Unpaid programming is feasible because it is fun. If a programming project is not fun, you are probably approaching the problem the wrong way, or with the wrong tools. When that happens, stop programming. Find or develop new approaches or new tools. Then resume the project. (This technique, which preserves the fun of programming, is more feasible in a volunteer or university setting than in industry. That may be why the Microsoft people didn't think of it.)
This is what I find fascinating about the programming process: when done properly, you can use computers to transform dog work into intellectual discovery. If that were not so, I wouldn't be a programmer.
Slashdot Mirror
Thanks for posting a link to your 13 ball solution. But your method does not answer the second part of the question - whether the odd ball is lighter or heavier - in all cases.
The post was submitted as Plain Old Text. I typed carriage returns; it must have been Slashdot which converted them to BRs.
I am not a big fan of HTML anyway. It combines content markup with style; I would rather see them separate.
Not DEC. (Not Digital Research, either, as someone else guessed.) Seattle Computer Products. And, according to some histories, not Bill Gates, but Paul Allen. (It did imitate CPM from DR, which in turn imitated RSX-22 from DEC.)
They should be able to name an efficient sort algorithm (bubble sort)
Ouch! Bubble sort, at O(n^3), is just about the least efficient determinstic sort possible. Ideally a move-based sort should move each item at most once - to the correct position. Bubble sort will move an item at most one position closer to the right spot with each exchange. You could be more inefficent only if you were to move items in the wrong direction! Use bubble sort in school if you must, but never thereafter.
1. How do you make a Nazi Cross with five matches?
2. A hole is drilled through the center of a sphere. The height of the resulting object (former sphere) is 6 inches. What is its volume?
Neither of these is particularly useful in an interview; (1) is an old joke (Ans: Stick four of them in his ear and light them with the fifth) and (2), though interesting to solve, doesn't really reveal aptitude, IMO. But they're still two of my favorites.
3. Given 12 balls - 11 identical and 1 either heavier or lighter than the others - and a balance beam, determine in as few weighings as possible which is the odd ball, and whether it is heavier or lighter.
This one is getting a bit too well-known - I first heard it perhaps 20 years ago. But if someone can explain their answer they might have some aptitude for information theory and problem solving.
4. Write a binary search.
Anyone who can do this cold, with no boundary errors, gets a gold star.
5. Find as many errors as you can in [some code]. Feel free to critique the style as well.
The interviewer should provide code salted with her favorite bugs, whatever they may be.
MDI stands for "Multiple Document Interface" - a single program presenting two or more documents at the same time. You can do it with tabs, split-screen, multiple windows, ...
The idea has been around for ages (emacs, for instance). The MDI initialism appeared in the late 80's courtesy of the late IBM/Microsoft GUI alliance.
Wireless on the train has been done, sort of. Amtrak Acela (northeast corridor), Hiawathas (Chicago) and Capitols (SF Bay Area) provide wireless internet access. But only with their computers, not yours.
[Switching to "serious" mode, temporarily] The "toothless" characterization was an attempt to point out the silliness - or at least the weirdness - of legislating a 20-year goal. How many current office-holders are going to be around to pass the budget bills that see it through, besides Strom Thurmond?
Twenty-year goals aren't really bad, I suppose. (Notwithstanding the dismal Soviet experience with five-year plans.) At least they show some foresight. But if I had to pick one, it wouldn't flying someone to Mars to plant a flag and collect a few rocks. Unless things go really badly for NASA we should already have some (recently acquired) Martian rocks by then.
Redundant: In 1969, Vice-President Spiro Agnew committed the United States to a manned Mars mission by the year 2000. That beats this bill by 22 years. [As a side note, the Vice-President has traditionally been the administration's point person for space activity. That is why Apollo mission responsibility shifted from the Kennedy Space Center in Florida to Mission Control in Texas (Lyndon Johnson's home state) as soon as the Saturn V cleared the launch tower.]
Toothless: There are no penalties for failure to execute. If the mission is not completed on schedule, NASA bosses should be looking at some hard prison time. Otherwise, what's the point?
'Nuff said.
I hope you don't mean my post; I didn't intend to imply that. I agree that the list is impressive. The set of OSes you can't (or don't choose to) support does not reflect badly on VMWare, it just shows the difficulty of the problem. As an impartial(?) observer, I say "congratulations, good work."
I'll grant the point of the paragraph - that UNIX process/destruction occurs more often that MVS address space creation or even task creation. And I'll buy that some "UNIX CPUs" can handle multiple instruction streams. But have any really implemented a single-cycle context switch?
VPC/Win cannot simply "shove [instructions] at the actual processor" as the original post suggested. A VPC/Win OS runs in user mode, while a "bare metal" OS runs in privileged mode. In x86, some instructions work (do not cause a fault) in both modes, but *do different things.* In order to properly run a guest OS, a host (like VPC/Win or VMWare) needs to scan the instruction stream and emulate those problematic instructions. The guys at VMWare figured out how to do this(*) with almost zero overhead. But it is not easy, especially with variable length instructions such as pervade the x86.
(*) Well, I figured it out also, but only after VMWare had shown that it could be done. Before that I would not have tried; I would have written it off as "impossible."
> Does anyone know an OS (for x86 architecture) that does not run under VMware?
VMWare only claims to support Windows, DOS 6.0, some Linuxes and FreeBSD as guests. Caldera Linux is noticeably absent from the list of supported guests. (It is supported as a host.) No mention of OS/2 or VxWorks that I can see. Maybe they work, but VMWare won't say so. Newsgroup messages say that VMWare had OS/2 "mostly working" as a guest. But if they were able to fully emulate a PC, it swould have simply worked.
The spec sheet for ESX server does say that other OSes "may be supported; please contact VMWare with any specific requirements." I don't fault VMWare for such a tentative position. A self-virtualizing x86 is like a singing pig. The wonder is that it exists at all.
The sad part is that x86 self-virtualization is so difficult in the first place. It would be much easier if user-mode accesses to control registers were disallowed. How hard could that be for Intel? Or for AMD?
Several other (less popular architectures) are much easier to virtualize: S/370, M680x0 and PowerPC e.g. Motorola just missed the target with the original 68000 - eight privileged status bits were user-readable. They fixed that in the M68010.
The x86 situation benefits only VMWare, which figured out how to virtualize x86 despite Intel. And VMWare still has trouble; it can handle only specific OSes in guest machines. By contrast VM/370 (or whatever IBM is calling it these days) can handle virtually any guest OS.
The message is between the lines. If there were ever an interview with a developer working in "go away and don't bug me" mode, this is it.
I can only assume that Internet Explorer is now fully integrated with Finder. The existence of a separate IE in Mac was always a liability in the DOJ case. :-)
In the late 70s or early 80s ACM's "Computing Surverys" ran an article on Soviet computing. Here's what I remember:
The Soviets said that military computers were generally original designs.
Most of the commercial computers were either IBM 360/370 models diverted through 3rd countries (direct exports were prohibited) or the Soviet "Ryad" line. Ryads were 360/370 copies. Not having to worry about copyright andd patent issues, the East copied IBM mainframes directly. IBM engineers recognized an I/O problem with one Soviet model, since the IBM original had the same problem. Just as the 360 model development was split among groups in Poughkeepsie and Endicott, different Soviet Bloc countries were assigned development/manufacturiing responsibility for the copies.
Software was, of course, pirated OS/360. (Back in those days, software came with source.)
(Saga which I read in Science magazine many years ago.)
The 1975 Viking Mars lander was expected to last only a few months on the Mars surface; battery life was the limiting factor. The battery lasted longer than expected, but eventually the Sun would come between Earth and Mars. With the lander fully powered the battery would be dead by the time Earth came back into view.
NASA (or maybe it was JPL) thought of reprogramming the Viking controller to power down, wait a few months, then power back up. (The power-up had to be automatic; in power-down mode there was no communication with Earth.)
Viking had reprogrammable firmware, but only for pre-flight programming. Reprogramming during the mission hadn't been anticipated, so the diagnostic bus through which the ROM was reprogrammed was removable. There was no record of whether the Viking which NASA had sent to Mars had that bus or not! Nor was there a way to detect bus presence.
On the chance that the bus was installed, new code was tested on an Earth-bound copy of the Viking which had the bus, then uploaded. The Mars lander did have the bus, the code worked, and NASA got several additional months of operation from Viking.
The article has a bunch of technical "fudges", but the reporter used them to create an article - in a few parapraphs - which fairly represented the RISC/CISC debate in an intelligible manner. Itanium architecture *is* intended to enable greater parallelism. And the article does include AMD's counter-argument that CISC has adopted the RISC techniques.
IBM's p690 does put 2 processors on a chip.
But you don't need 2 processors for multiprocessing. "Barrel processors" had one core with multiple contexts (register sets). The contexts would use the execution unit in round-robin fashion. Barrel processors were controlling I/O, where mainframes needed parallelism but not speed. I think CDC PP's and Amdahl channels used them.
Same thing happened to Ernst & Young, the accounting firm which hosts the kids money site moneyopolis.com. They lost .org through a bureacratic snafu, and a pornographer picked it up. This was written up in the NY Times of 10/26/2001; search on "Moneyopolis".
Their situation was a bit more dire, since a published book directs kids to the hijacked site! I've always felt funny about seeing cyberspace addresses in printed material, and I suppose that incident highlights part of the problem. Books last a long time, while URLs have yet to demonstrate staying power. You can date any publiciation with Cue Cat to within a couple of years. How long for URLs? Ten years? Twenty?
This doesn't make sense. The SX-70 was made by Polaroid, not Kodak. The code name was Aladdin. See this, for example.
So will this be the first (non-NTS) computer with a decent TOD clock, or just the world's most inaccurate watch?
The first 5,000 copies will be personally signed by Steve Ballmer himself! (Actually, his administrative assistant did the honors. But you'll never know.)
Itanium to x86 backwards compatibility is handled mostly in hardware, so you can credit Intel more than Microsoft for that.
Apple's support for 68K application under POWER must have been done in software, because POWER has no 68K emulation mode. (Although POWER and its predecessors have a long history of software emulation tools. In addition to the 68K, there are at least two POWER-based x86 emulators, and a POWER predecessor had a S/370 emulator.)
"Their most convincing argument is that programming is a job. It's work, and it can be hard work at times. But if all software is free, then who pays the programmers?"
Unpaid programming is feasible because it is fun. If a programming project is not fun, you are probably approaching the problem the wrong way, or with the wrong tools. When that happens, stop programming. Find or develop new approaches or new tools. Then resume the project. (This technique, which preserves the fun of programming, is more feasible in a volunteer or university setting than in industry. That may be why the Microsoft people didn't think of it.)
This is what I find fascinating about the programming process: when done properly, you can use computers to transform dog work into intellectual discovery. If that were not so, I wouldn't be a programmer.