Whiteboard Challenges

Anyway... back to challenges, nobody ever became a better programmer by simply talking.

As I mentioned I'll be posting solutions to these problems in due course; next one up is the missing integer (but I'll probably postpone anything on that until Friday, just in the event that some else cracks this for us). So please feel free to try your hand at any of these; I'm happy to assist at any time, simply PM or respond directly on this thread.

Btw I also didn't forget about @cguy's challenge -- but at this stage his follow on questions are probably too much, too complex, too soon, so we'll postpone that part until later; for now here's a quick Functional Programming rendition of the dot product of two vectors.

Code: 
import Foundation

public struct Vector{
  public let coordinates: [Double]
  public init(with coordinates: [Double]) {
    self.coordinates = coordinates
  }
}

public extension Vector {
  public func dotProduct(with vector: Vector) -> Double {
    assert(self.coordinates.count == vector.coordinates.count, "Aborted, coordinate mismatch: \(self.coordinates.count) vs. \(vector.coordinates.count).")
    return zip(self.coordinates, vector.coordinates).reduce(0) { $0 + ($1.0 * $1.1) }
  }
}

Description:
The zip command for those unaware; takes two input collections and merges into an array of tuple pairs, for example: [(6, 6), (5, 5), etc...], thereafter it's simple case of using reduce (fold left), to multiply the value within tuples and add it a sum total. 0 in the 'reduce(0)' command is our identity value i.e. the initial value that is proven neutral for addition; basically adding any number to 0, will always returns the number i.e. no side effect. For multiplication, the identity value is 1. $0 represents the carried forward sum total, and $1 refers to the duplex tuple created by the zip command, and in turn $1.0 references to the 1st vector value and $1.1 refers to the 2nd vector value.

Usage:
We start by creating 2 vectors: x and y -- the choice of the same value is just for simplicity sake (feel free to change this). The only restriction with dotProduct, is that both vectors must an equal value count.
Code: 
let x = Vector(with: [6, 5, 4, 3, 2, 1])
let y = Vector(with: [6, 5, 4, 3, 2, 1])
print(x.dotProduct(with: y)) // 91.0  (6 * 6) + (5 * 5) + (4 * 4) + (3 * 3) + (2 * 2) + (1 * 1)

And that's it, short and sweet, but missing all the follow on bits.
 
Last edited:
I'll take a stab at the missing integer.

Given a sorted array containing the values 0,1,...,N, with some integer i missing from that list, i.e. array = [0,1,2,...,i-1,i+1,...,N].

For a clearer picture, lets rewrite the array's indices vs its contents:
Code: 
index:   0 | 1 |  2 | 3 | ... | i-1 |  i   |  i+1 | ... |  N-1    //Note that the length of the array is N-1
value:   0 | 1 |  2 | 3 | ... | i-1 | i+1|  i+2 | ... |   N      //Note that i is missing in this list
The question boils down to determining the value for i. The simplest manner to do that is to check for the first consecutive pair of entries where
1. the first of the pair equals its index within the array,
2. the second does not (equal its index).

The answer would then be the latter of that pair.

Pseudocode for a hacky binary search follows:
Code: 
array = sorted array of length k, starting at 0 and terminating at k
//initiate "search" variables
lowerIndex = 0
upperIndex = k-1 (maximum index)
checkIndex = floor( (lowerIdx + upperIdx)/2)

missingInt = findMissingInteger(array, lowerIndex, upperIndex, checkIndex)

int findMissingInteger(arr, lowIdx, hiIdx, curIdx) {
  if (lowIdx > hiIdx) {       //search did not work (i.e. no missing integer found)
    return (-1)
  }
  else if ( arr[curIdx] == curIdx && arr[curIdx + 1] != (curIdx+1) ) {   //check current and next entries against their indices
     return (curIdx + 1)
  }
  else if ( arr[curIdx] != curIdx && arr[curIdx - 1] == (curIdx - 1) ) { //check current and prev entries against their indices
    return curIdx
  }
  else if (arr[curIdx] == curIdx) {   //entry and index correlate => search up
    lowIdx = curIdx + 1
    curIdx = floor( (lowIdx + hiIdx)/2 )
    return findMissingInteger(arr, lowIdx, hiIdx, curIdx)
  }
  else {  //entry and index do not correlate => search down
    hiIdx = curIdx - 1
    curIdx = floor( (lowIdx + hiIdx)/2 )
    return findMissingInteger(arr, lowIdx, hiIdx, curIdx)
  }
}
 
Last edited:
Rotate a square 2d array:

I feel a transpose and some massaging will work nicely in this case :)
I'll add an explanation tomorrow (hopefully) for below
Code: 
arr = NxN array
for (int i = 0; i < N; i++) {      //apply transpose first....
  for (int j = 0; j < N; j++) {
    if (i != j) {
      swap = arr[i][j]
      arr[i][j] = arr[j][i]
      arr[j][i] = swap
    }
  }
}

for (int i = 0, m = ceil(N/2); i < m; i++) {  //...then swap rows. Depending on language, you may need to iterate over each row's entries for the swap
  swapRow = arr[i]
  arr[i] = arr[N - i]
  arr[N - i] = swapRow
}
 
Missing integer. Forgive me, I didn't do computer science :p

Code: 
class Program
    {
        static Random random = new Random();
        static void Main(string[] args)
        {
            var arrayLength = random.Next(6, 60); 
            var intList = new List<int>();
            var startingInt = random.Next(0, 60); 
            for (int i = 0; i < arrayLength; i++)
            {
                intList.Add(i + startingInt);
            }
            var indexToRemove = random.Next(1, arrayLength);
            intList.RemoveAt(indexToRemove);

            var sortedArray = intList.ToArray();
            var result = FindMissingInteger(sortedArray);
            
        }

        static int FindMissingInteger(int[] array)
        {
            var differenceBetweenIndexAndInt = array[0];
            var midpoint = array.Length / 2;

            while (1 != 2)
            {
                if (CheckValue(array[midpoint], midpoint, differenceBetweenIndexAndInt))
                {
                    if ((array[midpoint] + 1) != array[midpoint + 1])
                    {
                        return array[midpoint] + 1;
                    }
                    midpoint = Convert.ToInt32(midpoint * 1.5);
                    CheckValue(array[midpoint], midpoint, differenceBetweenIndexAndInt);
                }
                else
                {
                    if ((array[midpoint] - 1) != array[midpoint - 1])
                    {
                        return array[midpoint] - 1;
                    }
                    midpoint = Convert.ToInt32(midpoint / 2);
                    CheckValue(array[midpoint], midpoint, differenceBetweenIndexAndInt);
                }
            }
        }

        static bool CheckValue(int value, int index, int difference)
        {
            return value == index + difference ? true : false;
        }
    }
 
Last edited:
BTW, the follow up from the missing integer question is: What if the array wasn't sorted? What would the minimum time complexity be? What if you were only allowed O(1) space complexity?
 
cguy said:
BTW, the follow up from the missing integer question is: What if the array wasn't sorted? What would the minimum time complexity be? What if you were only allowed O(1) space complexity?
Click to expand...

O(1) meaning the same time complexity no matter the size of the array?
 
DA-LION-619 said:
O(1) meaning the same time complexity no matter the size of the array?
Click to expand...

O(1), meaning that you're not allowed to create more than a constant amount of additional data in order to solve the problem. E.g., it would be trivial to have an array of size N of boolean values, and tick of index i as true, when integer i is seen, then run through it again to find the false (missing integer) entry. The additional space for this solution is O(N), and the time complexity is O(N). Sorting the data, and using the previously mentioned binary searches, is O(NlogN) time complexity, and O(1) space complexity. So the question is then, is there something better than O(NlogN) time? If so, can it be done with O(1) additional space.

Another example of such an algorithm is the merge sort. It's O(NlogN) time, but O(N) space, because it requires a second array to merge to, while quick sort and heap sort (and bubble sort) are O(1) space.
 
Last edited:
[)roi(];18710326 said:
A few more questions:

The missing integer (Amazon, Microsoft)
  • Question: Write a function that takes a sorted array of integers which contains all integers between 0 and N except one value as a parameter and find the missing integer in that array.
  • Example: if you are passed [0,1,2,3,5], this is an array between 0 and 5, it is sorted. However, the number 4 is missing. Your function would need to return (4).
Click to expand...

Code: 
static int FindMissingNumber(int[] input)
{
    for (int i = 0; i < input.Length; i++)
        if (input[i] != i)
            return i;

    return 0;
}

?

EDIT: Suppose you can optimise it and run it from both sides:

Code: 
static int FindMissingNumber(int[] input)
{
    for (int i = 0; i < input.Length; i++)
    {
        if (input[i] != i)
            return i;

        var j = input.Length - i;
        if (input[j-1] != j)
            return j;
    }

    return 0;
}
 
Last edited:
Hamster said:
Code: 
static int FindMissingNumber(int[] input)
{
    for (int i = 0; i < input.Length; i++)
        if (input[i] != i)
            return i;

    return 0;
}

?
Click to expand...

That will work, but it's O(N), while the others are O(logN). Generally, the point of these is to see how "low you can go".
 
cguy said:
That will work, but it's O(N), while the others are O(logN). Generally, the point of these is to see how "low you can go".
Click to expand...

Yeah, I think I missed the point of these questions. But to be honest, that's what I would've done in an interview given that exact question.

/cancels interview with Microsoft
 
The mystery function (Unattributed)
Question: You need to read the function below and tell us what you think it does:
Code: 
bool mystery (unsigned int num) {
    unsigned int other = num - 1;
    bool result = ((num & other ) == 0);
    return result;
}
Question: Also, which value would this function return an incorrect result for?
Note: This type of question has been to assess ability to interpret code just by looking at it. Naturally the answer is much more obvious once you run the code.
Click to expand...

So, no compilation or running... Explanation: This function checks to see if an integer anded with itself minus 1 is 0. The only time the most significant bit will ever become 0, after subtraction by 1, is if all bits but the most significant bit are 0. This means that for the anded numbers to be equal to zero, only one bit can be set. This means that the number is either a power of 2 or zero (zero would be the incorrect value suggested, since it is true for 0 and 0 is not a power of 2). Basically, this is a fast "isPower2(x)" check, for x!=0.
 
Last edited:
cguy said:
So, no compilation or running... Explanation: This function checks to see if an integer anded with itself minus 1 is 0. The only time the most significant bit will ever become 0, after subtraction by 1, is if all bits but the most significant bit are 0. This means that for the anded numbers to be equal to zero, only one bit can be set. This means that the number is either a power of 2 or zero (zero would be the incorrect value suggested, since it is true for 0 and 0 is not a power of 2). Basically, this is a fast "isPower2(x)" check, for x!=0.
Click to expand...
Excellent. The use of a bitwise operator was the key to the solution.

Naturally these types of question are tricky. The interviewer is more focused on your ability to read code instead of writing it.
The only way to prepare for something like this is to spend a lot of time reading code and making sense of it; Github is a great place to practice this; myriad of possibilities (good and bad). The question arguably helps the interviewer to assess your ability to not only review some else's code, understand it, and potentially point out flaws in it, but also your experience of working jointly with other developers.
 
cguy said:
O(1), meaning that you're not allowed to create more than a constant amount of additional data in order to solve the problem. E.g., it would be trivial to have an array of size N of boolean values, and tick of index i as true, when integer i is seen, then run through it again to find the false (missing integer) entry. The additional space for this solution is O(N), and the time complexity is O(N). Sorting the data, and using the previously mentioned binary searches, is O(NlogN) time complexity, and O(1) space complexity. So the question is then, is there something better than O(NlogN) time? If so, can it be done with O(1) additional space.

Another example of such an algorithm is the merge sort. It's O(NlogN) time, but O(N) space, because it requires a second array to merge to, while quick sort and heap sort (and bubble sort) are O(1) space.
Click to expand...

I've only ever done a single first semester course in CS, so time complexity's over my head. Would I be on the right track to think that the sorting algorithm* could double for the search itself?

For instance, suppose I implement a quicksort on the unsorted array, plus create an additional array/list... lets call it bucketArr. On every sort operation, I check value vs index (both sides of the swap). Then,
1. if value != index, I pop that particular value into bucketArr,
2. if value = index, I remove that value from bucketArr provided its contained there.

I should end up with bucketArr containing only one entry.

What would the time complexity and space be for this approach?

*I feel there needs to be some form of sorting implemented when searching for the missing int an unsorted array. Otherwise would mean checking the entire array?

EDIT: wait, I'm wrong. bucketArr would have more than one entry by the above.
Lets change it to:
1. Initialise bucketArr = [0, 1, ... , N]
2. remove values from bucketArr as you find new values from the quicksort
3. bucketArr should have one entry once the sort terminates.

Although, this probably breaks O(1) if I'm reading the definition correctly:
"Big O notation" is a way to express the speed of algorithms. n is the amount of data the algorithm is working with. O(1) means that, no matter how much data, it will execute in constant time. O(n) means that it is proportional to the amount of data
Click to expand...
...since an additional search is done on bucketArr, where the search becomes faster as bucketArr shrinks.

ANOTHER EDIT:
Following my first case (starting with empty bucketArr and filling it up), missing int would be related to the length of bucketArr, i.e. missing = N - (length/size of bucketArr)
 
Last edited:
cguy said:
O(1), meaning that you're not allowed to create more than a constant amount of additional data in order to solve the problem. E.g., it would be trivial to have an array of size N of boolean values, and tick of index i as true, when integer i is seen, then run through it again to find the false (missing integer) entry. The additional space for this solution is O(N), and the time complexity is O(N). Sorting the data, and using the previously mentioned binary searches, is O(NlogN) time complexity, and O(1) space complexity. So the question is then, is there something better than O(NlogN) time? If so, can it be done with O(1) additional space.

Another example of such an algorithm is the merge sort. It's O(NlogN) time, but O(N) space, because it requires a second array to merge to, while quick sort and heap sort (and bubble sort) are O(1) space.
Click to expand...

Getting the total sum of the array based on its length and then subtracting till the remainder is the missing integer?

static int GetArrayTotal(int arrayLength)
{
arrayLength++;
if (arrayLength % 2 == 0)
{
var mid = arrayLength / 2;
return mid * (arrayLength - 1);
}
else
{
var mid = (arrayLength - 1) / 2;
return mid * (arrayLength);
}
}


static int FindMissingInteger(int[] array)
{
var total = GetArrayTotal(array.Length);
for (int i = 0; i < array.Length; i++)
{
total -= array;
}
return total;
}
Click to expand...
 
In light of all the excellent responses to the Missing Integer challenge; I'm going bring the summary of this challenge forward to tomorrow. In short I've compiled 3 ways in which this problem could be tackled;

FYI: If after tomorrow I'm missing another option, then please feel free to add it, or simply berate me for missing the obvious, or both :D

  • 1 solution is O(log n), requires a sorted array and prior knowledge of (m)
  • 2 solutions are time O(n), and space O(1) and neither requires a sorted array or prior knowledge of (m)

Note:
  • (m) is the maximum value in the range, for example 0...20
  • 20 is (m)
 
Last edited:
battletoad said:
I've only ever done a single first semester course in CS, so time complexity's over my head. Would I be on the right track to think that the sorting algorithm* could double for the search itself?
Click to expand...

I don't think so - if you do the sorting, and then the search, that would be O(NlogN) + O(logN) time, which is the same as O(NlogN) time. If you integrate the sort and the search, it will still just be O(NlogN), because of the sort (i.e., the time complexity is "dominated" by the sort).

battletoad said:
For instance, suppose I implement a quicksort on the unsorted array, plus create an additional array/list... lets call it bucketArr. On every sort operation, I check value vs index (both sides of the swap). Then,
1. if value != index, I pop that particular value into bucketArr,
2. if value = index, I remove that value from bucketArr provided its contained there.

I should end up with bucketArr containing only one entry.

What would the time complexity and space be for this approach?
Click to expand...

Roughly, O(NlogN) time complexity, and O(N) space complexity. I say roughly because adding things to and from bucketArr, could actually increase the time complexity, since adding and removing things into bucketArry can be non-trivial (i.e., greater than O(1) operation). I.e., if you do O(NlogN) operations of O(logN), the total time complexity would be O(NlogNlogN). Also, the generic version of the quicksort is O(N^2), worst case (O(NlogN) expected case), so it could be longer, but of course you could just use a heapsort or such instead.

battletoad said:
*I feel there needs to be some form of sorting implemented when searching for the missing int an unsorted array. Otherwise would mean checking the entire array?
Click to expand...

Checking the array if it's unsorted is unavoidable - so the best one can hope for is O(N) time complexity. Sorting also has to touch every element, and often has to touch it multiple times, hence O(NlogN).

battletoad said:
EDIT: wait, I'm wrong. bucketArr would have more than one entry by the above.
Lets change it to:
1. Initialise bucketArr = [0, 1, ... , N]
2. remove values from bucketArr as you find new values from the quicksort
3. bucketArr should have one entry once the sort terminates.

Although, this probably breaks O(1) if I'm reading the definition correctly:
Click to expand...

Yup - if bucketArr starts off with N elements, you need N additional pieces of data, which is O(N).

DA-LION-619, computes the sum from 0..N, without iteration and stores it in 1 variable, so it uses O(1) space, and also takes O(1) time for this first step. Then it sums up what's actually in the array, which is O(N), so the total time complexity is O(N), and additional space complexity is O(1), which is as good as one is going to get for this problem.
 
Last edited:
cguy said:
explanation
Click to expand...
[)roi(] said:
Additional links
Click to expand...

thanks for the explanation and links. I'll keep this in mind when doing the other challenges and try to determine time complexity on my own.
 
Last edited:
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X