Flatten the tree into an array list, then generate a uniform random number from 0 to 1, and choose the corresponding index in the flattened array list.

Helpful Answer?

Yes | No

Inappropriate?

0 of 0 people found this helpful

Mar 8, 2012

by Anonymous:

Just pick a number from 1 to N and do an inorder traversal.

Helpful Answer?

Yes | No

Inappropriate?

To comment on this question, Sign In with Facebook or Sign Up

You might also be interested in: Interview Questions, Intern Interview Questions, Google Interview

Employees' Choice Winner: 2009, 2010, 2011, 2012

Google Overview (GOOG)

Edit

Website www.google.com

HQ Mountain View, CA

Industry

Internet Search & Navigation Services

Size

32,400+ Employees, $23B+ Revenue

Competitors

Microsoft, Apple, Facebook

Interviews by Company

Salaries by Company

Tags are like keywords that help categorize interview questions that have something in common.

About Us | Feedback | Help

Glassdoor ® is a registered trademark of Glassdoor, Inc.

Overview

Salaries

Reviews

Interviews

Photos

Jobs

Connections

1,223 Interview Reviews |

Interview Question for Intern at Google:

Given a generic tree, how would you pick a node at random with uniform probability?

Answers & Comments (2)

Flag this {0} as inappropriate

Thank you!

Oops!