Below are some questions I was recently asked, with my answers.
Please let me know if any of them are wrong, its a learning opportunity for me
What is the binary sort algorithm and how does it work?
The binary sort algorithm is insertion sort, except we use binary search to figure out where the insertion should happen.
The basic idea is as follows:
- Assume that the very first element i (index 0) is already sorted.
- Everything that is on the right of i is not sorted.
- Figure out where to put the value at i + 1, in the sorted part of the array. You do this by using binary search on the sorted part of the array. Where the start would be the 0 index, and end would be the pointer the start of the sorted section aka (i-1).
- The binary search algorithm would stop once it find a value less than or equal to what it was search for. Then you would take the value you want to insert and insert it into that position.
- The binary search algorithm would have to be modified since you aren’t searching for a particular value, rather your looking for a place. There for you would need to have two pointers converge to a particular point.
- Then you keep repeating this until you get through the whole array.
Time Complexity – O(n^2) : Since worst case we need to shift all values to the right, to do the insert.
Space Complexity – O(1): Since we are not creating anything new. O(n*log(n)) if we were to use recursive binary search, since would have function pointers on the call stack.
What is the binary search algorithm and how does it work?
The binary sort algorithm (BSA) is used to effectively sort data. It works on the principle of continuously cutting the data set in half, until it finds what it is searching for. However, this algorithm only works on data sets that are already sorted.
First the BSA checks the middle of the data set and compares the value it is searching for. If this value is the value it is searching for then it stops. However, if it is not equal, it checks if the value it found is bigger or smaller then the value it is trying to find. If the value is smaller, the BSA repeats the process on the left, whereas if the value is bigger it repeats the process on the right. This process is repeated multiple times until the value that the BSA is looking for is found.
What is recursion and how is it used?
Recursion is when the something starts calling its self, from inside its self. This programming technique is usually used when a single large program can be solved in smaller parts and has a valid base case. Such as computing the Fibonacci Sequence or traversing a binary search tree.
What is polymorphism and what is its purpose?
Polymorphism is an aspect of Object-Oriented Programming where a class can different functionality while sharing a common interface. For example you can have an DdConnector class, however there are many different types of DdConnectors that inherit from the base class. If you call the “open” method on a DdConnector object, it will use the under laying implementation, which could open a connection to SQLServer, Postgres, Redis, or etc.
Explain when you should use interfaces and when you should use abstract base classes.
Both interfaces and abstract classes are a type of contract, in the class structures of a software application. Interfaces are a form of contract between two different entities, where you want to separate the functionality from it’s implementation. This is done such that you reduce the amount of change required in your code. For example you could have an EmailSender interface, which would have one method called SendMail. Now you can accept the EmailSender interface every where, and call SendMail, while passing in the NameCheapEmailSender object that implements the EmailSender interface. When you need to change your email sender, you just need to pass in a new object that implements EmailSender, with out changing anything else in the read of your code.
An abstract class is a less extreme version of interfaces, where certain methods defined in it can have real implementations. This allows any child class that inherits from the abstract class to get those method implementations. However the abstract class cannot be instantiated.
The difference between the two can be further seen in how their child methods are derived. Since interfaces are “implemented”, where as abstract classes are “extended”.
When should you use static methods and static variables? And when shouldn’t you use them.
Static methods and variables can be used from a class without having to instantiate it. This is usually used when, you want to group a set of functionality or utility function together. An example of this is the “Math” class in JAVA, which gives the user all the math related function they need. You wouldn’t want to use them when you would be creating your inheritance-based class structures, most of the time.
And in general you wouldn’t want to use static variables in class to store the state of anything, since it could lead to concurrency issues depending on what your doing.
Write a SQL statement to create a table called “author” with the columns “id”, “name”, “age” (for MySQL or SQL Server).
-- For SQL Server CREATE TABLE author ( id int NOT NULL IDENTITY(1,1) PRIMARY KEY, name varchar(255) NOT NULL, age int, );
Write a SQL statement to create a table called “book” with the columns “id”, “title”, “genre”, “author_id” (for MySQL or SQL Server).
-- For SQL Server CREATE TABLE book ( id int NOT NULL IDENTITY(1,1) PRIMARY KEY, title varchar(255) NOT NULL, genre varchar(255), author_id int, CONSTRAINT FK_Book_Author FOREIGN KEY (author_id) REFERENCES author (id) ON DELETE CASCADE );
For the “author” and “book” tables created above, write a SQL statement to tell you the number of books each author has written, but only for authors who have written 2 or more books. The output should not show authors that have written only 1 book. The output should have the author’s name and the number of books they have written.
-- Way 1 SELECT author.name, COUNT(*) AS ‘# books’ FROM author, book WHERE author.id = book.author_id GROUP BY author.name HAVING COUNT(*) > 1; -- Way 2 select author.name, count(author.name) from author left join book on book.author_id = author.id group by author.name having count(author.name) >= 2; -- so "having" clause is basically a where clause for aggregate functions
In databases, what are indexes used for and how to you decided how to use them effectively.
Indexes in databases are used to speed up data retrieval. However, they come at the additional cost of space, and added complexity to database maintenance. They should only ever be used when the same type, or group of data is constantly being accessed. If the number of reads substantially utilizes the database host, then there should also be some sort of caching layer implemented in the application, such that it doesn’t need to query the SQL database directly.
What is the value of unit testing and what are some of your strategies for writing good unit tests?
Unit testing is used to test the functionality of the different parts of an application. Its value lies in the fact that they make the programmer, test their code in a systematic way. And feeds into a workflow where tests are run before anything gets committed to the master branch. I think the best way to write a test case, is to write the test before writing the application logic, since it gets you thinking about what edge/special cases to consider. This is also known as the test-driven development approach.
Is Java “pass-by-reference” or “pass-by-value”?
Java is pass by value. When you pass a object into a function, you aren’t actually passing the object or copying or anything of that nature. What you are actually is pass the value of a memory address, that points to an object on the heap.
There for if you pass a object to a function, you can change what the properties are and access methods on that object. But what you can’t do is, change what the pointer outside the function is pointing to.
A deeper explanation can be found here: https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value