For a decent website with couple hundred pages or more and keeps growing, you need a on-site search engine for your website. This is important so that your visitors could find pages easily.
Below are some free or cheap site search engines you could consider.
http://www.freefind.com
Free search engine for your website. FreeFind.com lets your visitors search your website. Add a search engine to your website today, for free, in less than ten minutes. This is the fastest and easiest way to add professional level searching to a website.
http://www.atomz.com
Atomz Site Search: The premier free search tool for your website.
http://www.picosearch.com
Add a free site search engine to search your web site - no software, easy to install, free! Powerful options, large maximum pages, more professional search features for business site search.
http://www.bravenet.com/webtools/search2/
Site search and free site search by bravenet.com. Let visitors search your site.
http://www.jrank.org
Are your visitors getting lost on your website? Put a search engine on your web site to help your visitors find the content they're looking for. Completely free, lightning fast, and super-easy to use.
Other than that, JiansNet.com is also a search engine for useful information for overseas Chinese in USA.
Friday, July 9, 2010
Sunday, July 4, 2010
Integration of Product Reviews on Google
Google is entering more into the semantic web by just brute force. Lately it has integrated product ratings and reviews from sources like:
--Amazon.com
--Overstock.com
--ePinions.com
Besides these large eCommerce sites, Google has also integrated reviews from different vendors through review engines such as Bazaarvoice.
So, when you do a search on Google product search, you will see full-length reviews, here is a sample link:
http://www.google.com/products?q=toy
Searching on Google.com will show snippet of a vendor's review content and linking back to the vendor's site.
In this regard, Google is definitely beefing up shopping related searches and compete with Microsoft Bing in terms of shopping search.
I think some day, eCommerce sites might be able to submit reviews directly to Google.
--Amazon.com
--Overstock.com
--ePinions.com
Besides these large eCommerce sites, Google has also integrated reviews from different vendors through review engines such as Bazaarvoice.
So, when you do a search on Google product search, you will see full-length reviews, here is a sample link:
http://www.google.com/products?q=toy
Searching on Google.com will show snippet of a vendor's review content and linking back to the vendor's site.
In this regard, Google is definitely beefing up shopping related searches and compete with Microsoft Bing in terms of shopping search.
I think some day, eCommerce sites might be able to submit reviews directly to Google.
Monday, June 28, 2010
Ten Tips for a Successful Internet Startup
Below are the 10 rules for creating a successful internet startup.
1. Don't wait for a revolutionary idea. It will never happen. Just focus on a simple, exciting, empty space and execute as fast as possible
2. Share your idea. The more you share, the more you get advice and the more you learn. Meet and talk to your competitors.
3. Build a community. Use blogging and social software to make sure people hear about you.
4. Listen to your community. Answer questions and build your product with their feedback.
5. Gather a great team. Select those with very different skills from you. Look for people who are better than you.
6. Be the first to recognize a problem. Everyone makes mistakes. Address the issue in public, learn about and correct it.
7. Don't spend time on market research. Launch test versions as early as possible. Keep improving the product in the open.
8. Don't obsess over spreadsheet business plans. They are not going to turn out as you predict, in any case.
9. Don't plan a big marketing effort. It's much more important and powerful that your community loves the product.
10. Don't focus on getting rich. Focus on your users. Money is a consequence of success, not a goal.
1. Don't wait for a revolutionary idea. It will never happen. Just focus on a simple, exciting, empty space and execute as fast as possible
2. Share your idea. The more you share, the more you get advice and the more you learn. Meet and talk to your competitors.
3. Build a community. Use blogging and social software to make sure people hear about you.
4. Listen to your community. Answer questions and build your product with their feedback.
5. Gather a great team. Select those with very different skills from you. Look for people who are better than you.
6. Be the first to recognize a problem. Everyone makes mistakes. Address the issue in public, learn about and correct it.
7. Don't spend time on market research. Launch test versions as early as possible. Keep improving the product in the open.
8. Don't obsess over spreadsheet business plans. They are not going to turn out as you predict, in any case.
9. Don't plan a big marketing effort. It's much more important and powerful that your community loves the product.
10. Don't focus on getting rich. Focus on your users. Money is a consequence of success, not a goal.
Wednesday, June 23, 2010
Searching Multiple Hot Deal Forums
We've launched SimpleDealSearch.com, a site that searches multiple deal forums. Right now it searches:
Fatwallet
DealSea
Bensbargains
Slickdeals
We are going to add more forums and sites as appropriate. If you have any suggestion for what sites/forums to search, let us know by following this message.
SimpleDealSearch.com, deal search made simple
Fatwallet
DealSea
Bensbargains
Slickdeals
We are going to add more forums and sites as appropriate. If you have any suggestion for what sites/forums to search, let us know by following this message.
SimpleDealSearch.com, deal search made simple
Sunday, June 13, 2010
百度空间博客上， ”文章内容包含不合适内容“
想在百度空间上放一篇博客文章，结果百度博客显示"文章修改失败! 文章内容包含不合适内容，请检查".
经过逐步删减词和句子后，发现就是"预测"两个字有问题。
另外，百度知道上也有人有同样的问题。
百度空间竟然将“预测”这个词作为不合适词汇屏蔽了，何故?
http://zhidao.baidu.com/question/158534946.html
经过逐步删减词和句子后，发现就是"预测"两个字有问题。
另外，百度知道上也有人有同样的问题。
百度空间竟然将“预测”这个词作为不合适词汇屏蔽了，何故?
http://zhidao.baidu.com/question/158534946.html
Tuesday, May 4, 2010
Last installment of the Google Interview Questions Series
This will be the last installment of the Google interview questions series. I think these interview questions are the best in terms of more search engine related. So without much ado, here you go:
* What method would you use to look up a word in a dictionary?
* In Java, what is the difference between static, final, and const. (If you don't know Java they will ask something similar for C or C ++.)
* Talk about your class projects or work projects (pick something easy), then describe how you could make them more efficient (in terms of algorithms).
* How would you compare two search engines?
* Write a function that takes a string and converts '%20' sequences to spaces (in place).
* You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
* How would you determine if adwords was up and running and serving contextual content?
* Describe the data structure that is used to manage memory. (heap / stack)
* Design a web server that serves the Google homepage. a) What are the requirements. b) Design a multi threaded web server that uses shared memory instead of disk access. c) Design a work load balancer for their data centers. d) Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP.
* What is multi-threaded programming? What is a deadlock?
* Describe Sorting algorithms and their complexity: Quick sort, Insertion Sort, Merge Sort.
* Given a list of numbers and a target sum, how would you efficiently determine whether a pair of numbers from the list can add up to the target sum? (list based approach is O(n^2) while hash-table based approach is O(n) )
* Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out the path to goal state.
* Design an algorithm which can find all the dictionary words correspond to a n-digit telephone number, assuming each digit maps to several alphabet letter.
* There are N stars in the sky, how do you find the closest pair?
* Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
* Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
* What are some trade-offs between a multi-threaded and single-threaded implementation?
* (string class) What do you need when you instantiate a string? (I said a byte array and possibly the length.)
* You have N threads and M resources. What protocol do you use to ensure no deadlocks occur?
* Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate (Delhi). How do you do the same?
* You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
* Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
* How many golf balls can fit in a school bus?
* You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
* Explain a database in three sentences to your eight-year-old nephew.
* How many times a day does a clock’s hands overlap?
* Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
* In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
* If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
* If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
* Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it is only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
* You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
* How many piano tuners are there in the entire world?
* You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weightings?
* You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
* Explain a database in three sentences to your eight-year-old nephew.
* Calculate the Resistance in ohm's that a knights move would require on an infinite plane of resistors(forgot the resistance of each resistor, or whatever).
* What is the most beautiful equation you have ever seen? Explain.
* You have 10,000 Apache servers, and 1 day to generate $1,000,000. What do you do?
* Why are manhole covers round?
* A man pushed his car to a hotel and lost his fortune. What happened?
* Explain the significance of "dead beef".
* Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
* Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
* Describe the algorithm for a depth-first graph traversal.
* Design a class library for writing card games.
* You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
* How are cookies passed in the HTTP protocol?
* What is the size of the C structure below on a 32-bit system? On a 64-bit?
struct foo {
char a;
char* b;
};
* Design the SQL database tables for a car rental database.
* Write a regular expression which matches a email address.
* Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
* You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
* Explain how congestion control works in the TCP protocol.
* Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. You are given:
--You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's)
--The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line.
--You can use only custom written applications or available free open-source software.
* What method would you use to look up a word in a dictionary?
* In Java, what is the difference between static, final, and const. (If you don't know Java they will ask something similar for C or C ++.)
* Talk about your class projects or work projects (pick something easy), then describe how you could make them more efficient (in terms of algorithms).
* How would you compare two search engines?
* Write a function that takes a string and converts '%20' sequences to spaces (in place).
* You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
* How would you determine if adwords was up and running and serving contextual content?
* Describe the data structure that is used to manage memory. (heap / stack)
* Design a web server that serves the Google homepage. a) What are the requirements. b) Design a multi threaded web server that uses shared memory instead of disk access. c) Design a work load balancer for their data centers. d) Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP.
* What is multi-threaded programming? What is a deadlock?
* Describe Sorting algorithms and their complexity: Quick sort, Insertion Sort, Merge Sort.
* Given a list of numbers and a target sum, how would you efficiently determine whether a pair of numbers from the list can add up to the target sum? (list based approach is O(n^2) while hash-table based approach is O(n) )
* Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out the path to goal state.
* Design an algorithm which can find all the dictionary words correspond to a n-digit telephone number, assuming each digit maps to several alphabet letter.
* There are N stars in the sky, how do you find the closest pair?
* Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
* Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
* What are some trade-offs between a multi-threaded and single-threaded implementation?
* (string class) What do you need when you instantiate a string? (I said a byte array and possibly the length.)
* You have N threads and M resources. What protocol do you use to ensure no deadlocks occur?
* Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate (Delhi). How do you do the same?
* You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
* Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
* How many golf balls can fit in a school bus?
* You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
* Explain a database in three sentences to your eight-year-old nephew.
* How many times a day does a clock’s hands overlap?
* Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
* In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
* If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
* If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
* Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it is only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
* You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
* How many piano tuners are there in the entire world?
* You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weightings?
* You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
* Explain a database in three sentences to your eight-year-old nephew.
* Calculate the Resistance in ohm's that a knights move would require on an infinite plane of resistors(forgot the resistance of each resistor, or whatever).
* What is the most beautiful equation you have ever seen? Explain.
* You have 10,000 Apache servers, and 1 day to generate $1,000,000. What do you do?
* Why are manhole covers round?
* A man pushed his car to a hotel and lost his fortune. What happened?
* Explain the significance of "dead beef".
* Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
* Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
* Describe the algorithm for a depth-first graph traversal.
* Design a class library for writing card games.
* You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
* How are cookies passed in the HTTP protocol?
* What is the size of the C structure below on a 32-bit system? On a 64-bit?
struct foo {
char a;
char* b;
};
* Design the SQL database tables for a car rental database.
* Write a regular expression which matches a email address.
* Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
* You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
* Explain how congestion control works in the TCP protocol.
* Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. You are given:
--You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's)
--The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line.
--You can use only custom written applications or available free open-source software.
Some tricky google interview questions
Google likes to ask interview questions with extreme cases. For example, those problems couldn't be solved with one computer, or, the data set is so big that it runs out of hard drive, etc. Below are some interesting Google interview questions for you to chew on.
* Given an array, you are given with three sorted arrays (in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.
i) find the longest continuously increasing subsequence.
ii) find the longest increasing subsequence.
* Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
* Find missing number in 4 billinon 32 bit integers
* Suppose you have N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
* There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
* Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
* Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n); bonus points for a constant time algorithm.
* You have a collection of numbers that's so big that it would not fit onto one single computer. It is therefore scattered across N number of machines, with roughly L number of numbers in each machine, how would you find the median in this entire collection?
* Write some code to find all permutations of the letters in a particular string.
* If you had a million integers how would you sort them efficiently, and how much memory would that consume? (modify a specific sorting algorithm to solve this)
* How do you find out the fifth maximum element in a Binary Search Tree in an efficient manner?
* Given a number, describe an algorithm to find the next number which is prime.
* Given an array, you are given with three sorted arrays (in ascending order), you are required to find a triplet (one element from each array) such that distance is minimum.
i) find the longest continuously increasing subsequence.
ii) find the longest increasing subsequence.
* Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
* Find missing number in 4 billinon 32 bit integers
* Suppose you have N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
* There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
* Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
* Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n); bonus points for a constant time algorithm.
* You have a collection of numbers that's so big that it would not fit onto one single computer. It is therefore scattered across N number of machines, with roughly L number of numbers in each machine, how would you find the median in this entire collection?
* Write some code to find all permutations of the letters in a particular string.
* If you had a million integers how would you sort them efficiently, and how much memory would that consume? (modify a specific sorting algorithm to solve this)
* How do you find out the fifth maximum element in a Binary Search Tree in an efficient manner?
* Given a number, describe an algorithm to find the next number which is prime.
Even More Google Interview Questions
This is another batch of the Google interview questions I managed to assemble. I heard to prepare for an interview with companies such as say, Google or Microsoft, you need to take 6 months to do the preparation for the interview questions.
* Implement division (without using the divide operator, obviously).
* Given a function that returns a random number between 1-5, write one that returns a random number between 1-7.
* Write a function (with helper functions if needed) called by Excel that takes an Excel column value (A,B,C,D… AA,AB,AC,… AAA…) and returns a corresponding integer value (A=1,B=2,… AA=27…).
* Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place! E.g.: "This is a sample" --> "sample a is This".
* How would you implement a stack to achieve constant time for "push", "pop" and "find mininum" operations?
* You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
* What should you consider when choosing a (sorting) alogrithm?
* Is it always better to use O(n log n) than O(n^2) (sorting) algorithm?
* There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find the heaviest stone?
* Order the functions in order of their asymptotic performance:
* What is the best and worst performance time for a hash tree and binary search tree?
* You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.
* How do you put a Binary Search Tree in an array in a efficient manner?
* Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN. Write an in-place algorithm to rearrange the elements of the array as A = i1 c1 i2 c2 ... in cn.
* How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
* Given a Binary Tree, programmatically can you prove it is a Binary Search Tree?
* Write a function to find the middle node of a single link list.
* Classic - Egg Problem
1. You are given 2 eggs. You have access to a 100-storey building.
2. Eggs can be very hard or very fragile, meaning it may break if dropped from the first floor or will not even break if dropped from 100 th floor.
3. Both eggs are identical. You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
4. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
* Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same values and same structure.
* Implement put/get methods of a fixed size cache with LRU replacement algorithm.
* You have to get from point A to point B. You don’t know if you can get there. What would you do?
* Write a function to determine whether a number is a power of two (used a bit-shifting based algorithm).
* Describe the stack ADT (abstract data type)- include functions and variables that might be useful.
* How would you design google maps
* Write a function that outputs an integer in ASCII format.
* (string class) What is the best and worst time for the operation 'equals'?
* (string class) How do you spe.ed up the 'equals' operation?
* Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
* Write some code to reverse a string.
* Describe an algorithm to find out if an integer is a square? (e.g. 16 is, 15 isn't)
* Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
* Implement division (without using the divide operator, obviously).
* Given a function that returns a random number between 1-5, write one that returns a random number between 1-7.
* Write a function (with helper functions if needed) called by Excel that takes an Excel column value (A,B,C,D… AA,AB,AC,… AAA…) and returns a corresponding integer value (A=1,B=2,… AA=27…).
* Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place! E.g.: "This is a sample" --> "sample a is This".
* How would you implement a stack to achieve constant time for "push", "pop" and "find mininum" operations?
* You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
* What should you consider when choosing a (sorting) alogrithm?
* Is it always better to use O(n log n) than O(n^2) (sorting) algorithm?
* There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find the heaviest stone?
* Order the functions in order of their asymptotic performance:
* What is the best and worst performance time for a hash tree and binary search tree?
* You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.
* How do you put a Binary Search Tree in an array in a efficient manner?
* Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN. Write an in-place algorithm to rearrange the elements of the array as A = i1 c1 i2 c2 ... in cn.
* How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
* Given a Binary Tree, programmatically can you prove it is a Binary Search Tree?
* Write a function to find the middle node of a single link list.
* Classic - Egg Problem
1. You are given 2 eggs. You have access to a 100-storey building.
2. Eggs can be very hard or very fragile, meaning it may break if dropped from the first floor or will not even break if dropped from 100 th floor.
3. Both eggs are identical. You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
4. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
* Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same values and same structure.
* Implement put/get methods of a fixed size cache with LRU replacement algorithm.
* You have to get from point A to point B. You don’t know if you can get there. What would you do?
* Write a function to determine whether a number is a power of two (used a bit-shifting based algorithm).
* Describe the stack ADT (abstract data type)- include functions and variables that might be useful.
* How would you design google maps
* Write a function that outputs an integer in ASCII format.
* (string class) What is the best and worst time for the operation 'equals'?
* (string class) How do you spe.ed up the 'equals' operation?
* Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
* Write some code to reverse a string.
* Describe an algorithm to find out if an integer is a square? (e.g. 16 is, 15 isn't)
* Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
Some more google interview questions
Google likes to ask tough interview questions. Some are just relating to the basics of computer science. Below are couple of typical Google interview questions.
1) Given a string of words separated by space char, expand the string to a certain length by adding more space chars inbetween the words. The space chars should be equally distributed as much as possible. method signature could be:
String expandStr(String s, int newLen) could be the method name.
Example: "abc de fg" (9 chars), could be expanded to "abc de fg"(11 chars)
2) Given the IMDB movie database and the following two API functions:
a. getAllMovies(String actorName)
b. getAllActors(String movieName)
Find out the degree of separation between two movie stars, such as Brad Pitt and Nicolas Cage
3) How to serialize a binary tree to a file? How to read the same file back to memory and re-construct the binary tree?
4) How to check if a string is partial reverse of the other string?
Example:
"abcdef" is partial reverse of "cdefab"
notice the original string is split into "ab" and "cdef" and put in reverse
"abcd" is partial reverse of "cdab"
notice the original string is split into "ab" and "cd" and put in reverse
To answer Google's tough interview questions, you first need to be calm and be focused on the interview question itself. Think about simple solutions first for that interview question. Then, find out optimized ways for solving the question.
During the interview process, be honest, don't panic. If you don't know the answer, just tell the interview person you don't know.
1) Given a string of words separated by space char, expand the string to a certain length by adding more space chars inbetween the words. The space chars should be equally distributed as much as possible. method signature could be:
String expandStr(String s, int newLen) could be the method name.
Example: "abc de fg" (9 chars), could be expanded to "abc de fg"(11 chars)
2) Given the IMDB movie database and the following two API functions:
a. getAllMovies(String actorName)
b. getAllActors(String movieName)
Find out the degree of separation between two movie stars, such as Brad Pitt and Nicolas Cage
3) How to serialize a binary tree to a file? How to read the same file back to memory and re-construct the binary tree?
4) How to check if a string is partial reverse of the other string?
Example:
"abcdef" is partial reverse of "cdefab"
notice the original string is split into "ab" and "cdef" and put in reverse
"abcd" is partial reverse of "cdab"
notice the original string is split into "ab" and "cd" and put in reverse
To answer Google's tough interview questions, you first need to be calm and be focused on the interview question itself. Think about simple solutions first for that interview question. Then, find out optimized ways for solving the question.
During the interview process, be honest, don't panic. If you don't know the answer, just tell the interview person you don't know.
Yet another Google interview experience
Below are some Google interview questions that someone got when conducting interviews with Google. Sharing below for my friends:
----
I had a phone interview with Google today. I took notes; some of the questions they asked were interesting. We were allowed to ask questions. The interviewer didn't ask many questions in response to my answers, except to occasionally say "interesting". There's almost certainly more than one answer to each of these, and a few are probably wrong answers or could be improved in some way; I only include my answers for comparison. Any intermediate questions that I asked for clarification or otherwise have been omitted.
Without further ado, a few of the more interesting ones:
Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"
(my answer): Take off all my clothes, wedge them between the blades and the floor to prevent it from turning. Back up against the edge of the blender until the electric motor overheats and burns out. Using the notches etched in the side for measuring, climb out. If there are no such notches or they're too far apart, retrieve clothes and make a rope to hurl myself out.
Q: "How would you find out if a machine's stack grows up or down in memory?"
(my answer): Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0. (If they're the same, you did something wrong!)
Q: "Explain a database in three sentences to your eight-year-old nephew."
(my answer): A database is a way of organizing information. It's like a genie who knows where every toy in your room is. Instead of hunting for certain toys yourself and searching the whole room, you can ask the genie to find all your toy soldiers, or only X-Men action figures, or only race cars -- anything you want.
Q: "How many gas stations would you say there are in the United States?"
(my answer): A business doesn't stick around for long unless it makes a profit. Let's assume that all gas stations in the US are making at least some profit over the long run. Assume that the number of people who own more than one car is negligibly small relative to the total American population. Figure that 20% of people are too young to drive a car, another 10% can't drive because of disability or old age, 5% of people use public transportation or carpool, another 5% choose not to drive, and another 5% of the cars are inventory sitting in lots or warehouses that a dealership owns but which no one drives.
There's about 280 million people in the US; subtracting 50%, that means there's about 140 million automobiles and 140 million drivers for them. The busiest city or interstate gas stations probably get a customer pulling in about twice a minute, or about 120 customers per hour; a slower gas station out in an agrarian area probably sees a customer once every 10 or 15 minutes, or about 4 customers per hour. Let's take a weighted average and suppose there's about one customer every 90 seconds, or about 40 customers an hour. Figuring a fourteen-hour business day (staying open from 7 AM to 9 PM), that's about 560 customers a day.
If the average gas station services 560 customers a day, then there are 250,000 gas stations in the US. This number slightly overstates the true number of gas stations because some people are serviced by more than one gas station. Actual number in 2003, according to the Journal of Petroleum Marketing: 237,284, an error of about 5%.
P.S. Apparently, if you make it to the next stage, you can't even tell people you're interviewing, because you sign a 6-page NDA. I haven't had to sign anything yet, though.
----
----
I had a phone interview with Google today. I took notes; some of the questions they asked were interesting. We were allowed to ask questions. The interviewer didn't ask many questions in response to my answers, except to occasionally say "interesting". There's almost certainly more than one answer to each of these, and a few are probably wrong answers or could be improved in some way; I only include my answers for comparison. Any intermediate questions that I asked for clarification or otherwise have been omitted.
Without further ado, a few of the more interesting ones:
Q: "You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?"
(my answer): Take off all my clothes, wedge them between the blades and the floor to prevent it from turning. Back up against the edge of the blender until the electric motor overheats and burns out. Using the notches etched in the side for measuring, climb out. If there are no such notches or they're too far apart, retrieve clothes and make a rope to hurl myself out.
Q: "How would you find out if a machine's stack grows up or down in memory?"
(my answer): Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0. (If they're the same, you did something wrong!)
Q: "Explain a database in three sentences to your eight-year-old nephew."
(my answer): A database is a way of organizing information. It's like a genie who knows where every toy in your room is. Instead of hunting for certain toys yourself and searching the whole room, you can ask the genie to find all your toy soldiers, or only X-Men action figures, or only race cars -- anything you want.
Q: "How many gas stations would you say there are in the United States?"
(my answer): A business doesn't stick around for long unless it makes a profit. Let's assume that all gas stations in the US are making at least some profit over the long run. Assume that the number of people who own more than one car is negligibly small relative to the total American population. Figure that 20% of people are too young to drive a car, another 10% can't drive because of disability or old age, 5% of people use public transportation or carpool, another 5% choose not to drive, and another 5% of the cars are inventory sitting in lots or warehouses that a dealership owns but which no one drives.
There's about 280 million people in the US; subtracting 50%, that means there's about 140 million automobiles and 140 million drivers for them. The busiest city or interstate gas stations probably get a customer pulling in about twice a minute, or about 120 customers per hour; a slower gas station out in an agrarian area probably sees a customer once every 10 or 15 minutes, or about 4 customers per hour. Let's take a weighted average and suppose there's about one customer every 90 seconds, or about 40 customers an hour. Figuring a fourteen-hour business day (staying open from 7 AM to 9 PM), that's about 560 customers a day.
If the average gas station services 560 customers a day, then there are 250,000 gas stations in the US. This number slightly overstates the true number of gas stations because some people are serviced by more than one gas station. Actual number in 2003, according to the Journal of Petroleum Marketing: 237,284, an error of about 5%.
P.S. Apparently, if you make it to the next stage, you can't even tell people you're interviewing, because you sign a 6-page NDA. I haven't had to sign anything yet, though.
----
Some Google Interview Questions
Google has tough interview questions for computer science graduates. You need to prepare with the following in mind:
1) Basic data structure and algorithms
2) Systems and networking knowledge (operating systems, database systems, computer network...)
Below are some google interview questions to give you an idea of what they are interviewing you with.
#1. Given a number, describe an algorithm to find the next number which is prime.
#2. There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find out the heaviest stone?
Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If the pan is remains balanced, the heavier is in the remaining (2). use pan again to find which is heavy from (2). (Total pan use 2)
If the pan does not remain balanced when weighing (3,3), pick the set of stones that outweigh other. Divide it into (1,1,1). use pan to weigh first two. It it remains balanced, the remaining stone is the heavier, otherwise the one outweighing other is heavier(total pan use 2)
#3. Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
Answer:
n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n
#4. what is the best and worst performance time for a hash tree and binary search tree?
Answer:
Best is O(c), worst is O(log n)
#5. Questions regarding a string Class
* What do you need when you instantiate a string ( i said a byte array and possibly the length) ?
* What is the best and worst time for the operation 'equals'
* How do you spedup the 'equals' operation (i said used hash MD5 for example)
This still has some problem ( a hash can be the same for unequal strings)
-> Use Boyer–Moore string search algorithm => O(n)
#6. Trade offs between a multi threaded and single threaded implementation?
#7. N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
#8. There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.
For example, let consider (6, 3, 1, 2). We need to find these products:
6 * 3 * 1 = 18
6 * 3 * 2 = 36
3 * 1 * 2 = 6
6 * 1 * 2 = 12
last one is simple
int mul = 1;
for i = 1 to N
mul *=a[i];
for i= 1 to N
a[i] = mul/a[i];
(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this.
Here's the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output
for (int i = 1; i <= n; i++)
{
if (i == 1)
print x[2,n];
else if (i == n)
print x[1,n-1];
else
print x[1,i-1] * x[i+1,n];
}
To build the table, start along the diagonal (x[i,i] = ni). Then do successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k+1]).
#9. Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort
#10. If you had a million integers how would you sort them and how much memory would that consume?
Binary tree - requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB
Insertion sort - can be done in under 4 MB
#11. Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn't.
a) simple answer - start at 2 and divide the integer by each successive value. If it divides evenly before you reach half way then it is.
b) complex answer after much leading - Do the bitwise AND of n and (n-1). If it is zero then it is a square (I think this is wrong. This actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
C)
i=2;
while(!NO)
{
if((i*i)==Number)
{
NO;
return True;
}
if((i*i)>Number)
{
NO;
return false;
}
i++;
}
#12. How would you determine if adwords was up and running and serving contextual content?
#13. Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
#14. Write some code to reverse a string.
#15. Implement division (without using the divide operator, obviously).
#16. Write some code to find all permutations of the letters in a particular string.
#17. You have to get from point A to point B. You don’t know if you can get there. What would you do?
#18. What method would you use to look up a word in a dictionary?
#19. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
#20. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?
#21. Phone interview
1. Describe the data structure that is used to manage memory. (stack)
2. whats the difference between local and global variables?
3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
4. In Java, what is the difference between static, final, and const. (if you dont know java they will ask something similar for C or C++).
5. Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
#22. In person interview (1)
1. In Java, what is the difference between final, finally, and finalize?
2. What is multithreaded programming? What is a deadlock?
3. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
4. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
5. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
6. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/Google_Interview_Questions"
#23. In person interview (1)
1. How many golf balls can fit in a school bus? This is a Fermi question.
2. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
3. How much should you charge to wash all the windows in Seattle?
4. How would you find out if a machine’s stack grows up or down in memory?
5. Explain a database in three sentences to your eight-year-old nephew.
6. How many times a day does a clock’s hands overlap?
7. You have to get from point A to point B. You don’t know if you can get there. What would you do?
8. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
9. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
10. In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
11. If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
12. If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
13. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
14. You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
15. How many piano tuners are there in the entire world?
16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
1) Basic data structure and algorithms
2) Systems and networking knowledge (operating systems, database systems, computer network...)
Below are some google interview questions to give you an idea of what they are interviewing you with.
#1. Given a number, describe an algorithm to find the next number which is prime.
#2. There are 8 stones which are similar except one which is heavier than the others. To find it, you are given a pan balance. What is the minimal number of weighing needed to find out the heaviest stone?
Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If the pan is remains balanced, the heavier is in the remaining (2). use pan again to find which is heavy from (2). (Total pan use 2)
If the pan does not remain balanced when weighing (3,3), pick the set of stones that outweigh other. Divide it into (1,1,1). use pan to weigh first two. It it remains balanced, the remaining stone is the heavier, otherwise the one outweighing other is heavier(total pan use 2)
#3. Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
Answer:
n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n
#4. what is the best and worst performance time for a hash tree and binary search tree?
Answer:
Best is O(c), worst is O(log n)
#5. Questions regarding a string Class
* What do you need when you instantiate a string ( i said a byte array and possibly the length) ?
* What is the best and worst time for the operation 'equals'
* How do you spedup the 'equals' operation (i said used hash MD5 for example)
This still has some problem ( a hash can be the same for unequal strings)
-> Use Boyer–Moore string search algorithm => O(n)
#6. Trade offs between a multi threaded and single threaded implementation?
#7. N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
#8. There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers.
For example, let consider (6, 3, 1, 2). We need to find these products:
6 * 3 * 1 = 18
6 * 3 * 2 = 36
3 * 1 * 2 = 6
6 * 1 * 2 = 12
last one is simple
int mul = 1;
for i = 1 to N
mul *=a[i];
for i= 1 to N
a[i] = mul/a[i];
(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this.
Here's the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output
for (int i = 1; i <= n; i++)
{
if (i == 1)
print x[2,n];
else if (i == n)
print x[1,n-1];
else
print x[1,i-1] * x[i+1,n];
}
To build the table, start along the diagonal (x[i,i] = ni). Then do successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k+1]).
#9. Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort
#10. If you had a million integers how would you sort them and how much memory would that consume?
Binary tree - requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB
Insertion sort - can be done in under 4 MB
#11. Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn't.
a) simple answer - start at 2 and divide the integer by each successive value. If it divides evenly before you reach half way then it is.
b) complex answer after much leading - Do the bitwise AND of n and (n-1). If it is zero then it is a square (I think this is wrong. This actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
C)
i=2;
while(!NO)
{
if((i*i)==Number)
{
NO;
return True;
}
if((i*i)>Number)
{
NO;
return false;
}
i++;
}
#12. How would you determine if adwords was up and running and serving contextual content?
#13. Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
#14. Write some code to reverse a string.
#15. Implement division (without using the divide operator, obviously).
#16. Write some code to find all permutations of the letters in a particular string.
#17. You have to get from point A to point B. You don’t know if you can get there. What would you do?
#18. What method would you use to look up a word in a dictionary?
#19. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
#20. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?
#21. Phone interview
1. Describe the data structure that is used to manage memory. (stack)
2. whats the difference between local and global variables?
3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
4. In Java, what is the difference between static, final, and const. (if you dont know java they will ask something similar for C or C++).
5. Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
#22. In person interview (1)
1. In Java, what is the difference between final, finally, and finalize?
2. What is multithreaded programming? What is a deadlock?
3. Write a function (with helper functions if needed) called toExcel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
4. You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
5. Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
6. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/Google_Interview_Questions"
#23. In person interview (1)
1. How many golf balls can fit in a school bus? This is a Fermi question.
2. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
3. How much should you charge to wash all the windows in Seattle?
4. How would you find out if a machine’s stack grows up or down in memory?
5. Explain a database in three sentences to your eight-year-old nephew.
6. How many times a day does a clock’s hands overlap?
7. You have to get from point A to point B. You don’t know if you can get there. What would you do?
8. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
9. Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
10. In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
11. If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
12. If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
13. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
14. You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
15. How many piano tuners are there in the entire world?
16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
17. You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
Saturday, May 1, 2010
美国交通事故违章罚款上法庭经验谈
以下转载网上看到的一篇文章:
刚从国内来的朋友因违章超车吃了ticket，需要记点加罚款，一时间胆小的他成了热锅上的蚂蚁，不知所措。那些想挣他钱的律师更是添乱，即不停地给他的住处送广告信，信的内容不外是可以代他庭，免除记点，但前提是先将多少美元打入他们的帐户或是给他们credit card #。胆小的朋友有点不干心，而找本人商量，可本人虽然一向调皮，但也没有这方便的经历与经验，一天一个偶然的机会我认识了一位在state farm做agent的朋友，结果她给我们指明了前进的方向，即有时间本人出庭就可以了，这样一可省去律师费，二则可在交完罚款后向法官要一张 PJC（注：凭此证可以免除记点，保险公司不会提升你个人的车保费，该证发放依据是本州法律，即一个家庭在三年内有一次赦免的机会），天底下既然有这等好，我们就决定亲自出庭，顺便也长点见识！出庭那天，因怕误点我们特意起了个大早来到法庭外排队，刚站稳脚根，身后就陆续来了大队人马，其中大多数是黑人朋友，亦有相当一部分是阿密哥，这我才意识到今天是个集中出庭的日子，可能是法庭为了工作上的方便集中处理交通违章案件。安检后进入法庭，工作人员命令大家贴着墙根一字排队，以好一一验证来者身份，并按违章类别将大家分成若干小组，以听候处理。被验证身份后，我有时间来作点调查、统计和观察，并得出如下结论：
1、按种族分类，60%左右的违章是黑哥们或黑大婶，35%是阿密哥，其它是white和yellow（就我们两人）等。
2、从外表看，黑人朋友大多理着光头，身材臃肿，脖子上几乎都有一条粗大的金项链，双耳插着ipod，嘴巴还在不停的抖动，长长的T 恤向下延伸至双侧膝关节以下。再看阿密哥，一个个体态健壮，除了脖子粗短一点，人人都有一头乌黑、致密而坚硬的头发，这预示着他们的肾都很强壮，故有着其它人没有的生育能力，并且他们都用厚厚的磨丝将乌黑的头发疏理得溜光，如果你不了解他们的来历，你绝不会相信他们大多来自周围的建筑工地，甚至连一纸证明自己身份的公文都没有。白人兄弟虽然大多已经秃顶，体态也大多丰满、硕大，但脸庞上还是看得出有几份自信、几份精神。至于我俩是一个什么样的形象，俺在此不想过多描述，再则大家心里也都清楚…..
3、从工作效率看，法庭人员的素质极佳、效率挺高，他们就三个人，仅用了一个小时多一点点的时间就将二百多号人查验完毕，整个过程非常有序，显得忙而不乱，特别是他个点名的黑小伙，非常合理地利用他那特有男中音点名，使得大家完全没有在出庭时的感觉，似乎是在听美声！当时我就想如果咱们的USCIS，特别是FBI这般爷们如果有这么个效率多好，咱们还用等吗？
4、从法庭的运作形式，你可以看得出法官的地位是何等高呢？我想这就是权力或权威的象征吧？因为，法庭的普通工作人员将出庭者点验、分组完毕后，身着黑袍法官大人才正式的姗姗来迟，尽管他步态不稳，可全体人员必须起立，就差奏乐和仪仗队了，待他那老朽的身躯落坐在那大大的皮革椅子后，其它人才允许坐下，我心想难怪他那么老了还不想退休？这感觉多好？
5、从过堂的形式看，咱们黄人仍然受歧视，别忘了咱们可是合法来到这里呀！当一众人马一一过堂，渐渐的让我生气的事情就冒出来了！为何？因为那些illegal的阿密哥大多不会说英文，可这又何妨？人家法庭早已给他们备好了翻译！他们一个个过堂时就像国家领导人出访那样，备有专职翻译！并且还是长得挺甜的小白妞！同胞们，你说这气不气人？最后，我灵机一动，计上心来，我告诉我朋友，轮到你，你就说因为刚来只能听懂一点点英语，更不会说，但能认！看他们如何是好？朋友一开始不肯接受我的建议，因为他害怕，随后他又突然变得勇敢起来了，为何？因为他越想越生气，NND！老子在国内开在左边都没有人管，咋在美国开在右边还要被罚款？终于轮到朋友，好戏也就开始了，法官怎么陈述他如何违章，老兄就是不开口认罪，一副呆诺木鸡的样子死死的站在被告席上，最后一旁的工作人员问他为什么？他用中文说“我听不懂英语，只能认”，cool！可法官也不是省油的灯，说道： “你不是有一个兄弟同你一块来的吗，那把他请帮忙！”朋友说：“不用了，他的英文比我还差，要不他不早就站在这里了吗？”没有办法，法庭为此延误了不少时间，随后只好书记将事件经过写在纸上，让朋友看后划押。
6、上帝送给的礼物，交罚款时，有趣的事情又冒出来了，因为原先警察开的罚单是一百六十美元，可柜台内的那个黑小妞只肯收下一百二十美元，个中原因俺不知道，难道是那小妞数学太差！傻乎乎的老兄这个时候又良心发现了，拼命argue为何不是一百六呢，而是一百二，俺真不明白他的脑子？你不是想省点，又咋啦？我扯了扯他的衣角，老兄总算是明白了，交钱走人。我们正离开时，柜台内的小妞还说：“That’s all over，bye”。
从法庭出来后，我问朋友，心里好受一点没？他说舒服多了！我说为何呢？他说至少省了一百律师费，又少交了四十美元的罚款，还顺便出了一口气，多好？接着他说：“这得感谢大哥你！”俺说：“我还得好好谢你呢，否则俺哪有这么个好机会，见世见世美国的法官大人，并且还颇有收获！只是以后你老兄记得别把国内如何如何带来美国来就是了。”老兄回答说：“记住了”，就坐在驾驶位去了，我敢忙说：“你还是让我来开吧？否则一高兴，又不知道弄出点什么明堂来?"
刚从国内来的朋友因违章超车吃了ticket，需要记点加罚款，一时间胆小的他成了热锅上的蚂蚁，不知所措。那些想挣他钱的律师更是添乱，即不停地给他的住处送广告信，信的内容不外是可以代他庭，免除记点，但前提是先将多少美元打入他们的帐户或是给他们credit card #。胆小的朋友有点不干心，而找本人商量，可本人虽然一向调皮，但也没有这方便的经历与经验，一天一个偶然的机会我认识了一位在state farm做agent的朋友，结果她给我们指明了前进的方向，即有时间本人出庭就可以了，这样一可省去律师费，二则可在交完罚款后向法官要一张 PJC（注：凭此证可以免除记点，保险公司不会提升你个人的车保费，该证发放依据是本州法律，即一个家庭在三年内有一次赦免的机会），天底下既然有这等好，我们就决定亲自出庭，顺便也长点见识！出庭那天，因怕误点我们特意起了个大早来到法庭外排队，刚站稳脚根，身后就陆续来了大队人马，其中大多数是黑人朋友，亦有相当一部分是阿密哥，这我才意识到今天是个集中出庭的日子，可能是法庭为了工作上的方便集中处理交通违章案件。安检后进入法庭，工作人员命令大家贴着墙根一字排队，以好一一验证来者身份，并按违章类别将大家分成若干小组，以听候处理。被验证身份后，我有时间来作点调查、统计和观察，并得出如下结论：
1、按种族分类，60%左右的违章是黑哥们或黑大婶，35%是阿密哥，其它是white和yellow（就我们两人）等。
2、从外表看，黑人朋友大多理着光头，身材臃肿，脖子上几乎都有一条粗大的金项链，双耳插着ipod，嘴巴还在不停的抖动，长长的T 恤向下延伸至双侧膝关节以下。再看阿密哥，一个个体态健壮，除了脖子粗短一点，人人都有一头乌黑、致密而坚硬的头发，这预示着他们的肾都很强壮，故有着其它人没有的生育能力，并且他们都用厚厚的磨丝将乌黑的头发疏理得溜光，如果你不了解他们的来历，你绝不会相信他们大多来自周围的建筑工地，甚至连一纸证明自己身份的公文都没有。白人兄弟虽然大多已经秃顶，体态也大多丰满、硕大，但脸庞上还是看得出有几份自信、几份精神。至于我俩是一个什么样的形象，俺在此不想过多描述，再则大家心里也都清楚…..
3、从工作效率看，法庭人员的素质极佳、效率挺高，他们就三个人，仅用了一个小时多一点点的时间就将二百多号人查验完毕，整个过程非常有序，显得忙而不乱，特别是他个点名的黑小伙，非常合理地利用他那特有男中音点名，使得大家完全没有在出庭时的感觉，似乎是在听美声！当时我就想如果咱们的USCIS，特别是FBI这般爷们如果有这么个效率多好，咱们还用等吗？
4、从法庭的运作形式，你可以看得出法官的地位是何等高呢？我想这就是权力或权威的象征吧？因为，法庭的普通工作人员将出庭者点验、分组完毕后，身着黑袍法官大人才正式的姗姗来迟，尽管他步态不稳，可全体人员必须起立，就差奏乐和仪仗队了，待他那老朽的身躯落坐在那大大的皮革椅子后，其它人才允许坐下，我心想难怪他那么老了还不想退休？这感觉多好？
5、从过堂的形式看，咱们黄人仍然受歧视，别忘了咱们可是合法来到这里呀！当一众人马一一过堂，渐渐的让我生气的事情就冒出来了！为何？因为那些illegal的阿密哥大多不会说英文，可这又何妨？人家法庭早已给他们备好了翻译！他们一个个过堂时就像国家领导人出访那样，备有专职翻译！并且还是长得挺甜的小白妞！同胞们，你说这气不气人？最后，我灵机一动，计上心来，我告诉我朋友，轮到你，你就说因为刚来只能听懂一点点英语，更不会说，但能认！看他们如何是好？朋友一开始不肯接受我的建议，因为他害怕，随后他又突然变得勇敢起来了，为何？因为他越想越生气，NND！老子在国内开在左边都没有人管，咋在美国开在右边还要被罚款？终于轮到朋友，好戏也就开始了，法官怎么陈述他如何违章，老兄就是不开口认罪，一副呆诺木鸡的样子死死的站在被告席上，最后一旁的工作人员问他为什么？他用中文说“我听不懂英语，只能认”，cool！可法官也不是省油的灯，说道： “你不是有一个兄弟同你一块来的吗，那把他请帮忙！”朋友说：“不用了，他的英文比我还差，要不他不早就站在这里了吗？”没有办法，法庭为此延误了不少时间，随后只好书记将事件经过写在纸上，让朋友看后划押。
6、上帝送给的礼物，交罚款时，有趣的事情又冒出来了，因为原先警察开的罚单是一百六十美元，可柜台内的那个黑小妞只肯收下一百二十美元，个中原因俺不知道，难道是那小妞数学太差！傻乎乎的老兄这个时候又良心发现了，拼命argue为何不是一百六呢，而是一百二，俺真不明白他的脑子？你不是想省点，又咋啦？我扯了扯他的衣角，老兄总算是明白了，交钱走人。我们正离开时，柜台内的小妞还说：“That’s all over，bye”。
从法庭出来后，我问朋友，心里好受一点没？他说舒服多了！我说为何呢？他说至少省了一百律师费，又少交了四十美元的罚款，还顺便出了一口气，多好？接着他说：“这得感谢大哥你！”俺说：“我还得好好谢你呢，否则俺哪有这么个好机会，见世见世美国的法官大人，并且还颇有收获！只是以后你老兄记得别把国内如何如何带来美国来就是了。”老兄回答说：“记住了”，就坐在驾驶位去了，我敢忙说：“你还是让我来开吧？否则一高兴，又不知道弄出点什么明堂来?"
许多英文网站比中文网站对于反向链接更加友好
我知道的很多海外中文网站都很小气，比如说mitbbs或者huaren.us，国内的网站我不熟悉，不便评论了。很多网站不喜欢给人家提供链接。这个可以理解。但，对于一些老用户，这些网站也是一视同仁的不给与外链的机会。
而相比之下，英文网站就比较好。很多都允许在签名档加链接到自己的网站。或者相关话题里面可以加链接到自己的网站。
我觉得造成这个现象的原因可能是中文网站比较惧怕垃圾信息。而很多英文网站因为管理的好，所以，内容比较干净而且质量高。所以，才可以提供一些外链的机会。
总之，我现在感觉在中文网站上发文章或者话题啥的没有什么动力了。因为带不来啥好的链接到这个站点。所以，干脆多光顾英文网站，发表一些好的文章内容，然后带流量回到这个网站。
而相比之下，英文网站就比较好。很多都允许在签名档加链接到自己的网站。或者相关话题里面可以加链接到自己的网站。
我觉得造成这个现象的原因可能是中文网站比较惧怕垃圾信息。而很多英文网站因为管理的好，所以，内容比较干净而且质量高。所以，才可以提供一些外链的机会。
总之，我现在感觉在中文网站上发文章或者话题啥的没有什么动力了。因为带不来啥好的链接到这个站点。所以，干脆多光顾英文网站，发表一些好的文章内容，然后带流量回到这个网站。
美国网址大全大全
最近查看了一下美国网址导航站，太多了。所谓的美国网址大全，基本上都是包罗万象，啥都有，不止是美国网址，连国内的网址都有，挺可笑的。下面是一些网址大全，关于美国的，基本上都是眼花缭乱:
美国网址大全|美国网站大全|美国网址导航|美国购物网址大全|美国生活
www.best918.com
美国网址大全
www.v1122.com/us/index.htm
美国网址大全_87871世界网址大全
这个搞笑，除了美国网址，还搞个世界网址大全，搞的过来吗？？
www.87871.com/us/index.htm
美国网址大全-美国在线|Myspace|YouTube|Lycos|哈佛大学|洛杉矶时报
www.world68.com/America.asp
美国网址导航--美国123网址大全--美国网址大全
www.meiguo123.net/
美国网址大全|云集世界网址导航|世界各国网址大全
yunji.ca/html/USA.html
等等。
这些网址大全网站，我都不知道谁会去看。特别是大而全的那种，貌似没有啥特色。
我最近也收录了一些网站，但都是我经常访问的，或者是我知道的。不是啥都往上放的那种美国网站. 虽然不多，但感觉比上述所谓的网址大全感觉要更加平易近人多啦。链接在这里: 美国实用网站
有朋友有建议的，可以加评论.
美国网址大全|美国网站大全|美国网址导航|美国购物网址大全|美国生活
www.best918.com
美国网址大全
www.v1122.com/us/index.htm
美国网址大全_87871世界网址大全
这个搞笑，除了美国网址，还搞个世界网址大全，搞的过来吗？？
www.87871.com/us/index.htm
美国网址大全-美国在线|Myspace|YouTube|Lycos|哈佛大学|洛杉矶时报
www.world68.com/America.asp
美国网址导航--美国123网址大全--美国网址大全
www.meiguo123.net/
美国网址大全|云集世界网址导航|世界各国网址大全
yunji.ca/html/USA.html
等等。
这些网址大全网站，我都不知道谁会去看。特别是大而全的那种，貌似没有啥特色。
我最近也收录了一些网站，但都是我经常访问的，或者是我知道的。不是啥都往上放的那种美国网站. 虽然不多，但感觉比上述所谓的网址大全感觉要更加平易近人多啦。链接在这里: 美国实用网站
有朋友有建议的，可以加评论.
Tuesday, April 27, 2010
Content Website Ad Revenue
Here is what I learned today:
http://dailyconversions.com/all-posts/content-website-ad-revenue/
http://dailyconversions.com/all-posts/content-website-ad-revenue/
Monday, April 26, 2010
Google Gmail's Great Customer Service, Freaking Awesome!!!
Google is freaking awesome!!
I tried to send an email out using gmail with attachment file. However, after I wrote the email, I forgot to attach the file and clicked on send button. Then I saw a popup alert, asking me if I really want to send the email 'cause I haven't attached anything but I said I would attach.
Boy, they are good at these little things. That's great customer service to learn ;-)
---
Opinion expressed by JiansNet.com, an ecommerce shopping site
I tried to send an email out using gmail with attachment file. However, after I wrote the email, I forgot to attach the file and clicked on send button. Then I saw a popup alert, asking me if I really want to send the email 'cause I haven't attached anything but I said I would attach.
Boy, they are good at these little things. That's great customer service to learn ;-)
---
Opinion expressed by JiansNet.com, an ecommerce shopping site
Sunday, April 25, 2010
More Hot Deals and eCommerce related Topics Coming to JiansNet.com
Since I am in the area of eCommerce web development, it is natural that I would focus more on eCommerce and related topics, such as hot deals, coupons, ecommerce website reviews, etc.
I believe this will make JiansNet eCommerce more focused and be more relevant to the users.
I believe this will make JiansNet eCommerce more focused and be more relevant to the users.
Monday, April 5, 2010
The wiki released for a demo use
Recently I've worked on a very simple wiki software as a programming practice, together with another friend. The wiki is pretty much ready and now we've released it to production usage on JiansNet.com here:
JiansNet Wiki
I hope this would be used as a test bed and a good SEO tool for content generation. If anyone is interested in this simple wiki tool, shoot me an email at jiansnet@gmail.com , there might be some collaboration for using this for a better user experience for your website.
JiansNet Wiki
I hope this would be used as a test bed and a good SEO tool for content generation. If anyone is interested in this simple wiki tool, shoot me an email at jiansnet@gmail.com , there might be some collaboration for using this for a better user experience for your website.
Subscribe to:
Posts (Atom)