It's not a difficult problem for humans with no lidar and 100W operating budget.
In particular, our vision is very very tied to our model of the world, and is clearly an evolutionarily derived trait, not something we learn from scratch as children. We are basically born with a model that can augment the raw sensory input with basic physics (object permanence, but also we have an intuition for things like "heavy = large momentum even at slow speeds", and for "what goes up will come down", some basic optics of how objects cast shadows, and others). In addition, we learn to recognize objects and we know their actual sizes from past experience, so we typically estimate distance this way far better than relying on parallax. "Small image of car" is automatically "car far away", even if seen with one eye, because we know what size a car is.
In fact, much of our brilliant vision starts going awry immediately in an artifical setting with misleading sized objects.
What you describe is largely the classical "cognitivist" model, which is more or less dead in the contemporary tought. We don't even have a very good account of depth estimation, apart from "bunch of things seem to affect it".
Note that many mammals have object permanence, and for some it develops right after birth. The fact that human development is so slow is the only reason some of these things look like actual learning. Another more clear example is our ability to walk/crawl - in humans it seems to be learned, but most other mammals are able to do it within minutes of being born, making it quite obvious it is in fact a genetically coded trait.
Being able to crawl within minutes (and even somewhat run within hours as horses do) is mostly due to anatomy and "reflex pathways". E.g. a cat can walk without brains [1], as can famosly headless chicken.
Human babies too have these kinds of reflexes but they are "abandoned" well before the baby learns to walk.
If you think quadruped walking is only a bunch of reflexes and human walking isn't, that still doesn't completely negate my point. Primate infants also display significantly more agility than human babies right afer birth, and "learn" to walk significantly faster.
Here [0] is a study for example that finds that the age of walking is 94% predictable for any mammalian species that walks on the ground by a particular ratio between the mass of the infant brain and the adult brain (that is, an infant animal essentially learns to walk when its brain reaches a certain percentage of its final brain size).
Besides this type of animal comparison, another signal we can use to distinguish between built-in capacities and things we learn from experience is to see whether a capacity can be developed later in life. For example, if you lack visual stimuli in the early part of brain development, even if you get it later, you will never develop vision (we know this from studies on kittens...).