[3 min IT]Coding Interview Questions

Cracking the Coding Interview- 150 Programming Questions and Solutions

*Data structures
1. Arrays and strings
— Hash tables: maps keys to values for highly efficient lookup
— Hash function: maps key to an integer to indicate the index in an array
— binary search tree: guarantee an O(log n) lookup time
— ArrayList: a dynamically resizing array, resize itself as needed while providing O(1) access. When the array is full, the array doubles in size.
— StringBuffer: create an array of all strings that need to concatenate and copy back to a string only when necessary
2. Linked lists
— Create a linked list: singly linked or doubly linked
— Delete a node from
1) a singly linked list: find previous note and set prev.next = n.next
2) a doubled linked list: then update n.next.orev = n.prev
3) check for the null pointer and update the head or tail pinter as necessary
— Runner technique: iterate through the linked list with 2 pointers simultaneously, with one ahead of the other
— Recursive problems: take at least O(n) space when n is the depth of the recursive call. All recursive algo can be implemented iteratively
3. Stacks and queues
— Implement a stack: LIFO = last in first out
— Implement a queue: FIFO = first in first out
4. Trees and graphs
— Binary tree: a rooted tree that is also an ordered tree in which every node has at most two children
— Binary search tree: for all nodes, left children are ≤ current node aka all the right nodes
— Balanced tree: the height of the left and right subtree of any node differ by not more than 1
— Full and complete tree: all leaves are at the bottom of the tree and all non-leaf nodes have exactly 2 children. Tree has 2^n -1 nodes
— Binary tree traversal: 1) in-order traversal = left — >root — >right = give nodes in non-decreasing order 2) post-order = left — >right — >root = delete tree 3) pre-order = root — >left — >right = copy tree
— Red-Black tree: a particular node has color as an extra attribute, either red or black
— AVL tree: dynamic self-balancing
— Tries: characters instead of numbers are stored at each node
— Graph traversal: 1) BFS = Breadth first search, good for large trees 2)DFS = depth first search, the easiest to visit every node but not for large trees

*Concepts and Algorithms
5. Bit manipulation
— Purpose: algorithmically manipulating bits or other pieces of data shorter than a word
— Bits facts and tricks
— Common bit tasks: get, set, clear, and update bit
6. Brain teas
— develop rules and patterns
— worst case shifting
— algorithm approaches
7. Mathematics and probability
— Prime numbers
— Probability
8. Object-oriented design
— Steps: 1) handle ambiguity 2) define the core objects 3) analyze relationships 4) investigate actions
— Design patterns: 1) singleton class: a class has only one instance 2) factory method: create an instance of a class, with its subclasses deciding which class to instantiate
9. Recursion and dynamic programming
— Recursion: build off solutions to sub-probelms, i.e. cimpute f(n) by f(n-1), can be implemented iteratively but inefficient
— Bottom-up recursion: from a simple case to multiple elements
— Top-down recursion: divide the problem for case N into sub-problems
— Dynamic programming: i.e. to generate Fibonacci numbers
10. Scalability and memory limits
— Steps: 1) make believe 2) get real 3) solve problems
11. Sorting and searching
— Bubble sort: runtime O(n²) avg, worst. memory O(1). Begin from first 2 elements, swap if 1st > 2nd
— Selection sort: runtime O(n²) avg, worst. memory O(1). Find the min. using a linear scan and move it to the front
— Merge sort: runtime O(n log(n)) avg, worst. memory depends. Divide the array in half, sort and marge back together
— Quick sort: runtime O(n log(n)) avg O(n²) worst. memory O(log(n)). Pick a random element and partition the array to have all smaller numbers come before larger numbers; partitioned element is not guaranteed to be the median
— Radix sort: runtime O(kn) avg. Sort integers that have finite number of bits by iterating through each digit of the number and grouping numbers by each digits
— Binary search: look for x in a sorted array by comparing x to the midpoint of the array. If x < midpoint, search the left half. If x>midpoint, search the right half. Repeat until find x or subarray has size=0
12. Testing
— Big picture understanding, knowing how the pieces fit together, organization, practicality
— Testing a real world object: 1) who will use it and why 2) what are the use cases 3) what are the bounds of use 4) what are the stress/failure conditions 5) how would you perform the testing 6) what are the test case and how to perform the testing
— Testing a piece of software: 1) manual or automated testing 2) black box or white box
— Testing a function: 1) define the test cases: normal case, extreme case, nulls and illegal inputs, strange inputs 2) define the expected result 3) write test code
— Troubleshooting: 1) understand the scenario 2) break down the problem 3) create specific manageable tests

*Knowledge based
13. C++
14. Java
15. Database
— Normalized database: minimize redundancy
— Denormalized database: optimize read time
— SQL statement:
Courses: courseID, courseName, teacherID
Teachers: teacherID, teacherName
Students: studentID, studentName
StudentCourse: courseID, studentID

Query 1: get a list of all students and how many courses each student is enrolled in
SELECT studentName, students.studentID, count(studentCourses.courseID) as [Cnt] FROM students
LEFT JOIN studentCourse ON students.studentID = studentCourse.studentID
GROUP BY students.studentID, students.studentName

SELECT max(studentName) as [studentName], students.studentID, count(studentCourse.courseID) as [Count] FROM students
LEFT JOIN studentCourse on students.studentID = studentCourse.studentID
GROUP BY student.studentID

Query2: get a list of all teacher and how many students they each teach
SELECT teacherName, isnull(studentSize.Number, 0) FROM teachers
LEFT JOIN
(SELECT teacherID, count(studentCourse.courseID) AS [Number]
FROM courses LEFT JOIN studentCourse
ON courses.courseID = studentCourse.courseID
GROUP BY courses.teacherID) studentSize
ON teachers.teacherID = studentSize.teacherID
ORDER BY studentSize.Number DESC

— Small database design: 1) handle ambiguity 2) define the core objects 3) analyze relationships 4) investigate actions
— Large database design: denormalize the data because joins are very slow
16. Threads and locks