Calculating value of K without messages

Question

Question:

Find the value of K in myInterViewArray without any messages/calls

I was given this hint:

The numbers in the array will never exceed 1-9.

NSArray *myInterViewArray = @[@2,@1,@3,@9,@9,@8,@7];

Example:

If you send 3, the array will return the 3 biggest values in myInterViewArray * 3. So in the example below, K = 9 + 9 + 8.

--

I was asked this question a while back in an interview and was completely stumped. The first solution that I could think of looked something like this:

Interview Test Array:

[self findingK:myInterViewArray abc:3];

-(int)findingK:(NSArray *)myArray abc:(int)k{ // With Reverse Object Enumerator
myArray = [[[myArray sortedArrayUsingSelector:@selector(compare:)] reverseObjectEnumerator] allObjects];

int tempA = 0;

for (int i = 0; i < k; i++) {
    tempA += [[myArray objectAtIndex:i] intValue];
}

k = tempA;
return k;
}

But apparently that was a big no-no. They wanted me to find the value of K without using any messages. That means that I was unable to use sortedArrayUsingSelector and even reverseObjectEnumerator.

Now to the point!

I've been thinking about this for quite a while and I still can't think of an approach without messages. Does anyone have any ideas?

Is it just me or did you knot really specify what the program is supposed to do? What is it supposed to find? K? What k? — luk2302, Jun 26 '16 at 17:25
Sorry for the confusion.. I hope my edit clears things up @luk2302 — , Jun 26 '16 at 17:28
" without using any messages" ? You returns the additions of the k biggest values, right? Because your explanation is still not that clear — Larme, Jun 26 '16 at 17:29
In all honesty, not sure what it's technically called when you call `sortedArrayUsingSelector`. Message? Call? — , Jun 26 '16 at 17:30
Can you even access an array subscript without a message or the length of the array?? After that it is plain old programming like in any other language. But I do not think the first two things are even possible. — luk2302, Jun 26 '16 at 17:31
Was that the ***exact*** terminology they used in the interview question. It just sounds impossible. Maybe they were just testing you anyway (to say "no") ;) — luk2302, Jun 26 '16 at 17:41
That's the exact question.. That's why my curiosity lead me to Stackoverflow @luk2302. — , Jun 26 '16 at 17:43

Sulthan · Accepted Answer · 2016-06-26T18:08:57.553

2

There is only one way to do that and that is bridging the array to CF type and then use plain C, e.g.:

NSArray *array = @[@1, @2, @3];
CFArrayRef cfArray = (__bridge CFArrayRef)(array);

NSLog(@"%@", CFArrayGetValueAtIndex(cfArray, 0));

However, if the value is a NSNumber, you will still need messages to access its numeric value.

Most likely the authors of the question didn't have a very good knowledge of the concept of messages. Maybe they thought that subscripting and property access were not messages or something else.

Using objects in Obj-C without messages is impossible. Every property access, every method call, every method initialization is done using messages.

Rereading the question, they probably wanted you to implement the algorithm without using library functions, e.g. sort (e.g. you could implement a K-heap and use that heap to find the K highest numbers in a for iteration).

edited Jun 26 '16 at 18:08

answered Jun 26 '16 at 17:56

Sulthan

128,090
22
218
270

1

+1 "Most likely the authors of the question didn't have a very good knowledge of the concept of messages." This kind of question is quite good. It quickly demonstrates which groups you don't want to work with. It's nice to get that out of the way quickly so you can interview with a better group. – Rob Napier Jun 26 '16 at 17:59
This is not so uncommon. There are some related questions in *SE workplace*, .e.g. http://workplace.stackexchange.com/questions/4314/how-to-tell-a-interviewer-that-he-is-wrong-on-a-technical-question – Sulthan Jun 26 '16 at 18:02
@Sulthan do you mind giving an example for the algorithm/sort function? – Jun 26 '16 at 18:19
1

@Filip You can check http://stackoverflow.com/questions/11209556/print-the-biggest-k-elements-in-a-given-heap-in-oklogk/11209770#11209770, once you have a [heap](https://en.wikipedia.org/wiki/Heap_(data_structure)) implementation, the algorithm is rather simple. It's the same algorithm used in heap-sort but heap-sort needs a N-heap while you need only a K-heap. – Sulthan Jun 26 '16 at 18:40

score 0 · Answer 2 · answered Jun 26 '16 at 17:45

I assume what is meant is that you can't mutate the original array. Otherwise, that restriction doesn't make sense.

Here's something that might work:

NSMutableArray *a = [NSMutableArray array];

for (NSNumber *num in array) {
    BOOL shouldAdd = NO;

    for (int i = a.count - 1; i >= k; i--) {
        if ([a[i] intValue] < [num intValue]) {
            shouldAdd = YES;

            break;
        }
    }

    if (shouldAdd) {
        [a addObject:num];
    }
}

int result = a[a.count - k];
for (int i = k; k < a.count; k++) {
    result += [a[i] intValue];
}

return result;

Calculating value of K without messages

2 Answers2