P0158 & P0160 codes 1999 Infiniti QX4

My 1999 Infiniti QX4, 6cyl, 3.3L, 4-wheel drive; failed emissions test due to codes P0158 and P0160.
The inspection place said I most likely just need to replace my O2 sensor. Went to an auto parts store and the guy said he's seen too many people replace the O2 sensors and there is nothing wrong with them, the cause is someting else.
The vehicle has 107,000 miles on it. Any suggestions of a possible fix would be greatly appreciated. Also, I understand the vehicle has 4ea O2 sensors, where are they located and which sensors are causing these OBDII codes to appear?
(FYI- it was just in the shop for replacement of timing belt, belt tensioner, water pump, radiator, hoses, belts and change of spark plugs)

then get it back to that shop then! codes that come up after service or repairs are not normally coincidence!