- Why do you want to join Google?
- What do you know about Google’s product and technology?
- If you are Product Manager for Google’s Adwords, how do you plan to market this?
- What would you say during an AdWords or AdSense product seminar?
- Who are Google’s competitors, and how does Google compete with them?
- Have you ever used Google’s products? Gmail?
- What’s a creative way of marketing Google’s brand name and product?
- If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?
- How much money you think Google makes daily from Gmail ads?
- Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.
- Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?
- Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.
Friday, August 31, 2012
Google Interview Questions: Product Marketing Manager
Monday, August 20, 2012
Amazon Interview question
Amazon interview questions:
Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can?t pass the value k to any function also.
What are the 4 basics of OOP?
Define Data Abstraction. What is its importance?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren?t present.
Given a string,find the first un-repeated character in it? Give some test cases
You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
What is a C array and illustrate the how is it different from a list.
What is the time and space complexities of merge sort and when is it preferred over quick sort?
Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
Explain polymorphism. Provide an example.
Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can?t pass the value k to any function also.
What are the 4 basics of OOP?
Define Data Abstraction. What is its importance?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren?t present.
Given a string,find the first un-repeated character in it? Give some test cases
You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
What is a C array and illustrate the how is it different from a list.
What is the time and space complexities of merge sort and when is it preferred over quick sort?
Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
Explain polymorphism. Provide an example.
Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
Amazon Interview Question
Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this difference should be least possible Minimum.. Hope the problem is clear :) :)
Sample:
N=3, K=3
N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100
here if 16, 17, 15 are chosen.. we get the minimum difference as 17-15=2.
Amazon Interview question
A random link list is a linked list where every node contains 2 links, one like a normal node which points to the next node. The other link points to a random node in the list, even itself. You are to write a function to perform a deep copy of this random link list.
Amazon Telephonic interview
Amazon Interview Round 2
The second round was also telephonic. It went for almost 1.5 hours though scheduled for one hour. The main reason for that i think is that i was solving questions and each time i was asked to re-look at the solution I used to improve it further.
Question 1: Shuffle pack of cards
Solution 1: It is one of the most common questions that are being asked in Amazon (Though I came to know this only after the interview:-D). I started with using Sets again but the complexity turned out to be very bad. I assumed that there is a random function with time complexity O(1) and I call this random function to get values from 1...52. Once i get that random function i will add that value in a SET. So in end I will have all the numbers from 1...52 in a random fashion. The catch in my solution was that if the random function returns number x, m times than for each number we will call this function m times and for 52 numbers it will be (m power 52). This is huge. I tried giving another solution but was no better. In the end he moved to next question. Check out here for solution.
Question 2: Count number of lines, characters and words in a file (Given that we don’t have much access to flashy java methods like readline, String methods like indexOf etc.)
Solution 2: The constraint given above simply means that one has to read character by character. I started with a basic program of reading character by character and passing that character to switch statement and doing some logic when ever i got ' ' , '\t', '\n','\r' . But the problem with this solution was that whenever i used to get some odd input like empty file, a file with just '\n' or a file with just a space then i used to patch my earlier solution. Then as i was giving solutions to problems i was asked if I could store some "state". I tokk that lead and provided another solution: -
Store a "state" variable. i.e. when ever a NON- special character (i.e. character apart from ‘ ‘ , ‘\n’ , ‘\r’, ‘\t’ , EOF comes then make the state 0. Whenever a special character comes make state 1. So whenever we go from state 0 to 1. Increase word count. Whenever we get \n or EOF we increase line count. And each time we increase character count.
After this solution no clarification was asked for.
Question 3: Write USE case for Auction model where you have a seller, an item and a buyer.
Solution: This was more generic design question and was just asked to write use-case. Not seq diagram etc.
Learning points 1: Have a nice grip on time complexity. They will make you calculate for each of the solutions you give.
Learning points 2: Concentrate real hard for that 1.5 hours and if you are not clear of the problem then don't hesitate in asking it again.
Learning points 3: You will be asked to write proper code.(even you will be asked to communicate the same through phone)
Learning points 4: The questions will be very generic and never specific to some language.
Learning point 5: Used a variety of test cases to check one's solution before presenting the same to interviewer.
Question 1: Shuffle pack of cards
Solution 1: It is one of the most common questions that are being asked in Amazon (Though I came to know this only after the interview:-D). I started with using Sets again but the complexity turned out to be very bad. I assumed that there is a random function with time complexity O(1) and I call this random function to get values from 1...52. Once i get that random function i will add that value in a SET. So in end I will have all the numbers from 1...52 in a random fashion. The catch in my solution was that if the random function returns number x, m times than for each number we will call this function m times and for 52 numbers it will be (m power 52). This is huge. I tried giving another solution but was no better. In the end he moved to next question. Check out here for solution.
Question 2: Count number of lines, characters and words in a file (Given that we don’t have much access to flashy java methods like readline, String methods like indexOf etc.)
Solution 2: The constraint given above simply means that one has to read character by character. I started with a basic program of reading character by character and passing that character to switch statement and doing some logic when ever i got ' ' , '\t', '\n','\r' . But the problem with this solution was that whenever i used to get some odd input like empty file, a file with just '\n' or a file with just a space then i used to patch my earlier solution. Then as i was giving solutions to problems i was asked if I could store some "state". I tokk that lead and provided another solution: -
Store a "state" variable. i.e. when ever a NON- special character (i.e. character apart from ‘ ‘ , ‘\n’ , ‘\r’, ‘\t’ , EOF comes then make the state 0. Whenever a special character comes make state 1. So whenever we go from state 0 to 1. Increase word count. Whenever we get \n or EOF we increase line count. And each time we increase character count.
After this solution no clarification was asked for.
Question 3: Write USE case for Auction model where you have a seller, an item and a buyer.
Solution: This was more generic design question and was just asked to write use-case. Not seq diagram etc.
Learning points 1: Have a nice grip on time complexity. They will make you calculate for each of the solutions you give.
Learning points 2: Concentrate real hard for that 1.5 hours and if you are not clear of the problem then don't hesitate in asking it again.
Learning points 3: You will be asked to write proper code.(even you will be asked to communicate the same through phone)
Learning points 4: The questions will be very generic and never specific to some language.
Learning point 5: Used a variety of test cases to check one's solution before presenting the same to interviewer.
Saturday, August 18, 2012
Amazon Interview questions
Interviewed in Bangalore (India) (Jun 2012 - took 1+ week)
Recruiter reached me with a schedule in a weekend for f2f interview. I think around 20 candidates were there. Had 4 rounds of technical discussions in a day. Each took 45minutes to 1hour. Mostly targeted with 2 major questions per round. If you totally mess up in one round, don't worry you might get another round as a chance.
Think in broad way. Avoid brute-force approach and give the best solution u think in the beginning itself. If you think about multiple efficient solutions explain all of them briefly. And explain the complexities (time/space).
Practice writing code in a paper. Interviewers will need it for reference and they'll take notes during your interview (they might be typing while you explain). You can ask them to stop it if it disturbs you. Its easy if you practice data structures and algorithms.
Think in broad way. Avoid brute-force approach and give the best solution u think in the beginning itself. If you think about multiple efficient solutions explain all of them briefly. And explain the complexities (time/space).
Practice writing code in a paper. Interviewers will need it for reference and they'll take notes during your interview (they might be typing while you explain). You can ask them to stop it if it disturbs you. Its easy if you practice data structures and algorithms.
Interview Questions
You have a list of sentences/words. How to find out the sub list that consists of a specific prefix?
Ex:
input: prefix="he", list = ["hello", "world", "hello world", "hey dude", "galaxy"....]
output: ["hello", "hello world", "hey dude"]
Ex:
input: prefix="he", list = ["hello", "world", "hello world", "hey dude", "galaxy"....]
output: ["hello", "hello world", "hey dude"]
Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab, aac.... aax, aaz, aba, abc... (Its same as excel column names).
Given an integer (n), generate n-th string from the above sequence.
Ps: Don't generate the full list of sequence till n. It'll be definitely bad approach :)
Given an integer (n), generate n-th string from the above sequence.
Ps: Don't generate the full list of sequence till n. It'll be definitely bad approach :)
Find the intersection of two array of integers.
Design a system and API that should support 50 instances of custom designed Queue. Basically the question is about how you'll make use the given block of memory, to achieve the above requirement.
How would you design a "recommended products for you" module of amazon.com. Design a zoo.
Find whether the strings in a file are anagrams
Write a program to check whether a binary tree is a binary search tree
Find whether the strings in a file are anagrams
Write a program to check whether a binary tree is a binary search tree
Negotiation Details
I got the package that I asked :)
Other Details
I got the interview through a Recruiter and the interview consisted of a Phone Interview, a 1:1 Interview,a Skills Test, a Personality Test and a Background Check.
Amazon Interview Experience
My resume was given to Amazon by a search firm. I got a call from Amazon Chennai office Recruiter and was told about the job profile and the interview rounds. I had two phone rounds, first with the Sr.Manager-HR, based at Hyderabad office, to which the position would report. This interview happened as per schedule, except for 15 mins delay. Lots of situation based questions and team issues handling, managing a team, mix of FTEs and Contractors, How would you rate a campus, planning skills etc. I got instant call from Chennai HR of Amazon after my first phone interview that I will have one more phone interview, next day at 11.00 am. Next day, I did not get any call till 11.25 am and then I mailed the Amazon Chennai Recruiter, who checked with the interviewer and came back after 2 hours that I will have a call in the evening as the interviewer got busy with some urgency. This call was also situation based but as this position was a replacement for her position, she was a realistic interviewer. Again, mostly campus experience based questions, planning, team management. This was the most engaging interview and I realised, I spoke to someone, well cultured, who respects candidates and was aware of corporate image of Amazon. I got feedback from Chennai Recruiter and was asked to visit Amazon, Hyderabad and Chennai offices in next 2 days; schedule was sent that had plans and details of interviewers, title, location, interview time, all details to perfection. This plan had even details of final interview at Amazon, Bangalore as well with Head of HR and GM- Operations.
Amazon Interview questions
1. Classify the Hashing Functions based on the various methods by which the key value is found
2. Common multipleQ: Given two numbers m and n, write a method to return the first number r that isdivisible by both (e.g., the least common multiple).
3. Array of sizeGiven an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?
4. Missing numberGiven an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
5. Denominations of coinsYou are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
6. Maximum sumGiven an array all of whose elements are positive numbers, find the maximum sum of a subsequent elements with the constraint that no 2 numbers in the sequence should be adjacent in the array. So, 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
7. Convert a decimal numberHow do you convert a decimal number to its hexa-decimal equivalent. Give a C code to do so.
8. Array of size nGiven an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
2. Common multipleQ: Given two numbers m and n, write a method to return the first number r that isdivisible by both (e.g., the least common multiple).
3. Array of sizeGiven an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?
4. Missing numberGiven an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
5. Denominations of coinsYou are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
6. Maximum sumGiven an array all of whose elements are positive numbers, find the maximum sum of a subsequent elements with the constraint that no 2 numbers in the sequence should be adjacent in the array. So, 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
7. Convert a decimal numberHow do you convert a decimal number to its hexa-decimal equivalent. Give a C code to do so.
8. Array of size nGiven an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
Amazon Interview questions
- Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can’t pass the value k to any function also.
- What are the 4 basics of OOP?
- Define Data Abstraction. What is its importance?
- Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
- Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.
- Given a string,find the first un-repeated character in it? Give some test cases
- You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
- Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
- What is a C array and illustrate the how is it different from a list.
- What is the time and space complexities of merge sort and when is it preferred over quick sort?
- Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
- Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
- Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
- Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
- How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
- Explain polymorphism. Provide an example.
- Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
- You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
- Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
Top 5 Google Interview Questions
Google Interview Questions 1 : 2 Eggs 100 Floors Puzzle
Difficulty ★★★★★ Popularity ★★★★★
-> You are given 2 eggs.
-> You have access to a 100-storey building.
-> Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
-> You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
-> Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
==============================================
Google Interview Questions 2 : Weighing Balance Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
You can place weights on both side of weighing balance and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
==============================================
Google Interview Questions 3 : Cross Bridge Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
==============================================
Google Interview Questions 4 : Google Interview Riddle
Difficulty ★★★☆☆ Popularity ★★★☆☆
How many times do a clock's hands overlap in a day ?
==============================================
Google Interview Questions 5 : Simple Simple Google Interview Puzzle
Difficulty ★★☆☆☆ Popularity ★★★☆☆
The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.
Difficulty ★★★★★ Popularity ★★★★★
-> You are given 2 eggs.
-> You have access to a 100-storey building.
-> Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
-> You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
-> Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
==============================================
Google Interview Questions 2 : Weighing Balance Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
You can place weights on both side of weighing balance and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
==============================================
Google Interview Questions 3 : Cross Bridge Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
==============================================
Google Interview Questions 4 : Google Interview Riddle
Difficulty ★★★☆☆ Popularity ★★★☆☆
How many times do a clock's hands overlap in a day ?
==============================================
Google Interview Questions 5 : Simple Simple Google Interview Puzzle
Difficulty ★★☆☆☆ Popularity ★★★☆☆
The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.
Top 5 Microsoft questions
Top 5 Microsoft Interview Questions
Microsoft Interview Questions 1 : Famous Riddle
Difficulty ★★☆☆☆ Popularity ★★★★★
On my way to St. Ives I saw a man with 7 wives. Each wife had 7 sacks. Each sack had 7 cats. Each cat had 7 kittens. Kitten, cats, sacks, wives. How many were going to St. Ives?
==============================================
Microsoft Interview Questions 2 : Challenging Puzzle
Difficulty ★★★★☆ Popularity ★★★★★
Outside a room there are three light switches. One of switch is connected to a light bulb inside the room.
Each of the three switches can be either 'ON' or 'OFF'.
You are allowed to set each switch the way you want it and then enter the room(note: you can enter the room only once)
Your task is to then determine which switch controls the bulb ??
==============================================
Microsoft Interview Questions 3 : Weighing Balance Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
You can place weights on both side of weighing balance and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
==============================================
Microsoft Interview Questions 4 : Find The Next Number
Difficulty ★★★★★ Popularity ★★★★☆
What are the next three numbers in this series?
4, 6, 12, 18, 30, 42, 60, 72, 102, 108, ?, ?, ?
==============================================
Microsoft Interview Questions 5 : Aeroplane Hardest Quiz
Difficulty ★★★★★ Popularity ★★★☆☆
The puzzle question is : On Bagshot Island, there is an airport. The airport is the homebase of an unlimited number of identical airplanes. Each airplane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The planes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel.
What is the fewest number of aircraft necessary to get one plane all the way around the world assuming that all of the aircraft must return safely to the airport? How did you get to your answer?
Notes:
(a) Each airplane must depart and return to the same airport, and that is the only airport they can land and refuel on ground.
(b) Each airplane must have enough fuel to return to airport.
(c) The time and fuel consumption of refueling can be ignored. (so we can also assume that one airplane can refuel more than one airplanes in air at the same time.)
(d) The amount of fuel airplanes carrying can be zero as long as the other airplane is refueling these airplanes. What is the fewest number of airplanes and number of tanks of fuel needed to accomplish this work? (we only need airplane to go around the world)
Microsoft Interview Questions 1 : Famous Riddle
Difficulty ★★☆☆☆ Popularity ★★★★★
On my way to St. Ives I saw a man with 7 wives. Each wife had 7 sacks. Each sack had 7 cats. Each cat had 7 kittens. Kitten, cats, sacks, wives. How many were going to St. Ives?
==============================================
Microsoft Interview Questions 2 : Challenging Puzzle
Difficulty ★★★★☆ Popularity ★★★★★
Outside a room there are three light switches. One of switch is connected to a light bulb inside the room.
Each of the three switches can be either 'ON' or 'OFF'.
You are allowed to set each switch the way you want it and then enter the room(note: you can enter the room only once)
Your task is to then determine which switch controls the bulb ??
==============================================
Microsoft Interview Questions 3 : Weighing Balance Puzzle
Difficulty ★★★★☆ Popularity ★★★★☆
You can place weights on both side of weighing balance and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
==============================================
Microsoft Interview Questions 4 : Find The Next Number
Difficulty ★★★★★ Popularity ★★★★☆
What are the next three numbers in this series?
4, 6, 12, 18, 30, 42, 60, 72, 102, 108, ?, ?, ?
==============================================
Microsoft Interview Questions 5 : Aeroplane Hardest Quiz
Difficulty ★★★★★ Popularity ★★★☆☆
The puzzle question is : On Bagshot Island, there is an airport. The airport is the homebase of an unlimited number of identical airplanes. Each airplane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The planes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel.
What is the fewest number of aircraft necessary to get one plane all the way around the world assuming that all of the aircraft must return safely to the airport? How did you get to your answer?
Notes:
(a) Each airplane must depart and return to the same airport, and that is the only airport they can land and refuel on ground.
(b) Each airplane must have enough fuel to return to airport.
(c) The time and fuel consumption of refueling can be ignored. (so we can also assume that one airplane can refuel more than one airplanes in air at the same time.)
(d) The amount of fuel airplanes carrying can be zero as long as the other airplane is refueling these airplanes. What is the fewest number of airplanes and number of tanks of fuel needed to accomplish this work? (we only need airplane to go around the world)
Microsoft Interview Questions collection
For answers, look after the questions..
Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.
Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?
Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?
Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.
Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.
Q6: Write a function to print the Fibonacci numbers
Q7: Write a function to print all of the permutations of a string.
Q8: Design a memory management scheme.
Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
Q10: How can I swap two integers in a single line statement?
Q11: Implement an algorithm to sort a linked list.
Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp
Q13: Given a linked list which is sorted, how will you insert in sorted way.
Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.
Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)
Q18: Implement an algorithm to reverse a doubly linked list.
Q19: Delete an element from a doubly linked list.
Q20: Implement an algorithm to sort an array.
Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?
Q22: Count the number of set bits in a number without using a loop.
Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.
Q24: How would you print out the data in a binary tree, level by level, starting at the top?
Q25: Do a breadth first traversal of a tree.
Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.
Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.
Q29: Write a function to find the depth of a binary tree.
Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
Q31: Write a small lexical analyzer for expressions like "a*b" etc.
Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
Q33: Write efficient code for extracting unique elements from a sorted list of array.
Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
Q35: Print an integer using only putchar. Try doing it without using extra storage.
Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).
Q37: Write source code for printHex(int i) in C/C++
Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.
Q39: How do you handle deadlock on a table that is fed with a live serial feed?
Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.
Q41: How would you implement a hash table? How do you deal with collisions.?
Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?
Q43: How would you do conditional compilation?
Q44: Write an algorithm to draw a 3D pie chart?
Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.
Q46: How would you implement a queue from a stack?
Q47: Write a funtion that finds repeating characters in a string.
Q48: Write a routine to reverse a series of numbers without using an array.
Q49: Write a function to find the nth item from the end of a linked list in a single pass.
Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).
Q51: Write a random number generator in a specified range.
Q52: Delete a node from a single linked list.
Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC. Find A, B, and C that satisfies this equation.
Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?
Q55: Write a small lexical analyzer for expressions like a(b|c)d*e+.
Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.
A1: p2 is guaranteed to reach the end of the list before p1 and every link will be tested by the while condition so no chance of access violation. Also, incrementing p2 by 2 and p1 by 1 is the fastest way of finding the cycle. In general if p1 is incremented by 'n' and p2 by 'm', ('n' not == 'm'), then if we number the nodes in the cycle from 0 to k-1 (k is the number of nodes in the cycle), then p1 will take values given by i*n (mod k) and p2 will take values i*m (mod k). These will collide every n*m iterations. Clearly, n*m is smallest for n==1 and m==2.
Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?
A2: Hash Table is the most efficient way to do this. You can use several hashing algorithms. For example, checksum of a link can be used as a key for hashing. This will ensure o(1) order provided good checksum algorithm is used which is always unique. Whenever page loads we can parse all URL's from the page and take their checksum and compare them w/ the hashtable. Whichever links matches are displayed in some different color.
Hashtable is the correct answer, but a constant order algo. sounds too fantastic. URLs are by themselves unique and so hash function should not add to the redundancy by being unique. O/w it becomes nothing but a linear sort of search, while binary can do better.
Though URLs are not inherently alphabetically ordered, one might think of ordering them that way, or making the hash function that utilizes this. This will entail a combined binary + linear search which sounds optimal and is open to complexity calculations. A good data structure can be a hash table pointing to a binary tree (an array pointing to a binary tree).
Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?
A3: Keep a list (or a binary tree) of hashes (using MD5, SHA1 or similar hash/digest algorithm) of pages you've visited. Then just compare digest of current page to the hashes in the tree.
Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.
A4: Use prim's algorithm; Kruskal's algorithm is faster than Prim's. For checking for an already seen url, use dictionary search tree. It is the most efficient i.e. O(1) for whatever number of urls you have in the database.
Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.
Q6: Write a function to print the Fibonacci numbers
Q7: Write a function to print all of the permutations of a string.
Q8: Design a memory management scheme.
Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
A9: x = ((x > 0) & !(x & x - 1));
Q10: How can I swap two integers in a single line statement?
A10: Use xor operator to accomplish this: a ^= b ^= a ^= b;
Q11: Implement an algorithm to sort a linked list.
A11: The merge sort algorithm:
Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp
Q13: Given a linked list which is sorted, how will you insert in sorted way.
Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
/* Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
For each position i in the array we can find out the sub array ending exactly at that position and having the largest sum. At the beginning for the first element the only possible sub array it that one containing the first element so initially the largest amount is a[1]. (For algorithm sake let assume that the array is 1-indexed). Following the principle of dynamic programming it will be proved that the best sub array( with the largest sum) ending in position i+1 is somehow related to best sub array ending in position i.
Let be k the starting index of the best sub array ending in position i and S the sum of this sub array. Let be t an index strictly less than k. The sum from the index t to i+1 is T + S + a[i+1] where T is the sum of elements from t to k-1 indexes. Because of the properties of index k T+S <= S otherwise k will not point to best sub array ending in i so each sub array starting in t
Similarly , let choose an index t between k+1 and i. The sum from index t to i+1 is T+a[i+1], where is the sum of elements between t and i positions. Again T < S according to the optimality of k index so the best sub array ending in i+1 is that one starting from k and that has S+a[i+1] as sum of array elements. But there is one more situation to analyse. If S is less then zero is obvious that S+a[i+1] < a[i+1] so in this case the best sub array ending in i+1 position is exactly the sub array containing only that element. In fact this situation direct you to start a new sub array that will be candidate for the best sub array of the entire array.
In conclusion the information to be kept while going through the array only once (O(n)) is the best sub array ending in the current position and best sub array found for the entire array until the current step.(if it necessary also the starting and ending position for these sub array can be kept). After the processing of the last element the algorithm will have determined the sub array having the largest sum.
Note: The algorithm works fine even there is no negative number in the array and it will produce of course as the largest sum the sum of all array elements.
Algorithm: arr is the array of n integer; the function will return the largest sum and the limits of the sub array producing that value */
Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.
A15: I'll try to do it in O(N) w/o using any additional memory. The key is to use content of the array as index into array, checking in O(1) if that number has been seen already.
Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)
Q18: Implement an algorithm to reverse a doubly linked list.
Q19: Delete an element from a doubly linked list.
Q20: Implement an algorithm to sort an array.
Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?
Q22: Count the number of set bits in a number without using a loop.
Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.
At first glance, it would appear that this algorithm generates all permutations with equal probability. On examination, though, one can see that this will generate NN arrangements of elements---each of the N iterations of the loop positions a value among the N available positions. It is known, though, that there are only N! possible permutations of N elements: for each permutation there are multiple ways to generate that permutation---on average, NN/N! ways.
Examination of the structure of this loop shows that it will generate N! arrangements of elements. All permutations are equally likely, aside from the very minor deviation from uniform distribution by selecting a random value between 0 and Dest as (rand() % (Dest+1)).
Q24: How would you print out the data in a binary tree, level by level, starting at the top?
Q25: Do a breadth first traversal of a tree.
Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.
Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.
Q29: Write a function to find the depth of a binary tree.
Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
Q31: Write a small lexical analyzer for expressions like "a*b" etc.
Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
Q33: Write efficient code for extracting unique elements from a sorted list of array.
Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
Q35: Print an integer using only putchar. Try doing it without using extra storage.
Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).
Q37: Write source code for printHex(int i) in C/C++
Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.
Q39: How do you handle deadlock on a table that is fed with a live serial feed?
Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.
Q41: How would you implement a hash table? How do you deal with collisions.?
Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?
A42: Overflow; If we're talking about ASP, JSP, CFML that sort of thing, I would suspect unsynchronized access to session data in a multi-threaded Servlet, JavaBean or COM object -- i.e., a non-threadsafe bug in the server application.
Q43: How would you do conditional compilation?
A43: The #if directive, with the #elif, #else, and #endif directives, controls compilation of portions of a source file. If the expression you write (after the #if) has a nonzero value, the line group immediately following the #if directive is retained in the translation unit. Plus, #ifdef and #ifndef identifier.
Q44: Write an algorithm to draw a 3D pie chart?
Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.
A45: The two common MST algorithms are by Kruskal and Prim. Djikstra gave us an algorithm for shortest path, not MST.
Q46: How would you implement a queue from a stack?
Q47: Write a funtion that finds repeating characters in a string.
Q48: Write a routine to reverse a series of numbers without using an array.
Q49: Write a function to find the nth item from the end of a linked list in a single pass.
A49: I would think keeping a gap of "n" between fptr and sptr would do. Then, advance both together till fptr->next (fptr is the one in front) = NULL.
Aren't you traversing the list twice - once with fptr and the second time with sptr. I think you should maintain an queue of pointers. Keep pushing a pointer into the queue and whenever the size of the queue becomes greater than n, remove a pointer at the head of the queue. When you reach the end of the list. The element at the head of the queue gives a pointer to the nth element from the end.
Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).
Q51: Write a random number generator in a specified range.
Q52: Delete a node from a single linked list.
Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.
Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.
Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?
Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?
Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.
Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.
Q6: Write a function to print the Fibonacci numbers
Q7: Write a function to print all of the permutations of a string.
Q8: Design a memory management scheme.
Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
Q10: How can I swap two integers in a single line statement?
Q11: Implement an algorithm to sort a linked list.
Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp
Q13: Given a linked list which is sorted, how will you insert in sorted way.
Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.
Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)
Q18: Implement an algorithm to reverse a doubly linked list.
Q19: Delete an element from a doubly linked list.
Q20: Implement an algorithm to sort an array.
Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?
Q22: Count the number of set bits in a number without using a loop.
Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.
Q24: How would you print out the data in a binary tree, level by level, starting at the top?
Q25: Do a breadth first traversal of a tree.
Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.
Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.
Q29: Write a function to find the depth of a binary tree.
Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
Q31: Write a small lexical analyzer for expressions like "a*b" etc.
Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
Q33: Write efficient code for extracting unique elements from a sorted list of array.
Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
Q35: Print an integer using only putchar. Try doing it without using extra storage.
Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).
Q37: Write source code for printHex(int i) in C/C++
Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.
Q39: How do you handle deadlock on a table that is fed with a live serial feed?
Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.
Q41: How would you implement a hash table? How do you deal with collisions.?
Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?
Q43: How would you do conditional compilation?
Q44: Write an algorithm to draw a 3D pie chart?
Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.
Q46: How would you implement a queue from a stack?
Q47: Write a funtion that finds repeating characters in a string.
Q48: Write a routine to reverse a series of numbers without using an array.
Q49: Write a function to find the nth item from the end of a linked list in a single pass.
Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).
Q51: Write a random number generator in a specified range.
Q52: Delete a node from a single linked list.
Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC. Find A, B, and C that satisfies this equation.
Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?
Q55: Write a small lexical analyzer for expressions like a(b|c)d*e+.
Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.
A1: p2 is guaranteed to reach the end of the list before p1 and every link will be tested by the while condition so no chance of access violation. Also, incrementing p2 by 2 and p1 by 1 is the fastest way of finding the cycle. In general if p1 is incremented by 'n' and p2 by 'm', ('n' not == 'm'), then if we number the nodes in the cycle from 0 to k-1 (k is the number of nodes in the cycle), then p1 will take values given by i*n (mod k) and p2 will take values i*m (mod k). These will collide every n*m iterations. Clearly, n*m is smallest for n==1 and m==2.
bool HasCycle(Node *pHeadNode)
{
Node *p1, *p2;
p1 = p2 = pHeadNode;
while (p2 && p2->Next) {
p1 = p1->Next;
p2 = p2->Next->Next;
if (p1 == p2)
return true;
}
return false;
}
Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?
A2: Hash Table is the most efficient way to do this. You can use several hashing algorithms. For example, checksum of a link can be used as a key for hashing. This will ensure o(1) order provided good checksum algorithm is used which is always unique. Whenever page loads we can parse all URL's from the page and take their checksum and compare them w/ the hashtable. Whichever links matches are displayed in some different color.
Hashtable is the correct answer, but a constant order algo. sounds too fantastic. URLs are by themselves unique and so hash function should not add to the redundancy by being unique. O/w it becomes nothing but a linear sort of search, while binary can do better.
Though URLs are not inherently alphabetically ordered, one might think of ordering them that way, or making the hash function that utilizes this. This will entail a combined binary + linear search which sounds optimal and is open to complexity calculations. A good data structure can be a hash table pointing to a binary tree (an array pointing to a binary tree).
Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?
A3: Keep a list (or a binary tree) of hashes (using MD5, SHA1 or similar hash/digest algorithm) of pages you've visited. Then just compare digest of current page to the hashes in the tree.
Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.
A4: Use prim's algorithm; Kruskal's algorithm is faster than Prim's. For checking for an already seen url, use dictionary search tree. It is the most efficient i.e. O(1) for whatever number of urls you have in the database.
Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.
Q6: Write a function to print the Fibonacci numbers
int fib (int n)
{
assert(n>=1);
return (n<=2 ? 1: (fib(n-1) + fib(n-2)));
}
int fibonacci (int n)
{
if (n <= 2) return 1;
int current, one_back 1, two_back = 1;
for (int i = 3; i <= n; i++) {
current = one_back + two_back;
one_back = two_back;
two_back = current;
} /* the end of for loop */
return current;
}
Q7: Write a function to print all of the permutations of a string.
mapmap_StrInt; void PermuteString(char* str, int n) { char ch = str[n-1]; for(int i = 0; i < n; i++) { swap (str[i], str[n-1]); PermuteString(str, n-1); swap (str[i], str[n-1]); } if (n == 1) map_StrInt[string(str)]++; }
Q8: Design a memory management scheme.
Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
A9: x = ((x > 0) & !(x & x - 1));
Q10: How can I swap two integers in a single line statement?
A10: Use xor operator to accomplish this: a ^= b ^= a ^= b;
Q11: Implement an algorithm to sort a linked list.
A11: The merge sort algorithm:
#include
typedef struct MNode *PNODE;
struct MNode
{
int Key;
struct MNode *Next;
};
PNODE Merge(PNODE p, PNODE q)
{
assert(p);
assert(q);
PNODE pHead;
if (p->Key < q->Key)
{
pHead = p, p = p->Next;
}
else
{
pHead = q, q = q->Next;
}
PNODE r = pHead;
while (p && q)
{
if(p->Key < q->Key)
{
r->Next = p, r = r->Next, p = p->Next;
}
else
{
r->Next = q, r = r->Next, q = q->Next;
}
}
if(!p) r->Next = q;
if(!q) r->Next = p;
return pHead;
}
PNODE Partition(PNODE pNode)
{
PNODE p1 = pNode;
PNODE p2 = pNode->Next->Next;
while (p2 && p2->Next)
{
p2 = p2->Next->Next;
p1 = p1->Next;
}
PNODE pSav = p1->Next;
p1->Next = NULL;
return pSav;
}
PNODE Merge_Sort(PNODE p)
{
if (!p || !p->Next) return p;
PNODE q = Partition(p);
p = Merge_Sort(p);
q = Merge_Sort(q);
p = Merge(p, q);
return p;
}
Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp
char * strstr (const char *str1, const char *str2) { char *cp = (char *)str1; char *endp = cp + (strlen(cp) - strlen(str2)); while (*cp & (cp <= endp)) { char *s1 = cp; char *s2 = (char *)str2; while ( *s1 & *s2 && (*s1 == *s2) ) s1++, s2++; if (!(*s2)) return(cp); // success! cp++; // bump pointer to next char } return(NULL); } char *strcat (char * dst, const char * src) { char *cp = dst; while (*cp) cp++; // find end of dst while (*cp++ = *src++); // Copy src to end of dst return (dst); // return dst } char *strcpy (char * dst, const char * src) { char* cp = dst; while (*cp++ = *src++); // Copy src over dst return(dst); } char *strtok (char *string, const char *control) { char *str; const char *ctrl = control; char map[32]; int count; static char *nextoken; /* Clear control map */ for (count = 0; count < 32; count++) map[count] = 0; // Set bits in delimiter table do { map[*ctrl >> 3] |= (1 << (*ctrl & 7)); } while (*ctrl++); // Initialize str. If string is NULL, set str to the saved pointer // (i.e., continue breaking tokens out of the string from the last strtok call) if (string) str = string; else str = nextoken; // Find beginning of token (skip over leading delimiters). Note that there is // no token iff this loop sets str to point to the terminal null (*str == '\0') while (*str && (map[*str >> 3] & (1 << (*str & 7)))) str++; string = str; // Find the end of the token. If it is not the end of the string, put a null there. for ( ; *str ; str++) if (map[*str >> 3] & (1 << (*str & 7))) { *str++ = '\0'; break; } // Update nextoken nextoken = str; // Determine if a token has been found. if (string == str) return NULL; else return string; } int strcmp(const char *src, const char* dst) { int ret = 0; while (!(ret = (*src - *dst)) & *dst); ++src, ++dst; if (ret < 0) ret = -1; else ret = 1; return ret; } char *strrev (char *string) { char *start = (char *)string; char *left = (char *)string; while (*string++); // find end of string string -= 2; while (left < string) { char ch = *left; *left++ = *string; *string-- = ch; } return start; } char *strrchr (const char *string, int ch) { char *start = (char *)string; while (*string--); // find end of string while (--string != start && *string != (char)ch); // search forward front if (*string == (char)ch) // char found ? return (char *)string; return (NULL); }
Q13: Given a linked list which is sorted, how will you insert in sorted way.
void Insert(PNODE &pHead, PNODE pThing)
{
if (pHead == 0)
pHead = pThing;
else
{
bool fComesFirst = true;
PNODE pCurrent = pHead;
PNODE pPrevious;
while (pCurrent)
{
if (pThing->Key < pCurrent->Key)
break;
pPrevious = pCurrent;
pCurrent = pCurrent->Next;
fComesFirst = false;
}
if (fComesFirst)
pHead = pThing;
else
pPrevious->Next = pThing;
pThing->Next = pCurrent;
}
}
Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
/* Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.
For each position i in the array we can find out the sub array ending exactly at that position and having the largest sum. At the beginning for the first element the only possible sub array it that one containing the first element so initially the largest amount is a[1]. (For algorithm sake let assume that the array is 1-indexed). Following the principle of dynamic programming it will be proved that the best sub array( with the largest sum) ending in position i+1 is somehow related to best sub array ending in position i.
Let be k the starting index of the best sub array ending in position i and S the sum of this sub array. Let be t an index strictly less than k. The sum from the index t to i+1 is T + S + a[i+1] where T is the sum of elements from t to k-1 indexes. Because of the properties of index k T+S <= S otherwise k will not point to best sub array ending in i so each sub array starting in t
Similarly , let choose an index t between k+1 and i. The sum from index t to i+1 is T+a[i+1], where is the sum of elements between t and i positions. Again T < S according to the optimality of k index so the best sub array ending in i+1 is that one starting from k and that has S+a[i+1] as sum of array elements. But there is one more situation to analyse. If S is less then zero is obvious that S+a[i+1] < a[i+1] so in this case the best sub array ending in i+1 position is exactly the sub array containing only that element. In fact this situation direct you to start a new sub array that will be candidate for the best sub array of the entire array.
In conclusion the information to be kept while going through the array only once (O(n)) is the best sub array ending in the current position and best sub array found for the entire array until the current step.(if it necessary also the starting and ending position for these sub array can be kept). After the processing of the last element the algorithm will have determined the sub array having the largest sum.
Note: The algorithm works fine even there is no negative number in the array and it will produce of course as the largest sum the sum of all array elements.
Algorithm: arr is the array of n integer; the function will return the largest sum and the limits of the sub array producing that value */
#include
using namespace std;
int GetLargestSubArray(int* arr, int n, int &iBeginRet, int &iEndRet)
{
int iBeginSaved=0, iEndSaved=0; // the start/end positions of the saved sub array
int iBegin, iEnd; // the start/end positions of the current sub array
int nSumSaved=0, nSum=0; // the sums of whole saved largest and current sub arrays
int i = 0; // index to loop in the array
if (0 == n) // Nothing to analyze, return invalid array indexes
{
iEndRet = iBeginRet = -1;
return 0;
}
nSumSaved = nSum = arr[i];
for(i = 2; i < n; i++)
{
/* Compute the current largest sum */
if (nSum<0 br="br"> {
nSum = arr[i];
iBegin = iEnd = i;
}
else
{
nSum += arr[i];
iEnd = i;
}
if (nSum > nSumSaved)
{
nSumSaved = nSum;
iBeginSaved = iBegin;
iEndSaved = iEnd;
}
}
iBeginRet = iBeginSaved;
iEndRet = iEndSaved;
return nSumSaved;
}
Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.
A15: I'll try to do it in O(N) w/o using any additional memory. The key is to use content of the array as index into array, checking in O(1) if that number has been seen already.
bool HasDups(int * a, int N) { bool fHasDup = false; for (int i = 0; i < N; i++) { int index = a[i] % N; if (a[index] > N) { fHasDup = true; break; } a[index] += N; } //restore the array for (int j = 0; j < i; j++) if (a[j] > N) a[j] %= N; return fHasDup; }
Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.
Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)
Node *RevSList(Node *pCur, Node *pRev) {
if (!pCur) return pRev;
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
return (RevSList(pNext, pRev));
}
Node * RevSList(Node *pCur) {
Node *pRev = NULL;
while (pCur)
{
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
pCur = pNext;
}
return pRev;
}
Q18: Implement an algorithm to reverse a doubly linked list.
Node *RevDList(Node *pCur)
{
if (!pCur) return pCur;
pSav = pCur->Next;
pCur->Next = pCur->Prev;
pCur->Prev = pSav;
if (!pSav) return pCur;
return RevDList(pSav);
}
Node *RevDList(Node *pCur)
{
while (pCur)
{
Node *pSav = pCur->Next;
pCur->Next = pCur->Prev;
pCur->Prev = pSav;
if (!pSav) return pCur;
pCur = pSav;
}
return pCur;
}
Q19: Delete an element from a doubly linked list.
Node *DelDLLNode(Node *pNode)
{
if (!pNode) return pNode;
if (pNode->Next) pNode->Prev->Next = pNode->Next;
if (pNode->Prev) pNode->Next->Prev = pNode->Prev;
return pNode; // delete it if it's heap-based.
}
Q20: Implement an algorithm to sort an array.
Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?
Q22: Count the number of set bits in a number without using a loop.
#define reverse(x) \
(x=x>>16 | (0x0000ffff&x)<<16 br="br"> x=(0xff00ff00&x)>>8|(0x00ff00ff&x)<<8 br="br"> x=(0xf0f0f0f0&x)>>4|(0x0f0f0f0f&x)<<4 br="br"> x=(0xcccccccc&x)>>2|(0x33333333&x)<<2 br="br"> x=(0xaaaaaaaa&x)>>1|(0x55555555&x)<<1 br="br">
#define count_ones(x) \
(x=((0xaaaaaaaa&x)>>1)+(0x55555555&x), \
x=((0xcccccccc&x)>>2)+(0x33333333&x), \
x=((0xf0f0f0f0&x)>>4)+(0x0f0f0f0f&x), \
x=((0xff00ff00&x)>>8)+(0x00ff00ff&x), \
x=(x>>16) + (0x0000ffff&x))
Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.
for (Src = 0; Src < N; Src++)
{
Dest = rand() % N; // All N positions equally likely
Swap (X[Src], X[Dest]);
}
At first glance, it would appear that this algorithm generates all permutations with equal probability. On examination, though, one can see that this will generate NN arrangements of elements---each of the N iterations of the loop positions a value among the N available positions. It is known, though, that there are only N! possible permutations of N elements: for each permutation there are multiple ways to generate that permutation---on average, NN/N! ways.
for (Src = 0; Src < N; Src++)
{
Dest = rand() % N; // All N positions equally likely
Swap (X[Src], X[Dest]);
}
Examination of the structure of this loop shows that it will generate N! arrangements of elements. All permutations are equally likely, aside from the very minor deviation from uniform distribution by selecting a random value between 0 and Dest as (rand() % (Dest+1)).
Q24: How would you print out the data in a binary tree, level by level, starting at the top?
Q25: Do a breadth first traversal of a tree.
typedef int VertexType;
typedef class Vertex *LPVertex;
class Vertex
{
int index;
int weight;
LPVertex next;
public:
int GetIndex();
bool Visited();
Vertex &Visit();
Vertex &Mark();
Vertex *GetNext();
};
enum { kMaxVertices = 7 };
typedef LPVertex HeaderArray[kMaxVertices];
HeaderArray adjacencyList;
void BreathFirstSearch (HeaderArray adjacencyList, LPVertex pv)
{
queue Q;
pv->Visit().Mark();
Q.push(pv);
while (!Q.empty())
{
pv = Q.front(); Q.pop();
pv = adjacencyList[pv->GetIndex()];
for (; pv; pv = pv->GetNext())
if (!pv->Visited())
{
pv->Visit().Mark();
Q.push (pv);
}
}
}
void DepthFirstSearch (HeaderArray adjacencyList, LPVertex pv)
{
stack S;
pv->Visit().Mark();
S.push(pv);
while (!S.empty())
{
pv = S.top();
pv = adjacencyList[pv->GetIndex()];
for (; pv; pv = pv->GetNext())
if (!pv->Visited())
{
pv->Visit().Mark();
S.push(pv);
}
S.pop();
}
}
Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.
char *ReverseWords (char *string)
{
char *start = strrev(string);
char *left;
char *right;
char ch;
while (*string)
{
while (*string == ' ' & *string)
string++;
left = string;
while (*string != ' ' & *string)
string++;
right = string-1;
while (left < right)
{
ch = *left;
*left++ = *right;
*right-- = ch;
}
}
return start;
}
Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.
Q29: Write a function to find the depth of a binary tree.
long findDepth(Node *pNode) { if (!pNode) return 0; long depthLeft = findDepth(pNode->Left); long depthRight = findDepth(pNode->Right); return (depthLeft>depthRight ? ++depthLeft: ++depthRight); }
Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
char *strtokrem (char *string, const char *control)
{
char *start = string;
char *str = string;
const char *ctrl = control;
char map[32];
int count;
/* Clear control map */
for (count = 0; count < 32; count++)
map[count] = 0;
// Set bits in delimiter table
do {
map[*ctrl >> 3] |= (1 << (*ctrl & 7));
} while (*ctrl++);
// Remove each token whenever it matches
while (*str)
if (map[*str >> 3] & (1 << (*str & 7))) {
for (char *pch = str; *pch; pch++)
*pch = *(pch+1);
}
else
str++;
return start;
}
Q31: Write a small lexical analyzer for expressions like "a*b" etc.
bool is_astarb(char* string)
{
// expressions: b, ab, aab, aaab, ...
bool bRet = false;
while (*string == 'a')
++string;
if (*string == 'b')
bRet = (*++string == '\0');
return bRet;
}
Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
Q33: Write efficient code for extracting unique elements from a sorted list of array.
void PrintUniqueElements(int rgNumb[], int cNumb)
{
assert(cNumb>0);
int iSav;
cout << (iSav = rgNumb[0]) << "\t";
for (int i = 1; i < cNumb; i++)
if (iSav != rgNumb[i])
cout << (iSav = rgNumb[i]) << "\t";
}
Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
Q35: Print an integer using only putchar. Try doing it without using extra storage.
void putDigits(int val)
{
if (val < 0) { cout << "-"; val = -val; }
stack S;
S.push(val);
while (!S.empty())
{
val = S.top(); S.pop();
if (val >= 10)
{
S.push(val%10);
S.push(val/10);
}
else
cout.put(val+'0');
}
}
Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).
Q37: Write source code for printHex(int i) in C/C++
void putHex(int val)
{
if (val < 0) {
printf("-");
val = -val;
}
if (val >= 0 & val < 16) {
printf("%c", val > 9 ? (val-10)+'A' : val+'0');
return;
}
putHex(val/16);
printf("%c", val%16 > 9 ? (val%16-10)+'A' : val%16+'0');
}
Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.
Q39: How do you handle deadlock on a table that is fed with a live serial feed?
Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.
Q41: How would you implement a hash table? How do you deal with collisions.?
Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?
A42: Overflow; If we're talking about ASP, JSP, CFML that sort of thing, I would suspect unsynchronized access to session data in a multi-threaded Servlet, JavaBean or COM object -- i.e., a non-threadsafe bug in the server application.
Q43: How would you do conditional compilation?
A43: The #if directive, with the #elif, #else, and #endif directives, controls compilation of portions of a source file. If the expression you write (after the #if) has a nonzero value, the line group immediately following the #if directive is retained in the translation unit. Plus, #ifdef and #ifndef identifier.
Q44: Write an algorithm to draw a 3D pie chart?
Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.
A45: The two common MST algorithms are by Kruskal and Prim. Djikstra gave us an algorithm for shortest path, not MST.
Q46: How would you implement a queue from a stack?
stack stk1, stk2;
void push(element e)
{
push.stk1(e);
}
element pop()
{
if(stk2.empty())
while(!stk1.empty())
stk2.push(stk1.pop());
return stk2.pop();
}
Q47: Write a funtion that finds repeating characters in a string.
Q48: Write a routine to reverse a series of numbers without using an array.
int iReverse (int iNum)
{
int iRev =0;
while(iNum !=0)
{
iRev = iRev * 10 + iNum % 10;
iNum /= 10;
}
return iRev;
}
Q49: Write a function to find the nth item from the end of a linked list in a single pass.
A49: I would think keeping a gap of "n" between fptr and sptr would do. Then, advance both together till fptr->next (fptr is the one in front) = NULL.
Aren't you traversing the list twice - once with fptr and the second time with sptr. I think you should maintain an queue of pointers. Keep pushing a pointer into the queue and whenever the size of the queue becomes greater than n, remove a pointer at the head of the queue. When you reach the end of the list. The element at the head of the queue gives a pointer to the nth element from the end.
#include
PNODE GetNthLastElement (PNODE pCur, unsigned nOffset)
{
queue Q;
for (; pCur && Q.size() < nOffset; Q.push(pCur), pCur = pCur->Next) ;
if (Q.size() < nOffset) return NULL;
while (pCur)
{
Q.pop();
Q.push(pCur);
pCur = pCur->Next;
}
return (Q.front());
}
Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).
Q51: Write a random number generator in a specified range.
#include
int random_range(int lowest_number, int highest_number)
{
¡¡¡¡if (lowest_number > highest_number)
¡¡¡¡{
¡¡¡¡¡¡¡¡swap(lowest_number, highest_number);
¡¡¡¡}
¡¡¡¡int range = highest_number - lowest_number + 1;
¡¡¡¡return lowest_number + int(range * rand()/(RAND_MAX + 1.0));
}
Q52: Delete a node from a single linked list.
Node *DelSLLNode(Node *pDelete, Node *pHead)
{
if (pHead == pDelete)
return (pHead = pHead->Next);
Node *pPrev = pHead;
for ( ; pPrev->Next; pPrev = pPrev->Next)
{
if (pPrev->Next == pDelete)
{
pPrev->Next = pPrev->Next->Next;
break;
}
}
return pHead;
}
Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.
1! + 4! + 5! = 145
Subscribe to:
Comments (Atom)