#### 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*

*Jump to section: Data Structures Concepts and Algorithms Knowledge Based*

## Data Structures

### Arrays and Strings

- Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
- Given two strings, write a method to decide if one is a permutation of the other.
- Implement a function in C/C++: void reverse(char *str), which reverses a null terminated string.
- Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.
- 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

- Write code to remove duplicates from an unsorted linked list. (Follow up: how would you solve this problem without a temporary buffer?)
- 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.
- 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. - Given two sorted linked lists, how can you combine them?

### Stacks & Queues

- Implement a MyQueue class which implements a queue using two stacks
- 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

- 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.
- Given a sorted array, write an algorithm to create a binary search tree with minimal height.
- 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.
- 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.
- Given a directed graph, perform a Breadth First Search algorithm.

## Concepts and Algorithms

### Object-Oriented Design

- Design the data structures for an online book reader system.
- 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.
- 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.
- Design and implement a hash table which uses chaining (linked lists) to handle collisions.

### Recursion/Dynamic Programming

- 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?
- Implement a recursive function that takes an integer and prints the hexadecimal representation.
- Write a recursive binary search.
- Given a string, find all its permutations.
- Maximum subarray: Given an integer array
`nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

### Sorting/searching

- 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:
- A: 1 3 5 8 _ _ _ _
- B: 6 7 9 10

- Imagine you have a 20GB file with one string per line. Explain how you would sort the file.

### Testing

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

## Knowledge based

### C++

- How do virtual functions work in C++?
- Follow up: why does a destructor in a base class need to be declared virtual?

- 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

- Write a SQL query to get a list of tenants who are renting more than one apartment.
- Draw an entity-relationship diagram fro a database with companies, people, and professionals (people who work for companies).
- 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

- What’s the difference between a thread and a process?
- 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)

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