|
1) It wasn't my interview question, it was one that I got
2) You still don't seem to understand the POINT of the question. It is NOT for you to give the "best" or "right" answer. It is to judge how you THINK. Why do you have such difficulty understanding that?
If I was hiring a junior or mid-level software engineer / coder, I would ask him/her basic coding questions to judge their coding skills because I would only give them CODING assignments.
On the other hand, if I was hiring a Senior / Team Lead Software Engineer, I'd expect them to be able to SOLVE PROBLEMS. That was a question designed to see how you SOLVE PROBLEMS.
If you do not know the difference between a coder and a software engineer / architect, I can see how you would not understand the point of the question. Judging by the fact that you are still stuck on the facts that you "aren't allowed" to use a database or that there aren't 78B license plates in the world, it would imply to me (or any other interviewer) that you do not have good problem solving skills and/or are unwilling to think outside the box.
If I am hiring a senior guy, I would not waste my time asking him stupid C# programming questions out of the "C# interview questions" hand book because I would not expect a guy who can not code to have made it that far.
But just for arguments sake, since you aren't interested in jobs that require you to think, what WOULD you consider a good interview question?
modified 4-Feb-12 15:57pm.
|
|
|
|
|
SledgeHammer01 wrote: it was one that I got...It is to judge how you THINK. Why do you have such difficulty understanding that?
Perhaps because I have experienced it more than you?
The fact that either you presume that the interviewer is only interested in your thought processes or even if the interviewer actually told you that doesn't in fact mean that the interviewer is actually going to be comfortable accepting answers that meet that goal.
I have been an interviewer in group interview situations where developers specifically told the interviewee that they were asking open ended questions and yet it became almost immediately obvious that the interviewer was fishing for very specific responses. I have also been on the receiving end of that as well.
SledgeHammer01 wrote: If you do not know the difference between a coder and a software engineer /
architect
Hopefully I know that since I have been both and worked with both.
SledgeHammer01 wrote: ...what WOULD you consider a good interview question?
Thought that it was implicitly obvious that my problem with the initial question was the explicit requirements. If the question was open then letting the interviewee suggest a database and/or bring up limitations of the questions itself (about realistic volumes) would certainly suggest some level of expertise.
Conversely as an open ended question if the interviewee attempted to suggest an in memory memory model (again since I would leave it open ended) it would suggest that the developer doesn't have significant real world experience (presuming that their resume didn't already reveal that they were a junior level.)
|
|
|
|
|
jschell wrote: Perhaps because I have experienced it more than you?
Experienced what? Getting thrown out of interviews for being a tool? lol. No, I haven't. The only thing I have heard from you so far is that you refuse to answer the question because its "too conceptual" and "not a real world scenario" and you would only do it with a database and are not open to any other method. In fact, you are so offended by the stupidity and unrealism of the question & scenario that you would just walk out of the interview before being thrown out  .
Pretty much everybody else who responded to this thread was able to offer a non database based solution of some sort. You are the only person who has been downright throwing a tantrum at the mere thought of getting such a stupid question.
|
|
|
|
|
SledgeHammer01 wrote: is that you refuse to answer the question because
I don't believe I said that.
SledgeHammer01 wrote: scenario that you would just walk out of the interview before being thrown out
No I didn't say that.
SledgeHammer01 wrote: Pretty much everybody else who responded to this thread was able to offer a non
database based solution of some sort.
I suggest that you might want to read all of my responses. Or re-read them.
|
|
|
|
|
How about a ZDD of 36 * 7 variables? If there are any patterns (and there will be) it should do fine. As a bonus you can give it more interesting queries than just "is this one available?" or even "give me the lexicographically smallest available number" - such as, "give me all the available numbers that have 'R0FL' in them"
By the way, why is a packed bit array out again? 9GB isn't that much at all..
|
|
|
|
|
Never even heard of a ZDD haha. From googling it, it looks like a DAWG type thing?
|
|
|
|
|
Well, not exactly, but I can see how they could be called related.
|
|
|
|
|
Lol, well, I tried looking at a paper on it and it went way over my head, but it was a technical paper.
|
|
|
|
|
|
As has been said, a database is likely the best general solution. Otherwise, a word search tree (similar to the DAWG you mentioned) might work fairly well.
One of the problems with the situation described is that few real-world cases require each client to maintain its own copy of such a large collection of data. Usually there will be connectivity to a shared server of some sort. However, there are situations in which a client must continue working when the connection is disconnected. But in such situations, the client probably shouldn't be allowed to add data to the collection.
Anecdote time: I was once involved in such a situation. What had been done was to store four bits per item in a binary file (this was on DOS by the way), so for instance the first byte of the file held the status for item 0 in the low nybble and the status of item 1 in the high nybble, etc. Access to a particular item's status was a simple calculation, disk seek, and read one byte. I don't remember what the highest numbered item was at the time -- let's say a million -- so that would be about a half MB of disk to store the list. Once a day a whole new file was downloaded to each connected client and throughout the day updates would be sent. If a client was disconnected it would start getting updates when it reconnected and a whole file within a day -- this was fine for the purpose.
|
|
|
|
|
Why would you store ALL license plates? Why not just the ones that are available eg?
That should reduce the size of your object significantly.
In addition, the question is just ridiculous without use of a database. 
V.
|
|
|
|
|
How would you only store the available ones 
For what is now probably the 17th time  , this had nothing to do with databases or license plates , they were asking a DATA STRUCTURE question. I.e. how would you deal with large amounts of data. You do not always have the option of using a database.
|
|
|
|
|
SledgeHammer01 wrote: You do not always have the option of using a database.
No, you pretty much always do nowadays.
|
|
|
|
|
Oh my lord... .
Ok, fine... let me rephrase the question since people don't seem to understand what "hypothetical" and "think outside the box" mean .
Almost the same exact problem, but completely rephrased. Instead of 0 - 9 & A - Z as your alphabet, you now only need to deal with A - Z. Instead of "words" fixed at 6 characters, you can now have "words" of any length. Given an input, I need you to find out if that "word" is "taken". Oh yeah, and this is for a mobile device where you have limited resources, so the customer will get mad if he is only able to install our application and no other because it fills up his mobile device.
Sounds almost like a spell check / dictionary type problem, no? . Kind of like the original problem if you were able to "think outside the box" .
Would you store a complete list of English words in a database to do a spell check? Heck No. That would be a horrible solution and a complete waste of space.
But you say "thats a completely different problem!!!! you bastard!!!"... not really... imagine if instead of spell checking english words, you "spell checked" the license plates .
Now obviously, when applied to the license plate problem, there are other issues, like the "spell check" solution AND/OR a database solution would be a horrible idea if you had a lot of items. Clearly for that problem, the packed bit array is the most scalable, compact & fastest runtime. Ok, but do mobile devices have 9GB of resources available? Probably not.
Anyways, it wasn't a real world design issue, it was a problem solving exercise .
But clearly, the license plate issue is pretty similar to a spell check problem.
|
|
|
|
|
It's not that similar because the reason you wouldn't store every word* in a dictionary is because words have associations that you can exploit to organise the data. In particular, words tend to share their beginnings and therefore you can create some form of tree-like structure which can chop off large sections of the search space, and cut down on duplication.
As stated in the problem, the plates are entirely uniformly distributed in the search space and that means you can't do that.
(*: to be honest you probably would, a word list is going to be measured in megabytes and even on a phone these days that's not even close to a problem)
|
|
|
|
|
Whaaaaatttt??? I'm confused. Aren't there 1.6M license plates that start with XYZ? And 1.6M license plates that start with 123 and so on?
You are probably right though, that a flat list of English words if we assumed 1M words at 10chars avg would only be 10MB.
There are 78B possible license plates though .
|
|
|
|
|
Yes, that's my point. Potential plates (at least in this system) are uniformly distributed, so you can't use the clustering to your advantage. For words, there are (say) 100,000 starting with 'exa' but 0 starting with 'ejf'. So your top level of tree, if you make it 3 characters (max 26³ entries), can cut out whole sections of the theoretical word space. That is because of the clustering of words within the search space which is predictable and non-random.
|
|
|
|
|
I think it was you who misunderstood me.
The whole hypothetical situation of storing a buttload of data in memory is fine, but it's not because "no database is available".
SledgeHammer01 wrote: Would you store a complete list of English words in a database
Yes, I have, for checking Scrabble words. In fact I used Access  to do it.
For an actual spell-checker I would use a spell check tree, but I still need to persist the list between runs -- ergo, a database, which can then be loaded (perhaps on demand) the next time I run it. (The tree could be more of a cache.)
On a mobile, I expect a Web Service would be more appropriate.
SledgeHammer01 wrote: the packed bit array is the most scalable, compact & fastest runtime.
And it's even better if you can leave it on disk rather than hold it in memory
.
|
|
|
|
|
PIEBALDconsult wrote: it's not because "no database is available".
No, it's because that's what you were asked in the interview  . If you told your interviewer that you refused to answer the question aside from using a database and you would refuse to implement any solution that did not use one, I'm guessing you probably wouldn't get the job  .
Anyways, while its not likely the majority of the time NOW, there are plenty of scenarios where a database might not be available: mobile, embedded, military, etc. Now sure, I could add a requirement to the Air Force Smart Bomb design where I need to install an Access database  on every bomb, but seeing as I'm just going to blow it up, I'm guessing they want to make it as cheap as possible.
Now, before you go off all half-cocked, foaming at the mouth about why a smart bomb would have a spell checker, it wouldn't. It was a hypothetical example of a situation where you MIGHT not have one.
I have an iPhone now, but I used to have a Moto Razr. I'm guessing the iPhone has a database and the Moto Razr didn't. Hmm... weird... the Moto Razr had EXTREMELY limited resources, but it still happened to have a full spell checker in it.
EDIT: the Moto Razr had 5MB of available space. That's for the OS, phone book, pics, videos, games, email, etc. STILL managed to squeeze a spell checker in there... bet there wasn't room for an access database or a database of any variety . Bet they had to use some really efficient data structures.
|
|
|
|
|
V. wrote: Why not just the ones that are available eg?
That doesn't alter the essential question (stupid question it may be) -- creating an in-memory structure to hold a whole lot of data.
|
|
|
|
|
PIEBALDconsult wrote: stupid question it may be) -- creating an in-memory structure to hold a whole
lot of data.
Yeah, true. Cuz you NEVER need to do that . Maybe not that AMOUNT of data, but...
|
|
|
|
|
Such a vague scenario is pretty much impossible to answer, because how you'd go about it depends on where the data has patterns. For example, if IDs are allocated in blocks, use a range based structure. If it will always be very sparse, store only the 'hits'. If the search space is likely to be over 50% full, you might want to use an inverse (i.e. store the empties).
License plates are a clearly unrealistic scenario because the number you need to store will only be of the order of 100m at most and therefore you can just use a conventional database (even at 1kb per record you're still only talking 100GB which is within the capacity of a normal computer, never mind an institutional server).
9GB is not big enough to be a problem, as long as you don't hook it all into memory, so I'd just dump the whole bit array to a file, in sequence, and use seek to look in the right place (and poke a bit back when a plate is allocated), if a database was disallowed and there was no aggregation or querying requirement.
Edit: obviously, if I was writing this system for real, I'd just use a database, heh.
|
|
|
|
|
I'm confused: you say the specific question asked was specifically about checking available license plates, but, then, you say the question was about data structures, and databases are "irrelevant:" did the interviewer(s) tell you the question was about data structures, and exclude "databases," specifically, or not ?
Or are these conclusions that you inferred from the interviewer(s) question ?
imho any perceived ambiguity in the interviewer(s)' question "opens the door" for you to follow-through with clarifying questions that attempt to frame the question asked in terms of real-world scenarios: like, as mentioned in a comment above, that the largest possible number of license plates for any one real state (in the US) would be far less than 78 billion ... as in California's 37 million, of which we can safely assume that many do not have a driver's license.
My answer would have been to say straight out: that storing the total possible set of all possible variations of license plates was absurd, no matter what data structures would be used, and that the database should store only the plates already allocated, and use a function to generate new ones at random, or new ones that meet some predefined criteria like having the letters "IAMOK" somewhere in the sequence (similar to the custom tag services offered by many states for which a fee is charged).
If the interviewer(s) then altered the question, so it became, in general: how would you store very large amounts of data: I would have replied that to answer that question requires a consideration of the internal organization of the data, and its usage, and storage (centralized vs. distributed), and there is no "one-size-fits-all" answer, and that a good programmer becomes intimately familiar with the internal organization of the data, its real-world "incarnation," and how the data is used in the real world, and then selects data structures based on several criteria, including efficiency of storage, compatibility with existing hardware and network constraints, the speed of access that end-users will demand/require, etc.
And then, I'd probably walk over to the food-stamp office, to collect my monthly allocation, and think about the next job interview
best, Bill
"Our life is a faint tracing on the surface of mystery, like the idle, curved tunnels of leaf miners on the surface of a leaf. We must somehow take a wider view, look at the whole landscape, really see it, and describe what's going on here. Then we can at least wail the right question into the swaddling band of darkness, or, if it comes to that, choir the proper praise." Annie Dillard
|
|
|
|
|
BillWoodruff wrote: I'm confused: you say the specific question asked was specifically about
checking available license plates, but, then, you say the question was about
data structures, and databases are "irrelevant:" did the interviewer(s) tell you
the question was about data structures, and exclude "databases," specifically,
or not ?
The question was to determine how you think when large amounts of data are involved. Do you think you would not have to solve such problems if you were working at say Google? or Amazon?, etc.
Your response is actually pretty similiar to the majority I have gotten . "This problem is stupid", "there aren't that many license plates in the entire world", etc. rather then thinking of the problem in generic terms. For example.. oh hey, maybe this problem is a variation on the traveling salesman problem, or the backpack problem and I can apply that solution .
That was the point of the exercise , but everybody seems to be focusing on the license plate aspect of the question .
modified 3-Feb-12 12:31pm.
|
|
|
|
|
SledgeHammer01 wrote: The question was to determine how you think when large amounts of data are involved.
SledgeHammer01 wrote: everybody seems to be focusing on the license plate aspect of the question
I think the very simple reason for the focus on the "license plate" issue is: that's what you told us the actual question was.
Now, if you had told us the question actually asked was:
"We want you to tell us the strategies you would employ for storing very large amounts of data, as Google, and Amazon, do: you might use as an example, to make this question more specific: the issue of a license-plate management system where all permutations of the sets ... blah and blah ... are ... blah ... blah ... blah ... and an immediate task is the allocation of an unused license number.
Then, I think you would have received a very different set of replies.
To that (hypothetical) question, I would have replied: "what is the correlation of adding an unused license number of a car from a set of all permutations, to adding a new user, book review, to Amazon, or to adding a new link-listing to Google: are you asking about the issue of generating unique identification indexes in master databases (GUIDS, or some hash) ?"
Note my assumption (which you have every right to be skeptical about) that: in technical interviews, where you know the people interviewing you are "smart," and informed about what they are asking you about: that they respect someone who responds to vague, overly-broad, questions, by pro-actively demanding they be clarified: in the process of which you reveal your awareness of the issues and factors that surround real-world implementations.
Also, I believe a "challenging interviewee" ... who shows intellectual balance in the act of challenging ... and demonstrates emotional equanimity in the art of doing so ... is impressive ... or at least would impress persons at companies I would wish to be employed by.
But, I would make these distinctions: HR "screening" interviews are inappropriate places to be challenging: they ask "mush," and should be given back whatever "mush" they want to hear. "Rubber-stamp" interviews with managers, when you've been offered the job based on the real technical interviews, are also scenarios where you just want to "go with the flow," and appear as a "good citizen" who looks forward to "learning the job."
"Float like a butterfly, sting like a bee." Muhammad Ali
Where'd I put those food stamps
best, Bill
"Our life is a faint tracing on the surface of mystery, like the idle, curved tunnels of leaf miners on the surface of a leaf. We must somehow take a wider view, look at the whole landscape, really see it, and describe what's going on here. Then we can at least wail the right question into the swaddling band of darkness, or, if it comes to that, choir the proper praise." Annie Dillard
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
