Deleting a middle node from a single linked list when pointer to the previous node is not available

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/delete-non-tail-node-in-linked-list-given-only-access-to-that-node/. Problem Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e Solution If we are allowed to make some assumption,...

Read More

Array implementation of stack

Here will discuss the array implementation of stack. Problems with array implementation Underflow - Array may be empty but people may try to pop the element Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html Null items - Can nulls be added - Yes in this case, nulls can be added in stack Loitering (java specific) - Holding a reference to an object wen it is no longer needed. To over come this...

Read More

5 Pirates Problem

Problem : Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose?...

Read More

100 Programmers Problem

Problem : 100 programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front...

Read More

Sum it Up

Problem:  you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)? what if there are two repeating numbers (and the same memory constraint?) Solution: as a programmer, my first answer to this problem...

Read More

Palindromes

Problem:  This year on October 2, 2001, the date in MM/DD/YYYY format will be a palindrome (same forwards as backwards). 10/02/2001 when was the last date that this occurred on? (see if you can do it in your head!) Solution: we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can’t be any year in 1900 because that would result in a day of 91. same for 1800 down to 1400. it could be a year in...

Read More

Daughters’ Ages

Problem : Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years. the first grad says to the second: “how have you been?” second: “great! i got married and i have three daughters now” first: “really? how old are they?” second: “well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..” first: “right, ok.. oh wait.. hmm,...

Read More

int atoi( char* pStr )

Problem:  Write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the...

Read More

Bumblebee

Problem:  two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle...

Read More

100 Doors in a Row - Solution

Problem:  you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door. What state are...

Read More

Reverse a String

Problem: A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is “the house is blue”, the return value would be “blue is...

Read More

The Circular Lake Monster Problem

Problem: For #1, how about row in a circle a bit smaller 1/4r in size. Since he won't be able to keep up with you, when he is on the opposite shore you can make a brake for it. You have r*3/4 to travel, but 4*3/4 is less then pi, so he won't be able to catch you in time Solution: Assume x is the monster's speed. Then to get the circle trick to work, you row a circle a little less than 1/x of the radius, leaving you 1 - 1/x to row when he is...

Read More

Some terms and their synonyms in programming languages

Scope/Visibility Nested/Inner Class Instance/Member  Class/Static Local/Automatic variable...

Read More

Arrays tip : Ignoring the zeroth row

This trick can be used in any language but is shown in java right now. Sometimes you want to use natural input values as an index, the real values that that data has instead of starting with zero. Let's take the case of data that starts with the value 1, like the day of the month. The standard approach is to subtract one from every day value that's used as an index. This is annoying and error prone. Another way to do handle this case is...

Read More

Enums in java

In prior releases, the standard way to represent an enumerated type was the int Enum pattern: // int Enum Pattern - has severe problems! public static final int SEASON_WINTER = 0; public static final int SEASON_SPRING = 1; public static final int SEASON_SUMMER = 2; public static final int SEASON_FALL = 3; But these are not type safe, and clearly naming them is bit of a problem. So in Java 5, they introduced Enums. Eg. enum Season { WINTER, SPRING, SUMMER, FALL } public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE,...

Read More

Modifying Java Variables (w.r.t c and c++)

Modifying Simple Variable The only mechanism for changing the value of a simple Java variable is an assignment statement. Java assignment syntax is identical to C assignment syntax. As in C, an assignment replaces the value of a variable named on the left- hand side of the equals sign by the value of the expression on the right- hand side of the equals sign. Modifying Object Variable  Java object variables can be changed in two ways. Like simple variables, you can make assignments to object variables. When this is done the object referenced...

Read More

Constructor in java 1

ConstructorsWhen you create a new instance (a new object) of a class using the new keyword, a constructor for that class is called. Constructors are used to initialize the instance variables (fields) of an object. Constructors are similar to methods, but with some important differences. Constructor name is class name. A constructors must have the same name as the class its in. Default constructor. If you don't define a constructor for a class, a default parameterless constructor is automatically created by the compiler. The default constructor...

Read More

Common naming convention : Coding Style

Variable names must be in mixed case starting with lower case.  Common practice in the Java development community and also the naming convention for variables used by Sun for the Java core packages. Makes variables easy to distinguish from types, and effectively resolves potential naming collision as in the declaration eg. int state; Names representing constants (final variables) must be all uppercase using underscore to separate words. MAX_ITERATIONS, COLOR_RED Common practice in the Java development community and also the naming convention...

Read More

Improving coding style into classes

Class and Interface declarations should be organized in the following manner:  1. Class/Interface documentation.  2. class or interface statement.  3. Class (static) variables in the order public, protected, package (no access modifier), private.  4. Instance variables in the order public, protected, package (no access modifier), private. 5. Constructors.  6. Methods (no specific order). Reduce complexity by making the location of each class element predictable.  Imported classes should always be listed...

Read More

Improving coding style into functions or methods

Method modifiers should be given in the following order: static abstract synchronized final native The modifier (if present) must be the first modifier. public static double square(double a); // NOT: static public double square(double a); is one of public, protected or private while includes volatile and transient. The most important lesson here is to keep the access modifier as the first modifier. Of the possible modifiers, this is by far the most important, and it must stand out in the method declaration. For the other modifiers, the...

Read More

Specific cases of naming enhancing naming style

The term find can be used in methods where something is looked up. vertex.findNearestVertex(); matrix.findSmallestElement(); node.findShortestPath(Node destinationNode);Give the reader the immediate clue that this is a simple look up method with a minimum of computations involved. Consistent use of the term enhances readability. The term initialize can be used where an object or a concept is established. printer.initializeFontSet();The American initializeshould be preferred over the English initialise. Abbreviation init must be avoided. Plural...

Read More

Java specific naming convention

JFC (Java Swing) variables should be suffixed by the element type. widthScale, nameTextField, leftScrollbar, mainPanel, fileToggle, minLabel, printerDialog Enhances readability since the name gives the user an immediate clue of the type of the variable and thereby the available resources of the object. Array specifiers must be attached to the type not the variable. int[] a = new int[20]; // NOT: int a[] = new int[20] The arrayness is a feature of the base type, not the variable. It is not known why Sun allows both forms. Java source files...

Read More