## Wednesday, July 30, 2014

### Algorithm Interview Questions - Set 1

1. A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.
2. Intersection of n sets without using a hash table.
3. Implement a LRU(Least Recently Used) cache
4. Implement a function to compute cubic root
what is the time complexity?
5. Given a matrix with 1′s and 0′s, find the number of groups of 1′s. A group is defined by horiz/vertically adjacent 1′s.
6. Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the cells in the corresponding column and row to zero.
7. You are given a set of numbers 0 – n. Given a k, print all subsets of size k. Give the time complexity of the algorithm.
8. Given an unsorted array of integers, find a 3-element subset that sums to zero..Complexity…?
9. Multiply two big integers which don’t fit into an built-in integer type. How would you represent big numbers as a data structure? Write the function to multiply two big integers.
10. Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0
11. How to implement Sqrt(double k) efficiently?   OR   Compute the square root of a number down to a certain precision.
ie sqrt(num, precision) returns a number that is in-between sqrt(num) – precision and sqrt(num) + precision.
12. How to implement multiple inheritance in Java
13. Given set of coins and each coin has its unique probability to be head up, say double[] probs stores the probability values for all coins, print out all different cases and accordingly probability.
14. Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons).
15. FInd the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 –> 2 4 6
16. Given an array of integers, now we want to erase all 0′s (can be other value), and we want the result array condensed, meaning no empty cell in the array.
17. given a list of words with a same size and a big string that contains one of the permutation of all the words combined(say p), find the startindex of the string p in the big string
18. Reverse a Linked list (Recursively/Non recursively)
19. Write the actual code to parse a regular expression including “*”, which stands for 0 or more characters, “+”, which stands for 1 or more characters, and “.”, which stands for 1 exact character.
20. print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3
21. search needle in haystack problem. Make it more robust.
22. Implement a function rotateArray(vector arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.
23. Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum.
Eg – “(ab(xy)u)2)” -> “(ab(xy)u)2″
“)))(((” -> “”
24. All Possible balanced parenthesis problem
25. How will you design TinyUrl?
26. How will you design facebook newsfeed. Focus was on a design which could handle the huge number of status updates and display them on each of the user’s friend’s wall.
27. Implement a function
which returns single lines from a buffer. To read the buffer, you can makes use of a function
which fills buf with upto len chars and returns the actual number of chars filled in. Function readLine can be called as many times as desired. If there is no valid data or newline terminated string available, it must block. In order to block, it can use read function which in turn will block when it doesn’t have anything to fill the buf.
28. Find Kth smallest element in a BST.
29. Implement a queue data structure given only stacks. What is the time complexity of enqueuing and dequeuing operations?
30. Given a Binary Search Tree, iterate over the elements without using recursion.
31. Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc.
32. Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.
33. Print a singly-linked list backwards, in constant space and linear time.
34. Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).
35. Given a set of words, group them into sets of anagrams.
36. Given a string, remove all the duplicate characters (not necessarily consecutive)
37. Write a function to tell if two line segments intersect or not.
38. Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ).
39. Write a function that computes log2() using sqrt().
40. Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?
41. Write a function to prettify Json objects
42. Given sorted arrays of length n and 2n with n elements each, merge first array into second array.
43. You are given intervals of contiguous integers, like [1, 10), [15, 25), [40, 50), which are non-overlapping and of a fixed size.
Design a data structure to store these intervals and have the operations of insert, delete, and find functions
44. Design a system to detect typos and provide suggestions to users.  Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
45. Find the n-th smallest element in a binary tree.
46. Print a binary tree in infix order. Recursive and iterative.
47. Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.What's the advantage of the design?How would the total credit points of a user be calculated based on my design?
48. Write a code to convert an ASCII representation of a positive integer to it's numeric value.
49. Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
50. Given a binary tree, write a function to find the length of the longest path in the tree.
51. Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
52. Find the minimum depth of binary search tree.. http://www.glassdoor.com/Interview/Find-the-minimum-depth-of-binary-search-tree-QTN_127018.htm
53. Print a binary search tree. Each level on a new line.
54. Implement the div operator without using / or %
55. You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house.
56. Given a matrix print it clockwise from the first element to the very inner element.
57. Given an array of integers and size find 3 integers that sum to zero.
58. You are going to take some numbers as an input from a file. You need to witer a program to find longest increasing sequence. You should process it as soon as you are taking an input. After finishing the last input immediately you should be able to tell the sequence.
Input: 1 5 3 4 6 4
Output: 3 4 6
59. A file contains 10 billions of Strings and need to find duplicate Strings. You have N number of systems available. How will you find duplicates?
60. Given a set of integers, print out all its subsets.
61. Code a program to check if a given string is matching a given regular expression
62. Each key on the telephone represents a list of letters. Given a telephone number, please write a program to output all the possible strings the telephone number represents.
63. write a function to check if a graph was bipartite.
64. Given two binary trees, return true if they have same elements (irrespective of tree structure)
65. Given a string, remove all chars from the string that are present in say another string called filter.
66. Given two events, each with a start and end time, implement a boolean check to see if they overlap.
67. Print out all combinations of k numbers out of 1...N
e.g. when k = 2, n = 4
Print out 12, 13, 14, 23, 24, 34
68. runtime complexity of binary search and the average num of guesses it takes to find a number between 1 to 1000.  Given the numbers 1 to 1000, what is the minimum numbers guesses needed to find a specific number if you are given the hint "higher" or "lower" for each guess you make.
69. Advantage of B Trees - Used in databases for indexing. Adv. Less number of memory lookups because of less hierarchy. Large fanout.
70. Given a set of inputs in a log file: log:
example:
1,2
1,1
2,1
3,1
1,2

out:
1,2
2,1
3,1

The output should be all the unique numbers and the count associated with them.
71. Given an array, print the largest subarray that has elements in an increasing order
72. How do you find sequences of consequtive integers in a list that add to a particular number.
73. Given a score S, and individual points p1,p2,...,pn. give all combinations of p that add up to s.
74. Given a large string (haystack), find a substring (needle) on it.
75. Given a list of strings, for each string, find if it has an anagram in the list.
76. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. n = 3.
1 1 1
1 2
2 1
3
Ans = 4
77. Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E
Output: A->E->B->D->C
78. Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping. Input: face
Map: {a -> @, 4, A}
Output: f@ce, f4ce, fAce
79. Get numeric number out of a roman string, linear time
Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
Input/Output:
II = 2, III = 3, IV = 4
VI, VII, VIII
IX = 9
XL = 40,
XLIX = 49
80. Merge 'k' sorted arrays, each array may have max 'n' elements
81. how does hash map implementation looks like
82. Implement strstr in C
83. Write some pseudo code to raise a number to a power.
84. Given an array of integers, find the maximum number that can be reached by summing the best possible consecutive subsequence of the array.
85. Design a linked list operation that takes a singly-linked list (only forward ptrs, no backward ptrs) as input and reverses the list.
86. Given a 1TB file of serialized 4 byte integers, and 2GB of ram, sort the integers into a resulting 1TB file. My interviewer was very collaborative in entertaining various solution ideas until we came up with a combo that would work performantly and reduce the number of passes over the 1TB file and intermediate files.
87. Write a list class where the only data structure available is a stack
88. Determine the 10 most frequent words given a terabyte of strings.
89. Use basic arithmetic operations (+-*/) to implement sqrt function.
90. Print out all the permutations of a string
91. Write a function that prints out all subsets of a given set of numbers.
92. Write a function that takes in two binary strings and returns their sum (also a binary string).
93. Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.
94. Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number.
For example, from array 1, 1, 2, 3, 3, 1
You should get 2, 1, 1, 2, 2, 3, 1, 1
Write a program to solve this problem.
95. given the utitlies getFriend(User u) and areFriends(User u1, User u2), write the function which takes as parameter the array of users and return a bool saying if you can divide the users in 2 groups s.t. if u1 and u2 both belong to a certain group, they are not friends.
96. remove duplicates in a string.
97. Given a file with 3-letter words, print all 3x3 with each row, column and diagonal being one of the words from given file.
98. Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph).
99. Given n+1 buckets with n of them with ball inside and move(a,b) function, that moves ball from bucket a to bucket b. Each ball has a different number from [1,n] on it. Move balls, so each bucket has a ball with matching number in it.
100. Implement a power function to raise a double to an int power, including negative powers.
101. Given a String containing java-script assets, write a parser which will output the String with proper indentation.
102. Given a certain state of an Othelo game board, location on the board, a certain piece to place on the given location, update the board and make the required validations
103. Given a collection of words, return a collection of anagrams found in the
given collection
104. Output a single linked list in reverse, in linear time and constant space, and recursively
105. Pascal’s Triangle – print a row
106. Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).