Ultimate goal to join Google

Orkut Profiles !

Sep 13, 2008

Google Knol

“Knol”, announced at the official Google blog, is a currently private, invitation-only knowledge sharing service (update July 2008: it’s live now at knol.google.com). Google says that a Knol is a “unit of knowledge," and in the style of the old-school About.com website, experts are invited to the service to write an introductory article on a subject of their expertise. Google wants to provide all the tools to write this, and host the content and so on, so that experts can focus just on the content. Then, ad revenues those pages generate can be shared.

Knol pages will be made available for indexing by search engines, Google announced, including appearing in Google search itself. Google’s Udi Manber says, “Our job in Search Quality will be to rank the knols appropriately when they appear in Google search results.” (It’s not 100% clear from that statement if Google will treat Knol pages as just another organic web source, or give them some kind of special onebox, or special organic result formatting.)

A knol on a particular topic is meant to be the first thing someone who searches for this topic for the first time will want to read. The goal is for knols to cover all topics, from scientific concepts to medical information, from geographical and historical, to entertainment, from product information, to how-to-fix-it instructions. Google will not serve as an editor in any way, and will not bless any content. All editorial responsibilities and control will rest with the authors. We hope that knols will include the opinions and points of view of the authors who will put their reputation on the line. Anyone will be free to write. For many topics, there will likely be competing knols on the same subject. Competition of ideas is a good thing.

Knols will include strong community tools. People will be able to submit comments, questions, edits, additional content, and so on. Anyone will be able to rate a knol or write a review of it. Knols will also include references and links to additional information. At the discretion of the author, a knol may include ads. If an author chooses to include ads, Google will provide the author with substantial revenue share from the proceeds of those ads.

Also, Knols can be released under a Creative Commons license. It’s good to see Google finally starting to utilize this type of licensing

Sep 12, 2008

Google Chrome

Little late to write this. I am sure by now most of you would have read and heard about the new Google Chrome Browser. But here are a few things that you may not know. Check it out anyway.
It gives away a lot of features. I have copied the context of this from site:

1.New Tab Page: For the first look it looks much like a Opera feature. According to Google, new tab page let's you see a visual sampling of your most visited sites, most used search engines, and recently bookmarked pages and closed tabs.
2.Application Shortcuts: This feature directly loads your favorite online applications. You can create a shortcut as follows:#Go to Page menu and select Create application shortcuts#select the checkboxes where you want shortcuts to be placed on your computer(Desktop,Start Menu, Quick Launch Bar).
3.Dynamic Tabs: This is really an awesome feature. Dynamic Tab feature let's you drag tabs out of the browser to create a new window. You can even gather multiple tabs into one window or arrange your tabs according to your wish.
4.Crash Control:In the Google Chrome each tab run independently in the browser, there by reducing the chances of crash of all the tabs if one application crashes at any time.
5.Incognito Mode: Web pages that you open and files downloaded while you are incognito won't be logged in your browsing and download histories; all new cookies are deleted after you close the incognito window.
6.Safe Browsing: By the help of this feature, Chrome warns the user if the user is opening a unsafe website.
7.Task Manager:Google Chrome has it's own Task Manager which lets you kill any non-responsive tabs instantly.

Now the above crap is everywhere else, but read the following:
Just copied from some forum
Chrome is a shameless copy.
The speed dial - Opera
The address bar - IE 8 + FF3
Incognito - Safari & IE 8
Tabs as separate processes - IE 8
The name Chrome - Microsoft's codename for a multimedia browser years back.
Chrome consumes less memory (really very less) as compared to the resource hog - Firefox 3.
Shortcuts, if you like
Control + Shift + N : Opens the famous “incognito” windows. Thanks to it you will be able to surf without leaving any footprint on your PC (cookes, history etc.)
You can also open a website in an “incognito” window by right-clicking on a link and selecting: Open link in incognito window.
Alt + Home : Loads your Google Chrome home page along with thumbnails of your most visited sites.
Control + T : Opens a new Tab.
Control + Shift + T : Opens your most recently closed tab. Press this key combination again to open the tab closed before the one you just opened.
Control + 1, Control + 2, Control + 3, etc. : Lets you jump to different tabs.
Control + Tabs : Lets you open tabs in order.
As in Fireofx 3, you can drag a link onto a tab to it , or drop it between two tabs to open a new tab.
Control +B : Hides or shows the bookmark’s bar.
Control + H : Opens the History page.
Control + J : Opens the download page.
To delete an item from the download page, right-click on the selected item and click Remove.
Right-click the top of the browser window, select Task manager to find out how much memory tabs and plug-ins are taking from your computer to work. Select one of them and click End process to stop it running.
About:plugins (write it in the address bar): Lets you see what plug-in you are using.
About:crash (write it in the address bar): Lets you see what a crashed tab looks like.
To know more information about Google Chrome you can also type in the address bar the following commands: about:stats, about:network, about:histograms, about:memory, about:cache, about:internets.
To delete all of your data stored into Google Chrome: click the Tools icon and select Clear browsing data…
Shift + Escape: Lets you bring up the Google Chrome Task manager.

Google's hoaxes

Google has a tradition of perpetrating April Fools' Day hoaxes, which generally have an intellectual sense of humor.

2000

Google announced a new "MentalPlex" search technology that supposedly read the user's mind to determine what the user wanted to search for, thus eliminating the step of actually typing in the search query. This always ended up to a page full of April Fool's results.

* Mentalplex


2002

Google reveals the technology behind its PageRank Systems—PigeonRank. Google touts the benefits of this cost-effective and efficient means of ranking pages and reassures readers that there is no animal cruelty involved in the process. The article makes many humorous references and puns based on computer terminology and how Google PageRank really works.

* Piegeonrank

2004

Fictitious job opportunities for a research center on the moon. Luna/X (a pun to Linux as well as a reference to both the Windows XP visual style and Mac OS X) is the name of a new operating system they claimed to have created for working at the research center.

* Lunar Job

2005

Google Gulp, a fictitious drink, was announced by Google in 2005. According to the company, this beverage would optimize one's use of the Google search engine by increasing the drinker's intelligence. It was claimed this boost was achieved through real-time analysis of the user's DNA and carefully tailored adjustments to neurotransmitters in the brain (a patented technology termed Auto-Drink). The drink was said to come in "4 great flavors": Glutamate Grape (glutamic acid), Sugar-Free Radical , Beta Carroty,and Sero-Tonic Water.

This hoax was probably intended as a parody of Google's invite-only email service called Gmail. Although ostensibly free, the company claimed the beverage could only be obtained by returning the cap of a Google Gulp bottle to a local grocery store: a causal loop. In the Google Gulp FAQ, Google replies to the observation "I mean, isn't this whole invite-only thing kind of bogus?" by saying "Dude, it's like you've never even heard of viral marketing."

* Googlegulp

2006

Google Romance logo

On April Fool's Day 2006, Google Romance was announced on the main Google search page with the introduction, "Dating is a search problem. Solve it with Google Romance." It pretends to offer a "Soulmate Search" to send users on a "Contextual Date". A parody of online dating, it amusingly had a link for "those who generally favor the 'throw enough stuff at the wall' approach to online dating" to Post multiple profiles with a bulk upload file, you sleaze in addition to Post your Google Romance profile. Clicking on either of these gave an error page, which explained that it was an April Fool's joke and included links to previous April Fool's Jokes for nostalgia.

* Romance


2007

Gmail Paper

At about 10:00 PM Pacific time (where Google has its headquarters) on 30 March 2007, Google changed the login page for Gmail to announce a new service called Gmail Paper. The service offered to allow users of Google's free webmail service to add e-mails to a "Paper Archive", which Google would print (on "96% post-consumer organic soybean sputum") and mail via traditional post. The service would be free, supported by bold, red advertisements printed on the back of the printed messages. Image attachments would also be printed on high-quality glossy paper, though MP3 and WAV files would not be printed. The page detailing more information about the service features photographs of Ian Spiro and Carrie Kemper, current employees of Google. Also featured are Product Marketing Managers of Gmail Anna-Christina Douglas, and Kevin Systrom.

* Index

Google TiSP

Google TiSP (short for Toilet Internet Service Provider) was a fictitious free broadband service supposedly released by Google. This service would make use of a standard toilet and sewage lines to provide free Internet connectivity at a speed of 8 Mbit/s (2 Mbit/s upload) (or up to 32 Mbit/s with a paid plan). The user would drop a weighted end of a long, Google-supplied fiber-optic cable in their toilet and flush it. Around 60 minutes later, the end would be recovered and connected to the Internet by a "Plumbing Hardware Dispatcher (PHD)". The user would then connect their end to a Google-supplied wireless router and run the Google-supplied installation media on a Windows XP or Vista computer ("Mac and Linux support coming soon"). Alternatively, a user could request a professional installation, in which Google would deploy nanobots through the plumbing to complete the process. The free service would be supported by "discreet DNA sequencing" of "personal bodily output" to display online ads that relate to culinary preferences and personal health. Google also referenced the cola-and-Mentos reaction in their FAQ: "If you're still experiencing problems, drop eight mints into the bowl and add a two-liter bottle of diet soda." Also, look for delivery offered through the sewage system!

* Tisp

2008

Adsense for Conversations

Google releases Adsense for conversations (Introducing-adsense-for-conversations)

Blogger "Google Weblogs (beta)"

The Blogger dashboard featured an announcement for Google Weblogs, or "GWeblogs," or "Gblogs," the next revolution in personal publishing. Features include algorithms putting your best content at the top of your blog (rather than publishing by reverse chronology), automatically populating your blog's sidebar with the most relevant content, posting directly into Google search results for maximum visibility, blog headers refreshed with images from Google's team of artists for anniversaries of a scientific achievement (similar to Google Doodle), and automatic content generation ('Unsure of what to post about? Just click "I'm Feeling Lucky" and we'll "take care" of the rest!')

The announcement was followed by a link to a video tour of the product, which actually led to Tay Zonday's cover of Rick Astley's "Never Gonna Give You Up."

* Blogger Buzz: Beta

Dajare

Google launches Dajare in Japan (google.co.jp), with the mission of "organizing the world's laughter."

gDay

Google announces gDay in Australia gDay, a new beta search technology that will search web pages 24 hours before they are created.

Gmail Custom Time

Gmail's sign-in page and a banner at the top of each gmail inbox announced a new feature, called Gmail Custom Time, that would allow its users to "pre-date" their messages and choose to have the message appear as "read" or "unread". The new feature uses the slogan "Be on time. Every time."

Around 11:00 p.m. EST March 31, 2008, on the newer and older version of Gmail, but not in the basic HTML version, in the upper right corner, next to Settings, a link appeared labeled, "New! Gmail Custom Time". The link led to a 404 error until April 1, when it led to the full Gmail Custom Time hoax . Clicking any of the three links at the bottom of the page brought the user to a page stating that Gmail Custom time was, in fact, their April Fool's day joke.

Google wrote that the new joke feature "utilizes an e-flux capacitor (a pun from the movie Back to the Future) to resolve issues of causality." Fake testimonials are given by "beta users"; one example is, "I used to be an honest person; but now I don't have to be. It's just so much easier this way. I've gained a lot of productivity by not having to think about doing the 'right' thing."

The feature only allows for ten pre-dated emails per year, claiming that any more "would cause people to lose faith in the accuracy of time, thus rendering the feature useless."

* Custome time

Google Book Search Scratch and Sniff

Google Book Search has a new section allowing users to "scratch and sniff" certain books. Users are asked to "...please place your nose near the monitor and click 'Go'", which then "loads odors". When clicking on "Help", users are redirected to a page in a book that describes the origins of April Fools' Day .

* Inside Google Book Search Blog: "Google Book Search now smells better"

Google Calendar is Feeling Lucky

Google added the "I'm Feeling Lucky" button to its calendar feature. When you tried to create a new event, you were given the regular option of entering the correct details and hitting "Create Event," and also the new option of "I'm Feeling Lucky" which would set you up with an evening date with, among others, Matt Damon, Eric Cartman, Tom Cruise, Jessica Alba, Pamela Anderson, Paris Hilton, Angelina Jolie, Britney Spears, Anna Kournikova, Johnny Depp, George W. Bush, or Lois Griffin.

Google Dialect Translation

Google announces Google (Google dialect translation) for translating regional dialects of Korean to and from Standard Korean.

Google Docs

A little easter egg was added, where a user can click the file menu and directly under new document is "New Airplane" which immediately opens a copy of a Google branded paper airplane. To reach the file menu, click the new menu, then "Document" then a new window opens. The image that is embedded in the "New Airplane" document can be seen here.

Google Manpower Search

Google launches Manpower Search in China (google.cn). This new feature is powered by 25 million volunteers who do the searching around the clock. When the user entered a keyword, volunteers will search any possible answers from a mass of paper documents as well as online resources. The user is expected to get the search result within 32 seconds.

* Google Manpower

Google Summer of Code Licenses

Google changed the licenses on the SoC pages to all be "WTF Public License, Version 2".

* Summer code licencses

Google Talk

Google announced plans to, on April 22, 2008 (Earth Day), shorten all conversations over Google Talk thereby reducing the energy required to transmit chats in an effort to reduce carbon output.

Google talk

Google Wake Up Kit

Google launched their "Wake Up Kit" as a calendar notification option. The option sends a series of increasingly aggressive alerts, starting with an SMS message to your cellphone, and ending with a bucket of water dumped into your bed, which would then flip over, tossing you out (all using apparently-free equipment).

* Wakeup kit


Virgle

Google announces a joint project with the Virgin Group to establish a permanent human settlement on Mars Virgle. This operation has been named Project Virgle. The announcement includes videos of Richard Branson (founder of Virgin Group) as well as Larry Page and Sergey Brin (the founders of Google) on YouTube, talking about Virgle. An "application" to join the settlement includes questions like "I am a world-class expert in" A. Physics, B. First Aid, C. Engineering, or D. Guitar Hero II. After you submit the application, the site notifies you that you are not fit for space, or that your application is fine and "all you have to do is submit your video" [as a response to their video on YouTube]. As a result, an open source Virgle group has been established, OpenVirgle.

Yogurt

Google's Orkut displayed its name as Yogurt.

YouTube

On April 1, 2008, all featured videos on the UK and Australian homepages, and later, all international homepages, of Google-owned YouTube linked to a video of Rick Astley's song Never Gonna Give You Up, causing all users of the website who clicked on featured videos to be Rickrolled. This was the first year YouTube participated in Google's April Fool's day tradition.

Easter eggs

Various Google services also hide Easter eggs meant to be amusing entertainment.

* Searching for "the answer to life, the universe, and everything" will make the Calculator answer 42, a reference to Douglas Adams's novel The Hitchhiker's Guide to the Galaxy. In order for this Easter egg to be successful the phrase must be entered in lowercase and without the quotation marks.
* Searching for "number of horns on a unicorn" produces the answer "1" in the Calculator.
* Searching for "once in a blue moon" shows the result "1.16699016 × 10-8 hertz".
* Google offers services in many languages, including several uncommon ones like Swedish Chef's Bork bork bork, Pig Latin, Hacker (Actually leetspeak), Elmer Fudd, and Klingon.
* When asked how to get from a location in North America to a location in Europe or Africa, Google Maps included the instruction "Swim across the Atlantic Ocean", (now removed)
* When asked for directions from North America to Australia, Google Maps includes the instruction "Kayak across the Pacific Ocean". (now removed)
* The measurement tool in Google Earth allows users to measure distance in Smoots. This is a unit of length derived from a tradition at MIT.
* Taking the term Easter egg literally (and perhaps to celebrate the Easter holiday), Google has an official Easter Eggs page.
* Set the iGoogle theme to the "Beach" option. At 3:14 AM every mourning, the Loch Ness Monster surfaces for 1 minute, then at 3:15 dives back under. The reason for the timing of 3:14 is rumoured to be a tribute to the number pi. Additional 3:14 eggs include the "Seasonal Scape" showing off the Northern Lights, the "City Scape" with UFO's, the "Spring Scape" with a monster, and the "Tea House" that has spirits in the mist.
* On Google Earth, tapping out ctrl-alt-A will activate a hidden flight simulator.
* Going on Google Street Views, and heading to the rear of the company's Googleplex headquarters in Mountain View, California, the Google Street View's production team can be seen.

Aug 18, 2008

Questions at Google Job Interview

1. How many golf balls can fit in a school bus?

Solution: The point of the question isn't to see how golf balls you think are in the bus, but to see what your deduction skills are like. Do you just make a random guess or try to cop out by saying a lot, or do you actually try to come up with a legitimate answer by going through a logical series of steps.


2. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?


Solution:You simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people.


3. How much should you charge to wash all the windows in Seattle?

Solution:As crazy as it might sound, questions like these demonstrate your ability to think through a complex problem with little or no information. They expect you to take an educated guess. Most of the time you can ask them questions like - how many buildings are there in Seattle.


4. How would you find out if a machine’s stack grows up or down in memory?

Solution:Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0.


5. Explain a database in three sentences to your eight-year-old nephew.

Solution:A database is like a file cabinet. The files, or data, is stored in it and can be arranged in categories. But unlike an actual file cabinet, you can do a lot more cool stuff with a database like being able to make it accessible through the internet.


6. How many times a day does a clock’s hands overlap?

Solution:The Hour hand and Minute hand would be meeting exactly 11 times in 12 hours (Hour hand would have taken 1 clockwise round and Minute hand would have taken 12 clockwise rounds, so 12 - 1 = 11 rounds).

result: First time hour and minute hands overlap will be 12 Hours / 11 = 01:05:27.27. So at this time only hour and minute hands would be overlapping and second hand will not be any near to them. Similarly for 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th and 10th overlap of hour and minute hand the Second hand wont be any nearby. So all 3 hands (hour, minute and Second) overlap only 2 times i.e. (0:0:0 and 12:0:0).

Also we all know when we get our watches repaired, normally the repairman overlaps all the three hands to 12.

If we are considering that the second hand is not present, then the rest two overlaps 22 times in 24 hours.

There again is a catch, if we check the angles by which the hour hand and minute hand moves.

The second hand moves 6 degree in a second. In that time the minute hand will move 6/60 degrees. and the hour hand will move 6/(60*12) degrees. now taking these things in the considerations. if we check the positions of the hour and minute hand in terms of angle from the marker 12, for our first rendezvous time, i.e. 01:05:27.27 sec.
first thing that comes to my mind is that, there is fraction in the seconds. So that time can’t be measured. there will be no exact overlap. now lets calculate the angles:

1 hour 5 mins and 27 seconds = 3600 + 5*60 + 27 = 3927 seconds.

angle of hour hand = 3927 * 6/(60*12) = 32.725 degree.
angle of minute hand = 3927 * 6/60 = 392.7 degree
subtracting 360 degree from it we get - 32.7 degree.

So at 01:05:27 both hands don’t overlap. Now for 01:05:28 :
Angles : hour hand - 32.73333
minute hand - 32.8
so obviously they dont meet at 01:05:28 either.

So they overlap at 12:00 and 24:00 only. So the answer is 2 only.



7. You have to get from point A to point B. You don’t know if you can get there. What would you do?

Solution:Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther.

Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed.

During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements.

This is the best chance you have reaching point B if you don’t know if you can get there.


8. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?

Solution:Let’s suppose there are
a set of attributes of each shirt you are interested in: e.g. sleeve length, color, buttons (no buttons, fully button, partially buttoned from collar to chest level).
Let’s say the closet is a simple wall closet with a single closet rod running the entire length of closet. On the left you put all the short sleeve shirts, and on the right the long sleeve shorts. You separate then long and short sleeve sides with a specially marked coat hanger. Then you separate each group into no buttonoed, partially buttoned, and fully button, using more specially marked hangers. Then each sub group is separated into colored and monochrome sub-sub-groups (specially marked hangers aren’t needed for separators unless you are color blind) Then each colored group is sorted left to right according to the color spectrum: ROYGBIV: red, orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is sorted left to right: white on the left, black on the right, and shades of grey in the middle, the darker greys on the right, the lighter on the left.


9. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Solution:1. There is only one cheat husband
- If it is so then 99 wives knew it before. So the cheated wife got the idea from queen that her husband is cheating. So she will kill him. Next morning every wife will know there is no cheat husbands anymore.


2. There are more than one cheat husbands

- In this case, all of the wives already had the idea prior to queen's information. Its just that the cheated wives knew the count which is one less than what the non-cheated wives' knew - thats all. i.e. if there were 2 cheat husbands then their wives knew the count is 1 and others knew its 2. So the queen just repeated the info saying "at least 1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife kills her husband.


10. In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

Solution:From pure probability,we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1


11. If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

Solution:If the chance to see the car is 10 percent per minute, the first minute you have 10% chance, the second minute you have 10% of 90% = 9% (so total 19%), the third minute 10% of 81% (= 8,1%, total 27,1 %) ......
As the chance for 30 minutes is 95 percent, the chance for 1 minute is 9.5% and for 10 minute 63.1 %.


12. If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)

Solution:7.5 degrees (the hour hand is 1/4th of the way between 3 and 4, the angle measure of that is 360/12 = 30 degrees between hours / 4 = 7.5 degrees).


13. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it�s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Solution:1 and 2 cross, taking 2 minutes, 1 goes back carrying the flashlight total=3 minutes. 5 and 10 cross, taking 10 minutes totaltime now= 13 minutes, 2 goes back,total time now = 15 minutes. 1 and 2 cross again, taking 2 minutes making it 17 minutes.


14. You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

Solution:No.


15. How many piano tuners are there in the entire world?

Solution:1) At first list out all the piano manufacturing companies in the world.
2) Then look into their purchase records and find out the piano purchasers information.
3) i) If the purchase is made by an individual or a house hold then the piano is played at best case by all the people of the house.
ii) Else if the piano is purchased for school then list out the students that opted the piano course in their music curriculum.
iii) If the piano is purchased by a Church then count the no of major or minor events of the church and count the piano users.
sum up all the numbers to get more or less accurate piano users count.


16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

Solution:choose 6 balls and weigh 3 against 3
- if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one
- if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them:
- if they weigh the same, the remaining ball is the heavier one; otherwise you just found the heavier one by weighing the 2 chosen balls.


17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

Solution:The highest ranked pirate gets 98 gold coins
---Two pirates get 1 gold coin each
---The other 2 pirates get nothing.

Aug 16, 2008

Google telephonic Interview

Google telephonic Interview

1. Asked about my project. Prepare well to answer any type of questions that may arise in your project.They will just ask to explain about any one of the projects listed in your resume.
2. In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now given these n points.Find the maximum number of collinear points.
Solution:
The duality algorithm would work. Find the point of intersection with maximum no of lines incident on it in the dual plane. It works in O(n^2).
3. Write the code for finding the min of n number.

I gave:

for(i=0;i {
if( a[i] {
min = a[i] ---- eq(i)
}
}


Given that n numbers are from random sampling how many times (probability) does the line (i) be executed


Solution:

min=a[0];
for(i=1;i {
if( a[i] {

min = a[i]; -------eq(i)
}

}


Once the variable min is initialized,the probability of a[i] < min is 1/2. So the expected number of occurances of equation i is (n-1)/2 .


Round 2:


1. What is Bottom up parsing and what is top down parsing?

Solution:


Bottom-up parsing is a strategy for analyzing unknown data relationships that attempts to identify the most fundamental units first, and then to infer higher-order structures from them. It attempts to build trees upward toward the start symbol. It occurs in the analysis of both natural languages and computer languages.


Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural languages and computer languages. Please refer to these links for much better information.


http://en.wikipedia.org/wiki/Bottom-up_parsing


http://en.wikipedia.org/wiki/Top-down_parsing


2. What is a symbol table?

Solution:
In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its type, scope level and sometimes its location.
Check out
http://en.wikipedia.org/wiki/Symbol_table



3. There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situation to make sure that the user gets the response quickly.


Solution:
Every row has a primary key. Suppose the primary key for this
particular database is the name of the user then we can sort the names based
on alphabets and do secondary indexing based on the starting alphabet . If
the data is uniformly distributed we can go for multilevel indexing or
hashing.Similarly if we have a registration number as the primary key then
we can sort the table based on registration number and then do indexing
either secondary level or multilevel or apply hashing techniques based on
the distribution of data. Many efficient algorithms are available for
indexing and hashing.



4. There are 8 identical balls. One of them is defective. It could be either heavier of lighter. Given a common balance how do you find the defective ball in least number of weighings.


Solution:
Weigh 3 balls against 3 others.
Case A: If, on the first weighing, the balls balance, then the defective is among the 2 remaining balls and can be determined using 2 weighings making it a total of 3.

Case B:

Step1: If, on the first weighing, the balls don't balance.
If the balls do not balance on the first weighing, we know that the odd ball is one of the 6 balls that was weighed. We also know that the group of 2 unweighed balls are normal, and that one of the sides, let's say Side A, is heavier than the other (although we don't know whether the odd ball is heavy or light).
Step 2 : Take 2 balls from the unweighed group and use them to replace 2 balls on Side A (the heavy side). Take the 2 balls from Side A and use them to replace 2 balls on Side B (which are removed from the scale).

I. If the scale balances, we know that one of the 2 balls removed from the scale was the odd one. In this case, we know that the ball is also light. We can proceed with the third weighing amd determine the lighter of the 2 balls ,hance the defective.

II. If the scale tilts to the other side, so that Side B is now the heavy side, we know that one of the three balls moved from Side A to Side B is the odd ball, and that it is heavy. We proceed with the third weighing and determine the heavier one ,the defective.

III. If the scale remains the same, we know that one of the two balls on the scale that was not shifted in our second weighing is the odd ball. We also know that the unmoved ball from Side A is heavier than the unmoved ball on Side B (though we don't know whether the odd ball is heavy or light).




Step 3 (for Case B): Weigh the ball from Side A against a normal ball. If the scale balances, the ball from Side B is the odd one, and is light. If the scale does not balance, the ball from Side A is the odd one, and is heavy.



5. You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?


Solution:
Dozens of different data structures have been proposed for implementing dictionaries including hash tables, skip lists, and balanced/unbalanced binary search trees -- so choosing the right one can be tricky. Depending on the application, it is also a decision that can significantly impact performance. In practice, it is more important to avoid using a bad data structure than to identify the single best option available.As the frequency of look ups for a word is also important,weighted binary search tree with weights in proportion to the frequency of lookups and determining the depth, can be effective.


6. Asked me about all the details of hash table and heaps.


7. Write code for finding number of zeros in n!


Solution:

A zero in n! typically occurs when a multiple of 5 gets multiplied to an even number.We use this simple yet effective information to solve this problem.In the first n natural numbers,those divisible by 5 are always less than the no of even numbers.So it all boils down to the power of 5 in the prime factorization of n! .
This simple formula works for finding it floor(n/5)+floor(n/25)+floor(n/125)+......


function zeros(int n)
{
int count=0,k=5;
while(n>=k)
{
count+=n/k;
k*=5;
}
return count;
}


this count is the number of o's in n!.




Round 3 :



1. Write C++ class for the game Connect Four. [Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping discs into a seven column grid with the objective of getting four of one's own discs in a line.]


2. Given a stack and an input string of 1234.At any point you can do anyone of the follow

i. take the next input symbol and Enque.
ii. you can pop as many as you can. When ever you
pop an element it will be printed
(you cannot pop from an empty stack)


How many such permutations are possible on an input of size N?


Solution:
It is Nth catalan number.For a detailed solution look at question5 of Stacks and Queues



3. Give an example of one permutation that this data structure cannot generate.

For Example:

1234 is input.

First push all 1,2,3,4 on to stack and pop all.
output will be 4321.


It means that this data structure can generate 4321.


Solution:
3124
for a detailed solution please look at question7 of the post
Stacks and Queues



4. Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque.

Input: 12345
Data Structure: Deque ( Doubly Que )

Note: Deque is a data structure into which you can do enque
and deque from both sides.Some thing like this
__________________________________
enque ---> <----enque dequeue <---- ----->dequeue
__________________________________




Solution:
It is N!. Guess why?(no constraints).Convince yourself by proving that every permutation can be generated by a set of valid operations.This prove can be using the principle of strong mathematical induction.So for this specific input the answer is 120.


5. Classic Egg Puzzle Problem You are given 2 eggs.You have access to a 100-store building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-store building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.


Solution:
Let "d" be the number of drops required to find out the max floor.we need to get the value of d.

let's say if we drop from height d then if it breaks then we have d-1 floors to check for the second egg . so max of "d" drops, so first we will drop it from height "d" if it doesn't break at a height "d" then we are left with "d-1" drops,so lets drop it from d + 'd-2' + 1 height suppose if it break there then you are left with 'd-2' drops.
and so on until that sum is less than 100, it's like a linear search,

in equations,

(1+(d-1))+ (1+(d-2)) + .... >= 100

here we need to find out d

from the above equation

d(d + 1)/2 >= 100


from above d is 14





Round 4 :



1. Given n non overlapping intervals and an element. Find the interval into which this element falls.


Solution:
we can extend binary search to intervals.(Assuming the intervals are sorted)
consider interval [a,b].
if (a-x)(b-x) <=0
then x belongs to [a,b].
else
if x>a
element can be present only in the intervals to its right.
so select the middle interval among them to it's right
and repeat the procedure.
else
element can be present only in the intervals to its left.
so select the middle interval among them to it's left
and repeat the procedure.

The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals.


2. Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n). So please give a solution that will do better than O(n).


3. Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..)


Solution:
If the above intervals are overlapping ,then they can be merged in O(N) and then the exact intervals can be resolved later.Otherwise ,we can identify one correct interval and then linear search on its left and right neighbourhood to find the other solutions.




4. Write code for Random Sort?

Algorithm is explained:

Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.





Round 5: This is Manager Round



1. Tell me an achievement that you have done in your non academics


2. Tell me about one of your project


3. Take a feature of C++ and tell me how you have implemented it in one of your project


4. By taking one of your project as example tell me how you have taken care of software engineering where you would have handled more data


5. There is a routine already written to find the subtraction of two sets ( set A - set B) . Write test cases for testing it.Tell me how do you test the test cases you have written?


6. There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have?


Solution: Well people,this is too simple a question ..so do give it a try..(no malice,too simple)

Google Top Interview Puzzles

1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

Solution : At each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting A[i]=a*b,where a=cumulative product of all those elements to the left of A[i] and b=cumulative product of all those elements to the right of A[i].

We can put this simply by storing the result in a separate array and by traversing the input array twice.

In the first iteration, we traverse the input array left to right and assign Output[i]=a (where a is the product of all the numbers preceding A[i]).

Now we traverse the input array again ,but in reverse direction and this time we find
b(here b is the product of all the numbers following A[i]) and Assign

Output[i]=Output[i]*b; which amounts to putting Output[i]=a*b

Hence Each Output[i] contains the product of all the elements in A except A[i].

Below is a C function to do the same.


int* function(int input[],int size,int output[])
{
long int result=1;
for(int i=0;i {
output[i]=result;
result*=input[i];
}
result=1;
for(int i=size-1;i>=0;i--)
{
output[i]*=result;
result*=input[i];
}
return output;
}

2 .There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

Solution : Traverse the list, generating a new random number for each entry. Keep a ‘top k’ chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.

This random number generated for each element can be defined as a function f=absolute(irand()-rand()),which is random enough.


3 . Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm

Solution : This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:


base = n/8; (base is the char whose certain bit needs to be set)

offset = 1 << (n mod 8); (offset is the bit to be set)

b_array[base] |= offset; (I set the particular bit)

Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.

base = m/8; (base is the char whose certain bit needs to be set)

offset = 1 << (m mod 8); (offset is the bit to be set)

if (b_array[base] & offset)
// found the number
else
//number could not be found


*Any other solutions will be appreciated.

4 . You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

Solution : Please refer to Question1.This question is identical to the first one,except that it is made to look much harder.


5 . How do you put a Binary Search Tree in an array in a efficient manner.

Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.

Solution : The method of construction given in Hint though looks good at a mere glance,it has too many shortcomings.Exponential memory is required at the worst case.

The solution is maintain inorder and one of the other 2 traversals of the tree.These 2 are sufficient to construct back the tree.So the space requirement now is 2N i.e O(N)


6. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.

Solution :int num=0;
void max(tree*t)
{
if(t==NULL)
return;
max(t->right);
num++;
if(num==5)
printf("%d\n",t->no);
max(t->left);
}

7 . Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn

Solution : we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.

8 . Given two sequences of items, find the items whose
absolute number increases or decreases the most when comparing
one sequence with the other by reading the sequence only once.

Solution : Well, this question requires some reading and understanding
of data streams.The stress is upon the algorithmic challenges in web search engines.It wouldn't be appropriate to quote a short piece of text
as the answer.So please go through the paper finding Frequent Items in Data Streams to have a thorough understanding of the problem
as well as its applications.

9 . How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

Solution : The three non-collinear points form a triangle. There will be 3 lines which are equidistant from all the three points.
Draw altitudes from each point to the line joining the other two points.We get 3 altitudes.Now draw a line passing through the mid point of the altitude line and parallel to line onto which the altitude is drawn.This line is equidistant from all the 3 points.Thus we get 3 lines.

10 . Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

Solution : This solution has been framed on the assumption that all the occurances of a string in the large string of length N are to be reported.
So one can just sort the M strings in O(l*Mlog(M)).An additional l figures because comparison function of strings of length l is of complexity O(l).
Once these M strings are sorted,we can simply do a binary search on them for each of the N-l+1 continuous substrings of big string.The complexity of this search for each such substring is O(l*logM).
So the complexity of this procedure is O(l*MlogM)+O((N-l+1)*(l*logM)).
For N>>l this reduces to O(l*MlogM)+O(N*l*log(M).
This can be reduced to O((M+N)*l*log(M)).

11 . Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code.
Solution : If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.

bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}

Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.

12 . You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

Solution : For each chunk of sorted list which occupies a block,make a note of the first and last elements.Thus we have lookup table giving the first and last elements of each of the blocks.Now associate an empty list with each of the blocks.
Now try to find the block which might contain the first entry A[1]of the small sorted list(say)A given.Since we knew the first and last elements of all the blocks,we can identify the block Bi ,which only can contain the desired number.Now add A[1] to the empty list associated with Bi.Now we need to identify the candidate block for A[2].As A is also sorted,A[2] should lie either in Bi or its successors.So we simultaneously traverse
A as well as lookup table.When we are done with finding the probable blocks of all the numbers in A,we have also finished the look up table. We also have in the lists associated with each block,all those entries of A to search for, in that particular block.Now for each block Bi,search for all the entries in its list using binary search.This way we have minimized the number of disk block accesses,which is the bottleneck .

13 . Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?

Solution : Different solutions exist for this problem,depending on how once perceives the question.
If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2.
We go on merging like this until we have a single union of all the companies.
Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2)*........*(2c2)=(N!*(N-1)!)/2^(N-1) .

One more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be merged.

We could have merged companies 1&2 in the first iteration and 3&4 in the 2nd iteration.Likewise we could have also merged 3&4 in the first iteration and then 1&2 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn't even consider that.
If we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are identical .Then this problem reduces to parenthesis problem,i.e number of ways of putting N pairs of parenthesis.The answer then would be N-1 th Catalan Number,
i.e (2N-2)!/N!(N-1)!.

If the companies aren't identical ,with some permutations also getting into the picture, then the solution isn't straightforward and we couldn't figure it out.

14 . Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

Solution : The maximum size of int is 2,147,483,647 in case of 32-bit integers. Thus we need declare an array of long long int.
Then we can do a merge sort and in doing so we can find the integers which appear atleast twice in the merge step.Thus we can solve the problem in
nlogn time.

15 . Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Solution : This question is similar to question 9 in the context which it appears and
answer lies in the same paper Finding Frequent Items in Data Streams.

16 . Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Solution : Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.

Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).

17 . Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

Solution : This is a flavour of coin change problem ,for which sufficient material is available at Coin Change Problem.
If you have gone through the above link,please refer below to the minor changes we make to the pseudo code of one given in the above link.

Let p[n][m] denote the minimum no of coins of various denomination required to give change for n cents from coins of m different denominations.

P[n][m]=min((1+p[n-S[m]][m]),p[n][m-1])// these notations will be clear only if you go through the above link thoroughly.

Then it isn't much difficult to write the conditions for base cases as well.
This is only a suggested solution to this problem and we have clues here and there as to how to proceed.

18 . Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.

Solution : a)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.

b)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.
The following is a function which returns the length of the longest increasing subsequence in a.


int lis(int*a,int n)
{
int length[n],path[n],i,j,max=0;

for(i=0;i < N;i++)
length[i]=1,path[i]=i; //path contains the longest subsequence.

for(i=1;i < N;i++)
for(j=0;j < i;j++)
if(a[i] > a[j] && length[i] < length[j]+1)
length[i]=length[j]+1,path[i]=j;

for(i=0;i < N;i++)
if(max < length[i])
max=length[i];

return max;
}


19 . Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Solution : This is a repeated question, same as the 16th. So please refer to the 16th answer.

20 . Write a function to find the middle node of a single link list.

Solution :

typedef struct linklist
{
int no;
struct linklist*next;
}list;

void midvalue(list*start)
{
list*head;
head=start;
while(1)
{
if(start->next==NULL)
{
if(head->next==NULL)
{
printf("Only one node in the list which is %d\n",head->no);
}
else
{
printf("Middle node is %d\n",head->next->no);
}
break;
}
if(start->next->next==NULL)
{
printf("Middle nodes are %d and %d\n",head->no,head->next->no);
}
start=start->next->next;
head=head->next;
}
return;
}


This algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).


21 . Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Solution : The following is a function to check if the two trees are similar or not.It returns true if they are similar else false.


int compareTree(struct node* a, struct node* b) {
if (a==NULL && b==NULL)
return(true);
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
compareTree(a->left, b->left) &&
compareTree(a->right, b->right)
);
}
else return(false);
}


22 . Implement put/get methods of a fixed size cache with LRU replacement algorithm.

Solution : Each cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.
Getting some data is just a search for the data thereby incrementing it age and resorting the cache units.


get(id)
{
z=search(id);
data=cache[z].data;
cache[z].age++;
sort(cache);
return(x);
}

put(id,x)
{
if(top==cachesize) //if cache is full
top--
cache[top].id=id;
cache[top].data=x;
cache[top].age=0;
top++;
}


23 . You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity

Solution : Point to the first elements of the three arrays, namely a[0],b[0],c[0].
Find the smallest and second smallest of the three.Let us say that a[0] is the smallest and b[0] is the second smallest. Increment the pointer of a until you find a[i]>b[0]. Calculate the difference between a[i-1] and c[0] and store it as current min. Now,again find the smallest and second smallest between a[i], b[0], and c[0] and repeat the above process. If the new difference is smaller than current min,update the value of current min.
Repeat the above process until one of the arrays are finished.


24 . Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Solution : Let d be the number of drops required.
Now we need to find an optimal solution no matter at which floor the egg breaks.
So we find d such that it doesn't depend on the floor number.

Let us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.
If the egg doesn't break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.
We proceed in this fashion,till we reach the 100th floor.

Thus we break at d,2*d-1,3*d-2,....

thus d+(d-1)+(d-2)+.... 1 <=100
=>d=14
Thus we need atmax of 14 attempts for any case.

Google Interview Questions

Google Interview Questions ::

Total there are five Technical Interviews followed by Management round.

So here are the questions.

Round 1 ::

  1. What is the Space complexity of quick sort algorithm? how do find it?

    Solution: Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
    * in-place partitioning is used. This requires O(1).
    * After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.
    The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

    However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.


  2. What are dangling pointers?

    Solution: A dangling pointer is a pointer to storage that is no longer allocated. Dangling pointers are nasty bugs because they seldom crash the program until long after they have been created, which makes them hard to find. Programs that create dangling pointers often appear to work on small inputs, but are likely to fail on large or complex inputs.


  3. Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

    Solution:The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.
    Nth state can be arrived directly by taking 2 step movement from N-2 or 1 step from N-1.Remember N-2 -> N-1 -> N is not a direct path from N-2th state to Nth state.Hence the no of solutions is no of ways to reach N-2th step and then directly taking a 2 jump step to N + no of ways to reach N-1th step and then taking 1 step advance.


  4. You are given biased coin. Find unbiased decision out of it?

    Solution:Throw the biased coin twice.Classify it as true for HT and false for TH.Both of these occur with probability=p*(1-p),hence unbiased. Ignore the other 2 events namely HH and TT.



  5. On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.




Round 2 ::

  1. You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

    Solution:
    The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.

    Sum of first N natural numbers=N*(N+1)/2

    and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !!



    Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.

    We solve this problem by solving 2 essential equations.



    They are X+Y=N*(N+1)/2 -S---------->(1)

    X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries.

  2. You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

    Solution:
    The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.

    Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z

    Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.


  3. Questions on my project please be prepare well about your project


  4. How do you search for a word in a large database
  5. How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.

Round 3 ::

  1. You have given an array. Find the maximum and minimum numbers in less number of comparisons.

    Solution:
    only 3n/2 comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements.

  2. You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).

    Solution:All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.


Round 4 ::

  1. Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
           Ex: A="abcd" B="xyz" C="axybczd". answer is yes.


    Solution:

    bool test(A,B,C)
    {
    i=j=k=0;
    while(k < i ="=" j ="=">
    The above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing one in to a dilemma whether to accept the character from A or B.


  2. Given two sorted arrays A and B.
    1. Find the intersection of these arrays A and B.

      Solution:The intersection can be found by using a variation of merge routine of the merge sort.


    2. If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?

      Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.

Round 5 ::

  1. If you get into Google, which products are you going to work on?
  2. What is TCP, UDP. what is reliability, unreliability, give examples of these?

    Solution:
    Click Here To Read About TCP
    Click Here To Read About UDP
    Click Here To Read About Reliability

  3. What is http protocol?

    Solution:
    Click Here To Read About HTTP

  4. How does Google search engine works?
  5. What is indexing, what is the input and output to it. how Google does that?
Sorry, couldn't find any translationPlease support us by using Babylon search engine

Aug 12, 2008

Google Technology

The massive popularity of search engines lies in its ability to turn up results for search queries very quickly and accurately (University of Minnesota Browsing the Web?). Google database boasts a 6-billion-item index, which includes web pages as well as newsgroup articles and images (Parker, P. 2004). This site receives up to 250 million searches a day, which equals to roughly 18.7 million hours spent on the site per month (Sullivan, D., 2003, Sullivan, D., 2004).

Google's Page Rank algorithm, which was named in part after Larry Page, analyses recursive links between sites. This works by assigning every page, its own Page Rank which is a specified link to the page, and how important the linking pages are. This helps to determine the sites that are of actual importance, and enables Google to deliver results that are as accurate as possible. Sites on the web are gathered by the Gogebic, a Web Crawler which trawls the internet going through links. Google then creates a digital copy or a cache of pages that are new or actively tries to update the cache, removing links that are no longer working and updating pages that have been changed. All this takes place on Google server (Price, G., (2001)). The caches purpose is to allow dead links to be viewed even though the source is down for whatever reason. The pages do not stay in the Google cache, although a useful feature has been the source of some legal disputes (Olsen, S., 2003).

Google’s ability to handle such a huge volume of traffic lies in its unique computer architecture, which distributes a search query over many servers operating in small networks. Queries are distributed over the networks depending on the users physical proximity to that network. According to a consensus, it is believed that Google has an estimated 100,000 servers, although a somewhat more accurate estimate puts the number of servers at between 63,272 machines to 79,112 machines. On the higher end, Google would have whopping 316,448 GHz of computing power, 158,224 GB of RAM and 6,180 Tb of hard disk space (Levy, S., 2004, Tristan, L., 2004).

------------------------------------------------------------------------------------------------

Aug 10, 2008

Best Captures over Google

  1. Basic Google search WITHOUT ADS - This has got to be my easier search,and I’m glad to bookmark it to use,lot more than the usual Google. Don’t remove the &output=googleabout from the URL, because it will not work otherwise.
  2. An old advertisment page - An old advertisment page is where we find the first Google AdWords Select program.
  3. Solutions for Financial Services (metrics) - A page with very interesting Google statistics, dated November 2005.
  4. Jumpstart - If you’re a new advertiser planning to spend at least 50 U.S. dollars a day on AdWords, Google’s Jumpstart specialists will use their extensive knowledge of AdWords to create a customized campaign that you can modify and can also use as a model for future campaigns.
  5. Advertising Demos and Guides – This will be the best for advertising tutorials, demos and guides to expand the nature of business.
  6. 10 Tips for Enterprise Search - Use these tips to find, index and rank pages on your company websites very effectively and can improve your users’ search experience.
  7. The last Adwords newsletter - dated July 2004, with few spectacular sidebar stats.
  8. Guidelines for Third Party Use of Google Brand Features - ALL the Google trademarks for their services. The page also provides guidelines for the use of Google’s brand features.
  9. The Google Web Directory - A page which is nomore with public,listing some nice infos and facts about the Google Directory.
  10. Google Corporate contact page - Which is not with public for some time now, and where we find some OTHER phone numbers than the ones used these days in their current contact page (go ahead and compare the numbers below with the ones that are now in their contact pages):

11. Google Inc.
1600 Amphitheatre Parkway
Mountain View CA 94043

phone: (650) 623-4000
fax: (650) 618-1499

  1. Security Issues E-mails - You will find e-mails and send reports regarding security problems with any of Google’s services, systems, or networks and are Quite useful.
  2. Google dance 2002 and Google Dance 2003 - A funny Dance competition at Google organized by them.We find Lots of ever before seen photos of Googler’s and the Plex.
  3. Notification of Account Termination for My-Deja Email Accounts - I actually don’t know what exactly is this (I only have a basic idea).
  4. Google Jobs@Britney – According to me,it’s a test page of their spelling suggestion system. Anyway, I think I may report that page in the right spam report place, because it uses keyword stuff :D
  5. Google Lunar Jobs - Google is interviewing candidates for engineering positions at their lunar hosting and research center, opening late in the spring of 2007. Nice huh ?
  6. Some Lunar jobs test page - A test/saved page which (I think) got left on the server. Anyway, you can re-view the old Google interface.
  7. Add Google buttons to Netscape – An old page with info on how to put favourite bookmarks in Netscape’s browser (page is no longer with public).
  8. PDF Form It is to seek permission for the usage of Google’s brand features.
  9. Googlers in the Halloween Spirit - Some cool pictures with Googlers from the year 2000 Halloween Party.
  10. SEARCH AND DEPLOY - The race to build a better search engine - The New Yorker, May 29, 2000 © Michael Specter 2000. May not be reprinted without permission.
  11. Google’s Zeitgeist 2001 Timeline - A neat Zeitgeist 2001 press timeline with some nice coverage and info’s. Offcourse it’s not public anymore ;)
  12. Google’s 3 Billion mark - Google offers immediate access to 3 billion web documents (December 11, 2001)
  13. Google’s 6 Billion mark - Google offers immediate access to 6 billion web documents (February 17, 2004)
  14. Google’s Adsense launch – Google “The award-winning search engine”, today announced a new self-service option for Google AdSense,A program that enables website publishers to serve ads precisely & is targeted to the specific content of their individual web pages (June 18, 2003).
  15. ASK.com begins using Google’s PPC program - Ask Jeeves and Google sign $100 million three-year deal (July 18, 2002).
  16. Yahoo! and Google Join Forces - (Now that’s a FIRST) Yahoo! Everywhere and Google join forces offer award-winning search technology to wireless Internet users (April 10, 2001).
  17. Google Searches Related to America Under Attack - Google searches, stats and graphs from the 9/11/01 event (page not public anymore).
  18. Google US Puzzle Championship - Is your brain feeling under utilized ? Gives an enough mental challenge to your daily job?
  19. Fade PSAs - A suggestion gone extinct.
  20. Papers written by Googlers - A partial list of papers written by people now at Google, showing the range of background people in Google Engineering.
  21. Online Business presentation page - Google can help your business to make more money (yeah right)… Page not public anymore.
  22. 1, 2, 3, 4 – These are few PDF documents.
  23. Improving Google Adwords - The ideaology of the engineers that drive online advertising innovation.
  24. Holiday Certificate: Enjoy the gift of Google.
  25. Enable Cookies help page.
  26. Google and Dilbert Doodle created by cartoonist Scott Adams for Google’s Holiday Logos.
  27. About Dennis Hwang (Hwang Jung-moak) - The finest designer of almost all of Google doodles. He’s a 28 years old Korean artist.
  28. Google Grants returns the 404. I guess Google’s tired to give money for free, or someone made a bubu. Look at these Google Grants PDF documents from 2004 : Account Basics , Keywords , Ads , Extra Help .
  29. Why we sell advertising, not search results.
  30. Google Fan Logos - great collection of Google logos, made by fans all across the Globe and I don’t think,this page is public.
  31. Google’s code of conduct - Our informal corporate motto is “Don’t be evil”.
  32. Google’s financial data where we learn that they actually made a dedicated row for “Settlement of dispute with Yahoo” for the 2004 Google - Yahoo dispute. Funny thing is that the WSJ reports a figure of $328 million and Google reports a figure of $201 million (which represented about 6% of all of Google’s 2004 income).
  33. Google Press Blog -YES, very few knew about it,It has even got a feed, so you can be up to date. None of the regular Google Blogs link to it anyway.
  34. Google Milestones - A history of Google’s achievements.
  35. Trademark Complaint Procedures - If you have concerns about the use of your trademark in the advertiser’s ads or in a parked domain name.
  36. Some older pages on a Google Tour and Building a better query
  37. The 2004 version of Google Labs: Why should you work at Google versus the 2006 (current) one.
  38. Explanation - Google’s explanation for their disturbing search results while searching for “Jew” (2004).
  39. Google Store, Americans and Worldwide - Buy stuff branded with Google, like a Google beach towel or a White Google Polo Shirt for your wife. And yes, the Google stores are developed using Microsoft Technology (ASP).
  40. Google Gulp - They are pleased to announce Google Gulp (BETA)™ with Auto-Drink™ (LIMITED RELEASE), a line of “smart drinks” designed to maximize your surfing efficiency,by making you more intelligent, and less thirsty.
  41. 2000 Google Easter Animation - Catch the eggs in order to spell “Google” (if you complete the game twice, there’s a suprise). Very funny
  42. Some 100 Euro Adwords coupon for Google.de - Wrote in german.
  43. 10 Tips for Enterprise Search - A best practices tip sheet .
  44. 10 things about Google’s Philosophy.
  45. Google’s fight spyware information page - In the footer, they recommend some anti-spyware programs.
  46. Google Alert #1: June 26, 2000, Google Launches World’s Largest Search Engine (is that right ? ;) )
  47. 20 Year Usenet Timeline - “Google has fully integrated with past 20 years of Usenet archives into Google Groups and now offers access to more than 800 million messages dating back to 1981. This is by far the most complete collection of Usenet articles ever assembled and a fascinating first-hand historical account.”
  48. How to create a successful Google Grants campaign.
  49. Bouncing Heart Applet - See the 2000 and 2001 credits.
  50. Google Cheatsheet. FYI, did you knew that “~auto loan” will allow auto to match car, truck, etc ?. Here’s an extended Cheat Sheet from GoogleGuide and another PDF Cheat Sheet for print.
  51. Google Jobs Internship Opportunities - They’re looking for students pursuing degrees in computer science (or closely related areas), who love to problem-solve, code, and design.
  52. Google Jobs: Top 10 Reasons to Work at Google. I especially like #7 :

7. Good company everywhere you look. Googlers range from former neurosurgeons, CEOs, and U.S. puzzle champions to alligator wrestlers and former-Marines. No matter what their backgrounds Googlers make for interesting cube mates.
I mean, who the heck at Google is an alligator wrestler ?

  1. Video: An Inside Look at Google.
  2. Some funked up Google Logo, live on Google’s servers, from (insert unknown year and ocasion here):
  3. 2001 Google Search Guide PDFs - Front and back . From the content:

DIRECTORIES VS. SEARCH ENGINES
If you have a general idea of the subject in which you’re interested, but are not sure exactly what you’re looking for, a directory is a great place to start. Directories like Yahoo! use human editors to organize information in broad categories, such as finance, sports, or travel. Think of them as giant card catalogs.

  1. 10 Google fun facts:

Googlers are multifaceted. One operations manager, who keeps the Google network in good health is a former neurosurgeon. One software engineer is a former rocket scientist. And the company’s chef formerly prepared meals for members of The Grateful Dead and funkmeister George Clinton.

  1. Google Timelines from 2001 and from 2002.
  2. Google Zeitgeist Special Edition - Election 2004 - A bit of insight into people’s 2004 campaign interests.
  3. Hi resolution TIF images (zip archived) with Google Executives like Larry Page, Sergey Brin, Larry AND Sergey, Eric Schmidt, Cindy Mccaffrey, Craig Silverstein, David Drummund, George Reyes, Jonathan Rosenberg, Omid Kordestani and others. Here is the full list of zip archives:

http://www.google.com/press/guides/picasa2_overview_highres.zip
http://www.google.com/press/images/cindy_mccaffrey.zip
http://www.google.com/press/images/craig_silverstein.zip
http://www.google.com/press/images/david_drummund.zip
http://www.google.com/press/images/mini.zip
http://www.google.com/press/images/es_results.zip
http://www.google.com/press/images/george_reyes.zip
http://www.google.com/press/images/francais.zip
http://www.google.com/press/images/google_eps.zip
http://www.google.com/press/images/google_hi_res.zip
http://www.google.com/press/images/google_homepage.zip
http://www.google.com/press/images/google_omid.zip
http://www.google.com/press/images/google_search_appliance2.zip
http://www.google.com/press/images/google_search_results.zip
http://www.google.com/press/images/google_tabs_homepage.zip
http://www.google.com/press/images/jonathan_rosenberg.zip
http://www.google.com/press/images/larry_page.zip
http://www.google.com/press/images/page_brin.zip
http://www.google.com/press/images/omid_kordestani.zip
http://www.google.com/press/images/sergey_brin.zip
http://www.google.com/press/images/toolbar_hires.zip
http://www.google.com/press/images/toolbar_screenshot.zip
http://www.google.com/press/images/toolbar_screenshot_hires.zip
http://www.google.com/press/images/shona_brown.zip
http://www.google.com/press/images/eric_schmidt.zip
http://www.google.com/press/images/alan_eustace.zip

  1. Zeitgeist Archive from 2001 till date, including searches done for CNN or World Trade Center, Pentagon, Nostradamus or Bin La Den on Sep. 11. Other Search Statistics Related to September 11, 2001.
  2. Corporate Information: Google Offices around the world featuring phones and addresses for each office, including driving directions - Page not public anymore.
  3. Google Content-Targeted Advertising - The ancestor of Adsense. From the page:

How do you get started?

It’s easy. If you’re a web publisher who sells advertising inventory, and your site receives more than 20 million page views a month, you could be a great fit for Google’s content-targeted ads.

20 Million ? Really ? :)

  1. Premium Service for AdSense PDF- A 2003 PDF presentation of the Google Adsense Premium service. See the HTML version.
  2. A 2004 Adsense Tax PDF. Look, we have a fax and a telephone number in the header :)
  3. Google AdSense Charity Ad Formats proposals and feedback requests. Amongst the questions asked by Google in this particular feedback page:

1. What is your overall feedback about the proposed changes?
2. The Public Service Announcements are no longer Google branded. What is your feedback about this specific change?

  1. The results were on this page. They were named as PSA too (from charity ads).
  2. Google AdSense Charity ad formats example (when there were only 6 formats available). Funny thing (if you look in the source code) about these “charity” ads, It is a PUB ID and the fact that all those ID’s are live

So SlashDot used Adsense in the past ? Or was it a charity website ? :)

  1. A certain Frankfurt Print Tour by Thomson Course Technology.
  2. A cool 2004 Adsense Tour.
  3. Google Gmail tour from 2005 - It’s a movie based. Great tour BTW.
  4. 2005 Gmail Program Policies Redline version (???) - updated June 28, 2004.
  5. A page with bloggers that wrote (reviews) about Gmail.
  6. Gmail’s Third Party Software Error page.
  7. Bulk e-mail sending tips and information from Gmail.
  8. 3 Gmail XMLs : spam-0, trash-0 and trash-1. Plz don’t ask me what they are.
  9. A Google Healthcare Powerpoint presentation (zip) by Kevin Gough (Product Marketing Manager - Google Enterprise).
  10. Google Mini Sweepstakes Rules.
  11. A 2005 Google Search appliance flash presentation.
  12. Google Mini Administration Interface presentation. I always wondered how the Admin interface for a Mini looks like :)
-------------------------------------------------------------------------------------------------