My software development journey
Given a circularly sorted array, how to search for an element efficiently? For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3. Since the array is sorted but rotated, we can expect it to be solved using the binary search technique. We can design an…
Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations? For example the array [4, 5, 1, 2, 3] is (right) rotated twice. Before proceeding to find a solution, let’s note some observations. To find the number of rotations, we have to find the smallest element in the…
Given an array of N distinct values, how to find the number of pairs with a difference of K? For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}. One obvious solution could be to examine each possible pair…
Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array. For example consider the following two arrays. array1 = [3, 27, 45, 68, 70, 81, 99] array2 = [9, 16, 25, 35, 70, 84]…
Given a linked list, how do efficiently find the nth node from the end? For example in the following linked list, 3rd node from the end is ‘6’. 2 -> 1 -> 6 -> 5 -> 9 One obvious method is to find the length of the linked list (len) by going through the list.…
Given a large file containing many lines of text, How do we write an efficient program to print last k lines from that file. One obvious approach is to read the entire file first to find the number of lines (n). In the second iteration skip first (n-k) lines, and print the remaining k lines. …
Given a string, how do we reverse the words inside the string? For example if the input string is “this is a test” the output should be “test a is this”. The algorithm is simple. This can be done in two steps. The first step is to reverse the entire string. In the second step…
We all know that while executing a program, they store their data in memory. Memory can assumed as a large array of bytes. The endianness of the machine indicates in which order the data gets stored in the memory. Please refer this and this link for a detailed introduction to this topic. Here is the…
Given an array of positive and negative values. We have to find the maximum sum a sub-array can have. For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}. To solve this problem, we take two variables to keep…
Given an array of numbers which indicates the prices of stocks for a period of time. We have to find the two values in the array such that their difference is maximum and also the greater value must appear later than smaller value. In another way, we have to find the buying and selling price…