Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the last occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 4 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the last occurrence in the array, the number to the right of it must be larger. We …

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the first occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 2 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the first occurrence in the array, the number to the left of it must be smaller. We …

Question: Given a matrix that is sorted in row wise and column wise, find a number if present in the most efficient way. Input: Find if 54 is present in matrix. 4 8 15 16 23 6 9 20 21 44 8 11 24 26 49 9 13 25 27 54 10 17 29 30 66 Output: Present Method 1(Brute force):- Here, we use two loops search the element in entire matrix. Its a linear search so its not an efficient way to solve this problem. Time Complexity:- O(rows * …

Question: Find sum of digits in a given number. Input: 65536 Output: 25 Method 1 (Iterative): In this code sample by using modulus operator(%), we extract the individual digits of given number then we add them together Method 2 (recursive):

Question: Given a sorted Linked List. Write a program to remove all the duplicates. Input: 4 -> 8 -> 8 -> 8 -> 15 -> 16 -> 23 -> 23 -> 42. Output: 4 -> 8 -> 15 -> 16 -> 23 -> 42 In a sorted Linked List, all the node that are duplicate will be together. To remove duplicates we need to traverse the linked list and if two adjacent nodes have same value, remove one of them. If adjacent node have different value then move forward. Time …

Question: Write a program to check if 2 linked lists are identical? Method 1(Iterative):- To Determine if both Linked lists are identical, we need to traverse both lists simultaneously, and while traversing we need to compare data of each node. Implementation Method2( Recursive):- It may seem that both recursive and iterative implementation are the same but the iterative version is recommended since it offers better control and the recursive implementation maintains a stack of all the callbacks.

Question: Write a program to count the number of bits that are 1(set bits) in a given integer. Input: 8 (1000) 11 (1011) Output: For 8 – 1 set bit For 11 – 3 set bits This question can be done in a very long way where we first convert the integer to its binary form and store its result in a character array. Traversing that character array would give the number of set bits. But that will not be an efficient way. We will use bit manipulation to solve …