Company-specific Interviews

From Foreignliving

This page contains company-specific interview questions and advice. For general advice on how to prepare for interviews and what to expect, see the article on Interview questions.

Note to contributors: The section below can contain information about the interview process at various companies, such as how many interviews do they hold, what to expect during screening interviews and on-site interviews etc.

Contents 1 Amazon 2 Bloomberg 3 Google 4 Microsoft 5 Schlumberger 6 VMWare 7 Others

Amazon

Make a class to represent a deck of cards. Write an algorithm to shuffle the deck and distribute amongst 4 players.

An array has only duplicates but one non-duplicate. For example [2 2 5 5 6 7 7]. How would you detect the non-duplicate. Give an O(n^2),O(nLog(n)) and O(n) solution. What if we XOR them all together?

You have a million web-pages with links linking each other. You initially have n pages. You have to scan all the million pages just once and tell how many times each page has been linked?

Find out the prime number just below n. Optimize the algorithm.

Swap two integers without using external memory.

Write efficient code to tell if a number is a power of 2.

Write a single statement to tell if a number is even, (without using the mod function).

Difference between a linked list and an array? Pros and Cons of each?

Write code to find an element in a binary tree? Now insert s new element.

What is the complexity of an insertion in a tree, heap, array and a hash table?

How does a hash table work?

Give examples of some hash functions?

Whenever a user visits a webpage, we get that visitor's IP and date of visit. We have a list of the IP and date of visit. You need to find the number of unique visitors that have visited the website on two or more different days. Given an O(n) solution with minimum storage. How much storage is required?

An array has numbers of ranging between 0 and 1000. The array size is n. Write an O(n) algorithm to sort them.

What does it mean by function inlining?

What is polymorphism?

What is virtual and pure virtual and what is the use?

You have a string of characters. You have to compress them. How would you do that?

If to compress a string you are using something of this sort that for a string "ggggjjjklluttttttt" --> 4g3jk2lu7t. Write an algorithm for this? What will happen if the string contains digits. How to counter that?

How does exception handling work in java?

Selection Process

• 90 minute screening interview
• ...

Bloomberg

Questions taken from Myke's page. Some answers on this page

Phone Screen

1. What is dead lock, how can you make one?
2. What is shared memory? How it works
3. What in inline function? Which functions cannot be inlined?
4. List the disadvantages of Multiple Inheriteance.
5. Questions about stack and heap.

Onsite:

1. What when a process, what is its address space lay out? (data area, stack, heap, process information, environment variables)
2. How the OS load and execute files ( load process,set up space, to virtual memeory)
3. How compiler works, e.g. cc hello.c
4. What’s the difference between hello.o, hello.exe and hello.dll
5. differences between Pipe and Socket
6. Interprocess communications in Unix, list several that you know.
7. What is firewall
8. Design patterns and give examples how you use them in your work
9. In what situation could Garbage Collection fail?
10. strncpy vs memcpy
11. compare Array and Linked list; compare doubly linked-list and singly-linked list
12. List all the possible scopes for variable in C or C++, list as much as you can.
13. What does it mean if your read from socket returns 0?
14. When you try to pass an SQL value into a C++ string, what you should do first? (Set the string to 0 because SQL string doesn’t have null terminate)
15. Write a function to remove spaces in a string
16. write function to print out the third level nodes in a tree.
17. Which language do you prefer, C# or C++?
18. List the difference between C# and C++
19. List the Difference between Java and C++
20. Talking about Java Clone()
21. XML schema and different ways to do it
22. What do u do if you add new features to a software, what will u do before put the feature into release?
23. If you have a directory of hundreds of files, .c, txt or other type which is left by the previous employee. What do you do with it?
24. Why do u want to work here
25. what do you think you can contribute if we hire you

Google

How do you think orkut keeps track of your friends lists. ANS: Using graphs.

How do you find the shortest path in your friends list to some one. ANS: Use dijkstra. You actually have to tell them how dijkstra works.

What does it mean by declaring static variables?

What are static functions in C and C++ what is the difference? Are there static classes?

What does it mean by the "volatile" and "explicit" keywords in C?

Tell me about any difficult situation that you faced and how did you debug it?

If you have a million nodes and you have to find the shortest path between A and B how would you do that? ANS: Dijkstra

If Dijkstra was to be optimized for just finding that path between A and B how would you do that? ANS: Don't add all the neighbors in the heap, just those being encountered from A and B.

How would the heap grown in such a case? ANS: Exponentially

How to optimize the heap size in such a case? ANS: Start at both the ends A and B and meet in the middle.

How much memory is needed to implement gooogle search on a billion webpages? How would the algorithm work

If the memory in insufficient how would you cater for that? ANS: Use external storage and load specific hash table in memory at one time.

What would be the latency in such a case? Come of with some number?

Suppose if you were using distributed servers. For every search 100 servers return results. But you have to show sorted results. How would you do that? ANS: Each server should send a sorted list and then a function could be implemented to merge them.

What is we just want to display top 20 results? AND: In that case, each server should just give 20 sorted results each?

Imagine these servers in a LAN. When we send them queries each returns answers. Can you see any prospective problems with this? ANS: When every server returns queries you can overflow the bandwidth. Also there will be collisions.

Suppose we have enough bandwidth and we are using TCP. How does TCP handle collisions? ANS: Using acks in sliding window.

Do you see any problem with it? ANS: Yes acks will generate more traffic.

How would you handle this? ANS: Each server sends results at different times. Server 1 sends at 2 ms, sever 2 at 4ms and so on.

Suppose that you are not sure about the number of servers, how would you use the same approach? ANS: Use a random interval after which each server sends replies.

Tell me the bounds of the random interval?

Suppose that we are using switching in the LAN how would that change your answers? ANS: There are no collisions in switching so we are fine.

What other problems can you see? ANS: The head computer receiving results from all the servers might not be able to handle all the requests.

How to handle this? ANS: TCP already does that using flow control.

What is the problem with that? ANS: TCP uses more packets to advertise adv window. Thats wasteful.

If we implemented congestion control at the hardware level in switches. Each switch sends packet to originating servers if queues start to get filled. How is that better than TCP? ANS: TCP congestion detects congestion after the packet has been lost but your approach detects it before congestion forms.

Any problem you see with the above approach? ANS: One server can keep sending. The switch might penalize some servers too much. Basically the problem of fairness.

How to correct this? ANS: Use priorities. Priority queuing.

How to implement this queuing?

Suppose you have a for loop that you are going through indefinitely. Within that loop you call two different functions. How to call function A at the rate of 5/sec and function B at 7/sec provided that you have timers? ANS: Use a timer for every function that interrupts after a specified interval (1000000/5 for function A, 1000000/7 for function B).

Suppose that you are restricted to using one timer, how would you implement?

ANS: We will find the values of (1000000/7 and 1000000/5) and take the GCD and interrupt after that GCD interval. Then we can mod the time with the values to detect for which function call has the timer interrupted.

Suppose that there is no GCD. What would you do then? ANS: We will pick some coarse interval and the timer would interrupt after that interval. In the loop for each function would check if the timer value has reached a value close enough to the value at which that function should be called.

How close would that value be? Also how to deal with the inaccuracy? ANS: To deal with the inaccuracy we can first call when the timer overshoots and next time when the timer undershoots and so on. For this we will need another variable fir every function.

Where is most of the time spent when the timer interrupts? ANS: Comparing the timer to all the timer values.

How would you optimize? ANS: Use nested if/else with functions nested in sequence in which they are called. If one if matches, you skip the rest of the if conditions.

How to optimize? ANS: Use a sorted list . Every time a function call is made you reset the time value for that entry and resort.

How to optimize more? ANS: Use heap instead.

What is the lookup time of a heap? ANS: O(n)

For 100,000 webpages find the unique word count in each and store along with the webaddress. How would you do that? ANS: Hash table

Give estimated size of the hash table?

What hashing function can be used?

Given examples of some hashing functions?

Worst case of a has function?

Write a function to calculate all the factors of a number n?

Write an iterative and recursive functions to find permutations of a string of length n?

Write an iterative and recursive functions to find combinations of p character in a string of length n?

Selection Process

• Initial screening interview either at your university campus or via telephone.

Microsoft

From the Microsoft website (http://www.microsoft.com/college/int_overview.mspx):

Once your recruiter has had a chance to review your resume and gotten to know you a little better through brief chats or e-mail, they may wish to schedule an initial interview with you. These interviews are very casual and are usually held over the phone or on your campus. They are intended only to give us a general idea of your skills and interests and are usually not for specific open positions or teams.

Some things to keep in mind:

• Be prepared to discuss your strengths, expertise, and any experience or previous jobs that appear on your resume.
• If you're interested in one of our core technology positions-Software Design Engineer, Software Design Engineer in Test, or Program Manager-you may be asked some general problem-solving, design, or algorithm questions.
• If your passions run to other disciplines such as sales, finance, or user assistance, be prepared to answer general questions in your field.
• Ask your own questions. After all, this isn't just about Microsoft learning about you, but you learning about us, too.

Selection Process

• 30 min screening interview either at your university campus or via telephone.
• subsequent interviews take place at Microsoft campus

Schlumberger

Interview tips from Schlumberger's website

Get to know Schlumberger
Learn as much as possible about our company by reading the latest press releases. Then, you can ask our recruiters informed questions.

Prepare for your first Schlumberger interview
Remember, we've been there. We know how uncomfortable interviewing can be, especially when someone is going into details about your resume or application. Relax, and you'll do just fine.

We're trying to get to know you better, so we'll need your help. Be sure to express your strengths and skills clearly. You'll also want to explain the areas you feel you need to develop. Don't be afraid to share that with us. We can provide extensive training so if you've got a soft area or two, we can help you strengthen those areas.

First interviews usually last about an hour. Second interviews usually last all day.

During the interview
Listen well. Pay attention to the questions asked and make sure you give concise answers.

Be honest. Nobody's going to ask you if you have 20 years of experience. We know you're just graduating from school. Simply emphasize your strong points for our benefit.

Be direct, confident, and comfortable. If you don't understand a question, ask to have it repeated.

VMWare

• For internships, there are three phone-screens before the final decision is taken (can last from 30 to 60 minutes).
• Detailed questions about projects listed on your resume.
• How would you solve ...<some problem specific to the group you are being interviewed for> (check the vmware website for their various groups.
• Showing enthusiasm for vmware is a must, especially for internships. Download vmware workstation (free trial available) and use it a bit ahead of time.
• Brush up operating systems knowledge, be ready to answer questions related to threads and processes.
• Programming questions: mostly about the programming language of your choice. Not coding questions, but questions like "If a C library calls a C++ function, what do you need to check?". Also algorithmic questions where apparently the focus is not your problem-solving ability, rather your technical knowledge, i.e. whether you are familiar with standard ways of handling a situation.

Others

(add here)