A few Videos on Data Structures and Algorithms

 

Some Programming Questions

 Some Programming Questions

I was encouraged to write this blog by my friend Vinay Dabholkar. I thank him very much. I hope you find it useful.

I have “served” in the Indian IT Industry for about 14 years. I have conducted entry-level interviews. I have also been a faculty member at a private University at Bengaluru for a semester.

The most important skill I look for is “coding”, i.e., the ability to write a computer program.

One of my most favourite questions is write a method to find the minimum in an array. Many students will write the “main” method with print statements. Many will hard code an array. Many will make the mistake of sorting the array. If you got the method right, I will ask if the array can be empty and have you taken care of it.

Apart from coding, other questions include RDBMS and SQL. Nowadays students are expected to know a lot of current trending topics such as Data Structures and Algorithms, Data Science, Machine Learning and IoT.

I am listing below a few questions/problems. Most of them can be answered using a language like Java or C++. Handle all kinds of situations that can occur. Write the most efficient code,

1. Write a method which finds the sum of an integer array.

2. Write a method which finds the average of an integer array.

3. Consider the statement: double d = 1/2;

What is the value of d?

4. Consider the method:

int m(int x) {

x = x / 2;

}

… // main program

m(y);

…

What is the value of y after m is called?

5. Consider the method:

int m(int x) {

x = x / 2;

x++;

x++;

x++;

x = x++;

return --x;

}

… // main program

int y = m(7);

…

What is the value of y after m is called?

6. Write an efficient method which checks whether a given array contains a certain element. How will you do this using templates in C++ or generics in Java?

7. Write an efficient method which counts the occurrences in a given array of a certain element. How will you do this using templates in C++ or generics in Java?

8. Is it always possible to do binary search on an array? Write code for binary search.

9. Write a method that merges two sorted arrays into a single sorted array.

10. What is a stable sorting algorithm? Give examples of stable and unstable sorting algorithms.

11. What is the most efficient way of finding the middle-valued element of an array of numbers?

12. How can I find the minimum and maximum values in an array of numbers using the least number of comparisons?

13. What is the best way to represent a set? What are the times for set operations?

14. Write a class that implements a queue without using arrays or ready-made collections or STL classes.

15. Write a class that implements a stack without using arrays or ready-made collections or STL classes.

16. What is an abstract data type?

17. Write an interface for stack.

18. Write an interface for queue.

19. What are the ways of representing a directed graph?

20. Write a method to check if a directed graph has a cycle.

21. Write a method to check if a node can be reached from another in a directed graph.

22. Write a method to find the 3^rd smallest element in an array.

23. Write a method to find the k^th smallest element in an array.

24. Describe a data structure for storing words of a dictionary. It should be possible to search for any word in O(n) time where n is the word’s length. Write the search method,

25. What is a hash table? What is the difference between separate chaining and probing?

26. Write methods for insert and delete for a queue using a circular linked list. How is a circular linked list better than a simple linked list?

27. List applications of stacks.

28. List applications of queues.

29. List applications of heaps.

30. What are AVL trees? What are their advantages?

31. Write a method to reverse an array.

32. Write a method to find a given element in a sorted array efficiently.

33. Write a method that takes in two linked lists and joins them efficiently.

34. Write a method that will sort an array of size n in ascending order using O(1) extra space with a guarantee of O(n log n) worst case time.

35. Two linked lists of sizes m and n are the same beyond a common node. Write the most efficient code for finding the first common node. What is the time complexity?

36. Write a method to compute factorial of n which is efficient in time and space.

37. Write a class for a binary search tree with insert, delete and search methods.

38. Write a class for a general tree with insert, delete and search methods.

39. Write a method for in-order traversal of a binary tree.

40. Write a method which reads a string containing digits and operators +, -, *, / and evaluates it.

41. There is an array with positive and negative numbers.

Write a method to find a contiguous part of the array with the maximum sum.

42. Write an efficient method returning the Fibonacci of n.

43. Write an efficient method to multiply two matrices.

44. Write a method to find the least costs of travelling by air from Mumbai to all cities in India assuming fixed fares.

45. Determine the Merge Point of 2 Linked Lists

46. Find distinct elements common to all rows in a Matrix

47. Determine the Least Common Ancestor in a Binary Search Tree

48. Print the maximum square sub matrix of given size

49. Maximum size rectangle binary sub-matrix with all 1s

50. Palindrome Partitioning

51. Determine common elements in all rows of a given Matrix

52. Return the kth smallest element from an array of integers

53. Construct the Binary Search Tree given the Pre-order traversal

54. Merge 2 sorted arrays

55. Merge 2 sorted linked list such that the merged list is in descending order

56. Given a Circular Linked list find the element at 1st position after n shifts.

57. Given an array of numbers sorted in ascending order and a key, find the value in the array closest to the key.

58. Given a string of characters, find the length of the longest substring which is a palindrome.

59. Given a bag of limited weight capacity and a number of items each with a cost and weight, find how the bag can be filled to maximize the cost of the bag.

    1. Case 1: Assume that an item can be picked up even partially,

    2. Case 2” Assume that an item is either picked up or not picked up.

60. Given n-letter sequences of characters, we say a sequence is directly related to another if the former can be converted to the latter by changing only one character. Given a set of n-letter sequences, find if a sequence s can be connected to another d either directly or indirectly.

61. Given a set of points in a plane, find the least distance between any two points.

62. Assume there are n people who are on a road at different positions. There are n houses aat different locations along the road. How will you assign the houses the people so that the overall time taken for them to reach their houses is minimized?

63. Given two strings, find the length of the longest common subsequence.

64. Given a linked list, write a method to reverse it without creating any new node.

65. How will you cut a rope of length n into smaller parts of integral length so that the product of the lengths is maximized?

66. Given binary trees t and s, check if s is a subtree of t.

67. Given a piece of gold weighing m grams, break it into smaller pieces each of integral number of grams so that the net price is maximized. You have different prices for different weights.

68. Given a linked list, delete all occurrences with a given kay.

69. Given a binary tree containing values, check if it is a binary search tree.

70. Given a binary tree and a key, find the lowest level where the key occurs.

71. Given a sequence of cells each with a number of 1 Rupee coins, find the maximum money that can be had if I am allowed to pick up coins from a cell only if I am not picking up from a cell to its right and from the 2 immediate cells to its right.

72. Given a graph with units on the x axis starting from 0 and going till n, and different height on the y axis, find the maximum area rectangle that can fit in it.

73. Given a matrix, find the maximum sum subarray.

74. Given a matrix, find the maximum area of a rectangle with all zeros.

75. Trial Cars Problem.

76. Four Queens Problem: Given a 4 x 4 chess board, arrange 4 queens on it so that all the queens are safe from each other.

77. What is the best way to multiply two n-degree polynomials?

78. Activity Selection: Given n activities with positive integral start and end times, find the maximum number of activities that can be done if only one activity can be done at a time.

79. Job Sequencing: Given n jobs each with a positive integer deadline and a profit that can be gained if it is completed before the deadline, find the maximum profit, if only one job can be done at a time.

80. Shelves Fitting.

81. Egyptian Fraction: Given any fraction less than 1 in the form n/d, express it as a sum of fractions of the form 1/b where each b is unique. For example, 2/3 = ½ + 1/6.

82. Maximum Subarray Product: Given an array of integers (positive and negative), find the maximum product of any subarray.

83. Minimum Subarray Product: Given an array of integers (positive and negative), find the minimum product of any subarray.

84. Given an undirected graph and an integer m > 0, write a method to check if the vertices can be colored using m different colors so that no two adjacent vertices are of the same color.

85. Implement a stack using queues.

86. Implement a queue using stacks.

87. Search for a key in a sorted array.

88. Implement a stack with an additional operation which gets the minimum value in the stack efficiently with/without using an auxiliary stack.

89. Find the third largest element in an array.

90. Find the fourth largest element in a linked list.

91. Check if a binary tree is full, perfect or complete.

92. Check if a string of opening and closing parentheses is balanced.

93. How many reversals of “(“ and “)” are needed to make a string of parenthesis balanced?

94. Reverse a string.

95. Reverse every word in a string.

96. Word fitting with maximum profit.

97. Word processing with minimum cost.

98. Determine if a directed graph has cycles.

99. Topological sort in directed graph.

100. Evaluate a postfix expression.

101. Evaluate an infix expression containing integers +, -, *, ., { and ).

102. Convert from infix to postfix.

103. Sort a linked list in O(1) space.

104. Interleave 2 linked lists in O(1) space.

105. Delete all occurrences of a value from a liked list.

106. Delete all occurrences of a value from a doubly liked list.

107. Check if a linked list has a value.

108. Get least level of a key in a binary search tree.

109. Get n th number in sequence of multiples of 5 and 7.

110. Get LCM of two integers.