The issue is interviewing in the first place- you'd have to fly out specifically for the interview and hope that it works out. Quite a financial gamble if you do it repeatedly...
Yes, that would be a lot of money. Do companies do interviews over video-chat at all?
It may be somewhat easier at a company that's dealt with the process before, but most valley startups will have access to experienced immigration attorneys.