How to prepare for a tech interview - coding interview

I will not put unnecessary literature here just the raw relevant strategies and topics:

1. Be confident and positive
2. Know your weakness and be ready to face them
3. Expect failures and do not be frustrated
4. Practice and develop the though process and ability to reduce a problem to a known problem or a set of known problems
5. While in bus, lunch time keep thinking about problems you found hard to follow or even thinking about applications of different data structures

Where to start:
1. Stack, Queues and Linked List
2. Arrays (sorting, searching and rotation, merging, median etc)
3. Strings (substring, pattern matching,  duplicate removal, encoding, regex, reversal, anagrams etc.)
4. Trees (BST problems, LCA, Threaded tree, B+ tree, Tree to LL conversion etc.)
5. Graphs (BFS, DFS, Shortest path, Back tracking and graphs, Travelling sales man)
6. Dynamic programming (Edit distance, Longest sum sub array, longest common sub string, Longest increasing sub sequence, Longest sorted sub sequence, Bridge connection problem, 0/1 and fractional knapsack problem)
7. Miscellaneous - Matrix spiral traversal, Battleship game, mine sweeper game, Suffix tree, Trie, Trie applications, LRU, Linked HashMap design, Priority Queues

Write code on IDE, then on paper, get familiar with as much problems as possible and try to relate them mentally to a already known problem. Keep a mental index of class of problems and when encounter a new problem try and find which class it belongs to and see if you can apply the same solution techniques to it.


 

Question bank: DS, Algo, Problem solving, technology

A collection of questions for Technical interviews:

1. How would you detect a repeated element in an integer array?
2. Given two sets, Write a function to provide the union of them.
3. Write a function to smooth out stock fluctuations.
4. Design an algorithm and write code to find two numbers in an array whose sum equals a given value
5. Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
6. Order the following runtimes in order of their asymptotic performance  O(2^n), O(n^y), O( 10^100), O(n!), O(n^n)
7. Given an array containing both positive and negative integers and required to find the sub-array with the largest sum in O(N)
8. Given an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
9. You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
10. Write an algorithm for Soduku puzzle
11. Given a number, describe an algorithm to find the next number which is prime.
12. Write a function to figure out if a computer's stack grows up or down.
13. Implement a thread-safe class that will read/write to/from a buffer
14. Write an efficient algorithm and C code to shuffle a pack of cards. The cards are stored in an array of integers.
15. Implement an algorithm to do string matching with wildcards.
16. Given an array [100] which contains numbers between 1..99. Find the duplicate value.
17. Write a program to find if a machine is big-endian or little-endian.
18. What is the difference between malloc(), calloc(), and realloc()?
19. Implement malloc or write the code for malloc memory allocation function.
20. Write a function to find the K biggest elements in the array, and return the sum. Do both in O(n) time.
21. Given a square with side length of 1 unit, describe all points inside square that are closer to the center of the square than to the edge of the square.
22. Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words). Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms.
23. reverse all the bits in the byte
24. count the number of set bits in a number. Optimize for speed and time.
25. multiply a number by 8 without using the * or + operators. Can you multiply with 7?
26. Add numbes in base n (not any of 10,16,8, or 2) -2 charles simonyi
27. how to implement a Merge Sort on disk
28. How to sort 10 million 7 digit unique phone numbers with ~ 1 MB memory?
29. How could you generate a file of k unique random integers between 0 and n-1 in random order?
30. design a technique to initialize an entry of a vector to zero the first time it is accessed.
31. Solve the mouse in a maze problem
32. Wire Routing Problem using Queues.
33. A “rotated array” is an array of integers in ascending order, after which for every element i, it has been moved to element (i + n) mod sizeOfList. Write a function that takes a rotated array and, in less-than-linear time, returns n (the amount of rotation).
34. You are given a list of Ball objects. Each Ball is either Red or Blue. Write a function that partitions these balls so that all of the balls of each color are contiguous. Return the index of the first ball of the second color (your result can be Red balls, then Blue balls, or the other way around). In haskell, you’ll probably want to return a ([Ball],Int).
35. Live Search is a search engine. Suppose it was to be tied into an online store. Now you’re given two lists. One is a [(SessionId, NormalizedQuery)]. That is, when a particular user performs a query, it is turned into some consistent format, based on their apparent intent, and stored in this logfile. The second list is a [(SessionId, ProductId)]. This indicates the product bought by a particular user. Now, you want to take these two (potentially very long) lists, and return some structure that will make it easy to take a query and return a list of the most popular resulting purchases. That is, of people who have run this query in the past, what are the most common products they’ve wound up buying? The interviewer said that this is an instance of a well-known problem, but I didn’t catch the name of it.
36. You’re given an array which contains the numbers from 1 to n, in random order, except there is one missing. Write a function to return the missing number.
37. Write a function to reconstruct a binary tree from its preorder traversal and inorder traversal. Take into account that the traversals could be invalid.
38. You have a [(WeatherStationId, Latitude, Longitude)]. Similar to #3, write a function which will, off-line, turn this into a data structure from which you can easily determine the nearest Weather Station, given an arbitrary Latitude and Longitude.
39. Write a function for scoring a mastermind guess. That is, in a game of mastermind (http://en.wikipedia.org/wiki/Mastermind_(board_game)), given a guess, and the actual answer, determine the number correct, the number wrong,and the number out of place.
40. Implement a trie (http://en.wikipedia.org/wiki/Trie) data structure. Write a function add, which takes a word, and a trie, and adds the word to the trie. Write another function lookup, which takes a prefix and a trie, and returns all the words in the trie that start with that prefix.
41. Write an algorithm to shuffle a deck of cards. Now write a function to perform some kind of evaluation of “how shuffled” a deck of cards is.
42. You are given a C string. Design a function to remove duplicate characters. i.e. "aaabbbccc" → "abc", "abc abc abc" → "abc"
43. You must serialize and deserialize a binary tree. Design two functions such that: char *f(Node *); Node *g(char *); tree = g(f(tree);
44. Space-time trade off: You are given a 5x5 grid where each cell has a weight associated to it, and a scale with the ability to give the total weight of any arbitrary selection of cells. In this grid, four of the five rows contain only one pound weights. One of the five rows contains only two pound weights. What is the minimum number of times you must use the scale, and in what configuration, to find the row with the two pound weights.
45. Problem: Given an array of strings (char * a[100]). Devise a way to determine and display all of the anagrams in the array.
46. Problem: Write code for implementing 2 stacks in 1 array.
47. Write code for reversing a doubly linked list.  
48. Write a program that performs a breadth first traversal of a binary tree.
49. Write a program that finds the depth of a binary tree.
50. You are given two nodes in a tree. Write a program to find the common root of the nodes.
51. Difference between a linked list and an array
52. Implement a linked list
53. Sort a linked list in. Can you do it in O(n)?
54. Compare and contrast the sorting algorithms you know
55. Write code to reverse a linked list.
56. Write a program to insert a new node in a circular linked list without traversing it.
57. Write code to sort an array. Why did you chose your method? What are its pros and cons?
58. Write a program to perform wild card string matching
59. Reverse a string.
60. Reverse words in a sentence.
61. Find a substring.
62. String campare
63. Given array of 1001 integers. All the integers are between 1 and 1000 (inclusive). Also, each integer can appear only once in the array except for one which occurs twice.  Give an algorithm to find the repeated number. Assume that you can access each element of the array only once and try to solve it without using extra storage.
64. Write code to read and write from a bounded buffer
65. Write a function to manage a heap using an existing array
66. Write a program to return unique elements or in other words remove duplicates.
67. Given two strings return a string that consists of intersection of the characters in the two strings
68. Write a program to print the Fibonacci sequence.
69. Write a program to cop strings A and B. Last 10 characters of A overlap the first 10 characring B.
70. Implement quick sort
71. Print data in a binary tree, level by level, starting at the top. Breath First Traversal/Search.
72. Implement strpbak
73. Function to select the eight strongest radio stations in a radio
74. Given two fixed length buffers padded with nulls/ Swap and reverse them, not swapping and reversing nulls.
75. Design and implement a self managing Thread Pool class
76. Given a set of strings, write code to print the strings that are anagrams.
77. Write a program to compact an array (remove duplicates).
78. Given an array of size N which has a number between 1 and N. Find out if there are any duplicates in the array. You are allowed to destroy the array.
79. Write a function to draw a circle. (x**2 + y**2 = r** 2). You cannot use any floating point computations.
80. Write a routine putlong() that prints out an unsigned long in decimal numbering system. You are allowed to use only putchar (no sprintf, itoa, etc)
81. How do you test if a number if power of 2.
82. In the game of tic tac toe, write a program to generate moves by a computer. This should be fast.
83. How would you go about finding out where to find a book in a library ( You dont know before hand how exactly the books are organized).
84. Given strings A and B, delete from B all characters present in A.
85. Write a small lexical analyzer. it should be able to parse simple expressions like a*b
86. What is the solution to the reader-writers problem
87. How do you optimize symbol table storage
88. Propose a good data structure that can hold 'n' queues in a finite memory segment. you are allowed to have some datastructure separate for each queue.Try to consume at least 90% of the memory space.
89. Write code for extracting unique elements from a sorted list of array
90. Given an array of integers. The sum of the elements of the array is known to be less than the max integer. Compute the sum. What if we know that integers are in 2's complement form?
91. Given a set of pointers to very long strings. Find the pointer to the lexicographically smallest and largest strings.
92. virtual function in C++
93. what happens if there is an error in constructor destructir.
94. Given a fixed list of numbers A. compare with another list B to find out if an element in A exists in B
95. How can you align a pointer to a 4 byte boundary in an efficient way.
96. What is a balanced tree?
97. Given a linked list find the center of the linked list.
98. How do you find if the sum of two unsigned integers has resulted in an overflow?
99. How do you represent an n-ary tree. Write a program to perform an breadth first traversal of this n-ary tree.
100. Count the number of times a given number occurs in a linked list.
101. Get the data stored in the nth position of a linked list
102. Pop for linked list
103. Insert a new node at nth index
104. SortedInsert in a linked list
105. Sort a linked list. It should use SortedInsert method from above question
106. Append on linked list to another
107. Given a linked list, split it into two lists - one for the front half and, one for the last half. If odd number of elements are present the extra node should go to the front list
108. Remove duplicates from a linked list
109. Write a function to divide the nodes in a lists in an alternate fashion
110. Merge Sort a list using FrontBackSplit ad SortedMerge
111. SortedMerge takes two sorted lists and merges them.
112. SortedIntersect: Given two sorted linked lists, create and return a new linked list that represents the intersection of the two.
113. Reverse and recursive reverse a linked list
114. Object oriented Concepts
1. Encapsulation
2. Polymorphism
3. Inheritance

Questions for designing / analytical rounds of product cos

1. How would you go about designing a phone book application for mobile with a limitation on memory?
2. How would you process the log that is being generated by some web application that runs 24/7 and is in gigabytes of size? You need to display the log in sorted format.
3. Design a library management software with tagging facility. Tags may have associated sub tags which should get automatically assigned. A search feature in the same software which may provide facility to search based on tags, author, availability.
One feature of advanced reservation on books.
A feature to impose fine for over due books.
search of members/user based on over due frequency, fine amount, number of books issued etc..
4. How to design a distributed system with efficient throughput time?
5. What parameters should be taken into account for designing a distributed application with probably a million of users?
6. How would you go about designing a self update system which has say 10 different sources of information, all source being web server and has relevant web services and APIs for information retrieval?
7. How to design a car parking system?
8. How to design a traffic system?
9. How would solve a problem if you were to find out how many movie tickets were sold today in Bangalore?
10. How do you beak a system say a web application. In how many ways and how do you use if you gain sensitive information.

..... more will be added

Java interview questions for start up companies

A set of real time java interview questions for internet product companies:
(ngpay, CA, Canvera, Directi, Lime labs etc..)

This will contain 4 sections, viz. java, ds/algo, designing, miscellaneous:

Java:
------
1. What are the usages of final keyword?
2. How to make a Map case insensitive with out extending the class or using .toLower on sring.
3. How does a lock work ?
4. Describe the internals of how a thread manipulates the synchronized block?
5. what is the use of finalize()?
6. How to stop a thread?
7. Why in windows the max heap size is limited to 2 Gb?
8. Hows the stack is divided in JVM?
9. Draw the heap layout of JVM?
10. Describe different garbage collection algorithms
11. How to use an unreachable object in Java?
12. 2 scenario where it will produce memory leaks and how to prevent them?
13. If a Map is declared final, can we put objects in it? how?
14. Why we need interface when we have something called abstract class?
15. If I override the hashcode method and return 1, will it always result in the equality of the objects?
16. What do you mean by hashcode of an object? How does it work?
17. Difference between a Vector and a list
18. When to use a ArrayList and when to use a linkedList
19. How is stack implemented in JVM?
20. How to design a synchronized singleton?
21. How to break a synchronized singleton?
22. What are the collection framework API?
23. How a multi threaded application works with monitor?
24. What is the relation between the eauels() and hashcode() methods?
25. How to design one thread pool?
26. Can we prioritize a thread? How?
27. How thread execution is handled by JVM?
28. why string is mutable?
29. what is out in System.out.Print()?
30. How the class loader works?

Update: I try to provide explanation for all the questions asked above. But not sequentially nor question wise. I will write explanation to topics in general which will contain answer to the questions in it.

Compare two trees to see if they are structurally identical

Q. Compare two binary trees to see if they are structurally identical

Solution:-

boolean identicalTree(Node a, Node b) {
if (a==null && b==null) return(true);
else if (a!=null && b!=null) {
return(
a.data == b.data &&
sameTree(a.left, b.left) &&
sameTree(a.right, b.right)
);
}
else return(false);
}

This is done in O(n) time complexity.

Merging two sorted arrays

Q.Write a method that will take two sorted arrays as input and merge them and give a new sorted array as output.

Soln:- Take the two arrays straight go to the ends (I assume you consider checks for boundary conditions) cause in this approach you also handle the case that you are not allowed to use extra space with the condition that one of the array has extra space left to accommodate the other.
Start from the tail picking and comparing each element and putting the largest among them to the tail of new array. Decrement the index of the array of which a value is put in the new array. Repeat until all elements are traversed.

Code:

int[] MergeSortedArrays(int[] array1, int[] array2)
{
int indexArray1 = array1.length - 1;
int indexarray2 = array2.length - 1;


if(array1 == null || array1.length == 0)
return array2;
else if(array2 == null || array2.length == 0)
return array1;

int[] mergedArray = new int[array1.length + array2.length];


for(int indexDestination = indexArray1 + indexarray2 + 1;indexDestination>=0;indexDestination--)
{
if(array1[idexArray1] > array2[indexarray2])
{
mergedArray[indexDestination] =array1[indexArray1];
idexArray1--;
}
else
{
mergedArray[indexDestination] = array2[indexarray2];
indexarray2--;
}
}

return mergedArray;
}

Time complexity of this algorithm would be O(n) where n is the sum total of number of elements in both the arrays, with extra space complexity of O(n) which actually is the requirement

Number with odd number of occurrence - Amazon

Q. Given an array containing positive integers, all the integers occur even number of times except one. Find this integer occurring odd number of times.

Solution: Sort the array and run a linear search with a counter incrementing on each iteration. On encountering a new number see if the counter value is odd or even. If odd the previous number is the result. Other wise reset the counter. repeat until result is achieved.

To sort O(lg(n)) * search for all --> O(n(lg(n)).

Solution 2:
An XOR operation on a number with itself will nullify it. So as all the numbers except one occurs even number of times. Everything will be 0 except for the number itself. So XOR operation in a loop will get you the answer.

The time complexity will be O(n) here.