Arrays

Minimum Range over K arrays

Introduction This is one interesting problem with a non-trivial solution, this has been asked in couple of good interviews. Here goes the problem statement. "Given K positive integer arrays, each of which contains elements in sorted order. Find a range of integers such that it must contain at least one element from each array and the range is minimum." May be a diagram can make this more clear. Here you go! Understanding the Minimum Range over K arrays problem. In the above diagram we have 3 arrays each containing elements in increasing order. Now, let us identify a range which cont...
Read More

Student Enrollment Interview Question

Introduction This is another interview question which I find interesting. The problem statement goes as follow: "Its the beginning of a new academic year and I am a teacher of Data Structures and Algorithm subject. Many students with distinct roll numbers want to enroll for the class. After sometime few students wanted to opt out from the enrollment because they found some other subject much more interesting. Now, I also have a teaching assistant who can ask me the roll number of a student who is still enrolled into my class. It is not mandatory to tell him a different roll number every ti...
Read More

Find Frequency In Sorted Array

Problem Statement This is a question from one of the interview experiences. You are given a sorted array of numbers (this can be extended for arrays of characters, strings and what not) and a number K. Find the number of occurrences of K in the array. Solution Yes you got that right, it is really very simple. Walk through the array sequentially and if you get K then start counting till you get anything bigger than K. You can break out of the loop after this and the counter will tell you the obvious answer. So, why am I even writing this post? Because this is not fun, the above approach te...
Read More

Find Pair of Numbers in Array with a Given Sum

Problem Definition This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few: Find Pair of Numbers in Array with a Given Sum - The array is unsorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array is sorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array contains unique numbers only. In all the above versions, we have to return the ...
Read More

Arrays are permutation of each other

Problem Definition – Arrays are permutation of each other The problem definition goes as follows: Given two arrays of equal length, find out if the elements of one array is the permutation of the elements of another array. Of course the constraint is to solve it in constant space and linear time. Which means that the running time should be O(N) and auxiliary space required should be O(1). Approach There may be several thoughts which seem to work but eventually they will fail at one or the other ways. Here are few interesting ways which may not work for all the conditions: XORing the ...
Read More