Checking if an element exists in an array efficiently and return it

Question

I am writing a function for my node/angular app that will prompt the user with a random question that he was not asked before.

To achieve this I wrote this function:

function setQuestion() {
 var q; // question we will eventually ask the user
 for (q in questions) {
 if (!(q._id in questionsUserAlreadyAnswered)) {
 /* the user has NOT answered this question yet -> so we can ask him now! */
 $scope.title = q.description;
 $scope.questionToAsk = q;
 return;
 }
 }
 /* if we got here it means the user has already answered ALL the questions */
 $scope.title = 'None';
 $scope.questionToAsk = 'None';
}

Here questions is an array of questions (Strings) and so is questionsUserAlreadyAnswered.

I am wondering if this is efficient enough, since I have many questions in the database and the user possibly answered many of them before, so essentially I iterate over all the questions I asked him.(?) twice.

Answer 1

First, I would suggest to create a key-value object where the key is an ID (number, uuid etc.) and the value is the question. Then you use that key for lookups instead of array traversal. This makes it an easy O(1) (correct me if I'm wrong).

Your questions key-value pair can be an id-question, while the questionsUserAlreadyAnswered key-value pair can be an id-boolean, with true as already asked.

var ids = ['e8844ee5', '9b0b5eb1'];
var questions = {
 'e8844ee5': 'How are you?',
 '9b0b5eb1': 'What are you doing?',
}
var askedQuestions = {
 '9b0b5eb1': true, // "What are you doing?" already asked
}
// Generate number from 0 to ids.length - 1
// Get id at index
// Check if exists in questions and not asked in askedQuestions

Another way to do it is to create a single array of question objects, where the objects have the question and their state. That way, you can easily filter unasked questions, which is just 1 run through the array.

var questions = [{
 question: 'How are you?',
 isAsked: false,
}, {
 question: 'What are you doing?',
 isAsked: true,
}]
var unaskedQuestions = questions.filter(function(q){
 return !q.isAsked;
});
// if unaskedQuestions.length === 0, everything asked
// else generate random number from 0 to unaskedQuestions.length - 1
// set question

Now that you've mentioned that you can't change the fact that the data structures are arrays of strings, I suggest you look into indexOf. It's still linear under the hood, but it takes out most of the extra code you have.

// This is still equivalent to 2 loops (filter, indexOf)
var unansweredQuestions = questions.filter(function(q){
 return !~questionsUserAlreadyAnswered.indexOf(q);
});
// if unanswered questions is empty, all is answered
// else get one
var question = unansweredQuestions[0];

• Idos: Are you sure that the filter returns empty if all questions are answered? Isn't indexOf supposed to return "-1" in that case? or am I wrong?
• Flambino: @Idos Yes, indexOf returns -1 if nothing's found. But Joseph is using a bitwise NOT trick: ~-1 => 0, and since zero is false'y !~-1 == true. So the filter will return unanswered questions. It's a neat trick, but personally I tend to avoid it, only because it is a little arcane for my tastes. Still, you'll see it from time to time in JS code.

Answer 2

Another way, in addition to the ones Joseph mentioned, you could have a list of questions, and simply remove a question when you ask it.

I.e. something like:

function setQuestion() {
 $scope.question = null;
 if(questions.length) {
 var i = Math.random() * questions.length | 0; // get random index
 $scope.question = questions.splice(i, 1)[0]; // remove question and use it
 }
}

And when the question's answered:

questionsUserAlreadyAnswered.push($scope.question);

This way, you don't need to check multiple arrays.

If you need a "master list", you can do init things like so:

var allQuestions = [...],
 unasweredQuestions = allQuestions.slice(0), // copy array
 answeredQuestions = [];

On another note: Don't use for..in to iterate JavaScript arrays. It doesn't work the same as for..in in other languages. Use a regular for loop or the forEach function.