These days, I did lots of parallel programming. Although sometimes this activity does suffer from low efficiency, it do help me a lot for further preparing and studying of coding. Like other routine work, the more both of us prepared, the more efficient work we will have. Besides, there are several points worth mentioning in retrospect:
1) Format matters. Tab is a much better choice than several blanks.
2) Comments also matter. It will help others know why I wrote in this manner and what the underlying idea for some blocks of code.
3) Multiple screens are necessary: put severl UI in one screen, references in one, and debug windows in one. Cross referring among different dialogs and different screens is one way to improve efficiency.
4) As long as employ oneself in the subject, it will be more straightforward to achieve goals. After all, coding is only time-consuming in one aspect.
5) The use of short-cuts in vim definitely will improve the efficiency, and also seems like more professional:)
6) People will only accept suggestions when they know nothing about it. So, at most of the time, the better choice is just keeping quite and getting your own work done.
7) Reading more, practice more, improve faster.
Update:
Below is something I read from a programmer's blog.
At the time I was a fanatic chess player and my 'dream' was to build a chess program. Of course that was a fairly advanced thing to do, in the end my knowledge of computer programming, and my theoretical knowledge of chess, the memory of the computer, and the available time, they all limited me to writing a program that could do one of two end games (KQ vs K and KR vs K).
Looking back over all those years (I'm 45 now), I don't think there ever was a time when I wasn't programming or thinking about programming in some way or another since I gained that first little bit of insight into what makes a computer tick.
It's like a drug. I'm still fascinated by it, even almost 30 years to the day later I still read about languages, new ways to solve old problems, all kinds of developments in software and hardware, as though it is the first time that I hear about these things. It is a fascinating world, the world of software.
It has changed tremendously over that time, our 'small' computers of today are more powerful than the biggest 'big iron' that you could buy when I was a kid. Your average cell phone has more storage, computing power, and bandwidth available to it than a mainframe of 30 years ago. Programming itself has changed, from 'batch' programming to more and more interactive code, 'web' development and so on. But it has also - in essence - remained the same, small building blocks are piled on top of each other to create more complex constructs, which in turn can be used to create yet more complex constructs, and so on.
That process, the act of programming, is something that I need to do. Whether to make a living or to be fooling around with some idea, the bug is in my system and I highly doubt that it will ever leave me permanently. I can see myself taking a break, but I can't see myself ever stopping. All I'll end up doing then is to change my mode from work to play and eventually that will lead back to some form of work.
If you can't program yet, or if you think that it is 'complex', rest assured, there is nothing that can't be learned. Programming is not like playing a musical instrument, and it is not something that you have to have a genetic disposition for. The pay-off is in how much time you spend plugging away at it. Over time you'll get better, and at some point it will click. It may take a while (it took me more than a year to learn 'BASIC', which is a very simple language) and I gave up several times only to go back to it once more. Eventually, I got it, and I'm sure that everybody that can do basic arithmetic and that is able to put together a precise list of instructions on how to make coffee or a pizza can learn how to program.
Maybe you won't be the next Donald Knuth, but that's not what it takes, all you need to be is a little bit better than you were yesterday and to keep doing that for a long time.
Beware of that bug though, once it bites you, you'll be hooked for life.
Showing posts with label jobhunting. Show all posts
Showing posts with label jobhunting. Show all posts
March 8, 2011
March 7, 2011
advices about resume
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.
======
# 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 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 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.
January 8, 2011
job hunting
need to read:
thinking in Java
coding interviews
thinking in C++
CLRS and K&R, again...
in one month?.. ok, i will try.
thinking in Java
coding interviews
thinking in C++
CLRS and K&R, again...
in one month?.. ok, i will try.
October 29, 2010
backup: interview summary
谷歌笔试：
1.
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n] 中，w[i][j]
的值代表编号为i，j的队伍中更强的一支 所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。。。。。。
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，求出result
1.
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n] 中，w[i][j]
的值代表编号为i，j的队伍中更强的一支 所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。。。。。。
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，求出result
2.题目说的比较花哨，根据我的理解，本质上就是有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误
百度面试：
3.
用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平 最多可以从y个小球中找出较轻的那个，求y与x的关系式
4.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得m个记录
5.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度
网易有道笔试：
6. 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是
这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度
7.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法
discussion can be found @:
http://topic.csdn.net/u/20100930/13/9f10c56c-9545-488e-9b53-edffc9b6761d.html
==========
GOOGLE今天晚上的笔试题，刚参加回来.
第一题比较简单，检测同一个平面上的两个矩形是否重合
第二题是，给定一个随机函数，对一个数组进行随机排列，保证所有可能的排列出现的概率相等，也就是n!分之一
第三题就是约瑟夫问题的最优解法~Knuth具体数学上有，不过我忘记了，自己没推导出来，就写了个模拟
discussion can be found @:
http://topic.csdn.net/u/20101018/23/75b6dc53-610f-401e-b8ae-5aebee5cabe8.html
==========
雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
搜狐：
3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
创新工场：
4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html
==========
雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
搜狐：
3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
创新工场：
4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html
Subscribe to:
Posts (Atom)
Days of our lives
