GeeksSpot

There are N persons in a country. N is very big in millions. Design a efficient data structure and algorithm to find out whether there is blood relations between given two person or say they have a common ancestor . My solution: Used a map //UID by Nandan Nilekani :) struct person { struct person *father; struct person *mother; list child; //However may not be needed for this problem string name ...i.e. //Add more } struct person * findAncestor ( struct person *a, struct person *b) { Take first node in stack. While ( stack is not null ) { Mark Node. Push Its ancestor in stack; } Take second node in stack. while ( stack is not null ) { If marked return Node, push ancestor in stack. } return NULL; } It has a drawback, i need to clear the flagged node before i apply the search algorithm again. But till now the best i know.

62. Find largest word in dictionary. 63. display all word in dictionary with starting char “ab”. 64. Find a element in an array with indefinite length. 65. Find the size of indefinite length array. Note all elements are initialized with @. 66. Find which rows is having maximum zeroes. 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 Once a rows got a zero there wont be any more 1’s. 67. In a matrix where each row and each column is sorted, find a number in o(1). 68. Find a element in bitonic array. Bitonic array first increase and decrese or vice versa. 69. Find a element in a rotated sorted array. 70. Find whether X is majority element in an array.

39. Find first non repeating character in a string. 40. Find whether two arrays of same size have same values. 41. Given a minheap find the max element. 42. Convert an array to heap. 43. Kth element in a Min heap. 44. implement a stack using heap. 45. Implement queue using heap. 46. Find union of k sorted list. 47. Merge the two heap. 48. Fibonocci with memorization/ Dynamic programming. 49. Find no of BST can be formed with n nodes. 50. Find no of legeal path between x and y which does not include ‘+’ A - + - - + - - - - - + - + + - - - - - - B 51. Find the largest common subsequence between two given strings. 52. Find the shortest common super sequence. 53. In a string, find the longest substring which is palindrome. 54. Find the maximum sum subarray without selecting two consecutive number. 55. optimal matrix chain multiplication. 56. Generate binary sequence of constant ‘N’. 57. Given an array generate all the possibilities of a...