Given an array {7, 5, 8, 3, 1, 4} – write a program that will return the largest 3 nos

public class ReturnThreeMaxNos {

 public static void main(String[] args)
 {
  int array[] = {
    1, 22, 1, 3, 212, 4, 43, 5, 1
  };
  
  int max = -1;
  int max2 = -1;
  int max3 = -1;
  
  for (int i : array) {
   if (i > max) {
    max3  = max2;
    max2 = max;
    max = i;
   }
   else if (i > max2) {
    max3 = max2;
    max2 = i;
   }
   else if (i > max3) {
    max3 = i;
   }
  }
  
  Formatter f = new Formatter();
  f.format("The max is: %d\n The 2nd max is: %d\n the 3rd max is: %d", max, max2, max3);
  System.out.print(f.toString());
  
 }
}

Given an array {7, 1, 3, 2, 2, 4, 4, 5, 1}, write a program (java) that will match the first duplicate and return

Solution:

We would use a Set since it is primarily optimized for testing membership. Worst time is order of n.

import java.util.HashSet;
import java.util.Set;

public class FindFirstDuplicate {

 public static void main(String[] args)
 {
  int array[] = {
    1, 7, 1, 3, 2, 2, 4, 4, 5, 1
  };
  int firstDuplicate = matchFirstDuplicate(array);

  if (firstDuplicate == -1)
   System.out.println("No duplicates");
  else
   System.out.println("Duplicate found: " + firstDuplicate);

 }

 public static int matchFirstDuplicate(int[] array)
 {
  Set<Integer> dupMap = new HashSet<Integer>();
  
  for (int i : array) {
   if (dupMap.contains(i)) {
    return i;
   }
   else {
    dupMap.add(i);
   }
    
  }
  return -1;

 }

}

Technical Interview Questions – Java, Data Structures, Logic, Puzzles

The following is a list of technical interview questions that are going around in Silicon Valley as well as Microsoft. I disclaim any veracity of where the question originated just that these are questions that have been asked in interviews.

Please leave your comments or answers to these questions and I would be adding to that as well as to this list.

  1. Reverse a singly linked list – recursively. [Answer is on this site]
  2. Reverse a singly linked list – iteratively. [Answer is on this site]
  3. What is the difference between a recursive and an iterative process? What are the merits of each over the other? [Answer is on this site]
  4. Given an array {7, 1, 3, 2, 2, 4, 4, 5, 1}, write a program (java) that will match the first duplicate and return. [Hint: what data structure would you use and why? Do the analysis and come up with the Big O for your program] [Answer]
  5. Given an array {7, 5, 8, 3, 1, 4} – write a program that will return the largest 3 nos. [Answer]
  6. Write an implementation of a LRU cache. [Hint: you would need to use a Linked List and a Set implementation. Analyze it as well]
  7. Write a recursive and iterative program to list all files in a directory and its sub-directories. You are given the following two API calls:
    getSubFolder(String folderName) and getFiles(String folderName)
  8. What is the difference between Depth First Search (DFS) and Breadth First Searc (BFS). What search strategy to be used in order to utilze fewer resources (memory etc.)
  9. Implement Inorder, PostOrder and PreOrder traversals recursively. These are all DFS traversals.
  10. Implement Inorder, PostOrder and PreOrder traversals iteratively. These are all DFS traversals. This is more complicated and time consuming than the recursive approach.
  11. What is the difference between an arraylist and a linked list in Java. What is the difference between an array and a linked list generically.
  12. What is a multiway tree and how is it suitable for being used as an index in databases? [Explaing BTree]
  13. How do you detect overflow and underflow in Java. Write a program.
  14. Write a program to detect a cycle in a linked list. This implies that one of the nodes in a linked list points back to one of its predecessors.
  15. Write a program to print out the permutations of the characters in a string. For instance: print out the permutations for string “abcd”.
  16. Write a program to print out the combinations of the characters in a string. For instance: print out the combinations for string “abcd”. [This I found to be more complicated than evaluating the permutations.]
  17. Write a program to do merge sort either recursively or iteratively. [Answer for recursive]
  18. Write code to demonstrate a solution to the “towers of hanoi” problem. [Hint: write the recursive implementation]
  19. What is a deadlock – database or application and how can it be avoided? [Explain deadlocks and what it means in a database and in your java application and steps to avoid it.]
  20. Java: what are the thread states?
  21. Describe heap sort and the algorithm for retrieval.
  22. What is a priority queue? How can one implement a priority queue?
  23. What is a race condition in the context of threads?
  24. What is the double lock paradigm in Java? How is it resolved in Java 5 and upwards?
  25. What is the difference between an abstract class and an interface?
  26. What is the iterator paradigm?
  27. Describe Garbage Collection in Java. [Hint: talk about the 4 GC algorithms and the kind of applications that they are utilized in]
  28. What do you understand by network latency and network throughput.
  29. Explain memory management on Windows or Unix. [Hint: explain virtual memory, paging, page faults, swapping etc.]
  30. Describe changes in HTTP 1.1 over 1.0. [Hint: keep alive, persistent connections, asynchronous behavior through pipelining]
  31. What are complex types in XSD? How are complex types created?
  32. Specify the WSDL structure.
  33. What are the BP 1.1 approved web service styles? [Hint: Document/Wrapped, RPC/Literal]
  34. How will you optimize a SQL query in Oracle?
  35. What are nested loops in Oracle?
  36. What are hash joins in Oracle?
  37. What are corelated queries in SQL?
  38. What is a BTree index?
  39. What is a bitmap index?
  40. What is a binary search tree? Write code to insert an element in a binary search tree.
  41. Find the mth to the nth element in a linked list by writing code. For instance: find the 5th from the last element in this linked list.
  42. Write code to reverse an array.
  43. Write code to reverse a string.
  44. Write code to evaluate if a string is a palindrome.
  45. Write code to implement binary search iteratively.
  46. Java: Write a program to demonstrate the producer-consumer scenario using threads.
  47. Java: What is a semaphore and how is it used?
  48. Java: What is a latch in thread sematics – write code to demonstrate a latch.
  49. What are intrinsic locking in Java? What is the alternate?
  50. Describe an interruption policy for threads in Java.
  51. Given a set of ‘n’ numbers (all unique). One number is missing – how will you find the missing number?
  52. Write an implementation of a stack that has a maximum capacity of ‘n’ elements. It should block if there are 0 elements left to pop. It should also block when it has reached maximum capactity and the push operation is invoked.
  53. Repeat the same for a queue.
  54. Java: write two methods:
    String read(String key) => returns the value associated with a key
    and void refresh() => reads and populates the cache from a persistence store so that consumers can invoke the read() method to retrieve data. The refresh is a part of a scheduled job that runs every x minutes. Note, we have to think about the concurrency here.
  55. How do you find the strongly connected components of a Graph? [Answer Here]

 

 

Please feel free to provide even more questions and solutions. This way the solution that you provide can be vetted and debated and marked as the correct or most valuable solution. I would be adding solutions as well to the questions as and when I get time.

 

Recursion versus Iterative code development

Earlier we had looked at the structure of a linked list and demonstrated an iterative java program to reverse it. In this entry, the stress would be on recursively implementation.

What is recursion and why is it used?

Recursion is the process of solving a complex problem by breaking it into smaller subproblems that are easy to solve. It is a decompositional technique and a variety of computer problems make their way into easily being resolved through the art of recursion. For instance: divide and conquer algorithms such as merge sort, reversing a linked list, towers of hanoi etc.

The easiest way to provide a recursive solution to a complex problem is to break down the problem into subproblems and so on till the subproblems are easier to comprehend and consequently easier to solve. For instace, lets break down the problem of reversing a linked list.

We will examine a similar linked list to that in an earlier blog entry (A->B->C->D).

if size = 1 then there is no need to do anything

if size = 2 then traverse to the node 2 and then reverse pointer from 2 to 1

if size = 3 then traverse to node 3 and then reverse pointer from 3 to 2 and then perform the steps outlined above

and so on. This leads us to a solution of the problem recursively

static Node reverseRecursive(Node n, Node previous, Node end)
{
    if (n.next != null)
    {
        end = reverseRecursive(n.next, n, end);
    }
    else 
    {
        end = n;
    }
    n.next = previous;
    return end;
}

The primary advantage of recursion is that it is simple to implement as the mathematical concepts can be easliy translated into a recursive solution.

The disadvantage is the fact that there is a lot of overhead of the recursive method invoking itself repeatedly. This leads to method arguments, method return addresses etc being stored in stack.

Iterative program to reverse a linked list has been elucidated in an  earlier blog entry.