|
SledgeHammer01 wrote: so stuff like databases, etc. are irrelevant...Say you are working for the DMV
First thought - the requirements are broken, because of course a database is the solution.
Absolutely no one is going to just store the plate number. And of course no one would save the entire range.
So one is left with the silly task of creating a database from scratch.
Databases are based on indexes and pages. Presuming all they care about is the indexed plate number you just create a sparse b-tree index. First block in the file is the first letter followed by an page index (or zero for no use) to the next page and next letter. Each page in this structure has a fixed size with a pointer to the real record.
36 * 8 bytes
For optimization reasons you can increase node size to 2 characters, which is more likely to be reasonable with native storage device page size.
SledgeHammer01 wrote: ...because it didn't scale to handle the worst case or even beyond 200M ranges.
And *again* broken requirements. There are about 250 million vehicles in the United states. License plates are issued by state and other entities. So a valid bid for a system at the current time would never need to manage 200 million.
|
|
|
|
|
The point was to deal with a large amount of data, not license plates specifically  .
|
|
|
|
|
|
Collin Jasnoch wrote: I have noticed a pattern with him missing the point on many posts
You're just bitching b/c you got stuck in a troll thread in the Silverlight forum!
Never underestimate the power of human stupidity
RAH
|
|
|
|
|
Collin Jasnoch wrote: I have noticed a pattern with him missing the point on many posts. Gets stuck on the hypothetical part.
When people decide to denigrate me I always appreciate it if they try to be a bit creative about it.
Just saying.
|
|
|
|
|
SledgeHammer01 wrote: T<layer>he point was to deal with a large amount of data, not license plates specifically
My point is that I build business systems, not hypothetical ones. That of course is generally the point of a 'job' interview.
And a business system would use a database, not expect one to build that same functionality from scratch.
|
|
|
|
|
jschell wrote: That of course is generally the point of a 'job' interview
False. The point of a job interview is to get the job  .
jschell wrote: My point is that I build business systems, not hypothetical ones
Not trying to be a douche or anything , but have you been on a job interview recently? Not at a mom & pop shop or a non-software company that happens to have a few software people, but a *REAL* mid-to-large sized *TRUE* software company (Google, Amazon, Microsoft, etc)? They *ALL* ask hypothetical / algorithm questions like that. I even posted the EXACT question I got at my Google interview as a response to someone who said this question was retarded (besides you, I mean ). Only a guy who didn't know the first thing about interviewing would ask questions like "what's the difference between delete and delete[]?", or "what's the difference between Finalize and Dispose? etc". Basically someone who went on Google and googled C# interview questions.
It sounds like (again no offense intended) you are a guy who prefers to write code without having to think about it much. Sorry, thats not coming out right ... but hopefully you know what I mean... you want to be handed a set of business requirements and want to fullfil those business requirements and call it a day vs the guy who wants to do something new.
I've written MFC, Winforms and WPF apps til I'm blue in the face. I consider them all to be the same on a fundamental level. One app is working on widgets and another app is working on shipping the widgets between warehouses. Yet another app that does a similar (yet different) thing on wizzers. Its all the same. Essentially you are slapping controls on a form and mapping them to event handlers and running a sql query or whatever.
If you want a job where you do new things and do stuff thats outside the box, you would have an interview where you are asked to think outside the box.
If you have no interest in that type of work, I could see how you would refuse to answer hypothetical questions.
Unfortunately, I think you will find that most companies THINK they are doing something new and exciting when they aren't. My boss here thinks we are doing something new and exciting... but in reality, its a rehash and there are 10 competitors out there who do it way better then we do.
|
|
|
|
|
SledgeHammer01 wrote: If you have no interest in that type of work, I could see how you would refuse to answer hypothetical questions.
New technologies have nothing to do with hypothetical questions.
Of the interviews I have been in and the ones that I have given my experience would suggest that developers in general make poor interviewers. They ask technically specific questions, hypothetical or not, without understanding what they can realistically expect as an answer. Sometimes they don't even understand the breadth of the question they are asking.
Some interviewers understand that the lack of merit in their technological questions (in the way they are given), many are ignorant of the nature of how it might be accomplished, and some just refuse to even consider the possibility that confusion in the interview process might originate from the interviewer and not the interviewee.
|
|
|
|
|
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.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
