Reading the articles written by Joel sometimes feels frustrated. But, anyway, they are also illustrated. Here is another post about how to write readable resume:
======
# Proofread everything a hundred times and have one other person proofread it. Someone who got really good grades in English.
# Write a personal cover letter that is customized for the job you are applying for. Try to sound like a human in the cover letter. You want people to think of you as a human being.
# Don't apply for too many jobs. I don't think there's ever a reason to apply for more than three or four jobs at a time. Résuméspam, or any sign that you're applying for 100 jobs, just makes you look desperate which makes you look unqualified. You want to look like you are good enough to be in heavy demand. You're going to decide where you want to work, because you're smart enough to have a choice in the matter, so you only need to apply for one or two jobs. A personalized cover letter that shows that you understand what the company does goes a long way to proving that you care enough to deserve a chance.
# What we're really looking for when we look at résumés is someone who is passionate and successful at whatever they try to do. We like people who are passionate about software. Writing a shareware app when you're a teenager is just as good a qualification to us as getting into MIT. This is your life story, and by the time you're applying for a job it's probably too late to change that.
# The number one best way to get someone to look at your resume closely: come across as a human being, not a list of jobs and programming languages.
March 7, 2011
March 6, 2011
Comparing file diff in Ubuntu
I am still familiar with the highlighted view for differences rather than the "diff" command, which produces the results in a "+/-" form. After a easy google, the Meld turns out be one good alternative solution for this purpose. Here is its web page.
Just one step to do:
$ sudo apt-get install meld
Then, you will find the Meld in Application->Programming directory.
Have fun.
Just one step to do:
$ sudo apt-get install meld
Then, you will find the Meld in Application->Programming directory.
Have fun.
March 4, 2011
some basic C/C++ questions
1) What are some of the main differences between a linked list and an array?
Arrays are faster in access than a link list for random access with index.
Arrays are not dynamic while a link list is.
Arrays are easier to sort than a link list.
The elements of link list can be deleted/inserted while arrays cannot.
Arrays occupy the same block of memory, while a link list is distributed.
Array objects are automatically created by a compiler, while link lists are not.
Arrays are part of most compilers, while link lists are not.
Arrays are syntactically simple to read.
2) What are the differences between struct, class and union?
Struct, class and union all contain data members and methods. However, a struct and union have their member’s public by default, while the class members are private by default. Also, a struct cannot contain an instance of itself. A union cannot be used as a base class in inheritance. None of a union's data members can be declared static and none of its functions can be virtual.
3) What are virtual functions?
Virtual functions are functions whose behavior is known at runtime rather than at compile time. Due to this behavior, it can be said that virtual functions implement Polymorphism. In other words, preceding a function name with virtual in the base class means that that function is intended to be re-implemented (overridden) in the sub-class.
4) Explain the mechanism of virtual functions and virtual function tables.
Whenever a class member function is declared as virtual, the compiler creates a virtual table in memory which contains all function pointers that are declared as virtual in that class. This enables run time polymorphism (i.e. finding out the desired function at run time). Virtual function tables also have an additional pointer in the object to the vtable. As this additional pointer and the vtable increases the size of the object, a class designer needs to be judicious about declaring functions virtual. The sequence of events upon calling a method on the base object pointer is:
Get vtable pointer (this vtable pointer points to the beginning of the vtable).
Get the function pointers in the vtable using offset.
Invoke the function indirectly through the vtable pointer.
5) Given a singly linked list and a pointer to a certain node in the list, how would you delete that node in constant time?
First of all, check if this node is the last node in the list. If not, copy the contents of the next node to the current node, and delete the next node.
6) What are recursive functions? What are the advantages and disadvantages of recursive algorithms?
A function that calls itself repeatedly, satisfying some condition, is called a Recursive Function. In my point of view, the recursive functions should be avioded at most of the time via the "while" loop sentence. However, on the other hand, some problems inherently are better suited for recursion, such as Fibonacci series generation.
Some advantages of recursive algorithms are: concise in terms of source code; and looking more elegant. The disadvantages of recursion include: requiring more of stack than non-recursive algorithms, due to several activation stacks for each call of the function; and correcting or testing recursive functions would require a lot of careful thinking.
7) What leads to code-bloating in C++?
Inline functions and templates, if not used properly, may lead to code bloating. Multiple Inheritance may also lead to code bloating (this is because the sub classes will end up getting members from all the base classes even if only few members will suffice).
Inline is great. Reasons: They look like functions, they act like functions, they're ever so much better than macros (Whenever you write a macro, you have to remember to parenthesize all the arguments in the macro body. Otherwise you can run into trouble when somebody calls the macro with an expression. On the contrary, inline funtions do not have that kind of troubles), and you can call them without having to incur the overhead of a function call. Moreover, as inlining a function, it may enable compilers to perform context-specific optimizations on the body of the function. Most compilers never perform such optimizations on "outlined" function calls.
However, the idea behind an inline function is to replace each call of that function with its code body, which is likely to increase the size of your object code. On machines with limited memory, overzealous inlining can give rise to programs that are too big for the available space. Even with virtual memory, inline-induced code bloat can lead to additional paging, a reduced instruction cache hit rate, and the performance penalties that accompany these things.
Solution: Initially, don't inline anything, or at least limit your inlining to those functions that must be inline (eg. functions defined inside a class which are implicitly declared inline) or are truly trivial (such as Person::age). By employing inlines cautiously, you facilitate your use of a debugger, but you also put inlining in its proper place: as a hand-applied optimization. Don't forget the empirically determined rule of 80-20, which states that a typical program spends 80% of its time executing only 20% of its code. It's an important rule, because it reminds you that your goal as a software developer is to identify the 20% of your code that can increase your program's overall performance. You can inline and otherwise tweak your functions until the cows come home, but it's wasted effort unless you're focusing on the right functions.
8) What are references in C++? Why do you need them when you have pointers?
Reference variables are internally implemented as a pointer; it’s just that programmers can't use it the way they use pointers. As a side note, a reference must refer to some object at all times, but a pointer can point to NULL. In this way, references can be more efficient when you know that you'll always have an object to point to, because you don't have to check against NULL.
9) How do you do dynamic memory allocation in C applications? List advantages and disadvantages of dynamic memory allocation vs. static memory allocation.
In C, malloc, calloc and realloc are used to allocate memory dynamically. In C++, new(), is usually used to allocate objects.
Advantage is that memory is allocated on an as-needed basis, which helps remove the inefficiencies inherent to static memory allocation, that is when the amount of memory needed is not known at compile time and one has to make a guess.
Disadvantages: 1) dynamic memory allocation is slower than static memory allocation, because dynamic memory allocation happens in the heap area; 2) dynamic memory needs to be carefully deleted after use, because they are created in non-contiguous area of memory segment, and if not properly handled, the operations would cause memory fragmentation; 3) dynamic memory allocation causes contention between threads, so it degrades performance when it happens in a thread.
10) What are constructors and destructors?
Constructors and destructors are provisions for initialization and cleanup of objects.
A constructor is a special member function with the same name as the Class. It is invoked automatically when the object is created. It usually contains initialization code for member variables and allocation of memory. There can be multiple overloaded constructors, with different input arguments, used to initialize the object in a variety of ways.
A destructor is a special member function that is called just before an object is destroyed. For example, when the object variable goes out of scope. It is used to perform cleanup. There can be only one destructor. Its name is ‘~’ followed by the class name.
11) What happens if an error occurs in a constructor or destructor?
Constructors don't have a return type, so it's not possible to use error codes. The best way to signal constructor failure is therefore to throw an exception. However, keep in mind that the memory for the object itself is released, and the destructors for all sub-objects (i.e. members and base classes) whose constructors have successfully run to completion will be called, which will consquently cause memory leak by the object pointer.
12) Differentiate between a copy constructor and an assignment operator.
The copy constructor is used to copy an object to a newly created object. This is used during initialization and not during ordinary assignment. The copy constructor is invoked whenever a new object is created and initialized to an existing object of the same kind.
In other words, the assignment operator handles assigning one object to another of the same class. If a statement creates a new object it is using initialization. If it alters the value of an existing object it is assignment.
13) What are virtual destructors?
Destructor implemented by declaring a base class’s destructor with the keyword virtual is called a virtual destructor. A virtual destructor ensures that, when delete is applied to a base class pointer or reference, it calls the destructor implemented in the derived class, if an implementation exists.
Let’s take the simplest polymorphic relation: A - base class, B - class derived from A. If we've got a pointer (or reference) to class A, but under the hood it is an object of type B, and we're trying to delete the object, declaration of virtual destructor in class A ensures that the destructor of class B will be called.
B* b = new B;
A* a = b //due to polymorphism!
delete a; // both A and B destructors are called.
14) What is multiple inheritance? What are the potential pitfalls of multiple inheritance? How would you avoid multiple inheritance?
Deriving a class from more than one direct base class is called multiple inheritance. Note that the order of derivation is relevant only to determine the order of default initialization by constructors and cleanup by destructors.
Potential pitfalls of Multiple Inheritance are: 1) Ambiguity; 2) slow; 3) The “Common Ancestor” problem: For example, if class B and class C derived from class A and if class D derived from class B and class C, then class D will have 2 copies of class A that might lead to inconsistency, as the class doesn't know which copy it is viewing.
15) What is exception handling? What are the advantages of exception handling?
Exceptions are an alternative to function return values. The big differences are: 1) Exceptions cannot be ignored. They must be caught or the app will crash. It is a way of forcing the caller of a function to deal with an exceptional condition. 2) It is also an improvement over return values, because you can put all possible values of your return type to good use, instead of having to dedicate one or more values as the "invalid" value. 3) In addition, exceptions allow you to jump out of deeply nested function calls conveniently, avoiding a lot of return type checking and conditional statements.
16) What is the difference between new()/delete() and malloc()/free ()?
The main difference is that malloc() and free() don't know anything about constructors and destructors, where as new and delete do. The following lists the main differences: 1) new automatically computes the size of the data object. In malloc you would have to use the sizeof operator. 2) new automatically returns the correct pointer type. In malloc you would have to use a type cast. 3) with new you can initialize the object while creating the object. 4) new and delete can be overloaded. 5) It's safe to delete a NULL pointer, but you'll get core dump to free a NULL pointer.
17) Describe different types of polymorphism available in C++.
1. Compile time polymorphism; 2. Runtime Polymorphism. Operator overloading and Function Overloading are the examples for compile time polymorphism. Using Virtual Functions we will achieve run time polymorphism.
Computer Network
The Internet Protocol (IP) is a key part of the mechanism for transferring data across the internet. Information is broken into small packets, and the IP is responsible for relaying and routing them around the system by identifying and locating hosts. The current version is IPv4, and because it is made up in sets of 32 bits, it is limited to having just under 4.3 billion addresses. It seems like a lot but they are almost all used up.
Arrays are faster in access than a link list for random access with index.
Arrays are not dynamic while a link list is.
Arrays are easier to sort than a link list.
The elements of link list can be deleted/inserted while arrays cannot.
Arrays occupy the same block of memory, while a link list is distributed.
Array objects are automatically created by a compiler, while link lists are not.
Arrays are part of most compilers, while link lists are not.
Arrays are syntactically simple to read.
2) What are the differences between struct, class and union?
Struct, class and union all contain data members and methods. However, a struct and union have their member’s public by default, while the class members are private by default. Also, a struct cannot contain an instance of itself. A union cannot be used as a base class in inheritance. None of a union's data members can be declared static and none of its functions can be virtual.
3) What are virtual functions?
Virtual functions are functions whose behavior is known at runtime rather than at compile time. Due to this behavior, it can be said that virtual functions implement Polymorphism. In other words, preceding a function name with virtual in the base class means that that function is intended to be re-implemented (overridden) in the sub-class.
4) Explain the mechanism of virtual functions and virtual function tables.
Whenever a class member function is declared as virtual, the compiler creates a virtual table in memory which contains all function pointers that are declared as virtual in that class. This enables run time polymorphism (i.e. finding out the desired function at run time). Virtual function tables also have an additional pointer in the object to the vtable. As this additional pointer and the vtable increases the size of the object, a class designer needs to be judicious about declaring functions virtual. The sequence of events upon calling a method on the base object pointer is:
Get vtable pointer (this vtable pointer points to the beginning of the vtable).
Get the function pointers in the vtable using offset.
Invoke the function indirectly through the vtable pointer.
5) Given a singly linked list and a pointer to a certain node in the list, how would you delete that node in constant time?
First of all, check if this node is the last node in the list. If not, copy the contents of the next node to the current node, and delete the next node.
6) What are recursive functions? What are the advantages and disadvantages of recursive algorithms?
A function that calls itself repeatedly, satisfying some condition, is called a Recursive Function. In my point of view, the recursive functions should be avioded at most of the time via the "while" loop sentence. However, on the other hand, some problems inherently are better suited for recursion, such as Fibonacci series generation.
Some advantages of recursive algorithms are: concise in terms of source code; and looking more elegant. The disadvantages of recursion include: requiring more of stack than non-recursive algorithms, due to several activation stacks for each call of the function; and correcting or testing recursive functions would require a lot of careful thinking.
7) What leads to code-bloating in C++?
Inline functions and templates, if not used properly, may lead to code bloating. Multiple Inheritance may also lead to code bloating (this is because the sub classes will end up getting members from all the base classes even if only few members will suffice).
Inline is great. Reasons: They look like functions, they act like functions, they're ever so much better than macros (Whenever you write a macro, you have to remember to parenthesize all the arguments in the macro body. Otherwise you can run into trouble when somebody calls the macro with an expression. On the contrary, inline funtions do not have that kind of troubles), and you can call them without having to incur the overhead of a function call. Moreover, as inlining a function, it may enable compilers to perform context-specific optimizations on the body of the function. Most compilers never perform such optimizations on "outlined" function calls.
However, the idea behind an inline function is to replace each call of that function with its code body, which is likely to increase the size of your object code. On machines with limited memory, overzealous inlining can give rise to programs that are too big for the available space. Even with virtual memory, inline-induced code bloat can lead to additional paging, a reduced instruction cache hit rate, and the performance penalties that accompany these things.
Solution: Initially, don't inline anything, or at least limit your inlining to those functions that must be inline (eg. functions defined inside a class which are implicitly declared inline) or are truly trivial (such as Person::age). By employing inlines cautiously, you facilitate your use of a debugger, but you also put inlining in its proper place: as a hand-applied optimization. Don't forget the empirically determined rule of 80-20, which states that a typical program spends 80% of its time executing only 20% of its code. It's an important rule, because it reminds you that your goal as a software developer is to identify the 20% of your code that can increase your program's overall performance. You can inline and otherwise tweak your functions until the cows come home, but it's wasted effort unless you're focusing on the right functions.
8) What are references in C++? Why do you need them when you have pointers?
Reference variables are internally implemented as a pointer; it’s just that programmers can't use it the way they use pointers. As a side note, a reference must refer to some object at all times, but a pointer can point to NULL. In this way, references can be more efficient when you know that you'll always have an object to point to, because you don't have to check against NULL.
9) How do you do dynamic memory allocation in C applications? List advantages and disadvantages of dynamic memory allocation vs. static memory allocation.
In C, malloc, calloc and realloc are used to allocate memory dynamically. In C++, new(), is usually used to allocate objects.
Advantage is that memory is allocated on an as-needed basis, which helps remove the inefficiencies inherent to static memory allocation, that is when the amount of memory needed is not known at compile time and one has to make a guess.
Disadvantages: 1) dynamic memory allocation is slower than static memory allocation, because dynamic memory allocation happens in the heap area; 2) dynamic memory needs to be carefully deleted after use, because they are created in non-contiguous area of memory segment, and if not properly handled, the operations would cause memory fragmentation; 3) dynamic memory allocation causes contention between threads, so it degrades performance when it happens in a thread.
10) What are constructors and destructors?
Constructors and destructors are provisions for initialization and cleanup of objects.
A constructor is a special member function with the same name as the Class. It is invoked automatically when the object is created. It usually contains initialization code for member variables and allocation of memory. There can be multiple overloaded constructors, with different input arguments, used to initialize the object in a variety of ways.
A destructor is a special member function that is called just before an object is destroyed. For example, when the object variable goes out of scope. It is used to perform cleanup. There can be only one destructor. Its name is ‘~’ followed by the class name.
11) What happens if an error occurs in a constructor or destructor?
Constructors don't have a return type, so it's not possible to use error codes. The best way to signal constructor failure is therefore to throw an exception. However, keep in mind that the memory for the object itself is released, and the destructors for all sub-objects (i.e. members and base classes) whose constructors have successfully run to completion will be called, which will consquently cause memory leak by the object pointer.
12) Differentiate between a copy constructor and an assignment operator.
The copy constructor is used to copy an object to a newly created object. This is used during initialization and not during ordinary assignment. The copy constructor is invoked whenever a new object is created and initialized to an existing object of the same kind.
In other words, the assignment operator handles assigning one object to another of the same class. If a statement creates a new object it is using initialization. If it alters the value of an existing object it is assignment.
13) What are virtual destructors?
Destructor implemented by declaring a base class’s destructor with the keyword virtual is called a virtual destructor. A virtual destructor ensures that, when delete is applied to a base class pointer or reference, it calls the destructor implemented in the derived class, if an implementation exists.
Let’s take the simplest polymorphic relation: A - base class, B - class derived from A. If we've got a pointer (or reference) to class A, but under the hood it is an object of type B, and we're trying to delete the object, declaration of virtual destructor in class A ensures that the destructor of class B will be called.
B* b = new B;
A* a = b //due to polymorphism!
delete a; // both A and B destructors are called.
14) What is multiple inheritance? What are the potential pitfalls of multiple inheritance? How would you avoid multiple inheritance?
Deriving a class from more than one direct base class is called multiple inheritance. Note that the order of derivation is relevant only to determine the order of default initialization by constructors and cleanup by destructors.
Potential pitfalls of Multiple Inheritance are: 1) Ambiguity; 2) slow; 3) The “Common Ancestor” problem: For example, if class B and class C derived from class A and if class D derived from class B and class C, then class D will have 2 copies of class A that might lead to inconsistency, as the class doesn't know which copy it is viewing.
15) What is exception handling? What are the advantages of exception handling?
Exceptions are an alternative to function return values. The big differences are: 1) Exceptions cannot be ignored. They must be caught or the app will crash. It is a way of forcing the caller of a function to deal with an exceptional condition. 2) It is also an improvement over return values, because you can put all possible values of your return type to good use, instead of having to dedicate one or more values as the "invalid" value. 3) In addition, exceptions allow you to jump out of deeply nested function calls conveniently, avoiding a lot of return type checking and conditional statements.
16) What is the difference between new()/delete() and malloc()/free ()?
The main difference is that malloc() and free() don't know anything about constructors and destructors, where as new and delete do. The following lists the main differences: 1) new automatically computes the size of the data object. In malloc you would have to use the sizeof operator. 2) new automatically returns the correct pointer type. In malloc you would have to use a type cast. 3) with new you can initialize the object while creating the object. 4) new and delete can be overloaded. 5) It's safe to delete a NULL pointer, but you'll get core dump to free a NULL pointer.
17) Describe different types of polymorphism available in C++.
1. Compile time polymorphism; 2. Runtime Polymorphism. Operator overloading and Function Overloading are the examples for compile time polymorphism. Using Virtual Functions we will achieve run time polymorphism.
Computer Network
The Internet Protocol (IP) is a key part of the mechanism for transferring data across the internet. Information is broken into small packets, and the IP is responsible for relaying and routing them around the system by identifying and locating hosts. The current version is IPv4, and because it is made up in sets of 32 bits, it is limited to having just under 4.3 billion addresses. It seems like a lot but they are almost all used up.
March 3, 2011
interview at the point of interviewer
also comes from Joel on software
How do you detect smart in an interview? The first good sign is that you don’t have to explain things over and over again. The conversation just flows. Often, the candidate says something that shows real insight, or brains, or mental acuity. So an important part of the interview is creating a situation where someone can show you how smart they are. Remember, smart does not mean “knows the answer to trivia questions.” Anyway, software teams want to hire people with aptitude, not a particular skill set. Any skill set that people can bring to the job will be technologically obsolete in a couple of years, anyway, so it’s better to hire people that are going to be able to learn any new technology rather than people who happen to know how to make JDBC talk to a MySQL database right this minute. In general, the way to learn the most about a person is to let them do the talking. Give them open-ended questions and problems.
That’s just a list of questions that I want to ask. Here’s a typical plan for interviewing a programmer:
1. Introduction
2. Question about recent project candidate worked on
3. Easy Programming Question
4. Pointer/Recursion Question
5. Are you satisfied?
6. Do you have any questions?
What should you look for during the open ended questions?
One: Look for passion. Smart people are passionate about the projects they work on. They get very excited talking about the subject. They talk quickly, and get animated. Being passionately negative can be just as good a sign. “My last boss wanted to do everything on VAX computers because it was all he understood. What a dope!” There are far too many people around that can work on something and not really care one way or the other. It’s hard to get people like this motivated about anything.
Bad candidates just don’t care and will not get enthusiastic at all during the interview. A really good sign that a candidate is passionate about something is that when they are talking about it, they will forget for a moment that they are in an interview. Sometimes a candidate comes in who is very nervous about being in an interview situation—this is normal, of course, and I always ignore it. But then when you get them talking about Computational Monochromatic Art they will get extremely excited and lose all signs of nervousness. Good. I like passionate people who really care. (To see an example of Computational Monochromatic Art try unplugging your monitor.) You can challenge them on something (try it—wait for them to say something that’s probably true and say “that couldn’t be true”) and they will defend themselves, even if they were sweating five minutes ago, because they care so much they forget that you are going to be making Major Decisions About Their Life soon.
Two: Good candidates are careful to explain things well, at whatever level. I have rejected candidates because when they talked about their previous project, they couldn’t explain it in terms that a normal person could understand. Often CS majors will just assume that everyone knows what Bates Theorem is or what O(log n) means. If they start doing this, stop them for a minute and say, “could you do me a favor, just for the sake of the exercise, could you please explain this in terms my grandmother could understand.” At this point many people will still continue to use jargon and will completely fail to make themselves understood. Gong! You don’t want to hire them, basically, because they are not smart enough to comprehend what it takes to make other people understand their ideas.
Three: If the project was a team project, look for signs that they took a leadership role. A candidate might say, “We were working on X, but the boss said Y and the client said Z.” I’ll ask, “So what did you do?” A good answer to this might be “I got together with the other members of the team and wrote a proposal…” A bad answer might be, “Well, there was nothing I could do. It was an impossible situation.” Remember, Smart and Gets Things Done. The only way you’re going to be able to tell if somebody Gets Things Done is to see if historically they have tended to get things done in the past. In fact, you can even ask them directly to give you an example from their recent past when they took a leadership role and got something done—overcoming some institutional inertia, for example.
Most of the time in the interview, though, should be spent letting the candidate prove that they can write code. Reassure candidates that you understand that it’s hard to write code without an editor, and you will forgive them if the whiteboard gets really messy. Also you understand that it’s hard to write bug-free code without a compiler, and you will take that into account.
These softball questions seem too easy, so when I first started asking them, I had to admit that I really expected everyone to sail right through them. What I discovered was that everybody solved the problem, but there was a lot of variation in how long it took them to solve. That reminded me of why I couldn’t trade bonds for a living (http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html), which means that if the basic concepts aren’t so easy that you don’t even have to think about them, you’re not going to get the big concepts. You see, if you can’t whiz through the easy stuff at 100 m.p.h., you’re never gonna get the advanced stuff.
15 years of experience interviewing programmers has convinced me that the best programmers all have an easy aptitude for dealing with multiple levels of abstraction simultaneously. In programming, that means specifically that they have no problem with recursion (which involves holding in your head multiple levels of the call stack at the same time) or complex pointer-based algorithms (where the address of an object is sort of like an abstract representation of the object itself). Furthermore, I’ve come to realize that understanding pointers in C is not a skill, it’s an aptitude. Pointers require a complex form of doubly-indirected thinking that some people just can’t do, and it’s pretty crucial to good programming. A lot of the “script jocks” who started programming by copying JavaScript snippets into their web pages and went on to learn Perl never learned about pointers, and they can never quite produce code of the quality you need.
That’s the source of all these famous interview questions you hear about, like “reversing a linked list” or “detect loops in a tree structure.” Even though the format of the interview is, superficially, just a candidate writing some code on the whiteboard, my real goal here is to have a conversation about it. “Why did you do it that way?” “What are the performance characteristics of your algorithm?” “What did you forget?” “Where’s your bug?”
That means I don’t really mind giving programming problems that are too hard, as long as the candidate has some chance of starting out, and then I’m happy to dole out little hints along the way, little toeholds, so to speak. I might ask someone, say, to project a triangle onto a plane, a typical graphics problem, and I don’t mind helping them with the trig (SOH-CAH-TOA, baby!), and when I ask them how to speed it up, I might drop little hints about look-up tables. Notice that the kinds of hints I’m happy to provide are really just answers to trivia questions—the kinds of things that you find on Google.
Inevitably, you will see a bug in their function. So we come to question five from my interview plan: “Are you satisfied with that code?” You may want to ask, “OK, so where’s the bug?” The quintessential Open Ended Question From Hell. All programmers make mistakes, there’s nothing wrong with that, they just have to be able to find them. With string functions in C, most college kids forget to null-terminate the new string. With almost any function, they are likely to have off-by-one errors. They will forget semicolons sometimes. Their function won’t work correctly on 0 length strings, or it will GPF if malloc fails… Very, very rarely, you will find a candidate that doesn’t have any bugs the first time. In this case, this question is even more fun. When you say, “There’s a bug in that code,” they will review their code carefully, and then you get to see if they can be diplomatic yet firm in asserting that the code is perfect.
How do you detect smart in an interview? The first good sign is that you don’t have to explain things over and over again. The conversation just flows. Often, the candidate says something that shows real insight, or brains, or mental acuity. So an important part of the interview is creating a situation where someone can show you how smart they are. Remember, smart does not mean “knows the answer to trivia questions.” Anyway, software teams want to hire people with aptitude, not a particular skill set. Any skill set that people can bring to the job will be technologically obsolete in a couple of years, anyway, so it’s better to hire people that are going to be able to learn any new technology rather than people who happen to know how to make JDBC talk to a MySQL database right this minute. In general, the way to learn the most about a person is to let them do the talking. Give them open-ended questions and problems.
That’s just a list of questions that I want to ask. Here’s a typical plan for interviewing a programmer:
1. Introduction
2. Question about recent project candidate worked on
3. Easy Programming Question
4. Pointer/Recursion Question
5. Are you satisfied?
6. Do you have any questions?
What should you look for during the open ended questions?
One: Look for passion. Smart people are passionate about the projects they work on. They get very excited talking about the subject. They talk quickly, and get animated. Being passionately negative can be just as good a sign. “My last boss wanted to do everything on VAX computers because it was all he understood. What a dope!” There are far too many people around that can work on something and not really care one way or the other. It’s hard to get people like this motivated about anything.
Bad candidates just don’t care and will not get enthusiastic at all during the interview. A really good sign that a candidate is passionate about something is that when they are talking about it, they will forget for a moment that they are in an interview. Sometimes a candidate comes in who is very nervous about being in an interview situation—this is normal, of course, and I always ignore it. But then when you get them talking about Computational Monochromatic Art they will get extremely excited and lose all signs of nervousness. Good. I like passionate people who really care. (To see an example of Computational Monochromatic Art try unplugging your monitor.) You can challenge them on something (try it—wait for them to say something that’s probably true and say “that couldn’t be true”) and they will defend themselves, even if they were sweating five minutes ago, because they care so much they forget that you are going to be making Major Decisions About Their Life soon.
Two: Good candidates are careful to explain things well, at whatever level. I have rejected candidates because when they talked about their previous project, they couldn’t explain it in terms that a normal person could understand. Often CS majors will just assume that everyone knows what Bates Theorem is or what O(log n) means. If they start doing this, stop them for a minute and say, “could you do me a favor, just for the sake of the exercise, could you please explain this in terms my grandmother could understand.” At this point many people will still continue to use jargon and will completely fail to make themselves understood. Gong! You don’t want to hire them, basically, because they are not smart enough to comprehend what it takes to make other people understand their ideas.
Three: If the project was a team project, look for signs that they took a leadership role. A candidate might say, “We were working on X, but the boss said Y and the client said Z.” I’ll ask, “So what did you do?” A good answer to this might be “I got together with the other members of the team and wrote a proposal…” A bad answer might be, “Well, there was nothing I could do. It was an impossible situation.” Remember, Smart and Gets Things Done. The only way you’re going to be able to tell if somebody Gets Things Done is to see if historically they have tended to get things done in the past. In fact, you can even ask them directly to give you an example from their recent past when they took a leadership role and got something done—overcoming some institutional inertia, for example.
Most of the time in the interview, though, should be spent letting the candidate prove that they can write code. Reassure candidates that you understand that it’s hard to write code without an editor, and you will forgive them if the whiteboard gets really messy. Also you understand that it’s hard to write bug-free code without a compiler, and you will take that into account.
These softball questions seem too easy, so when I first started asking them, I had to admit that I really expected everyone to sail right through them. What I discovered was that everybody solved the problem, but there was a lot of variation in how long it took them to solve. That reminded me of why I couldn’t trade bonds for a living (http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html), which means that if the basic concepts aren’t so easy that you don’t even have to think about them, you’re not going to get the big concepts. You see, if you can’t whiz through the easy stuff at 100 m.p.h., you’re never gonna get the advanced stuff.
15 years of experience interviewing programmers has convinced me that the best programmers all have an easy aptitude for dealing with multiple levels of abstraction simultaneously. In programming, that means specifically that they have no problem with recursion (which involves holding in your head multiple levels of the call stack at the same time) or complex pointer-based algorithms (where the address of an object is sort of like an abstract representation of the object itself). Furthermore, I’ve come to realize that understanding pointers in C is not a skill, it’s an aptitude. Pointers require a complex form of doubly-indirected thinking that some people just can’t do, and it’s pretty crucial to good programming. A lot of the “script jocks” who started programming by copying JavaScript snippets into their web pages and went on to learn Perl never learned about pointers, and they can never quite produce code of the quality you need.
That’s the source of all these famous interview questions you hear about, like “reversing a linked list” or “detect loops in a tree structure.” Even though the format of the interview is, superficially, just a candidate writing some code on the whiteboard, my real goal here is to have a conversation about it. “Why did you do it that way?” “What are the performance characteristics of your algorithm?” “What did you forget?” “Where’s your bug?”
That means I don’t really mind giving programming problems that are too hard, as long as the candidate has some chance of starting out, and then I’m happy to dole out little hints along the way, little toeholds, so to speak. I might ask someone, say, to project a triangle onto a plane, a typical graphics problem, and I don’t mind helping them with the trig (SOH-CAH-TOA, baby!), and when I ask them how to speed it up, I might drop little hints about look-up tables. Notice that the kinds of hints I’m happy to provide are really just answers to trivia questions—the kinds of things that you find on Google.
Inevitably, you will see a bug in their function. So we come to question five from my interview plan: “Are you satisfied with that code?” You may want to ask, “OK, so where’s the bug?” The quintessential Open Ended Question From Hell. All programmers make mistakes, there’s nothing wrong with that, they just have to be able to find them. With string functions in C, most college kids forget to null-terminate the new string. With almost any function, they are likely to have off-by-one errors. They will forget semicolons sometimes. Their function won’t work correctly on 0 length strings, or it will GPF if malloc fails… Very, very rarely, you will find a candidate that doesn’t have any bugs the first time. In this case, this question is even more fun. When you say, “There’s a bug in that code,” they will review their code carefully, and then you get to see if they can be diplomatic yet firm in asserting that the code is perfect.
XML is a Dumb Format For Storing Data
originally wrote by Joel Spolsky
I'm not sure why XML got so sexy. It has its advantages; it's sure a good idea for data interchange or for all those little files you need to store settings. But for real work it just can't do what a solid, multiuser, relational database can do. The next time some uninformed analyst at Gartner or Giga or Forrester tells you "in the future, everything will be XML," ask them how to do "SELECT author FROM books" fast with XML. Hint: you can't. It has to be slow. XML is not the way to store a lot of data. Now tell me how to insert a new book at the beginning of the table without massive bitblts. Of course, I doubt if there is an analyst in one of those companies who would even understand that sentence, but that's life. Now lets look at the books table in XML.
<?xml blah blah>
<books>
<book>
<title>UI Design for Programmers</title>
<author>Joel Spolsky</author>
</book>
<book>
<title>The Chop Suey Club</title>
<author>Bruce Weber</author>
</book>
</books>
Quick question. What is the code to move to the next record?
Uh...
At this point a good programmer would say, well, let's parse the XML into a tree in memory so that we can operate on it reasonably quickly. The amount of work that has to be done here by the CPU to SELECT author FROM books will bore you absolutely to tears. As every compiler writer knows, lexing and parsing are the slowest part of compiling. Suffice it to say that it involves a lot of string stuff, which we discovered is slow, and a lot of memory allocation stuff, which we discovered is slow, as we lex, parse, and build an abstract syntax tree in memory. That assumes that you have enough memory to load the whole thing at once. With relational databases, the performance of moving from record to record is fixed and is, in fact, one CPU instruction. That's very much by design. And thanks to memory mapped files you only have to load the pages of disk that you are actually going to use. With XML, if you preparse, the performance of moving from record to record is fixed but there's a huge startup time, and if you don't preparse, the performance of moving from record to record varies based on the length of the record before it and is still hundreds of CPU instructions long.
What this means to me is that you can't use XML if you need performance and have lots of data. If you have a little bit of data, or if what you're doing doesn't have to be fast, XML is a fine format. And if you really want the best of both worlds, you have to come up with a way to store metadata next to your XML, something like Pascal strings' byte count, which give you hints about where things are in the file so that you don't have to parse and scan for them. But of course then you can't use text editors to edit the file because that messes up the metadata, so it's not really XML anymore.
------
By the way, when I published this digest from Joel, I have no idea how to put the HTML code in my blog contents. Here is the solution, and the full table of escape characters are here.
I'm not sure why XML got so sexy. It has its advantages; it's sure a good idea for data interchange or for all those little files you need to store settings. But for real work it just can't do what a solid, multiuser, relational database can do. The next time some uninformed analyst at Gartner or Giga or Forrester tells you "in the future, everything will be XML," ask them how to do "SELECT author FROM books" fast with XML. Hint: you can't. It has to be slow. XML is not the way to store a lot of data. Now tell me how to insert a new book at the beginning of the table without massive bitblts. Of course, I doubt if there is an analyst in one of those companies who would even understand that sentence, but that's life. Now lets look at the books table in XML.
<?xml blah blah>
<books>
<book>
<title>UI Design for Programmers</title>
<author>Joel Spolsky</author>
</book>
<book>
<title>The Chop Suey Club</title>
<author>Bruce Weber</author>
</book>
</books>
Quick question. What is the code to move to the next record?
Uh...
At this point a good programmer would say, well, let's parse the XML into a tree in memory so that we can operate on it reasonably quickly. The amount of work that has to be done here by the CPU to SELECT author FROM books will bore you absolutely to tears. As every compiler writer knows, lexing and parsing are the slowest part of compiling. Suffice it to say that it involves a lot of string stuff, which we discovered is slow, and a lot of memory allocation stuff, which we discovered is slow, as we lex, parse, and build an abstract syntax tree in memory. That assumes that you have enough memory to load the whole thing at once. With relational databases, the performance of moving from record to record is fixed and is, in fact, one CPU instruction. That's very much by design. And thanks to memory mapped files you only have to load the pages of disk that you are actually going to use. With XML, if you preparse, the performance of moving from record to record is fixed but there's a huge startup time, and if you don't preparse, the performance of moving from record to record varies based on the length of the record before it and is still hundreds of CPU instructions long.
What this means to me is that you can't use XML if you need performance and have lots of data. If you have a little bit of data, or if what you're doing doesn't have to be fast, XML is a fine format. And if you really want the best of both worlds, you have to come up with a way to store metadata next to your XML, something like Pascal strings' byte count, which give you hints about where things are in the file so that you don't have to parse and scan for them. But of course then you can't use text editors to edit the file because that messes up the metadata, so it's not really XML anymore.
------
By the way, when I published this digest from Joel, I have no idea how to put the HTML code in my blog contents. Here is the solution, and the full table of escape characters are here.
March 2, 2011
some advices about low-level programming
see also <Back to Basic>
reference <Advice for Computer Science College Students>
Learn how to write
The difference between a tolerable programmer and a great programmer is not how many programming languages they know, and it's not whether they prefer Python or Java. It's whether they can communicate their ideas. By persuading other people, they get leverage. By writing clear comments and technical specs, they let other programmers understand their code, which means other programmers can use and work with their code instead of rewriting it. Absent this, their code is worthless. By writing clear technical documentation for end users, they allow people to figure out what their code is supposed to do, which is the only way those users can see the value in their code. There's a lot of wonderful, useful code buried on sourceforge somewhere that nobody uses because it was created by programmers who don't write very well (or don't write at all), and so nobody knows what they've done and their brilliant code languishes.
If you can write, wherever you get hired, you'll soon find that you're getting asked to write the specifications and that means you're already leveraging your influence and getting noticed by management. Start a journal or weblog. The more you write, the easier it will be, and the easier it is to write, the more you'll write, in a virtuous circle.
Learn C
C. Notice I didn't say C++. Although C is becoming increasingly rare, it is still the lingua franca of working programmers. It is the language they use to communicate with one another, and, more importantly, it is much closer to the machine than "modern" languages that you'll be taught in college like ML, Java, Python, whatever trendy junk they teach these days. You need to spend at least a semester getting close to the machine or you'll never be able to create efficient code in higher level languages. You'll never be able to work on compilers and operating systems, which are some of the best programming jobs around. You'll never be trusted to create architectures for large scale projects. I don't care how much you know about continuations and closures and exception handling: if you can't explain why "while (*s++ = *t++);" copies a string, or if that isn't the most natural thing in the world to you, well, you're programming based on superstition, as far as I'm concerned: a medical doctor who doesn't know basic anatomy, passing out prescriptions based on what the pharma sales babe said would work.
some special cases to indicate this point
char bigString[1000]; /* I never know how much to allocate... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");
The time consumption will increase as the n^2, where n indicates the number of characters that have already in the char array, for the reason that every time the strcat will begin to search at the beginning of the array. To reduce the runtime decrease as linear as input number of values:
char* mystrcat( char* dest, char* src )
{
while (*dest) dest++;
while (*dest++ = *src++);
return --dest;
}
char bigString[1000]; /* I never know how much to allocate... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");
The designers of Pascal were aware of this problem and "fixed" it by storing a byte count in the first byte of the string. These are called Pascal Strings. They can contain zeros and are not null terminated. Because a byte can only store numbers between 0 and 255, Pascal strings are limited to 255 bytes in length, but because they are not null terminated they occupy the same amount of memory as ASCIZ strings. The great thing about Pascal strings is that you never have to have a loop just to figure out the length of your string. Finding the length of a string in Pascal is one assembly instruction instead of a whole loop. It is monumentally faster.
The old Macintosh operating system used Pascal strings everywhere. Many C programmers on other platforms used Pascal strings for speed. Excel uses Pascal strings internally which is why strings in many places in Excel are limited to 255 bytes, and it's also one reason Excel is blazingly fast.
For a long time, if you wanted to put a Pascal string literal in your C code, you had to write:
char* str = "\006Hello!";
Yep, you had to count the bytes by hand, yourself, and hardcode it into the first byte of your string. Lazy programmers would do this, and have slow programs:
char* str = "*Hello!";
str[0] = strlen(str) - 1;
Notice in this case you've got a string that is null terminated (the compiler did that) as well as a Pascal string. I used to call these fucked strings because it's easier than calling them null terminated pascal strings but this is a rated-G channel so you will have use the longer name.
Well, since we're looking at the bits today I shouldn't have ignored this. I should have done this correctly: figured out how many bytes I needed and allocated the right amount of memory. Shouldn't I have?
Because otherwise, you see, a clever hacker will read my code and notice that I'm only allocating 1000 bytes and hoping it will be enough, and they'll find some clever way to trick me into strcatting a 1100 byte string into my 1000 bytes of memory, thus overwriting the stack frame and changing the return address so that when this function returns, it executes some code which the hacker himself wrote. This is what they're talking about when they say that a particular program has a buffer overflow susceptibility. It was the number one cause of hacks and worms in the olden days before Microsoft Outlook made hacking easy enough for teenagers to do.
(bold malloc...)How does the malloc work? The nature of malloc is that it has a long linked list of available blocks of memory called the free chain. When you call malloc, it walks the linked list looking for a block of memory that is big enough for your request. Then it cuts that block into two blocks -- one the size you asked for, the other with the extra bytes, and gives you the block you asked for, and puts the leftover block (if any) back into the linked list. When you call free, it adds the block you freed onto the free chain. Eventually, the free chain gets chopped up into little pieces and you ask for a big piece and there are no big pieces available the size you want. So malloc calls a timeout and starts rummaging around the free chain, sorting things out, and merging adjacent small free blocks into larger blocks. This takes 3 1/2 days. The end result of all this mess is that the performance characteristic of malloc is that it's never very fast (it always walks the free chain), and sometimes, unpredictably, it's shockingly slow while it cleans up. (This is, incidentally, the same performance characteristic of garbage collected systems, surprise surprise, so all the claims people make about how garbage collection imposes a performance penalty are not entirely true, since typical malloc implementations had the same kind of performance penalty, albeit milder.)
Smart programmers minimize the potential distruption of malloc by always allocating blocks of memory that are powers of 2 in size. You know, 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. For reasons that should be intuitive to anyone who plays with Lego, this minimizes the amount of weird fragmentation that goes on in the free chain. Although it may seem like this wastes space, it is also easy to see how it never wastes more than 50% of the space. So your program uses no more than twice as much memory as it needs to, which is not that big a deal. Furthermore, when you call realloc, you should always double the size of memory that was previously allocated. That means that you never have to call realloc more than lg n times, which has decent performance characteristics even for huge strings, and you never waste more than 50% of your memory.
reference <Advice for Computer Science College Students>
Learn how to write
The difference between a tolerable programmer and a great programmer is not how many programming languages they know, and it's not whether they prefer Python or Java. It's whether they can communicate their ideas. By persuading other people, they get leverage. By writing clear comments and technical specs, they let other programmers understand their code, which means other programmers can use and work with their code instead of rewriting it. Absent this, their code is worthless. By writing clear technical documentation for end users, they allow people to figure out what their code is supposed to do, which is the only way those users can see the value in their code. There's a lot of wonderful, useful code buried on sourceforge somewhere that nobody uses because it was created by programmers who don't write very well (or don't write at all), and so nobody knows what they've done and their brilliant code languishes.
If you can write, wherever you get hired, you'll soon find that you're getting asked to write the specifications and that means you're already leveraging your influence and getting noticed by management. Start a journal or weblog. The more you write, the easier it will be, and the easier it is to write, the more you'll write, in a virtuous circle.
Learn C
C. Notice I didn't say C++. Although C is becoming increasingly rare, it is still the lingua franca of working programmers. It is the language they use to communicate with one another, and, more importantly, it is much closer to the machine than "modern" languages that you'll be taught in college like ML, Java, Python, whatever trendy junk they teach these days. You need to spend at least a semester getting close to the machine or you'll never be able to create efficient code in higher level languages. You'll never be able to work on compilers and operating systems, which are some of the best programming jobs around. You'll never be trusted to create architectures for large scale projects. I don't care how much you know about continuations and closures and exception handling: if you can't explain why "while (*s++ = *t++);" copies a string, or if that isn't the most natural thing in the world to you, well, you're programming based on superstition, as far as I'm concerned: a medical doctor who doesn't know basic anatomy, passing out prescriptions based on what the pharma sales babe said would work.
some special cases to indicate this point
char bigString[1000]; /* I never know how much to allocate... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");
The time consumption will increase as the n^2, where n indicates the number of characters that have already in the char array, for the reason that every time the strcat will begin to search at the beginning of the array. To reduce the runtime decrease as linear as input number of values:
char* mystrcat( char* dest, char* src )
{
while (*dest) dest++;
while (*dest++ = *src++);
return --dest;
}
char bigString[1000]; /* I never know how much to allocate... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");
The designers of Pascal were aware of this problem and "fixed" it by storing a byte count in the first byte of the string. These are called Pascal Strings. They can contain zeros and are not null terminated. Because a byte can only store numbers between 0 and 255, Pascal strings are limited to 255 bytes in length, but because they are not null terminated they occupy the same amount of memory as ASCIZ strings. The great thing about Pascal strings is that you never have to have a loop just to figure out the length of your string. Finding the length of a string in Pascal is one assembly instruction instead of a whole loop. It is monumentally faster.
The old Macintosh operating system used Pascal strings everywhere. Many C programmers on other platforms used Pascal strings for speed. Excel uses Pascal strings internally which is why strings in many places in Excel are limited to 255 bytes, and it's also one reason Excel is blazingly fast.
For a long time, if you wanted to put a Pascal string literal in your C code, you had to write:
char* str = "\006Hello!";
Yep, you had to count the bytes by hand, yourself, and hardcode it into the first byte of your string. Lazy programmers would do this, and have slow programs:
char* str = "*Hello!";
str[0] = strlen(str) - 1;
Notice in this case you've got a string that is null terminated (the compiler did that) as well as a Pascal string. I used to call these fucked strings because it's easier than calling them null terminated pascal strings but this is a rated-G channel so you will have use the longer name.
Well, since we're looking at the bits today I shouldn't have ignored this. I should have done this correctly: figured out how many bytes I needed and allocated the right amount of memory. Shouldn't I have?
Because otherwise, you see, a clever hacker will read my code and notice that I'm only allocating 1000 bytes and hoping it will be enough, and they'll find some clever way to trick me into strcatting a 1100 byte string into my 1000 bytes of memory, thus overwriting the stack frame and changing the return address so that when this function returns, it executes some code which the hacker himself wrote. This is what they're talking about when they say that a particular program has a buffer overflow susceptibility. It was the number one cause of hacks and worms in the olden days before Microsoft Outlook made hacking easy enough for teenagers to do.
(bold malloc...)How does the malloc work? The nature of malloc is that it has a long linked list of available blocks of memory called the free chain. When you call malloc, it walks the linked list looking for a block of memory that is big enough for your request. Then it cuts that block into two blocks -- one the size you asked for, the other with the extra bytes, and gives you the block you asked for, and puts the leftover block (if any) back into the linked list. When you call free, it adds the block you freed onto the free chain. Eventually, the free chain gets chopped up into little pieces and you ask for a big piece and there are no big pieces available the size you want. So malloc calls a timeout and starts rummaging around the free chain, sorting things out, and merging adjacent small free blocks into larger blocks. This takes 3 1/2 days. The end result of all this mess is that the performance characteristic of malloc is that it's never very fast (it always walks the free chain), and sometimes, unpredictably, it's shockingly slow while it cleans up. (This is, incidentally, the same performance characteristic of garbage collected systems, surprise surprise, so all the claims people make about how garbage collection imposes a performance penalty are not entirely true, since typical malloc implementations had the same kind of performance penalty, albeit milder.)
Smart programmers minimize the potential distruption of malloc by always allocating blocks of memory that are powers of 2 in size. You know, 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. For reasons that should be intuitive to anyone who plays with Lego, this minimizes the amount of weird fragmentation that goes on in the free chain. Although it may seem like this wastes space, it is also easy to see how it never wastes more than 50% of the space. So your program uses no more than twice as much memory as it needs to, which is not that big a deal. Furthermore, when you call realloc, you should always double the size of memory that was previously allocated. That means that you never have to call realloc more than lg n times, which has decent performance characteristics even for huge strings, and you never waste more than 50% of your memory.
March 1, 2011
tree search algorithm (cont.)
The previous post is here
============
struct treeNode{
int element;
struct treeNode *left;
struct treeNode *right;
}:
typedef struct treeNode *searchTree;
searchTree makeEmpty(searchTree T){
if(T!=NULL){
MakeEmpty(T->left);
MakeEmpty(T->right);
free(T);
}
return NULL;
}
searchTree findVal(int val, searchTree T){
if(T==NULL)
return NULL;
if(valelement)
return findVal(val, T->left);
else if(val>T->element)
return findVal(val, T->right);
else
return T;
}
searchTree findMin(searchTree T){
if(T!=NULL)
while(T->left!=NULL)
T = T->left;
return T;
}
searchTree insertVal(int val, searchTree T){
if(T==NULL){
T=(searchTree)malloc(sizeof(struct treeNode));
if(T==NULL){
printf("Error! There is no new memory to allocate.\n");
exit(0);
}
T->element = val;
T->left = T->right = NULL;
}
else{
if(valelement)
T->left = insertVal(val, T->left);
else if(val>T->element)
T->right = insertVal(val, T->right);
else
printf("The element has already in this tree.\n");
}
return T;
}
searchTree deleteVal( int val, searchTree T){
searchTree temp;
if(T==NULL){
printf("The element is not found.\n");
return NULL;
}
else if(valelement)
T->left = deleteVal(val, T->left);
else if(val>T->element)
T->right = deleteVal(val, T->right);
else{ // here, find the specific element
if(T->left && T->right){
temp = findMin(T->right);
T->element = tmp->element;
T->right = deleteVal(tmp->element, T->right);
}
else{
temp = T;
if(T->left == NULL)
T = T->right;
else if(T->right==NULL)
T = T->left;
free(temp);
}
return T;
}
}
// the functions below returns node which element is closest
// and larger in the Tree. We could call it "next"
// assumption1: the inputs are inquiry val and the root node
searchTree nextLarger(int val, searchTree T){
searchTree temp;
if(T==NULL){
printf("There is no tree.\n");
return NULL;
}
if(valelement){
if(T->left!=NULL){
temp = T->left;
while(valelement && temp->left!=NULL){
T = temp;
temp = temp->left;
}
// This case indicate "temp->left==NULL" causes stop
// so temp should be the return value
if(valelement)
T = temp;
// otherwise, result might in a new right tree
// . or the parent node in this layer
else{
if (temp->right!=NULL){
temp = nextLarger(val, temp->right);
if (temp!=NULL)
T = temp;
}
}
}
return T;
}
else{
while(val>=T->element && T->right!=NULL)
T = T->right;
if(valelement){
T = nextLarger(val, T);
return T;
}
else
return NULL;
}
}
// assumption2: the input value is a given node in the tree.
// In this case, we might have to trace back.
// As a resutl, the original struct needs a little modification
struct treeNode{
int element;
struct treeNode *left;
struct treeNode *right;
struct treeNode *parenet; // to trace back
}:
typedef struct treeNode *searchTree;
searchTree nextLarger2(searchTree start){
searchTree temp, record;
if(start==NULL){
printf("There is not a valid input.\n");
return NULL;
}
if(start->right!=NULL){
start = findMin(start->right);
return start;
}
else if(start->parent!=NULL){
if(start == start->parent->left)
return start;
else{
while(start->parent!=NULL && start!=start->parent->left)
start = start->parent;
if(start==start->parent->left)
return start;
else
return NULL;
}
}
}
// references: <Introduction to algorithms>, <Coding Interviews>
// I just did some terrible interviews these days. Yes, some, and terrible.
// So, I wanna record everything here,
// no matter how stupid and rudimentary it is.
// Also as a means to push myself, everyday a step further.
============
struct treeNode{
int element;
struct treeNode *left;
struct treeNode *right;
}:
typedef struct treeNode *searchTree;
searchTree makeEmpty(searchTree T){
if(T!=NULL){
MakeEmpty(T->left);
MakeEmpty(T->right);
free(T);
}
return NULL;
}
searchTree findVal(int val, searchTree T){
if(T==NULL)
return NULL;
if(val
return findVal(val, T->left);
else if(val>T->element)
return findVal(val, T->right);
else
return T;
}
searchTree findMin(searchTree T){
if(T!=NULL)
while(T->left!=NULL)
T = T->left;
return T;
}
searchTree insertVal(int val, searchTree T){
if(T==NULL){
T=(searchTree)malloc(sizeof(struct treeNode));
if(T==NULL){
printf("Error! There is no new memory to allocate.\n");
exit(0);
}
T->element = val;
T->left = T->right = NULL;
}
else{
if(val
T->left = insertVal(val, T->left);
else if(val>T->element)
T->right = insertVal(val, T->right);
else
printf("The element has already in this tree.\n");
}
return T;
}
searchTree deleteVal( int val, searchTree T){
searchTree temp;
if(T==NULL){
printf("The element is not found.\n");
return NULL;
}
else if(val
T->left = deleteVal(val, T->left);
else if(val>T->element)
T->right = deleteVal(val, T->right);
else{ // here, find the specific element
if(T->left && T->right){
temp = findMin(T->right);
T->element = tmp->element;
T->right = deleteVal(tmp->element, T->right);
}
else{
temp = T;
if(T->left == NULL)
T = T->right;
else if(T->right==NULL)
T = T->left;
free(temp);
}
return T;
}
}
// the functions below returns node which element is closest
// and larger in the Tree. We could call it "next"
// assumption1: the inputs are inquiry val and the root node
searchTree nextLarger(int val, searchTree T){
searchTree temp;
if(T==NULL){
printf("There is no tree.\n");
return NULL;
}
if(val
if(T->left!=NULL){
temp = T->left;
while(val
T = temp;
temp = temp->left;
}
// This case indicate "temp->left==NULL" causes stop
// so temp should be the return value
if(val
T = temp;
// otherwise, result might in a new right tree
// . or the parent node in this layer
else{
if (temp->right!=NULL){
temp = nextLarger(val, temp->right);
if (temp!=NULL)
T = temp;
}
}
}
return T;
}
else{
while(val>=T->element && T->right!=NULL)
T = T->right;
if(val
T = nextLarger(val, T);
return T;
}
else
return NULL;
}
}
// assumption2: the input value is a given node in the tree.
// In this case, we might have to trace back.
// As a resutl, the original struct needs a little modification
struct treeNode{
int element;
struct treeNode *left;
struct treeNode *right;
struct treeNode *parenet; // to trace back
}:
typedef struct treeNode *searchTree;
searchTree nextLarger2(searchTree start){
searchTree temp, record;
if(start==NULL){
printf("There is not a valid input.\n");
return NULL;
}
if(start->right!=NULL){
start = findMin(start->right);
return start;
}
else if(start->parent!=NULL){
if(start == start->parent->left)
return start;
else{
while(start->parent!=NULL && start!=start->parent->left)
start = start->parent;
if(start==start->parent->left)
return start;
else
return NULL;
}
}
}
// So, I wanna record everything here,
// Also as a means to push myself, everyday a step further.
Subscribe to:
Posts (Atom)
Days of our lives
