js-algorithm-question.js

/*--------------------------------QUESTION---------------------------------
An api called to receipt check items return an array like this (simplified mock data)

const checkItems = [
  {
    longName: 'Classic Burger',
    basePrice: 3.25,
    posItemId: 1,
    parentItemId: 0,
  },
  {
    longName: 'Pickles',
    basePrice: 0,
    posItemId: 11,
    parentItemId: 1,
  },
  {
    longName: 'Lrg Reg Fies',
    basePrice: 4,
    posItemId: 12,
    parentItemId: 1,
  },
  {
    longName: 'Twist and Shake',
    basePrice: 1.75,
    posItemId: 121,
    parentItemId: 12,
  },
  {
    longName: 'Red Onions',
    basePrice: 0,
    posItemId: 13,
    parentItemId: 1,
  },
  {
    longName: 'Burrito',
    basePrice: 2.5,
    posItemId: 2,
    parentItemId: 0,
  },
  {
    longName: 'Cheese Taco',
    basePrice: 1,
    posItemId: 3,
    parentItemId: 0,
  },
  {
    longName: 'Extra Cheese',
    basePrice: 0.3,
    posItemId: 31,
    parentItemId: 3,
  },
];

write a function to return a nested array of main check items with modifiers, like this
[
  {
    "longName": "Classic Burger",
    "basePrice": 3.25,
    "posItemId": 1,
    "parentItemId": 0,
    "modifiers": [
      {
        "longName": "Pickles",
        "basePrice": 0,
        "posItemId": 11,
        "parentItemId": 1,
        "modifiers": []
      },
      {
        "longName": "Lrg Reg Fies",
        "basePrice": 4,
        "posItemId": 12,
        "parentItemId": 1,
        "modifiers": [
          {
            "longName": "Twist and Shake",
            "basePrice": 1.75,
            "posItemId": 121,
            "parentItemId": 12,
            "modifiers": []
          }
        ]
      },
      {
        "longName": "Red Onions",
        "basePrice": 0,
        "posItemId": 13,
        "parentItemId": 1,
        "modifiers": []
      }
    ]
  },
  {
    "longName": "Burrito",
    "basePrice": 2.5,
    "posItemId": 2,
    "parentItemId": 0,
    "modifiers": []
  },
  {
    "longName": "Cheese Taco",
    "basePrice": 1,
    "posItemId": 3,
    "parentItemId": 0,
    "modifiers": [
      {
        "longName": "Extra Cheese",
        "basePrice": 0.3,
        "posItemId": 31,
        "parentItemId": 3,
        "modifiers": []
      }
    ]
  }
]
*/


/*--------------------------------EXPLANATION---------------------------------
This question test on handling JS array and searching algorithm for common ordering data.
The receipt array given is essentially a pre-order traversal of the nested order tree structure.
The candidate should be able to identify the relationship between modifier and parent by posItemId and parentItemId.
*/

/*--------------------------------SOLUTION---------------------------------
If we dont limit the data structure which they can use, maintaining a map is the most straight forward solution
Notice there is a implicit condition for the input: they are in order, parent comes before child.
*/
function buildMainItems(flatItems) {
  // edge cases
  if (flatItems === null || flatItems.length === 0) {
    return [];
  }

  const mainItems = [];
  const idToItemMap = {}; // candidate should know to use JS object as hashmap
  flatItems.forEach(function(item) {
    idToItemMap[item.posItemId] = item;
    item.modifiers = [];
    if (!(item.parentItemId in idToItemMap)) {
      mainItems.push(item);
    } else {
      idToItemMap[item.parentItemId].modifiers.push(item);
    }
  });
  return mainItems;
}

// Or, sometimes some algorithim tests limit the usage of Map structure.
// For example, if we ask them to use only JS array (which can be used as Queue or Stack),
// they should know to use a stack to maintain the references to the visited parents.
function buildMainItems2(flatItems) {
  // edge cases
  if (flatItems === null || flatItems.length === 0) {
    return [];
  }

  const parentNodes = []; // a stack of visited parents

  // candidate could use for...loop, forEach, or reduce to loop through the JS array
  return flatItems.reduce(function(mainItems, curr) {
    // try to find its parent
    while (parentNodes.length !== 0 && parentNodes[parentNodes.length - 1].posItemId !== curr.parentItemId) {
      // pop the visited nodes
      parentNodes.pop();
    }

    // the while loop ends in two cases
    // case 1. parentNodes is empty, then the curr should be a main item
    // case 2. the last item of parentNodes is its parent

    curr.modifiers = []; // init its own modifiers

    // if it is not the main item, push it to its parent
    if (parentNodes.length !== 0) {
      // attach itself to its parent
      const parent = parentNodes[parentNodes.length - 1];
      parent.modifiers.push(curr);
    } else {
      mainItems.push(curr);
    }

    // push itself to become the next available parents
    parentNodes.push(curr);

    return mainItems;
  }, []);
}

//--------------------------------TEST CASE---------------------------------
const checkItems = [
  {
    longName: 'Classic Burger',
    basePrice: 3.25,
    posItemId: 1,
    parentItemId: 0,
  },
  {
    longName: 'Pickles',
    basePrice: 0,
    posItemId: 11,
    parentItemId: 1,
  },
  {
    longName: 'Lrg Reg Fies',
    basePrice: 4,
    posItemId: 12,
    parentItemId: 1,
  },
  {
    longName: 'Twist and Shake',
    basePrice: 1.75,
    posItemId: 121,
    parentItemId: 12,
  },
  {
    longName: 'Red Onions',
    basePrice: 0,
    posItemId: 13,
    parentItemId: 1,
  },
  {
    longName: 'Burrito',
    basePrice: 2.5,
    posItemId: 2,
    parentItemId: 0,
  },
  {
    longName: 'Cheese Taco',
    basePrice: 1,
    posItemId: 3,
    parentItemId: 0,
  },
  {
    longName: 'Extra Cheese',
    basePrice: 0.3,
    posItemId: 31,
    parentItemId: 3,
  },
];

// write a function to return a nested array of main check items with modifiers, like this
const mainItems = buildMainItems(checkItems);

// try console log the result beautifully (test if they know JSON.stringify)
console.log(JSON.stringify(mainItems, null, 2));

/*--------------------------------FOLLOW UP---------------------------------
Give a list of main items (what we just get above), write a function to calculate the total price

This is a typical traverse question(DFS), candidate can use iterative or recursive way to solve the problem
*/


// recuisve method （straight forward, but use more call stack)
function getPrice(items) {
  let price = 0;
  if (items.length === 0) {
    return price;
  }
  items.forEach(function(item) {
    price += item.basePrice;
    price += getPrice(item.modifiers);
  });
  return price;
}

// iterative method
function getPrice2(items) {
  let price = 0;
  items.forEach(function(root) {
    let stack = []; // a stack for dfs
    stack.push(root);
    while (stack.length !== 0) {
      const curr = stack.pop();
      price += curr.basePrice;
      if (curr.modifiers.length !== 0) {
        stack = [...stack, ...curr.modifiers];
      }
    }
  });
  return price;
}

console.log(getPrice(mainItems)); // should be 12.8