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