Some popular programming questions for technical interviews


I realize that many including myself constantly practice programming questions and algorithms for technical interviews. There’s lots of ways to practice, but one book in particular has helped a lot. I will share some popular technical interview questions from “Cracking The Coding Interview“. Jump to section: Data Structures     Concepts and Algorithms     Knowledge Based

Data Structures

Arrays and Strings

  1. Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
  2. Given two strings, write a method to decide if one is a permutation of the other.
  3. Implement a function in C/C++: void reverse(char *str), which reverses a null terminated string.
  4. Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
  5. Assume you have a method called “isSubstring” which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only call to isSubstring. Example: “waterbottle” is a rotation of “erbotllewat”.

Linked Lists

  1. Write code to remove duplicates from an unsorted linked list. (Follow up: how would you solve this problem without a temporary buffer?)
  2. Write code to partition a linked list around a value ‘x’, such that all nodes less than x come before all nodes greater than or equal to x.
  3. Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. Example, input: remove node c (a-b-c-d-e), result (a-b-d-e), nothing is returned.
  4. Given two sorted linked lists, how can you combine them?

Stacks & Queues

  1. Implement a MyQueue class which implements a queue using two stacks
  2. Write a program to sort a stack in ascending order (biggest items on top). You can use at most 1 additional stack to hold items but you cannot use any other data structures such as an array. The stack supports push, pop, peek, and isEmpty.

Trees and Graphs

  1. Implement a function to check if a binary tree is balanced. A balanced tree is defined to be a tree such that the heights of the two subtrees of any node differ by more than 1.
  2. Given a sorted array, write an algorithm to create a binary search tree with minimal height.
  3. Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth. Example, if you have a tree with depth of 5, you will have 5 linked lists.
  4. You have two very large binary trees. T1 has millions of nodes. T2 has hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
  5. Given a directed graph, perform a Breadth First Search algorithm.

Concepts and Algorithms

Object-Oriented Design

  1. Design the data structures for an online book reader system.
  2. Imagine you have a call centre with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can’t handle the call, he or she must escalate teh call to a manager. If the manager is not free or able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implemented a method called ‘dispatchCall()’ which assigns a call to the first available employee.
  3. Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible.
  4. Design and implement a hash table which uses chaining (linked lists) to handle collisions.

Recursion

  1. Suppose you have a robot sitting at coordinate 0,0 of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from 0,0 to X,Y?
  2. Implement a recursive function that takes an integer and prints the hexadecimal representation.
  3. Write a recursive binary search.

Sorting/searching

  1. Given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Example:
    1. A: 1 3 5 8 _ _ _ _
    2. B: 6 7 9 10
  2. Imagine you have a 20GB file with one string per line. Explain how you would sort the file.

Testing

  1. How would test an umbrella?
  2. Find mistakes with this code.
    unsigned int i;
    for(i = 100; i >= 0; --i)
    printf("%d\n", i);
    

Knowledge based

C++

  1. How do virtual functions work in C++?
    1. Follow up: why does a destructor in a base class need to be declared virtual?
  2. What is the output of this program?
            #include <iostream>
    
            using namespace std;
    
            class polygon 
    
            {
    
                protected:
    
                int width, height;
    
                public:
    
                void set_values (int a, int b)
    
                { 
    
                    width = a; height = b;}
    
                };
    
                class output1 
    
                {
    
                    public:
    
                        void output (int i);
    
                };
    
            void output1::output (int i) 
    
            {
    
                cout << i << endl;
    
            }
    
            class rectangle: public polygon, public output1 
    
            {
    
                public:
    
                int area ()
    
                { 
    
                    return (width * height); 
    
                }
    
            };
    
            class triangle: public polygon, public output1 
    
            {
    
                public:
    
                int area ()
    
                {
    
                    return (width * height / 2); 
    
                }
    
            };
    
            int main () 
    
            {
    
                rectangle rect;
    
                triangle trgl;
    
                rect.set_values (4, 5);
    
                trgl.set_values (4, 5);
    
                rect.output (rect.area());
    
                trgl.output (trgl.area());
    
                return 0;
    
            }
    

Databases

  1. Write a SQL query to get a list of tenants who are renting more than one apartment.
  2. Draw an entity-relationship diagram fro a database with companies, people, and professionals (people who work for companies).
  3. Write a SQL query to get a list of all buildings and the number of open requests (Requests in whish status equals ‘Open’).

Threads and Locks

  1. What’s the difference between a thread and a process?
  2. You are given a class with synchronized method ‘A’ and a normal method ‘B’. If you have two threads in one instance of a program, can they both execute ‘A’ at the same time? Can the execute ‘A’ and ‘B’ at the same time?

MVC (Model-View-Controller)

  1. Explain Model-View-Controller in general.
  2. What is ASP.Net?
  3. Explain the role of Model in ASP.net MVC?
  4. Explain what a REST service is?
  5. What is routing in ASP.Net MVC?

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s