Use -prune on the directories that you're going to delete anyway to tell find not to bother trying to find files in them:
find . \( -name build -o -name obj -o -name '*.so' \) -prune -exec rm -rf {} + Also note that *.so needs to be quoted as otherwise it may be expanded by the shell to the list of .so files in the current directory.
The equivalent of your GNU -regex-type one would be:
find . \( -name build -o -name obj -o -name '*?.so' \) -prune -exec rm -rf {} + Note that if you're going to use GNU specific syntax, you might as well use -delete instead of -exec rm -rf {} +. With -delete, GNU find turns on -depth automatically. It doesn't run external commands so in that way, it's more efficient, and also it's safer as it removes the race condition where someone may be able to make you remove the wrong files by changing a directory to a symlink in-between the time find finds a file and rm removes it (see info -f find -n 'Security Considerations for find' for details).
find . -regextype posix-egrep -regex '.*/(obj|build|(obj|build)(/.*)?|.+\.so)' -delete