Job interview question : recursion

the question is asked here:

he doesnt solve but interviewee says “we can use a recursive function, i will first loop then i will store these subitems on a variable then i will call this function and pass these subitems on it, that will also return the name”

I came up with the following, was proud of myself as I just did it from his description and didnt need to research anything as it came naturally, after some refactoring I have:

const data = [
  {
    name: "Menu1",
    subitems: [
      {
        name: "mentu 2"
      }
    ]
  },
  {
    name: "menu 3",
    subitems: [
      {
        name: "menu4"
      }
    ]
  }
];

const arr = [];
const process = (items) => {
  items.forEach((elem) => {
    arr.push(elem.name);
    if (elem.subitems) {
      return process(elem.subitems);
    }
  });
};

My question is what is process to write the above iteratively?

I think:


const arr = [];
const process = (items) => {
  items.forEach((elem) => {
    arr.push(elem.name);
   // if (elem.subitems) {
    //  return process(elem.subitems);
   // }

I need some while loop here to replace the recusive call 
while there is subitems set the subitems to be the items?
 retain some pointer to the old??

  });
};

I have read that anything recursively can be written iteratively and vice versa is always true. what is the process for this? afterwards I would like to analyze complexities of both.

You are using a global variable. This is a big anti-pattern in recursion, as you cannot call your function again. I recommend fixing your recursive solution - this one wouldn’t do well in an interview.


This is one of the rare cases where the recursive solution is actually easier than the loop based approach. You can do this with a while loop and a pair of arrays, one to hold items to objects to check for subitems, and one to ‘result’ array to hold references to all items found.

1 Like

pretend he only need it once or anything new he just wants to add to what arr already is, just say this function will not provide him the luxury of knowing what he had before he last ran it…

Ok ill look at it later and try to get back to this.
thank you

1 Like

This is a very, very, very bad way to think about code. It is really worth it to go through the work to fix this. Any code that behaves this way would be an automatic rejection in code review for 99.9% of jobs. Programmers should be paranoid about the cases under which their code is run.

1 Like

I know. a function that can only be run once. its like it defeats the entire purpose…

I know. recruiters and hiring managers that dont know what they want and arent serious filling up my inbox and taking away my time from studying. I said ill do it.

you want this:


const encapsulated = (items) => {
  const arr = [];
  const process = (items) => {
    items.forEach((elem) => {
      arr.push(elem.name);
      if (elem.subitems) {
        return process(elem.subitems);
      }
    });
  };
  process(items)
  return arr
};

const process1=encapsulated(data);
console.log(process1);

const process2=encapsulated(data2);
console.log(process2);

ive fixed it yes?

That’s one way to fix it, though I personally probably wouldn’t accept that solution that into a codebase. That’s sort of patching the defect in the original solution instead of designing a new solution that works from scratch.

Do you know how to write recursion that uses the return value of the function call instead of needing an external accumulator? Understanding return values and function scope is important for job readiness.

Another way to repair this would be passing the accumulator as a function argument with a default value. If copies are expensive, I would be OK with that approach in a codebase I maintain.

1 Like

That’s sort of patching the defect in the original solution instead of designing a new solution that works from scratch.

you had said “using a global variable.”, so I just fix by using a scope.

Do you know how to write recursion that uses the return value of the function call instead of needing an external accumulator

I should. I mean the example shows how to do it:
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-countdown

I had a feeling this is what you would say after I posted, and wouldnt like the answer i gave.

Understanding return values and function scope is important for job readiness

They dont ever ask any real coding questions. they just want fill a role they dont care.

Another way to repair this would be passing the accumulator as a function argument with a default value. If copies are expensive, I would be OK with that approach in a codebase I maintain.

fine, i like that, now it is acceptable, yes, looks good to me:

const encapsulated = (items, acc = []) => {
  const process = (items) => {
    items.forEach((elem) => {
      acc.push(elem.name);
      if (elem.subitems) {
        return process(elem.subitems);
      }
    });
  };
  process(items);
  return acc;
};

const process1 = encapsulated(data);
const process2 = encapsulated(data2);

Interviewers want to see you demonstrate competency. Writing bad fragile or broken code makes you look bad. You are more likely to get a job if you write good code in the interviews. It is very expensive to hire a developer with poor skills who will cost senior developer time to babysit or who will, worse yet, write bad code that gets into the codebase.


At the very least, I’d avoid anti-patterns like writing single use functions that pollute the global variable space. That’s a big red flag.


The challenge you linked is a good one. I’d make sure you are able write recursive functions that use the return value like in that exercise:


Ok. it is not polluting anymore.
Maybe ill rewrite it again later like you really want

Ok i hope to get these types of interviews,

a developer with poor skills who will cost senior developer time to babysit

anyways in the interview I referenced the interviewer doesnt mention its a concern he just says he wants an array of all the names, and the interviewee doesnt write any code.

avoid anti-patterns like writing single use functions that pollute the global variable space. That’s a big red flag.

Yes, going back to that iterative method you mentioned, is this described as best as possible ?

ive done :

const encapsulated = (items, accumulated = []) => {
  const process = (items) => {
    items.reduce((acc, elem) => {
      accumulated.push(elem.name);
      if (elem.subitems) {
        return process(elem.subitems);
      }
      return acc;
    }, []);
  };
  process(items);
  return accumulated;
};

though i know its:

and not

Hi guys I want to know how to iterate through nested object and return all name values:

input:

output:

["Menu1", "Menu2", "Menu3", "Menu4", "Menu5", "Menu6"]

Rules: no recursive calls allowed.

Ive read the following but the description is unclear to me:

a while loop and a pair of arrays, one to hold items to objects to check for subitems, and one to ‘result’ array to hold references to all items found.

This is what I had originally thought to do:

any advice? thank you.

For breadth first, to avoid recursion can just mutate the array you’re iterating over as you iterate over it.

Set up an array to collect the names.
Iterate through the items
For each item, add the item name to the names array.
If the item has subitems, add each subitem to the end of the items array you’re iterating over.
Return the names.

For the example input you’ve shown, result should be like [Menu1, Menu3, Menu2, Menu4, Menu5, Menu6]

For depth first, recursion is a much clearer way to write it

1 Like

I dont know how to do it like it is in that exercise, i have to pass in a default value:

  const process = (data ,items = []) => {
    data.reduce((acc, elem) => {
      items.push(elem.name);
      if (elem.subitems) {
        return process(elem.subitems, items);
      }
      return acc;
    }, []);
    return items
  }

No

It makes sense but I not doing it right:

edit: I see its being mutated…

Because you’re using forEach, which iterates to the end of the array items. As it has two items in, means you get two nodes visited then it stops.

Edit: I would just use a loop; you can fanny on trying to make forEach work but a for…of is normally a better choice than forEach in all situations anyway and will Just Work here.

that prop is an array and should be an obj

Ah, I see what you’re doing. You’re not pushing each item, you’re pushing an array of subitems. And as arrays do not have the property “name” it’s never going to add anything to names (and as they don’t have the property “subitem” no more arrays will be added)

It shouldn’t be an object, it should be however many objects there are – push takes n arguments and adds each one to the end of the array

(Above advice still applies, just tested it)

true, thank you

const process = (items, names = []) => {
  // items.forEach((elem) => {
  //   names.push(elem.name);
  //   if (elem.subitems) {
  //     // return process(elem.subitems);
  //     console.log(items, "items before", "\n");
  //     items.push(elem.subitems);
  //     console.log(items, "items after push");
  //   }
  // });

  for (let i = 0; i < items.length; i++) {
    names.push(items[i].name);
    console.log(items[i], "i am expecting an items obj with a name prop");
    if (items[i].subitems) {
      // console.log(items, "items before", "\n");
      items.push(...items[i].subitems);
      // console.log(items, "items after push");
    }
  }
  console.log(names);
};

DFS i believe?

on line 82 is only true twice

yet line 89 is true 4 times w given data at the top of the file. Means I dont know the differnce between a forEach & a (for | for of) loop.