Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Google Interview Prep > Total - Information taken from Wikipedia, Google Website, "Hacking a Google Interview" by Bill Jacobs and Curtis Fonger, Topcoder.com Data Science Tutorials, Design Patterns Explained Simply > Flashcards

Total - Information taken from Wikipedia, Google Website, "Hacking a Google Interview" by Bill Jacobs and Curtis Fonger, Topcoder.com Data Science Tutorials, Design Patterns Explained Simply Flashcards

1
Q

Quicksort (Best, Average, Worst, Memory, Stable)

A

Best = n log(n) but there exists a variation that results in n
Average = n log(n)
Worst = n^2
Memory = log(n) on average with a worst case of n
Stable = Typical in place sort is not stable but stable versions exist
Note: Quicksort is usually done in-place with O(log n) stack space.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Merge sort (Best, Average, Worst, Memory, Stable)

A 
Best = n log(n)
Average = n log(n)
Worst = n log(n)
Memory = n but there is a hybrid block merge sort with a requirement of only O(1)
Stable = Yes
Note: Highly parallelizable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Heapsort (Best, Average, Worst, Memory, Stable)

A 
Best = n log(n)
Average = n log(n)
Worst = n log(n)
Memory = 1
Stable = No
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Insertion sort (Best, Average, Worst, Memory, Stable)

A 
Best = n
Average = n^2
Worst = n^2
Memory = 1
Stable = Yes
Note: Technically O(n+d) in the worst case over sequences that have d inversions.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Introsort (Best, Average, Worst, Memory, Stable)

A 
Best = n log(n)
Average = n log(n)
Worst = n log(n)
Memory = log(n)
Stable = No
Note: Used in several STL implementations.  Works by using Quicksort to a specific depth (e.g. 2 log2(n) for GNU Standard C++) and then applies Heapsort at that level.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Selection sort (Best, Average, Worst, Memory, Stable)

A 
Best = n^2
Average = n^2
Worst = n^2
Memory = 1
Stable = No
Note: Can be stable with O(n) extra space.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Timsort (Best, Average, Worst, Memory, Stable)

A 
Best = n
Average = n log(n)
Worst = n log(n)
Memory = n
Stable = Yes
Note: Makes n comparisons when the data is already sorted or reverse sorted.  BASIC description is that it works by finding "runs" in either direction (though must be "strictly" descending) and flips them appropriately and then merges them.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are (at least 5 of) the “10 things we know to be true” at Google?

A
  1. Focus on the user and all else will follow.
  2. It’s best to do one thing really, really well.
  3. Fast is better than slow.
  4. Democracy on the web works.
  5. You don’t need to be at your desk to need an answer.
  6. You can make money without doing evil.
  7. There’s always more information out there.
  8. The need for information crosses all borders.
  9. You can be serious without a suit.
  10. Great just isn’t good enough.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does Google mean when they say “Focus on the user and all else will follow.”?

A

Since the beginning, we’ve focused on providing the best user experience possible. Whether we’re designing a new Internet browser or a new tweak to the look of the homepage, we take great care to ensure that they will ultimately serve you, rather than our own internal goal or bottom line. Our homepage interface is clear and simple, and pages load instantly. Placement in search results is never sold to anyone, and advertising is not only clearly marked as such, it offers relevant content and is not distracting. And when we build new tools and applications, we believe they should work so well you don’t have to consider how they might have been designed differently.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does Google mean when they say “It’s best to do one thing really, really well.”?

A

We do search. With one of the world’s largest research groups focused exclusively on solving search problems, we know what we do well, and how we could do it better. Through continued iteration on difficult problems, we’ve been able to solve complex issues and provide continuous improvements to a service that already makes finding information a fast and seamless experience for millions of people. Our dedication to improving search helps us apply what we’ve learned to new products, like Gmail and Google Maps. Our hope is to bring the power of search to previously unexplored areas, and to help people access and use even more of the ever-expanding information in their lives.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does Google mean when they say “Fast is better than slow.”?

A

We know your time is valuable, so when you’re seeking an answer on the web you want it right away–and we aim to please. We may be the only people in the world who can say our goal is to have people leave our website as quickly as possible. By shaving excess bits and bytes from our pages and increasing the efficiency of our serving environment, we’ve broken our own speed records many times over, so that the average response time on a search result is a fraction of a second. We keep speed in mind with each new product we release, whether it’s a mobile application or Google Chrome, a browser designed to be fast enough for the modern web. And we continue to work on making it all go even faster.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does Google mean when they say “Democracy on the web works.”?

A

Google search works because it relies on the millions of individuals posting links on websites to help determine which other sites offer content of value. We assess the importance of every web page using more than 200 signals and a variety of techniques, including our patented PageRank™ algorithm, which analyzes which sites have been “voted” to be the best sources of information by other pages across the web. As the web gets bigger, this approach actually improves, as each new site is another point of information and another vote to be counted. In the same vein, we are active in open source software development, where innovation takes place through the collective effort of many programmers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does Google mean when they say “You don’t need to be at your desk to need an answer.”?

A

The world is increasingly mobile: people want access to information wherever they are, whenever they need it. We’re pioneering new technologies and offering new solutions for mobile services that help people all over the globe to do any number of tasks on their phone, from checking email and calendar events to watching videos, not to mention the several different ways to access Google search on a phone. In addition, we’re hoping to fuel greater innovation for mobile users everywhere with Android, a free, open source mobile platform. Android brings the openness that shaped the Internet to the mobile world. Not only does Android benefit consumers, who have more choice and innovative new mobile experiences, but it opens up revenue opportunities for carriers, manufacturers and developers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does Google mean when they say “You can make money without doing evil.”?

A

Google is a business. The revenue we generate is derived from offering search technology to companies and from the sale of advertising displayed on our site and on other sites across the web. Hundreds of thousands of advertisers worldwide use AdWords to promote their products; hundreds of thousands of publishers take advantage of our AdSense program to deliver ads relevant to their site content. To ensure that we’re ultimately serving all our users (whether they are advertisers or not), we have a set of guiding principles for our advertising programs and practices:

1) We don’t allow ads to be displayed on our results pages unless they are relevant where they are shown. And we firmly believe that ads can provide useful information if, and only if, they are relevant to what you wish to find–so it’s possible that certain searches won’t lead to any ads at all.
2) We believe that advertising can be effective without being flashy. We don’t accept pop–up advertising, which interferes with your ability to see the content you’ve requested. We’ve found that text ads that are relevant to the person reading them draw much higher clickthrough rates than ads appearing randomly. Any advertiser, whether small or large, can take advantage of this highly targeted medium.
3) Advertising on Google is always clearly identified as a “Sponsored Link,” so it does not compromise the integrity of our search results. We never manipulate rankings to put our partners higher in our search results and no one can buy better PageRank. Our users trust our objectivity and no short-term gain could ever justify breaching that trust.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does Google mean when they say “There’s always more information out there.”?

A

Once we’d indexed more of the HTML pages on the Internet than any other search service, our engineers turned their attention to information that was not as readily accessible. Sometimes it was just a matter of integrating new databases into search, such as adding a phone number and address lookup and a business directory. Other efforts required a bit more creativity, like adding the ability to search news archives, patents, academic journals, billions of images and millions of books. And our researchers continue looking into ways to bring all the world’s information to people seeking answers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does Google mean when they say “The need for information crosses all borders.”?

A

Our company was founded in California, but our mission is to facilitate access to information for the entire world, and in every language. To that end, we have offices in more than 60 countries, maintain more than 180 Internet domains, and serve more than half of our results to people living outside the United States. We offer Google’s search interface in more than 130 languages, offer people the ability to restrict results to content written in their own language, and aim to provide the rest of our applications and products in as many languages and accessible formats as possible. Using our translation tools, people can discover content written on the other side of the world in languages they don’t speak. With these tools and the help of volunteer translators, we have been able to greatly improve both the variety and quality of services we can offer in even the most far–flung corners of the globe.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does Google mean when they say “You can be serious without a suit.”?

A

Our founders built Google around the idea that work should be challenging, and the challenge should be fun. We believe that great, creative things are more likely to happen with the right company culture–and that doesn’t just mean lava lamps and rubber balls. There is an emphasis on team achievements and pride in individual accomplishments that contribute to our overall success. We put great stock in our employees–energetic, passionate people from diverse backgrounds with creative approaches to work, play and life. Our atmosphere may be casual, but as new ideas emerge in a café line, at a team meeting or at the gym, they are traded, tested and put into practice with dizzying speed–and they may be the launch pad for a new project destined for worldwide use.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What does Google mean when they say “Great just isn’t good enough.”?

A

We see being great at something as a starting point, not an endpoint. We set ourselves goals we know we can’t reach yet, because we know that by stretching to meet them we can get further than we expected. Through innovation and iteration, we aim to take things that work well and improve upon them in unexpected ways. For example, when one of our engineers saw that search worked well for properly spelled words, he wondered about how it handled typos. That led him to create an intuitive and more helpful spell checker.

Even if you don’t know exactly what you’re looking for, finding an answer on the web is our problem, not yours. We try to anticipate needs not yet articulated by our global audience, and meet them with products and services that set new standards. When we launched Gmail, it had more storage space than any email service available. In retrospect offering that seems obvious–but that’s because now we have new standards for email storage. Those are the kinds of changes we seek to make, and we’re always looking for new places where we can make a difference. Ultimately, our constant dissatisfaction with the way things are becomes the driving force behind everything we do.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Products under Web

A

Web Search
Google Chrome
Toolbar
Bookmarks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Product - Web Search

A

Search billions of web pages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Product - Google Chrome

A

A browser built for speed, simplicity and security

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Product - Toolbar

A

Add a search box to your browser (Note that this is for browsers that are not Chrome)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Product - Bookmarks

A

Access your bookmarks and starred items

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Products under Business

A 
AdWords
G Suite
Google Cloud Platform
Google My Business
AdSense
AdMob
Analytics
Google Domains
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Product - AdWords

A

Attract more customers and only pay for results (This is to put your advertisements on other people’s websites.)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Product - G Suite

A

Get email, docs, storage and more, customized for your business

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Product - Google Cloud Platform

A

Build and host applications and websites, store and analyze data on Google’s scalable infrastructure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Product - Google My Business

A

Make sure your business looks great on Google Search, Maps and Google+ for free

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Product - AdSense

A

Create online revenue today (This is to put advertisements on your website.)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Product - AdMob

A

Make money from your apps

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Product - Analytics

A

Know your audience and analyze traffic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Product - Google Domains

A

Find a domain a build a website for your business

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Products under Media

A 
YouTube
Google Play
Books
Image Search
News
Video Search
Google Photos
Google Cardboard
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Product - YouTube

A

Watch, upload and share videos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Product - Google Play

A

Your music, movies, books, and Android apps, available anywhere

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Product - Books

A

Search the full text of books

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Product - Image Search

A

Search for images on the web

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Product - News

A

Search thousands of news stories

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Product - Video Search

A

Search for videos on the web

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Product - Google Photos

A

All your photos on all you devices, organized and easy to share

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Product - Google Cardboard

A

Experience virtual reality in a simple, fun, and affordable way

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Products under Geo

A

Maps

Earth

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Product - Maps

A

View maps and directions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

Product - Earth

A

Explore the world from your computer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Products under Specialized Search

A 
Custom Search
Google Shopping
Finance
Scholar
Trends
Google Flights
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Product - Custom Search

A

Create a customized search experience for your community

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Product - Google Shopping

A

Search for stuff to buy

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Product - Finance

A

Business info, news and interactive charts

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Product - Scholar

A

Search scholarly papers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Product - Trends

A

Explore past and present search trends

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

Product - Google Flights

A

Find flights, track prices and book your next destination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Products under Home & Office

A 
Gmail
Drive
Docs
Sheets
Slides
Forms
Drawings
Sites
Calendar
Translate
Voice
Google Wallet
Google Cloud Print
Google Keep
Google Store
Hangouts
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Product - Gmail

A

Fast, searchable email with less spam

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Product - Drive

A

Create, share and keep all your stuff in one place

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

Product - Docs

A

Open, edit, and create documents

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

Product - Sheets

A

Open, edit and create spreadsheets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

Product - Slides

A

Open, edit and create presentations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

Product - Forms

A

Build free surveys

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

Product - Drawings

A

Create diagrams and flow charts

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

Product - Sites

A

Create websites and secure group wikis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

Product - Calendar

A

Organize your schedule and share events with friends

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Product - Translate

A

Instantly translate text, web pages, and files between over 50 languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

Product - Voice

A

One number for all your phones, online voicemail and cheap calling

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

Product - Google Wallet

A

Make your phone your wallet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Product - Google Cloud Print

A

Print anywhere, from any device

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

Product - Google Keep

A

Save what’s on your mind

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

Product - Google Store

A

Explore and shop the latest products made with Google

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

Product - Hangouts

A

Conversations that come to life. Anytime, anywhere, for free

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

Products under Social

A

Google+
Blogger
Groups
Spaces

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

Product - Google+

A

Discover amazing things, created by passionate people

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

Product - Blogger

A

Publish your passions, your way

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

Product - Groups

A

Create mailing lists and discussion groups

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

Product - Spaces

A

Find, discuss and do things with friends

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

Unsorted array (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O(1)
Delete = O(1)
Balance = N/A
Get at index = O(1)
Search = O(n)
Find minimum = O(n)
Find maximum = O(n)
Space usage = O(n)
Note: For Insert and Delete, the expectation is that values don't have to be moved for an unsorted array, and values don't have to be placed in a specific spot and everything else moved.  This may well be untrue in a given implementation.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

Sorted array (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O(n)
Delete = O(n)
Balance = N/A
Get at index = O(1)
Search = O( log(n) )
Find minimum = O(1)
Find maximum = O(1)
Space usage = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

Unsorted linked list (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O(1)
Delete = O(1)
Balance = N/A
Get at index = O(n)
Search = O( n )
Find minimum = O(n)
Find maximum = O(n)
Space usage = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

Sorted linked list (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O(n)
Delete = O(1)
Balance = N/A
Get at index = O(n)
Search = O( n )
Find minimum = O(1)
Find maximum = O(1)
Space usage = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q

Self-balancing binary tree (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O( log(n) )
Delete = O( log(n) )
Balance = O( log(n) )
Get at index = N/A
Search = O( log(n) )
Find minimum = O( log(n) )
Find maximum = O( log(n) )
Space usage = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q

Heap (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O( log(n) )
Delete = O( log(n) )
Balance = O( log(n) )
Get at index = N/A
Search = O( n )
Find minimum = O( 1 ) for min-heap, O(n) for max-heap
Find maximum = O( 1 ) for max-heap, O(n) for min-heap
Space usage = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q

Hash table (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O( 1 )
Delete = O( 1 )
Balance = O( n )
Get at index = N/A
Search = O( 1 )
Find minimum = O( n )
Find maximum = O( n ) 
Space usage = O( n )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q

Trie (Insert, Delete, Balance, Get at index, Search, Find minimum, Find maximum, Space usage)

A 
Insert = O( k )
Delete = O( k )
Balance = N/A
Get at index = O(k)
Search = O( k )
Find minimum = O( k )
Find maximum = O( k ) 
Space usage = O( k * n )
Note: k = average LENGTH of key
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q

List of (normal) Primitive Types

A 
Boolean
Character
Floating-point
Double - Wider floating-point size
Integer
Enumerated type - Small set of uniquely-named values
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q

List of (normal) Composite Types (or Non-primitive Types)

A

Array
Struct (also called a Record or Tuple)
Union - Crazy thing that can be two different types of variable and called any instance to serve as either one.
Tagged Union - Same as union except all accesses are verified to be “safe”. Reason to use instead of a struct is to save space, and possibly bit level conversions. (Insane)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q

List of (normal) Abstract Data Types

A 
Container
List
Associative array
Multimap
Set
Multiset
Stack
Queue
Double-ended queue (Deque)
Priority queue
Tree
Graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q

Data Type - Boolean

A

Primitive Type. Has two values (true/false). Normally used as the result of conditional statements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q

Data type - Character

A

Primitive Type. Unit of Information roughly corresponds to a grapheme (e.g. letter of an alphabet). Often encoded as a value length such as a byte for ASCII or variable length for UTF-8 (Unicode).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q

Data type - Floating point

A

Primitive Type. Representation of real numbers, normally 4 bytes and mapped using IEEE 754, which has 1 bit to signify greater than or less than zero, 8 bits to indicate exponent (with -127 offset) and 23 bits to communicate the mantissa.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q

Data type - Double

A

Primitive Type. 8 byte floating point. Short for double-precision floating-point format. Also specified in IEEE 754.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q

Data type - Integer

A

Primitive Type. Representative of an integer. Naming conventions are all over given the age of the data type, and therefore “long” can indicate 32 bits, and combinations with “word” doesn’t necessarily differentiate. Best indicators are “int” which seems specific to 32 bits, and int64 which seems specific to 64 bits.

90
Q

Data type - Enumerated type

A

Primitive Type. Data type consisting of a set of named values called elements, members, enumeral or enumerators of the type. These variables can have any number of specific names and the enumerator of that type can be assigned any of those names for storage and application at a later time.

91
Q

Data type - Array

A

Composite (Non-primitive) Type. Describes a collection of elements (values or variables), each selected by one or more indices (identifying keys) that can be computed at run time by the program. By analogy with the mathematical concepts of vector and matrix, array types with one and two indices are often called vector type and matrix type, respectively.

92
Q

Data type - Struct

A

Composite (Non-primitive) Type. (Also known as a record). This data type is a collection of fields, possibly of different data types, typically in fixed number and sequence.

93
Q

Data type - Tuple

A

Composite (Non-primitive) Type. A tuple is a finite ordered list of elements. Treated differently based on programming language, from a product of a function (i.e. able to return multiple values from a single function), to a set, similar to how it would be used in mathematics.

94
Q

Data type - Union

A

Composite (Non-primitive) Type. A value that can have several representations or formats. Can be used to minimize memory usage (out of date and very much frowned upon) or for converting between data types (assuming you want to read the map of a variable in another data type).

95
Q

Data type - Tagged Union

A

Composite (Non-primitive) Type. Similar to union, except provides a lock that only allows a certain data type within the union to be interacted with at a given time until a tag field within the variable is changed. This can be valuable in functional languages or scripting languages where the variable type may not be defined until during runtime.

96
Q

Data type - Container

A

Abstract Data Type. A container is a class, a data structure, or an abstract data type (ADT) whose instances are collections of other objects. Underlying (inherited) implementations of various container types may vary in size and complexity, and provide flexibility in choosing the right implementation for any given scenario.

97
Q

Data type - List

A

Abstract Data Type. A list or sequence is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream.

98
Q

Data type - Associative array

A

Abstract Data Type. An associative array (a.k.a. map, symbol table, or dictionary) is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during ‘search’, ‘delete’, and ‘insert’ operations. The two major solutions to the dictionary problem are a hash table or a search tree. In some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures.

Many programming languages include associative arrays as primitive data types, and they are available in software libraries for many others. Content-addressable memory is a form of direct hardware-level support for associative arrays.

99
Q

Data type - Multimap

A

Abstract Data Type. A multimap (sometimes also multihash) is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key.

Example: The index of a book may report any number of references for a given index term, and thus may be coded as a multimap from index terms to any number of reference locations or pages.

100
Q

Data type - Set

A

Abstract Data Type. A set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

101
Q

Data type - Multiset

A

Abstract Data Type. A generalization of the notion of a set is that of a multiset or bag, which is similar to a set but allows repeated (“equal”) values (duplicates). This is used in two distinct senses: either equal values are considered identical, and are simply counted, or equal values are considered equivalent, and are stored as distinct items. For example, given a list of people (by name) and ages (in years), one could construct a multiset of ages, which simply counts the number of people of a given age. Alternatively, one can construct a multiset of people, where two people are considered equivalent if their ages are the same (but may be different people and have different names), in which case each pair (name, age) must be stored, and selecting on a given age gives all the people of a given age.

102
Q

Data type - Stack

A

Abstract Data Type. A stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out). Additionally, a peek operation may give access to the top without modifying the stack.

The name “stack” for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.

103
Q

Data type - Queue

A

Abstract Data Type. A queue (/ˈkjuː/ kyew) is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it.

104
Q

Data type - Double-ended queue

A

Abstract Data Type. A double-ended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation.

105
Q

Data type - Priority queue

A

Abstract Data Type. A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like “a list” or “a map”; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

106
Q

Data type - Tree

A

Abstract Data Type. A tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

107
Q

Data type - Trie

A

A trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone.

108
Q

Data type - B-tree

A

A B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory. It is commonly used in databases and filesystems.

109
Q

Data type - Graph

A

Abstract Data Type. A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics.

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

110
Q

Name some things to “Do” during a Google Interview when asked a question:

A

Ask for clarification on a problem if you didn’t understand something or if there is any ambiguity

Let the interviewer know what you are thinking

Suggest multiple approaches to the problem

Bounce ideas off the interviewer (such as ideas for data structures or algorithms)

If you get stuck, don’t be afraid to let them know and politely ask for a hint

111
Q

Name some things NOT to Do during a Google Interview when asked a question:

A

Never give up! This says nothing good about your problem solving skills.

Don’t just sit in silence while thinking. The interviewer has limited time to find out as much as possible about you, and not talking with them tells them nothing, except that you can sit there silently.

If you already know the answer, don’t just blurt it out! They will suspect that you already knew the answer and didn’t tell them you’ve seen the question before. At least pretend to be thinking though the problem before you give the answer!

112
Q

Given a sorted array of integers, how can you find the location of a particular integer x?

A

Good answer: Use binary search. Compare the number in the middle of the array with x. If it is equal, we are done. If the number is greater, we know to look in the second half of the array. If it is smaller, we know to look in the first half. We can repeat the search on the appropriate half of the array by comparing the middle element of that array with x, once again narrowing our search by a factor of 2. We repeat this process until we find x. This algorithm takes O(log n) time.

Not-so-good answer: Go through each number in order and compare it to x. This algorithm takes O(n) time.

113
Q

Define Threads and Processes

A

A computer will often appear to be doing many things simultaneously, such as checking for new e-mail messages, saving a Word document, and loading a website. Each program is a separate “process”. Each process has one or more “threads.” If a process has several threads, they appear to run simultaneously. For example, an e-mail client may have one thread that checks for new e-mail messages and one thread for the GUI so that it can show a button being pressed. In fact, only one thread is being run at any given time. The processor switches between threads so quickly that they appear to be running simultaneously.

Multiple threads in a single process have access to the same memory. By contrast, multiple processes have separate regions of memory and can only communicate by special mechanisms. The processor loads and saves a separate set of registers for each thread.

Remember, each process has one or more threads, and the processor switches between threads.

114
Q

Define Mutexes and Semaphores

A

A mutex is like a lock. Mutexes are used in parallel programming to ensure that only one thread can access a shared resource at a time. For example, say one thread is modifying an array. When it has gotten halfway through the array, the processor switches to another thread. If we were not using mutexes, the thread might try to modify the array as well, which is probably not what we want.

To prevent this, we could use a mutex. Conceptually, a mutex is an integer that starts at 1. Whenever a thread needs to alter the array, it “locks” the mutex. This causes the thread to wait until the number is positive and then decreases it by one. When the thread is done modifying the array, it “unlocks” the mutex, causing the number to increase by 1. If we are sure to lock the mutex before modifying the array and to unlock it when we are done, then we know that no two threads will modify the array at the same time.

Semaphores are more general than mutexes. They differ only in that a semaphore’s integer may start at a number greater than 1. The number at which a semaphore starts is the number of threads that may access the resource at once. Semaphores support “wait” and “signal” operations, which are analogous to the “lock” and “unlock” operations of mutexes.

115
Q

What is a synchronized method in Java?

A

Each object in Java has its own mutex. Whenever a synchronized method is called, the mutex is locked. When the method is finished, the mutex is unlocked. This ensures that only one synchronized method is called at a time on a given object.

116
Q

What is Deadlock?

A

Deadlock is a problem that sometimes arises in parallel programming. It is typified by the following, which is supposedly a law that came before the Kansas legislature: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.” Strange as this sounds, a similar situation can occur when using mutexes. Say we have two threads running the following code:

Thread 1:
acquire(lock1);
acquire(lock2);

Thread 2:
acquire(lock2);
acquire(lock1);

Suppose that thread 1 is executed to just after the first statement. Then, the processor switches to thread 2 and executes both statements. Then, the processor switches back to thread 1 and executes the second statement. In this situation, thread 1 will be waiting for thread 2 to release lock1, and thread 2 will be waiting for thread 1 to release lock2. Both threads will be stuck indefinitely. This is called deadlock.

117
Q

How can we ensure that deadlock does not occur?

A

There are many possible answers to this problem, but the answer the interviewer will be looking for is this: we can prevent deadlock if we assign an order to our locks and require that locks always be acquired in order. For example, if a thread needs to acquire locks 1, 5, and 2, it must acquire lock 1, followed by lock 2, followed by lock 5. That way we prevent one thread trying to acquire lock 1 then lock 2, and another thread trying to acquire lock 2 then lock 1, which could cause deadlock. (Note that this approach is not used very often in practice.)

118
Q

What is polymorphism?

A

Polymorphism is the ability of one method to have different behavior depending on the type of object it is being called on or the type of object being passed as a parameter.

119
Q

What is a virtual function/method? (C++)

A

A method’s being “virtual” simply describes its behavior when working with superclasses and subclasses. Assume class B is a subclass of class A. Also assume both classes A and B have a method “bar()”. Let’s say we have the following code in C++:

A *foo = new B();
foo->bar();

If the method “bar()” is declared to be virtual, then when we call foo->bar(), the method found in class B will be run. This is how Java always handles methods and it’s usually what we want to happen. However, if the method bar() is not declared to be virtual, then this code will run the method found in class A when we call foo->bar().

120
Q

Write a function to convert a string into an integer.

A

Good answer: Go through the string from beginning to end. If the first character is a negative sign, remember this fact. Keep a running total, which starts at 0. Each time you reach a new digit, multiply the total by 10 and add the new digit. When you reach the end, return the current total, or, if there was a negative sign, the inverse of the number.

Okay answer: Another approach is to go through the string from end to beginning, again keeping a running total. Also, remember a number x representing which digit you are currently on; x is initially 1. For each character, add the current digit times x to the running total, and multiply x by 10. When you reach the beginning, return the current total, or, if there was a negative sign, the inverse of the number.

Note: The interviewer is likely to ask you about the limitations of your approach. You should mention that it only works if the string consists of an optional negative sign followed by digits. Also, mention that if the number is too big, the result will be incorrect due to overflow.

121
Q

Write a function to reverse the order of words in a string in place.

A

Reverse the string by swapping the first character with the last character, the second character with the second-to-last character, and so on. Then, go through the string looking for spaces, so that you find where each of the words is. Reverse each of the words you encounter by again swapping the first character with the last character, the second character with the second-to-last character, and so on.

122
Q

General algorithm for Merge Sort

A

Merge sort is a recursive way to sort an array. First, you divide the array in half and recursively sort each half of the array. Then, you combine the two halves into a sorted array. So a merge sort function would look something like this:

int[] mergeSort(int[] array) {
	if (array.length <= 1)
		return array;
	int middle = array.length / 2;
	int firstHalf = mergeSort(array[0..middle - 1]);
	int secondHalf = mergeSort(
			array[middle..array.length - 1]);
	return merge(firstHalf, secondHalf);
}

The algorithm relies on the fact that one can quickly combine two sorted arrays into a single sorted array. One can do so by keeping two pointers into the two sorted arrays. One repeatedly adds the smaller of the two numbers pointed to to the new array and advances the pointer.

123
Q

General algorithm for Quicksort

A

To sort an array using quicksort, one first selects a random element of the array to be the “pivot”. One then divides the array into two groups: a group of elements that are less than the pivot and a group of elements that are greater than the pivot. After this, there will be an array consisting of elements less than the pivot, followed by the pivot, followed by elements greater than the pivot. Then, one recursively sorts the portion of the array before the pivot and the portion of the array after the pivot. A quicksort function would look like this:

void quicksort(int[] array, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
// Base case (array segment has 1 or 0 elements
} else {
int pivotIndex = partition(array,
startIndex,
endIndex);
quicksort(array, startIndex, pivotIndex - 1);
quicksort(array, pivotIndex + 1, endIndex);
}
}

Quicksort is typically very fast in practice, but remember that it has O(n^2) worst-case running time, so be sure to mention another sorting algorithm, such as merge sort, if you need guaranteed O(n log n) running time.

124
Q

Describe an algorithm to identify the kth smallest element in an array of n elements.

A

Select a random pivot and partition the array as you would in the quicksort algorithm. Then, based on the index of the pivot element, you know which half of the array the desired element lies in. For example, say k = 15 and n = 30, and after you select your pivot and partition the array, the first half has 10 elements (the half before the pivot). You know that the desired element is the 4th smallest element in the larger half. To identify the element, you partition the second half of the array and continue recursively. The reason that this is not O(n log n) is that the recursive partition call is only on one half of the array, so the expected running time is n + (n/2) + (n/4) + (n/8) + … = O(n).

Note that finding the median of an array is a special case of this where k = n / 2. This is a very important point, as an interviewer will often ask you to find a way to get the median of an array of numbers.

125
Q

Nearest Neighbor. (For the purpose of the described solution, the problems is described as follows.)

Say you have an array containing information regarding n people. Each person is described using a string (their name) and a number (their position along a number line). Each person has three friends, which are the three people whose number is nearest their own. Describe an algorithm to identify each person’s three friends.

A

Good answer: Sort the array in ascending order of the people’s number. For each person, check the three people immediately before and after them. Their three friends will be among these six people. This algorithm takes O(n log n) time, since sorting the people takes that much time.

126
Q

How can one determine whether a singly linked list has a cycle?

A

Good answer: Keep track of two pointers in the linked list, and start them at the beginning of the linked list. At each iteration of the algorithm, advance the first pointer by one node and the second pointer by two nodes. If the two pointers are ever the same (other than at the beginning of the algorithm), then there is a cycle. If a pointer ever reaches the end of the linked list before the pointers are the same, then there is no cycle. Actually, the pointers need not move one and two nodes at a time; it is only necessary that the pointers move at different rates. This takes O(n) time. This is a tricky answer that interviewers really like for some reason.

Okay answer: For every node you encounter while going through the list one by one, put a pointer to that node into a O(1)‐lookup time data structure, such as a hash set. Then, when you encounter a new node, see if a pointer to that node already exists in your hash set. This should take O(n) time, but also takes O(n) space.

Okay answer: Go through the elements of the list. “Mark” each node that you reach. If you reach a marked node before reaching the end, the list has a cycle; otherwise, it does not. This also takes O(n) time.

Note that this question is technically ill‐posed. An ordinary linked list will have no cycles. What they actually mean is for you to determine whether you can reach a cycle from a node in a graph consisting of nodes that have at most one outgoing edge.

127
Q

Anagram Problem: Given an English word in the form of a string, how can you quickly find all valid anagrams for that string (all valid rearrangements of the letters that form valid English words)? You are allowed to pre-compute whatever you want to and store whatever you optionally pre-compute on disk.

A

Answer: We want to use a hash table! If your interviewer really hates hash tables (which they sometimes do for some reason), you can use a tree instead. But let’s assume you can use a hash table. Then for the pre-computing step, go through each word in the dictionary, sort the letters of the word in alphabetical order (so “hacking” would become “acghikn”) and add the sorted letters as a key in the table and the original word as one of the values in a list of values for that key. For example, the entry for “opst” would be the list [“opts”, “post”, “stop”, “pots”, “tops”, “spot”]. Then, whenever you get a string, you simply sort the letters of the string and look up the value in the hash table. The running time is O(n log n) for sorting the string (which is relatively small) and approximately O(1) for the lookup in the hash table.

There are several other possible answers to this question, but we feel that the answer above is considered an optimal solution.

128
Q

Without using a calculator, how many zeros are at the end of “100!”? (that’s 1009998…321)

A

Answer: What you don’t want to do is start multiplying it all out! The trick is remembering that the number of zeros at the end of a number is equal to the number of times “10” (or “25”) appears when you factor the number. Therefore think about the prime factorization of 100! and how many 2s and 5s there are. There are a bunch more 2s than 5s, so the number of 5s is also the number of 10s in the factorization. There is one 5 for every factor of 5 in our factorial multiplication (12…5…10…15*…) and an extra 5 for 25, 50, 75, and 100. Therefore we have 20+4 = 24 zeros at the end of 100!.

129
Q

Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely?

A

Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time.

Note that there are several possible solutions to this problem, as well as several good-looking answers that are incorrect. For example, a slight modification to the above algorithm whereby one switches each element with any element in the array does not give each reordering with equally probability. The answer given here is, in our opinion, the best solution. If you want to see other solutions, check the “Shuffling” page on Wikipedia.

130
Q

How to check if an element is present in a binary search tree?

A

To check whether an element appears in a binary search tree, one need only follow the appropriate links from parent to child.

131
Q

How to add an element to a binary search tree?

A

To add an element to a binary search tree, we begin as if we were searching for the element, following the appropriate links from parent to child. When the desired child is null, we add the element as a new child node.

132
Q

How to remove an element to a binary search tree?

A

To remove an element from a binary search tree, we first find the node containing that element. If the node has zero children, we simply remove it. If it has one child, we replace the node with its child. If it has two children, we identify the next-smaller or next-larger element in the tree (it doesn’t matter which), using an algorithm which we do not describe here for the sake of brevity. We set the element stored in the node to this value. Then, we splice the node that contained the value from the tree. This will be relatively easy, since the node will have at most one child.

133
Q

How can you use a binary tree as a hash table?

A

A small modification to a binary search tree allows it to be used to associate keys with values, as in a hash table. Instead of storing a single value in each node, one could store a key-value pair in each node. The tree would be ordered based on the nodes’ keys.

134
Q

Design an algorithm to find a path from one node in a binary tree to another.

A

Good Answer: There will always be exactly one path: from the starting node to the lowest common ancestor of the nodes to the second node. The goal is to identify the lowest common ancestor.

For each node, keep track of a set of nodes in the binary tree (using a hash table or a BST) as well as a current node. At each iteration, for each of the two current nodes, change the current node to be its parent and add it to the appropriate set. The first element that is added to one set when it is already present in the other set is the lowest common ancestor. This algorithm takes O(n) time, where n is the length of the path.

To improve the solution, we actually only need to use one set instead of two.

135
Q

What is the symbol for “bitwise xor”?

A

The symbol for bitwise xor is “^”.

Note that bitwise xor can often be used in a tricky way because two identical numbers in an expression involving xor will “cancel out”. For example, 15 ^ 12 ^ 15 = 12.

136
Q

What is the symbol for “bitwise negation”?

A

The symbol for bitwise negation is “~”.

137
Q

How can you quickly compute 2^x?

A

Good Answer: 1 &laquo_space;x (1 bitwise left-shifted by x)

138
Q

How can you quickly determine whether a number is a power of 2?

A

Good answer: Check whether x & (x - 1) is 0. If x is not an even power of 2, the highest position of x with a 1 will also have a 1 in x - 1; otherwise, x will be 100…0 and x - 1 will be 011…1; “and”-ing them together will return 0.

139
Q

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

A

Good answer: Go through the array in order, keeping track of the lowest stock price and the best deal you’ve seen so far. Whenever the current stock price minus the current lowest stock price is better than the current best deal, update the best deal to this new value.

140
Q

General thoughts on Program Design

A

Although it sometimes may seem like it, interviewers aren’t always interested in little programming tricks and puzzles. Sometimes they may ask you to design a program or a system. For example, it’s not uncommon to be asked to sketch out what classes you would need if you were to write a poker game program or a simulation of car traffic at an intersection. There are many different questions the interviewer could ask about design, so just keep in mind that if you need to design the classes for a program, try to keep your design simple and at the same time allow for future extensions on your design.

For example, if you were designing a five‐card draw poker game program, you could have a GameMode interface or superclass and have a FiveCardDraw subclass to encapsulate the particular rules for that version of the game. Therefore if the interviewer then asks you how you could extend the system to allow a Texas hold ‘em game, you could simply again make a TexasHoldEm subclass of GameMode.

141
Q

General thoughts on Design Patterns

A

A design pattern is a useful design technique that programmers have discovered to be so useful over the years that they give a specific name to it. Interviewers sometimes ask you to list some design patters you know, and may even ask you to describe how a particular one works. But besides questions that directly test your knowledge of them, design patters are very useful as building blocks for solving other questions, especially the ones that focus on program design.

142
Q

Design Pattern - Listener/Observer Pattern

A

This may be the most popular design pattern out there. The idea is this: suppose there were an e-mail list for Hacking a Google Interview (unfortunately there isn’t one, but if we had been a bit more forward-thinking, perhaps we would have made one). This list would allow for important announcements to be sent to anyone who cared about the class. Every student who put themselves on the list would be a “listener” (or “observer”). The teacher would be the “announcer” (or “subject” in some texts). Every time the teacher wanted to let the students know something, they would go though the e-mail list and send an announcement e-mail to each listener.

In a program, we would have a Listener interface that any class could implement. That Listener interface would have some sort of “update()” method that would be called whenever the announcer wanted to tell the listeners something. The announcer would store a list of all the listeners. If we wanted to add an object “foo” as a listener, we would call “announcer.addListener(foo)”, which would cause the announcer to add foo to its list of listeners. Whenever the announcer did something important that it wanted to tell the listeners about, it would go though its list of listeners and call “update()” on each of those objects.

Going back to the poker game program, you might mention to the interviewer that you could use the listener design pattern for several things. For example, you could have the GUI be a listener to several objects in the game (such as player hands, the pot, etc.) for any changes in game state for which it would need to update the display.

143
Q

Design Pattern - Singleton Pattern

A

The singleton pattern is used when you want to make sure there is exactly one instance of something in your program. If you were making a Lord of the Rings game, you would want to make sure that the One Ring was only instantiated once! We have to give Frodo a chance! In Java, for instance, to make sure there is only one of something, you can do something like this:

public class OnlyOneOfMe {
	private static OnlyOneOfMe theOneInstance = null;
	private OnlyOneOfMe() {
		// do stuff to make the object
	}
	public static OnlyOneOfMe getInstance() {
		if (theOneInstance == null) {
			theOneInstance = new OnlyOneOfMe();
		}
		return theOneInstance;
	}
}

Notice that there is no public constructor. If you want an instance of this class, you have to call “getInstance()”, which ensures that only one instance of the class is ever made.

144
Q

Design Pattern - Model-View-Controller

A

Model-view-controller (MVC) is a design pattern commonly used in user interfaces. Its goal is to keep the “data” separate from the user interface. For example, when designing a program that displays stock information, the code that downloads the stock information should not depend on the code that displays the information.

The exact meaning of model-view-controller is a bit ambiguous. Essentially, a program that uses model-view-controller uses separate programming entities to store the data (the “model”), to display the data (the “view”), and to modify the data (the “controller”). In model-view-controller, the view usually makes heavy use of listeners to listen to changes and events in the model or the controller.

Model-view-controller is a good buzzword to whip out when you’re asked a design question relating to a user interface.

145
Q

Let’s say you’ve just kidnapped Alyssa Hacker you want to leave a ransom note for Ben Bitdiddle, saying that if he ever wants to see her again, he needs to swear to never use Scheme again. You don’t want to write the note by hand, since they would be able to trace your handwriting. You’re standing in Alyssa’s apartment and you see a million computer magazines. You need to write your note by cutting letters out of the magazines and pasting them together to form a letter. Here’s the question: given an arbitrary ransom note string and another string containing all the contents of all the magazines, write a function that will return true if the ransom note can be made from the magazines; otherwise, it will return false. Remember, every letter found in the magazine string can only be used once in your ransom note.

For example, if the ransom note string was “no scheme” and the magazine string was “programming interviews are weird”, you would return false since you can’t form the first string by grabbing and rearranging letters from the second string.

A

Pretty-good answer: Make a data structure to store a count of each letter in the magazine string. If you’re programming in C, you can make an array of length 256 and simply use the ASCII value for each character as its spot in the array, since characters are 1 byte. If you’re programming in Java, you can just use a hash table instead (since characters are 2 bytes in Java). Then go through the magazine string and for each character, increment the value for that letter in your data structure. After you go though the whole magazine string, you should have an exact count of how many times each character appears in the magazine string. Then go through each character in the ransom note string and for every character you encounter,decrement the value for that letter in your data structure. If you ever find that after you decrement a count to something less than 0, you know you can’t make the ransom note, so you immediately return false. If however you get though the entire ransom note without running out of available letters, you return true.

Even better answer: Because the magazine string may be very large, we want to reduce the time we spend going through the magazine string. We use the same idea as above, except we go through the ransom note and the magazine string at the same time. Keep one pointer for our current character in the ransom note and another pointer for our current character in our magazine string. First, check to see if the count in our data structure for our current ransom note character is greater than 0. If it is, decrement it and advance the pointer in our ransom note. If it isn’t, start going through the characters in the magazine string, updating the counts in the data structure for each character encountered, until we reach the character we need for our ransom note. Then stop advancing the magazine string pointer and start advancing the ransom note pointer again. If we get to the end of the ransom note, we return true. If we get to the end of the magazine string (meaning we didn’t find enough letters for our ransom note), we return false.

146
Q

Write a program to determine whether an input string x is a substring of another input string y. (For example, “bat” is a substring of “abate”, but not of “beat”.) You may use any language you like.

A 
Sample Answer (in C++):
bool hasSubstring(const char *str, const char *find) {
	if (str[0] == '\0' &amp;&amp; find[0] == '\0')
		return true;
	for(int i = 0; str[i] != '\0'; i++) {
		bool foundNonMatch = false;
		for(int j = 0; find[j] != '\0'; j++) {
			if (str[i + j] != find[j]) {
				foundNonMatch = true;
				break;
			}
		}
		if (!foundNonMatch)
			return true;
	}
	return false;
}
147
Q

Describe a design for a text editor. Describe the classes, interfaces, and so on that you would use and how you would organize them.

A

Answer: There are so many possible answers to this problem that it would be difficult to say that one answer is the best. Look to make sure that they make classes to set up a text editor (classes for the GUI, formatting, saving/loading files, handling input, etc.). Using inheritance (subclassing in object-oriented programming) where it makes sense is also good for reusability and extendability. Using design patters (such as Model-View-Controller, Listener/Observer, or the Singleton pattern) is also a good thing. The main point is for them to get used to thinking about how they would design a system. Most importantly, they need to think about simplicity, reusability, and extendability in their design.

A text editor design question is slightly different from other design questions in that programmers often have strong feelings about how a text editor should work. Programmers often want the ability to greatly modify the behavior of their editor and want to be able to write extensions that add functionality to it. The major text editors used by programmers today, such as Emacs, Vim, Eclipse, and Visual Studio have this ability. A discussion about how their text editor would accomplish this (especially with how the design would include a place for extensions and how input would be handled) would be good.

148
Q

Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis. You can assume that each rectangle object has two variables in it: the x-y coordinates of the upper-left corner and the bottom-right corner.

A

Good Answer: Create a sorted array of the x coordinates of the left and right edges of the rectangles. Then, use a “scanline” to move from left to right through the rectangles. Keep a binary search tree containing the y coordinates of the top and bottom edges of the rectangles that overlap the scanline. For each element of the array, check whether it is a left or right edge. If it is a right edge, remove the corresponding top and bottom edges from the BST. If it is a left edge, search the BST for rectangles that overlap the current rectangle; if there is one, return the overlap. Then, add the y coordinates of the top and bottom edges of the rectangle to the BST. The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles and each of the 2n iterations takes O(log n) time.

149
Q

Write a function to remove a single occurrence of an integer from a doubly linked list if it is present. You may use any language you like.

A

Sample Answer (in Java):

void remove(Node head, int value) {
	Node cur = head;
	while (cur != null) {
		if (cur.value == value) {
			if (curr.prev != null)
				cur.prev.next = cur.next;
			if (cur.next != null)
				cur.next.prev = cur.prev;
			break;
		}
	cur = cur.next;
	}
}
150
Q

Describe a stack data structure that supports “push”, “pop”, and “find minimum” operations. “Find minimum” returns the smallest element in the stack.

A

Good Answer: Store two stacks, one of which contains all of the items in the stack and one of which is a stack of minima. To push an element, push it onto the first stack. Check whether it is smaller than the top item on the second stack; if so, push it onto the second stack. To pop an item, pop it from the first stack. If it is the top element of the second stack, pop it from the second stack. To find the minimum element, simply return the element on the top of the second stack. Each operation takes O(1) time.

151
Q

Describe an algorithm to output a die roll (a random number from 1 to 6), given a function that outputs a coin toss (a random number from 1 to 2). Each possible outcome should be equally likely.

A

Sample Answer: Flip the coin three times, and use the three coin flips as the bits of a three-bit number. If the number is in the range 1 to 6, output the number. Otherwise, repeat. Note that many other answers are possible.

152
Q

Given an integer x and an unsorted array of integers, describe an algorithm to determine whether two of the numbers add up to x. (In this case, say that the interviewer hates hash tables.)

A

Good Answer: Sort the array. Then, keep track of two pointers in the array, one at the beginning and one at the end. Whenever the sum of the current two integers is less than x, move the first pointer forwards, and whenever the sum is greater than x, move the second pointer backwards. If you cannot find two numbers that add to x before one of the pointers meet, then there is no pair of integers that sum to x. This solution takes O(n log n) time because we sort the numbers.

Another Good Answer: Create a binary search tree containing x minus each element in the array. Then, check whether any element of the array appears in the BST. It takes O(n log n) time to create a binary search tree from an array, since it takes O(log n) time to insert something into a BST, and it takes O(n log n) time to see if any element in an array is in a BST, since the lookup time for each element in the array takes O(log n). Therefore step one takes O(n log n) time and step two takes O(n log n) time, so our total running time is O(n log n).

153
Q

Describe a good strategy to find a bug in a program.

A

Answer: This question has many possible answers, and is the sort of open-ended question that interviewers occasionally ask. A good answer to this question might include identifying the portion of the program in which the bug appears to be occurring based on its behavior, as well as using breakpoints and a stepper to step through the program. Any answers that involve thinking about possible sources of the problem and finding ways to limit the search scope of the bug are good answers.

154
Q

Write a function to determine whether a given binary tree of distinct integers is a valid binary search tree. Assume that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent. You may use any language you like.

A

Good Answer: Note that it’s not enough to write a recursive function that just checks if the left and right nodes of each node are less than and greater than the current node (and calls that recursively). You need to make sure that all the nodes of the subtree starting at your current node are within the valid range of values allowed by the current node’s ancestors. Therefore you can solve this recursively by writing a helper function that accepts a current node, the smallest allowed value, and the largest allowed value for that subtree.

An example of this is the following (in Java):

boolean isValid(Node root) {
	return isValidHelper(root, Integer.MIN_VALUE,
			Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
	if (curr.left != null) {
		if (curr.left.value < min ||
				!isValidHelper(curr.left, min, curr.value))
			return false;
	}
	if (curr.right != null) {
		if (curr.right.value > max ||
				!isValidHelper(curr.right, curr.value, max))
			return false;
	}
	return true;
}

The running time of this algorithm is O(n).

155
Q

You’re given an unsorted array of integers where every integer appears exactly twice, except for one integer which appears only once. Write an algorithm (in a language of your choice) that finds the integer that appears only once.

A

Good Answer: Set up a hash set that we will put the integers from the array into. Have a second variable that will keep a sum. Start going through the array and for each integer, check to see if it’s already in the hash set. If it is not, add that integer to the sum and store that integer in the hash set. If it is in the hash set, subtract that integer from the sum. When the algorithm finishes going through the array, the sum variable should be equal to the integer we were looking for, since it is the only number we never subtracted from the sum. This takes O(n) time and O(n) space.

int oddManOut(int[] array) {
	HashSet s = new HashSet();
	int sum = 0;
	for (int i = 0; i < array.length; i++) {
		if (s.contains(array[i])) {
			sum = sum - array[i];
		} else {
			s.add(array[i]);
			sum = sum + array[i];
		}
	}
	return sum;
}

Really Awesome Answer: XOR all the values of the array together! Since XOR is commutative and is its own inverse, each integer in the array that appears twice will cancel itself out, and we’ll be left with the integer we’re looking for. This takes O(n) time and O(1) space. We told you bitwise stuff was handy!

int oddManOut(int[] array) {
	int val = 0;
	for (int i = 0; i < array.length; i++) {
		val ^= array[i];
	}
	return val;
}
156
Q

Without writing any actual code, describe as much as possible how you would design a poker game program. What classes would you have? What relationships would they have with each other? What would be the basic flow of the program and how would those classes play a part? If you then wanted to add a new type of poker game (such as Texas Hold ‘em), how would that fit into your design?

A

Answer: There are so many possible answers to this problem that it would be difficult to say that one answer is the best. Look to make sure that they make classes to simulate the basic parts of a poker game (perhaps a hand, the pot, a game type or rules, a round, the deck, etc.). Using inheritance (subclassing in object-oriented programming) where it makes sense is also good for reusability and extendibility. Using design patters (such as Model-View-Controller, Listener/Observer, or the Singleton pattern) is also a good thing. The main point is for them to get used to thinking about how they would design a system. Most importantly, they need to think about simplicity, reusability, and extendibility in their design.

157
Q

Describe a technique to identify a “leader” among a group of 10 identical servers that are all connected to every other server. There are no prior distinguishing characteristics of any of them and the same program to identify the leader starts running on all of them at the same time. After an answer is given, ask how much network traffic it requires and, if “ties” are possible, ask how you can break ties.

A

Good Answer: Have each server wait a random amount of time and then say “I’m it.” The “I’m it” announcement is time-stamped, and the computer that time-stamped its announcement first is elected the leader. This approach requires sending out 9 messages. If there is a tie, the computers can repeat the procedure.

Note that other answers are possible, but every correct answer will use randomness in some way.

158
Q

Describe a design for an instant messaging program where there are several servers, clients are connected to each server, and the servers communicate with each other. Describe the classes, interfaces, and so on that you would use and how you would organize them.

A

Answer: As in the previous design questions, there is no best answer. Good topics to discuss are how each client communicates with a server, how the servers maintain state with the other servers, how state information is communicated between servers and clients, and the speed/reliability of their design.

159
Q

Given an array, describe an algorithm to identify the subarray with the maximum sum. For example, if the input is [1, -3, 5, -2, 9, -8, -6, 4], the output would be [5, -2, 9].

A

Good Answer: Observe that the sum of a subarray from element i to element j is equal to the sum of the subarray from element 1 to element j minus the subarray from element 1 to element i - 1. Our algorithm will iterate through the array. The algorithm keeps track of the sum x of the elements no later than the element. It will also keep track of the minimum sum y of the subarray from the first element to an element no later than the current element. Finally, It will also keep track of the subarray z with the maximum sum so far. At each step, we update x by adding the current element to it. We update y by checking whether x < y; if so, we set y to be x. We update z by checking whether y - x is greater than z; if so, we set z to be y - x.

160
Q

Dot Product (Calculation and neat features)

A

A (dot) B = x_Ax_B + y_Ay_B = |A||B|cos(theta)

This allows for easily determining the angle between two vectors.

161
Q

Cross Product (Calculation and neat features)

A

Easiest way to remember how to calculate it is the determinant of a 3D matrix.

The resulting vector will be normal to the plane that the two vectors fall on, and AxB = |A||B|sin(theta) which is the area of the parallelogram defined by the two vectors, so (AxB) is the area of the triangle defined by the two vectors!

162
Q

How do you find the distance between a line and a point?

A

So say the line has two points on it, (A,B) and the point that we find the distance of is C.

(ABxAC)/2 is the area of the triangle defined by ABC, and since the area of the triangle is baseheight/2 we can say that the perpendicular distance from C to the line is (ABxAC)/(2|AB|) where |AB| is the length of segment AB.

Note that if point is to find the distance to segment (i.e. not the entire line) AB, then this may have to be solved another way.

163
Q

How do you find the area of a polygon?

A

Identify a node in the polygon to act as a base, and then calculate the area (ABxAC/2) of all triangles (in a row) that connect to this node.

For example, for polygon ABCDE, the sum of the triangles ABC, ACD, and ADE will be the area.

NOTE 1/2: The area may be found to be negative depending on the orientation of the polygon.

NOTE 2/2: This works for polygons with concave points as well as the area will be subtracted when calculating using this point.

164
Q

Given points (x_1, y_1) and (x_2, y_2) that define a line, place this line in form Ax+By=C.

A 
A = y_2-y_1
B = x_1-x_2
C = Ax_1+Bx_2
165
Q

Find where lines A_1 x + B_1 y = C_1 and A_2 x + B_2 y = C_2 intersect.

A

Easily solved as a matrix, which becomes the equations:

det = A_1B_2 - A_2B1.

if det == 0, then the lines are parallel. Otherwise:

x_intersect = (B_2*C_1 - B_1*C_2) / det
y_intersect = (A_1*C_2 - A_2*C_1) / det

NOTE: The coefficients that are positive were positive in the calculation of the determinant, and are the coefficients for the opposite variables they are calculating. (Probably easier to work it out mentally from looking at the matrix.)

166
Q

How do I find out if (x,y) is on segment (x_1,y_1) to (x_2,y_2)? (Assuming that we have already determined that (x,y) is on the overall line defined by (x_1,y_1) to (x_2,y_2).)

A

min(x_1,x_2) <= x <= max(x_1,x_2)
min(y_1,y_2) <= y <= max(y_1,y_2)

NOTE: If the segment is vertical or if (x,y) is very close to one of the points, there may be tolerance issues. Be wary of this.

167
Q

If we have three points that are not collinear, how do you find the the center of the circle defined by these points?

A

Identify two line segments defined by the points (any two are fine), identify the perpendicular bisectors, and calculate where they intersect.

168
Q

How do we find the perpendicular bisector of a line segment with equation Ax+By=C.

A

The equation for the line perpendicular to Ax+By=C is:

-Bx+Ay=D

where D is a value that can be set based on the point in the middle of the line segment.

169
Q

Find the reflection of point E over line Ax+By=C.

A

Find the line perpendicular to Ax+By=C (i.e. -Bx+Ay=D) that intersects point E. Find where the distance from E to where these two lines intersect, and then double that distance to find the location of the reflected point.

170
Q

When discussing a graph, what does the word “Order” mean?

A

“Order” means the number of vertices in a graph.

171
Q

When discussing a graph, what does the word “Size” mean?

A

“Size” means the number of edges in a graph.

172
Q

How do you delete a node from a Binary Search Tree (BST)?

A

For deleting node ‘n’:

If n has no children, then remove n from the tree.

If n has one child than remove n, and connect its parent to its child.

If n has two children, identify the smallest node that is larger than n (call it ‘m’). Remove m from the tree (and m should have at most one child). Replace n with m.

173
Q

General description of a red-black tree.

A

Red-black trees are an evolution of binary search trees that aim to keep the tree balanced without affecting the complexity of the primitive operations. This is done by coloring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one.

174
Q

What are the five properties of a red-black tree and what do they accomplish.

A

1) Every node is colored with either red or black.
2) All leaf (nil) nodes are colored with black; if a node’s child is missing then we will assume that it has a nil child in that place and this nil child is always colored black.
3) Both children of a red node must be black nodes.
4) Every path from a node n to a descendant leaf has the same number of black nodes (not counting node n). We call this number the black height of n, which is denoted by bh(n).
5) The root of the tree is black. (This isn’t actually necessary, but keeps things clean.)

These properties ensure that the path from the root to the farthest leaf is no more than twice as long as the path to the nearest leaf.

175
Q

Describe a red-black tree rotation:

A

Node P is the parent and node N is non-leaf right child.

Let N become the parent and place P as it’s left child.

Take N’s left child and make it P’s right child.

176
Q

What color (initially) does a node inserted into a red-black tree become?

A

Red.

177
Q

What are the five cases to consider when inserting a node (N) into a red-black tree?

A

1) N is the root node of the tree.
2) N’s parent (P) is black.
3) N’s parent (P) and uncle (U) are red.
4) N is added to right of left child of grandparent, or N is added to left of right child of grandparent (P is red and U is black)
5) N is added to left of left child of grandparent, or N is added to right of right child of grandparent (P is red and U is black)

178
Q

What are four valuable support functions for a red-black tree?

A

leftRotate, rightRotate, grandparent, and uncle.

Note that grandparent and uncle should take pointers as arguments and return pointers, while the rotation functions should take the node being rotated out as the ancestor of the subtree and return the node rotated into ancestor of the subtree.

179
Q

Situation: Red-black tree, insert node (N)

N is the root of the tree.

A

Convert the color of N from red to black.

180
Q

Situation: Red-black tree, insert node (N)

N’s parent (P) is black.

A

Trivial. Everything is okay.

181
Q

Situation: Red-black tree, insert node (N)

N’s parent (P) and uncle (U) are red.

A

Change the color of P and U to black, and change the color of the grandparent node to red.

Insert the grandparent node. (i.e. The initial insertion may not be complete and more modifications may be necessary.)

182
Q

Situation: Red-black tree, insert node (N)

N is added to right of left child of grandparent, or N is added to left of right child of grandparent (P is red and U is black)

A

Rotate P opposite the location of N. This leaves N as the parent of P, and both are still red.

Insert P. (This will be addressed by case 5 of insertion.)

183
Q

Situation: Red-black tree, insert node (N)

N is added to left of left child of grandparent, or N is added to right of right child of grandparent (P is red and U is black)

A

Rotate the grandfather node opposite the the location of N and P, and then switch the color of P and the grandfather node.

184
Q

Why is it initially) trivial to delete a node in a red-black tree with two non-leaf children?

A

As with a standard binary search tree, when deleting a node with two children, the node can be replaced either with the left most node on the right side, or the right most node on the left side. Since this replacement is occurring, the colors can remain the same.

NOTE: The node with at most one non-leaf child used to replace the two child node needs to be treated as if it’s deleted, and there are many cases that need to be addressed for the proper deletion of this node.

185
Q

Situation: Red-black tree, delete node (M)

M is red and has a single non-leaf child (C).

A

Trivial, as C can just replace M, and all rules are maintained including the number of black nodes to each of the leaf nodes to tree that derives from C.

186
Q

Situation: Red-black tree, delete node (M)

M is black and has a single non-leaf child (C) that is red.

A

Trivial, as the color of C can flip to black when it replaces M and maintain the requirements of a red-black tree.

187
Q

Architectural Pattern - Three-tier

A

Three-tier architecture is a client–server software architecture pattern in which the user interface (presentation), functional process logic (“business rules”), computer data storage and data access are developed and maintained as independent modules, most often on separate platforms.

Presentation tier
This is the topmost level of the application. The presentation tier displays information related to such services as browsing merchandise, purchasing and shopping cart contents. It communicates with other tiers by which it puts out the results to the browser/client tier and all other tiers in the network. In simple terms, it is a layer which users can access directly (such as a web page, or an operating system’s GUI).

Application tier (business logic, logic tier, or middle tier)
The logical tier is pulled out from the presentation tier and, as its own layer, it controls an application’s functionality by performing detailed processing.
Data tier

The data tier includes the data persistence mechanisms (database servers, file shares, etc.) and the data access layer that encapsulates the persistence mechanisms and exposes the data. The data access layer should provide an API to the application tier that exposes methods of managing the stored data without exposing or creating dependencies on the data storage mechanisms. Avoiding dependencies on the storage mechanisms allows for updates or changes without the application tier clients being affected by or even aware of the change. As with the separation of any tier, there are costs for implementation and often costs to performance in exchange for improved scalability and maintainability.

Web development usage

In the web development field, three-tier is often used to refer to websites, commonly electronic commerce websites, which are built using three tiers:

A front-end web server serving static content, and potentially some cached dynamic content. In web based application, Front End is the content rendered by the browser. The content may be static or generated dynamically.

A middle dynamic content processing and generation level application server (e.g., ASP.NET, Ruby on Rails, Django (web framework), Laravel, Spring Framework, CodeIgniter, Symfony, Flask (web framework))
A back-end database or data store, comprising both data sets and the database management system software that manages and provides access to the data.

188
Q

Architectural Pattern - Multitier

A

In software engineering, multitier architecture (often referred to as n-tier architecture) or multilayered architecture is a client–server architecture in which presentation, application processing, and data management functions are physically separated. The most widespread use of multitier architecture is the three-tier architecture.

N-tier application architecture provides a model by which developers can create flexible and reusable applications. By segregating an application into tiers, developers acquire the option of modifying or adding a specific layer, instead of reworking the entire application. A three-tier architecture is typically composed of a presentation tier, a domain logic tier, and a data storage tier.

While the concepts of layer and tier are often used interchangeably, one fairly common point of view is that there is indeed a difference. This view holds that a layer is a logical structuring mechanism for the elements that make up the software solution, while a tier is a physical structuring mechanism for the system infrastructure. For example, a three-layer solution could easily be deployed on a single tier, such as a personal workstation.

189
Q

Architectural Pattern - Blackboard

A

In software engineering, the blackboard pattern provides a computational framework for the design and implementation of systems that used to integrate large and diverse specialized modules, and implement complex, non deterministic control strategies. Blackboard pattern comes under behavioral design pattern.

The blackboard model defines three main components:

1) Blackboard - a structured global memory containing objects from the solution space
2) Knowledge sources - highly specialized modules with their own representation
3) Control component - selects, configures and execute knowledge sources.

Some usage-domains are speech recognition, vehicle identification and tracking, identification of the structure of protein molecules, and sonar signals interpretation.

The blackboard pattern provides effective solutions for designing and implementing complex systems where heterogeneous modules have to be dynamically combined to solve a problem. This provides properties such as reusability, changeability, robustness.

Blackboard pattern allows multiple processes to work closer together on separate threads, polling, and reacting, if it is needed.

190
Q

What’s the difference between a class and an object?

A

An object is a member or an “instance” of a class. An object has a state in which all of its properties have values that you either explicitly define or that are defined by default settings. This subtle conceptual difference between classes and objects shows why there is a tendency to want to use them interchangeably.

191
Q

What is instantiation?

A

In programming, instantiation is the creation of a real instance or particular realization of an abstraction or template such as a class of objects or a computer process.

192
Q

What’s the difference between a method and a function?

A

A function returns a value, but a procedure does not. A method is similar to a function, but is internal to part of a class. The term method is used almost exclusively in object-oriented programming. A function is something that takes a bunch of inputs and returns one or more values.

193
Q

What is a static method?

A

If you apply static keyword with any method, it is known as static method. A static method belongs to the class rather than object of a class. A static method invoked without the need for creating an instance of a class. static method can access static data member and can change the value of it.

194
Q

What is a constructor?

A

A constructor is a special method of a class or structure in object-oriented programming that initializes an object of that type. A constructor is an instance method that usually has the same name as the class, and can be used to set the values of the members of an object, either to default or to user-defined values.

195
Q

What is a destructor?

A

A destructor is a special member function that is called when the lifetime of an object ends. The purpose of the destructor is to free the resources that the object may have acquired during its lifetime.

196
Q

What is a superclass?

A

In object-oriented programming, a class from which other classes inherit code is called a superclass, and the class which inherits the code is called a subclass of that superclass. Typically, a subclass inherits the instance variables and member functions of its superclass.

197
Q

What is a subclass?

A

A subclass is a class that extends another class.

198
Q

What is inheritance?

A

In object-oriented programming, inheritance is when an object or class is based on another object (prototypal inheritance) or class (class-based inheritance), using the same implementation (inheriting from an object or class) or specifying a new implementation to maintain the same behavior (realizing an interface; inheriting behavior; programming by difference). Such an inherited class is called a subclass of its parent class or super class. It is a mechanism for code reuse and to allow independent extensions of the original software via public classes and interfaces. The relationships of objects or classes through inheritance give rise to a hierarchy.

199
Q

What is encapsulation?

A

In programming languages, encapsulation is used to refer to one of two related but distinct notions, and sometimes to the combination[1][2] thereof:

A language mechanism for restricting direct access to some of the object’s components.

A language construct that facilitates the bundling of data with the methods (or other functions) operating on that data.

200
Q

What is multiple inheritance?

A

Multiple inheritance is a feature of some object-oriented computer programming languages in which an object or class can inherit characteristics and features from more than one parent object or parent class.

201
Q

What is delegation?

A

In object-oriented programming, delegation refers to evaluating a member (property or method) of one object (the receiver) in the context of another, original object (the sender). Delegation can be done explicitly, by passing the sending object to the receiving object, which can be done in any object-oriented language; or implicitly, by the member lookup rules of the language, which requires language support for the feature. Implicit delegation is the fundamental method for behavior reuse in prototype-based programming, corresponding to inheritance in class-based programming.

The term delegation is also used loosely for various other relationships between objects; see delegation (programming) for more. Frequently confused concepts are simply using another object, more precisely referred to as consultation or aggregation; and evaluating a member on one object by evaluating the corresponding member on another object, notably in the context of the receiving object, which is more precisely referred to as forwarding (when a wrapper object doesn’t pass itself to the wrapped object).

202
Q

What is an abstract class?

A

Abstract classes are classes that contain one or more abstract methods. An abstract method is a method that is declared, but contains no implementation. Abstract classes may not be instantiated, and require subclasses to provide implementations for the abstract methods.

203
Q

What’s the difference between abstract and virtual methods?

A

Exactly. The point is that virtual methods can be overridden in derived classes, while abstract methods must be overridden. Likewise, a class that has at least one abstract method must itself be abstract, i.e. it cannot be instantiated directly since its implementation is (partially) missing.

204
Q

What is an interface?

A

An interface is a reference type in Java. It is similar to class. It is a collection of abstract methods. A class implements an interface, thereby inheriting the abstract methods of the interface. Along with abstract methods, an interface may also contain constants, default methods, static methods, and nested types.

The C++ interfaces are implemented using abstract classes and these abstract classes should not be confused with data abstraction which is a concept of keeping implementation details separate from associated data. A class is made abstract by declaring at least one of its functions as pure virtual function.

205
Q

What is method overriding?

A

Method overriding, in object oriented programming, is a language feature that allows a subclass or child class to provide a specific implementation of a method that is already provided by one of its superclasses or parent classes.

206
Q

What is method overloading?

A

Method Overloading is a feature that allows a class to have two or more methods having same name, if their argument lists are different.

207
Q

What is polymorphism?

A

Polymorphism describes a pattern in object oriented programming in which classes have different functionality while sharing a common interface.

208
Q

What is a type (or method) signature?

A

In computer science, a type signature or type annotation defines the inputs and outputs for a function, subroutine or method. A type signature includes the number of arguments, the types of arguments and the order of the arguments contained by a function. A type signature is typically used during overload resolution for choosing the correct definition of a function to be called among many overloaded forms.

209
Q

What is method (or name) visibility?

A

There are three accessors that I’m aware of: public, protected and private.

Let:

class Base {
    public:
        int publicMember;
    protected:
        int protectedMember;
    private:
        int privateMember;
};

Everything that is aware of Base is also aware that Base contains publicMember.

Only the children (and their children) are aware that Base contains protectedMember.

No one but Base is aware of privateMember.

NOTE: By “is aware of”, I mean “acknowledge the existence of, and thus be able to access”.

210
Q

What’s the difference between a static variable and an instance variable?

A

A static variable is shared between instances. For instance, if you want to count how many of an object you’ve created, you should have a static variable and increment it each time you create an object.

211
Q

Design question: Design a deck of cards that can be used for different card game applications.

A

Likely classes: a Deck, a Card, a Hand, a Board, and possibly Rank and Suit. Drill down on who’s responsible for creating new Decks, where they get shuffled, how you deal cards, etc. Do you need a different instance for every card in a casino in Vegas?

212
Q

Design question: Model the Animal kingdom as a class system, for use in a Virtual Zoo program.

A

Possible sub-issues: do they know the animal kingdom at all? (I.e. common sense.) What properties and methods do they immediately think are the most important? Do they use abstract classes and/or interfaces to represent shared stuff? How do they handle the multiple-inheritance problem posed by, say, a tomato (fruit or veggie?), a sponge (animal or plant?), or a mule (donkey or horse?)

213
Q

Design question: Create a class design to represent a filesystem.

A

Do they even know what a filesystem is, and what services it provides? Likely classes: Filesystem, Directory, File, Permission. What’s their relationship? How do you differentiate between text and binary files, or do you need to? What about executable files? How do they model a Directory containing many files? Do they use a data structure for it? Which one, and what performance tradeoffs does it have?

214
Q

Design question: Design an OO representation to model HTML.

A

How do they represent tags and content? What about containment relationships? Bonus points if they know that this has already been done a bunch of times, e.g. with DOM. But they still have to describe it.

215
Q

What’s the motivation behind MapReduce?

A

Many tasks: Process lots of data to produce other data

Want to use hundreds or thousands of CPUs

216
Q

What does MapReduce “Provide”?

A

Automatic parallelization and distribution

Fault-tolerance

I/O scheduling

Status and monitoring

217
Q

What can cause slow workers during a MapReduce execution?

A

Other jobs consuming resources on machine

Bad disks with soft errors transfer data very slowly

Weird things: processor caches disabled (!!)

218
Q

How does MapReduce handle the fact that certain workers may be much slower than others?

A

Redundant Execution. Near the end of a phase, the function spawns backup copies of tasks. Therefore, whichever workers finishes first “wins”.

219
Q

What issues is the Google File System (GFS) designed to address?

A

1) Component failures are the norm rather than the exception.
2) Files are huge by traditional standards.
3) Most files are mutated by appending new data rather than overwriting existing data.
4) Co-designing the applications and file system API benefits the overall system by increasing our flexibility. For example, we have relaxed GFS’ consistency model to vastly simplify the file system without imposing an onerous burden on the applications and we have introduced an atomic append operation so that multiple clients can append concurrently to a file without extra synchronization between them.

220
Q

What is a spinlock?

A

In software engineering, a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop (“spin”) while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting.

Because they avoid overhead from operating system process rescheduling or context switching, spinlocks are efficient if threads are likely to be blocked for only short periods. For this reason, operating-system kernels often use spinlocks. However, spinlocks become wasteful if held for longer durations, as they may prevent other threads from running and require rescheduling.

221
Q

What is preemption?

A

In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time. Such changes of the executed task are known as context switches. It is normally carried out by a privileged task or part of the system known as a preemptive scheduler, which has the power to preempt, or interrupt, and later resume, other tasks in the system.

Google Interview Prep (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions