nikoo28

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 …

We have discussed some very basic data structures. Sometimes, we need to decide which data structure to use at which place. Although is there is no hard and fast rule of using a data structure in a specific scenario, the below guidelines can help for general cases. For our program to be very efficient we must be aware of the sample data, our code needs to handle and a data structure should be used accordingly. Ordered Array :- If amount of data is small and predictable and search speed is …

Question: Write a program in C to print the given matrix in spiral order. Input: 1    2    3    4 5    6    7    8 9   10   11  12 13  14  15  16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6  7 11 10 Printing a matrix in spiral order can be better understood by the following image. Thus, printing a matrix in spiral order is just a way to traverse the matrix. The matrix can be supposed to be …

The general way to print any statement would be like:- But in this example we are using at least one semicolon(;). Our target is to print something on the screen without using even a single semi colon(;) . This is sort of a fun problem rather than an actual concept. It may seem to be impossible at once but we can utilize the fact that the statements inside an if condition is always executed and its result is used to determine the block to be executed. We can do something …