Last year I interviewed at a number of major companies for software engineering jobs. These companies will ask incredibly in-depth questions, particularly in algorithms and data structures. Here are some typical questions:
Given a singly linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Define mth to last such that when m=0, the last element of the list is returned.
You are given two pointers to a linked list. One pointer is to the head of the list, and another pointer is to a target node that you need to delete. If you don't care about maintaining the list in any order, how can you delete the target node in constant time?
Suppose you have a binary search tree storing integers. Design an algorithm to determine if the ordering of the data within the tree is correct. (hint: you can define a value, MAX_INT, that is the largest value that can be stored in the tree)
Consider a 32-bit integer with all bits set to 0 except for the 14th bit set to 1. What number is this in decimal and hex? (not a trick question, you just have to know to do it!)
Suppose you have an unsigned short set to -1 and you cast it into a signed integer. What do the bits look like? Repeat the same going from a signed short to an unsigned int.
You are given N numbers. Find the K largest numbers. Do it in faster than O(N K) time.
Write a recursive function to find the ith Fibonacci number. Assume this function works perfectly in a single-threaded program. Now in a multithreaded program, one of the threads calls your Fibonacci function for a large value of i, and then all the threads start crashing. What could be the problem?
Write some C or C++ code to determine if the stack on a computer grows up or down. What if the compiler unpredictably allocates automatic variables?
Suppose you have a function that returns random 64-bit integers without checking if a particular integer has already been used. How many integers would be returned before the probability that an integer has been repeated is above 0.5? (hint: have you heard of the "birthday" puzzle, probably in your statistics class?)
How would you implement reliable, efficient delivery using UDP?
When does a C++ virtual destructor get called?
How do you use 'const' in C++ (two ways)?
What is a C++ virtual function lookup table? Where in memory is it stored?
What is a Unix zombie process? How do you prevent zombie processes? How do you deal with zombie processes?
Suppose you are concerned with a particular file. How can you report to the user that this file has been modified or moved to another volume?
Describe the toughest bug you've fixed.
Describe a difficult interpersonal time you've had working on a team.
Facebook
Twitter