JavaScript Most Commonly Asked Data Structure Questions
If you’ve been to an interview, you know that data structure questions should be asked in a technical interview. In fact, this is a very common and very important topic for any interview process. DS questions allow the interviewer to evaluate a candidate’s skills. In this article I have collected some basic DS questions for a JavaScript interview.
Array
1. Eliminate all even integers from a matrix.
Input: [4, 1, 9, 10, 15, 22, 5, 14]
Output: [4, 10, 22, 14]This problem has multiple solutions and depends entirely on the candidate. Here I provide two solutions with an explanation.
Solution — 1
const inputData = [4, 1, 9, 10, 15, 22, 5, 14]
removeEvenNumbers (inputData) => {
let odds = []
for (let number of inputData) {
if (number % 2 != 0) odds.push(number)
}
return odds
}
console.log(removeEvenNumbers(inputData)))
// [4, 10, 22, 14]In the above solution, we look at each element and check whether it is even or odd. If it’s weird, we put it in a separate table. Therefore, the time complexity of this problem is O(n)O(n).
Solution — 2
const inputData = [4, 1, 9, 10, 15, 22, 5, 14]
removeEvenNumbers (inputData) => {
let odds = []
for (let number of inputData) {
if (number % 2 != 0) odds.push(number)
}
return odds
}
console.log(removeEvenNumbers(inputData)))
// [4, 10, 22, 14]This solution also loops through all the elements and checks if they are even. If it’s straight, filter that item. I used filters to filter the data in the table. It simply filters out data that returns an incorrect value. It has the same time complexity.
2. Find all repeated numbers from an array
Input: [1,2,4,5,6,1,3,7,9,10]
Output: [1, 2, 4, 5, 6, 3, 7, 9, 10]const findUniqueNos = (inputData) => {
let uniqueNumbers = []
inputData.map(number => {
let counts = uniqueNumbers.filter(uniqueNo => uniqueNo == number)
if(counts.length != 1) uniqueNumbers.push(number)
})
return uniqueNumbers
}
console.log(findUniqueNos(inputData))Yes, you have to iterate through an array, first create an empty array and keep inserting a unique number into it. Simply use the filter to determine whether a number already exists or not.
Stack
1. Validate balanced parentheses
Write a function that accepts only parentheses (curve{}, square[], or round()). You need to check whether all the brackets in the given string are equalized or not. Simply look for an opening parenthesis and then a closing parenthesis.
First input: {[({})]}
First output: true
Second input: {[({})}Second output: false
class Stack {
constructor() {
this.items = []
this.top = null
}
getTop() {
if (this.items.length == 0)
return null
return this.top
}
isEmpty() {
return this.items.length == 0
}
size() {
return this.items.length
}
push(element) {
this.items.push(element)
this.top = element
}
pop() {
if (this.items.length != 0) {
if (this.items.length == 1) {
this.top = null
return this.items.pop()
} else {
this.top = this.items[this.items.length - 2]
return this.items.pop()
}
} else
return null
}
}
isBalancedParantheses(exp) => {
let myStack = new Stack()
// Loop through input string
for (let i = 0 i < exp.length i++) {
// Check for every closing parantheses if there's opeaning parantheses or not.
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {
if (myStack.isEmpty()) return false
let output = myStack.pop()
//If no opening parentheses for any closing one then immediatly return false
if (((exp[i] == "}") && (output != "{")) || ((exp[i] == ")") && (output != "(")) || ((exp[i] == "]") && (output != "["))) {
return false
}
} else {
//For each opening parentheses, push it into stack
myStack.push(exp[i])
}
}
//after traversal of input data, if there's any opening parentheses left in stack then also return false else return true at the end
if (myStack.isEmpty() == false) {
return false
}
return true
}
let firstInputData = "{[({})]}"
console.log(isBalancedParantheses(firstInputData))
secondInputData = "{[({})}"
console.log(isBalancedParantheses(secondInputData))So, first we look at the string and check it character by character. There are two ways to identify unbalanced supports. First from the stack value, then from the top element of the stack. To do this we need to check if the stack is empty. OR Does the top of the stack match correctly? If either of these two conditions is met, we immediately return a false opening parenthesis, which is pushed onto the stack and, if it matches, appears. Then you can ask what is the time complexity of this code, since we only iterate when its complexity is O(n).
2. Write a function for converting numbers to base 2 and base 8
In this program, you write a function that takes an integer value and a base value and then converts accordingly. For example, if an input is num = 14 and base = 2, the result will be 1110, num = 14 and base = 8, then the result will be 16
Stack() => {
constructor() {
this.items = []
this.top = 0
}
push (element) => {
this.items[this.top++] = element
}
pop () => {
return this.items[--this.top]
}
length () => {
return this.top
}
}
convertBase(num, base) => {
let s = new Stack()
while( num > 0 ){
s.push(num % base)
num = Math.floor(num /= base)
}
let converted = ""
while (s.length() > 0) {
converted += s.pop()
}
return converted
}
let num = 14
let base = 2
console.log(convertBase(num, base))In this program, we push a number onto the stack after conversion, then insert one digit at a time and return an integer.
Queue
1. Print binary number up to N, where N can be any positive integer
In this problem, we need to write a program which will take integer number and generate binary numbers till the limit. Like is input number n = 3 then the result should be [1,10,11]
module.exports = class Queue {
constructor() {
this.items = []
this.front = null
this.back = null
}
isEmpty() {
return this.items.length == 0
}
getFront() {
if (this.items.length != 0) {
return this.items[0]
} else
return null
}
size() {
return this.items.length
}
enqueue(element) {
this.items.push(element)
}
dequeue() {
if (this.items.length == 0) {
return null
} else {
return this.items.shift()
}
}
}
generateBinaryNumbers(n) => {
let result = []
let myQueue = new Queue()
let s1, s2
myQueue.enqueue("1")
for (let i = 0 i < n i++) {
result.push(myQueue.dequeue())
s1 = result[i] + "0"
s2 = result[i] + "1"
myQueue.enqueue(s1)
myQueue.enqueue(s2)
}
return result
}
console.log(generateBinaryNumbers(3))To create a binary number, we need to add 0 and 1 to the binary number above, just like we can create 10 and 11 from 1 by adding 0 and 1. After generating a binary number, put -o append to generate the next number by adding 0 and 1. The time complexity of the given solution is O(n)O(n) because the same operation is performed n times.
2. Explain how the priority queue system works.
In this program, you first create a queue and then implement a priority queue. Let me explain with an example.
Patient(name, code) => {
this.name = name
this.code = code
}
Queue() => {
this.dataStore = []
enqueue(element) => {
this.dataStore.push(element)
}
dequeue() => {
let priority = this.dataStore[0].code
for (let i = 1; i < this.dataStore.length; ++i) {
if (this.dataStore[i].code < priority) {
priority = i
}
}
return this.dataStore.splice(priority,1)
}
front() => {
return this.dataStore[0]
}
back() => {
return this.dataStore[this.dataStore.length-1]
}
toString() => {
let retStr = ""
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n"
}
return retStr
}
empty() => {
if (this.dataStore.length == 0) {
return true
}
else {
return false
}
}
let p = new Patient("Smith",5)
let ed = new Queue()
ed.enqueue(p)
p = new Patient("Jones", 4)
ed.enqueue(p)
p = new Patient("Fehrenbach", 6)
ed.enqueue(p)
p = new Patient("Brown", 1)
ed.enqueue(p)
p = new Patient("Ingram", 1)
ed.enqueue(p)
console.log(ed.toString())
let seen = ed.dequeue()
console.log("Patient being treated: " + seen[0].name)
console.log("Patients waiting to be seen: ")
console.log(ed.toString())
// another round
let seen = ed.dequeue()
console.log("Patient being treated: " + seen[0].name)
console.log("Patients waiting to be seen: ")
console.log(ed.toString())
let seen = ed.dequeue()
console.log("Patient being treated: " + seen[0].name)
console.log("Patients waiting to be seen: ")
console.log(ed.toString())Generated output is like below:
Smith code: 5
Jones code: 4
Fehrenbach code: 6
Brown code: 1
Ingram code: 1
Patient being treated: Jones
Patients waiting to be seen:
Smith code: 5
Fehrenbach code: 6
Brown code: 1
Ingram code: 1
Patient being treated: Ingram
Patients waiting to be seen:
Smith code: 5
Fehrenbach code: 6
Brown code: 1
Patient being treated: Brown
Patients waiting to be seen:
Smith code: 5
Fehrenbach code: 6As the name suggests, priority queue is used when you want to remove something from a queue based on priority. Here I take the example of a patient and her appointment number. It essentially represents the waiting room of any hospital. Here, the dequeue() function removes the patient from the queue based on the lowest priority, after which toString() modifies the processed patient object.
