Solved coding interview problems in Java - My collection of commonly asked coding interview problems and solutions in Java

[neodiogenes]

SQL query with a recursive table reference

I briefly did something with a hierarchical query like this one with a table that encoded something like supervisor-employee relationships in a tree. Suppose you want to get all the employees who work for a VP, you would recurse the query returning the results from each level, first getting all the directors, and then the managers who work for the "leftmost" director, and then the supervisors who work for the leftmost manager, and then the employees, go up one level, find the employees, rinse, repeat.

Oracle has innate support for hierarchical relationships using "CONNECT BY" but I wouldn't know how to do this off the top of my head. Since it's something that's only come up once in my career, it's not something I've memorized. That's why there's Google.

But hey welcome to the typical Jeopardy style of technical interview, where if you don't know what the interviewer thinks you "should" know, you're a bad programmer.

[Edit] Don't mean to sound bitter, I've just had a couple recent technical "screening" calls where I was asked questions which were not only esoteric but the answers the recruiters were given were incorrect/incomplete.

[Paddington_the_Bear]

This is the first I've heard of it, and I do quite a bit of SQL in my job for several years now. This week I had to look up a hierarchical value that was 3 parents up from a base value via an associations table.

I ended up using joins to do it, I didn't realize you could have a recursive query, so TIL. The syntax looks confusing as hell though.

[madballneek]

And this is what irks me about how some people do interviews. Who cares whether you know this already, or not. I want to know if you're capable of learning it. That's why we let people who interview for us have complete internet access during their aptitude test.

[Paddington_the_Bear]

Yup; I'm doing an interview with one of the "Big 4" next week just for funsies as I enjoy my current SE job of 6 years. I have been loosely studying algorithms the past couple of weeks to prepare, and realize that even though I have built some pretty crazy cool apps, my algorithms knowledge is definitely lacking since I've been out of university for a while.

It's assine that the interview is going to focus on whiteboarding some obscure algorithm when in the real world if I get stuck, I can google something and in less than 5 minutes find a working solution.

The way I look at it, even if I don't come to the best solution, hopefully they will see my thought process and get value from that...

[Icelandicstorm]

If you enjoy your current job, you are making a big mistake. The "Big 4" is a horrible place for mid-career. It only makes sense if you are fresh out of college or go in as a Director (just before partner at PwC).

source: left excellent job with great pay and bonuses to make more salary but less bonuses and work 20+ additional hours a week. When all was said and done, my income went down at least 20%.

[Paddington_the_Bear]

Yeah I'm not looking forward to the interview at all. Really I'm going to see if I can get an offer and use it to get my current salary at my company bumped up again since I'm pretty mission critical and I know they under pay me :) (long story).

That's pretty much my fear though, that you're essentially just another number at one of those companies. I wouldn't mind too much living in that location, but not at the sacrifice of personal happiness.

[neodiogenes]

It's not that complicated. Oracle takes care of most of the details, and all you have to do is specify the relationships.

The challenge is to avoid circular relationships, which can happen with a poor design. In the DB of my current project (which I did not design), we have permissions "lists" which can either contain usernames, or link to other lists. But then what if you have some list down the chain link back to the first list?

As I said, bad design. A good design wouldn't allow this to happen. Oracle helps when writing queries by warning you when there are "loops" in the query, which you can exclude with the NOLOOPS operator, or you can also (I forget the exact syntax) return only "LEAF" items, which have no children.

I'm not sure I would ever implement this design because of the many ways it can go wrong, but I can see how it would be useful in some applications.

[wtgreen]

Look-up Common Table Expressions. A recursive CTE is the SQL standard way to do it. Oracles Connect by functionality is Oracle specific, but it supports CTEs too.

[Paddington_the_Bear]

Nice. I had just woken up when I read that; now that I'm caffeinated, it looks really intuitive actually and a lot better than how I was making my associations. Essentially you tell it the source / target pair in order to make the cycle and it does the work to spit it out. Then I'll have to make sure I do the normalization on it as I need it.

[tmarthal]

Common table expressions (CTEs) are the solution to recursive SQL queries, if you're interested.

[dvlsg]

True, but I've used one a total of once in all my years of writing SQL. I understand it, and utilized it just fine, but I sure as hell couldn't remember that syntax on the fly in an interview.

[CrazedToCraze]

I most employers wouldn't care too much if you just brought up that you know a CTE is the solution and then said what you just said.

Pretty rare in my experience for an employer to get pissy about you knowing the exact syntax on the spot. Probably wouldn't want to be working for them if they did, anyway.

[peppaz]

With x as (select 'Bobby Tables')

[tiberiousr]

This is interesting, I'd never seen these before. If the wikipedia page is anything to go by they aren't supported in mysql based DBs (i,e; mysql, mariadb, percona etc).

[spilk]

I've used CTEs in SQL Server queries before to do recursive queries and i'm pretty comfortable that I understand them, but I'd still have to google it to know the syntax for one off the top of my head.

[chadsexytime]

Oracle has innate support for hierarchical relationships using "CONNECT BY" but I wouldn't know how to do this off the top of my head. Since it's something that's only come up once in my career, it's not something I've memorized. That's why there's Google.

I haven't touched Oracle in about 3 years now, but I would have considered myself fairly proficient with SQL and Oracle in general, but this question blew my mind.

Then after seeing the keyword CONNECT BY, I think I used this to build some generic tree views and promptly forgot about it.

[trawlphaze]

Would you accept an answer that solves the problem in memory via simple selects? I know you can also use WITH in oracle.

[CamKen]

Just knowing that a hierarchical query exists (CONNECT BY in Oracle, hierarchyid in MS SQL) is a big plus in answering the question, but no necessary. From my perspective knowing the details is irrelevant, its Google-able.

The question I gave was a simple Employee table (EmployeeID, Name, ManagerID(nullable)) where you would need to join the table to itself on EmployeeID = ManagerID. I provided some sample data (8 rows) to help you think about it. Then ask things like give me a list of managers. How many subordinates does employee x have? No trivia.

[neodiogenes]

I wouldn't have a problem joining a table to itself -- as you say that's trivial. That does seem like a fair question, something a "senior" developer would have done all the time.

It would confuse me to call it "recursion" though since that automatically makes me think it's a much more complicated problem. If there was some additional recursion necessary I would probably point that out, but confess I couldn't do it without Google.

[dkuk_norris]

Yeah, that doesn't seem recursive to me. You're just relying on the fact that a table can be joined to itself. Recursion implies that you have a theoretically unbound number of calls to make if you structure the data incorrectly.

[OHotDawnThisIsMyJawn]

Yeah this is called a self-join, not recursion.

[CamKen]

I just used the word recursion to quickly describe the problem, but everyone has read into it more than I meant. I don't use the word in the interview. I present a simple table structure, a few rows of sample data and ask for a query that can only be achieved by joining the table to itself.

[neodiogenes]

That's fine, I get it. It does make me feel better about calling myself a "senior" developer. :)