Showing posts with label MS interview Question. Show all posts
Showing posts with label MS interview Question. Show all posts

July 01, 2011

Google Interview Questions - Check-sum, Cryptography, or Stupid

Full Question:
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

It's a kind of making you stupid. Some possible answers are here.

1. Check-sum
Since you are just "checking," you ask him to call you at a certain time. If he doesn't, he doesn't have your number. Too simple? A reader suggest: "In that case you need a check-sum. Have Bob add all the digits of your phone number together, write down the total, and pass that back to you."

2. Public key Cryptography
Here is my public key, please encrypt my phone number you have with it and send back to me.
key=num-reveres of num

e.g if my no is 9740852296
the key=2818271817 Eve can't read it as Eve doesn't have my number so she can't predict & she has to lot of computation which only possible she know my number or some its digits ..so she can't decode the my key.

(we can also extend the explanation so i write on the paper that bob i am sending you key to decode it reverse the key & then decode using logic you have so the same thing bob has to do in its side & same he write back to me..m not using this in this solution )

then bob decode it using computation he tries all the way +,-*,/, %,xor all possible way to decode if he has my correct phone number then suppose he try to subtract my key from my phone number he has so if has correct phone number then after subtracting the key from my number he will send 9740852296-2818271817=6922580476 & he also write that after decoding reverse it so i will get my original number e.g. 9740852296 so i can say bob has my correct phone number else it would have been some other value & after reversing it i wont get my exact no so i can say bob don't have my correct number..

Posted in , , ,

May 03, 2011

In Java, what is the difference between static, final, and const.

Full Question:
In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++).

const: static final. It defines a constant. Now we do not use const keyword any more.

final
Define an entity once that cannot be changed nor derived from later. More specifically: a final class cannot be subclassed, a final method cannot be overridden, and a final variable can occur at most once as a left-hand expression. All methods in a final class are implicitly final.

static
Used to declare a field, method or inner class as a class field. Classes maintain one copy of class fields regardless of how many instances exist of that class. static also is used to define a method as a class method. Class methods are bound to the class instead of to a specific instance, and can only operate on class fields. (Classes and interfaces declared as static members of another class or interface are actually top-level classes and are not inner classes.)

Posted in , , , , , , ,

What is multithreaded programming? What is a deadlock?

Full Question:
What is multithreaded programming? What is a deadlock?

Multithreading as a widespread programming and execution model allows multiple threads to exist within the context of a single process. These threads share the process' resources but are able to execute independently. The threaded programming model provides developers with a useful abstraction of concurrent execution. However, perhaps the most interesting application of the technology is when it is applied to a single process to enable parallel execution on a multiprocessor system.

This advantage of a multithreaded program allows it to operate faster on computer systems that have multiple CPUs, CPUs with multiple cores, or across a cluster of machines — because the threads of the program naturally lend themselves to truly concurrent execution. In such a case, the programmer needs to be careful to avoid race conditions, and other non-intuitive behaviors. In order for data to be correctly manipulated, threads will often need to rendezvous in time in order to process the data in the correct order. Threads may also require mutually-exclusive operations (often implemented using semaphores) in order to prevent common data from being simultaneously modified, or read while in the process of being modified. Careless use of such primitives can lead to deadlocks.

In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for the other to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions). Deadlock is a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a software lock or soft lock. Computers intended for the time-sharing and/or real-time markets are often equipped with a hardware lock (or hard lock) which guarantees exclusive access to processes, forcing serialized access. Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks.

This situation may be likened to two people who are drawing diagrams, with only one pencil and one ruler between them. If one person takes the pencil and the other takes the ruler, a deadlock occurs when the person with the pencil needs the ruler and the person with the ruler needs the pencil to finish his work with the ruler. Neither request can be satisfied, so a deadlock occurs.

The telecommunications description of deadlock is weaker than Coffman deadlock because processes can wait for messages instead of resources. A deadlock can be the result of corrupted messages or signals rather than merely waiting for resources. For example, a dataflow element that has been directed to receive input on the wrong link will never proceed even though that link is not involved in a Coffman cycle.

Posted in , , , , ,

In Java, what is the difference between final, finally, and finalize?

Full Question:
In Java, what is the difference between final, finally, and finalize?

  • final – Define an entity once that cannot be changed nor derived from later. More specifically: a final class cannot be subclassed, a final method cannot be overridden, and a final variable can occur at most once as a left-hand expression. All methods in a final class are implicitly final.
    Example.
    // final class
    public final class MyFinalClass {...}

    // final method
    public class MyClass {
       public final void myFinalMethod() {...}
    }

    //final variable
    public class Sphere {
       public static final PI = 3.141592653589793; // a constant
       public final double radius;
     
       Sphere(double r) {
          radius = r;
       }
    }

  • finally – The finally block always executes when the try block exits, except System.exit(0) call. This ensures that the finally block is executed even if an unexpected exception occurs. But finally is useful for more than just exception handling — it allows the programmer to avoid having cleanup code accidentally bypassed by a return, continue, or break. Putting cleanup code in a finally block is always a good practice, even when no exceptions are anticipated.
    Example.
    try {
       System.out.println("Entering second try block");
       try {
          throw new MyException();
       } finally {
          System.out.println("finally in 2nd try block");
       }
    } catch (MyException e) {
       System.err.println("Caught MyException in 1st try block");
    } finally {
       System.err.println("finally in 1st try block");
    }

    Result:
       Entering second try block
       finally in 2nd try block
       Caught MyException in 1st try block
       finally in 1st try block
  • finalize() – method helps in garbage collection. A method that is invoked before an object is discarded by the garbage collector, allowing it to clean up its state. Should not be used to release non-memory resources like file handles, sockets, database connections etc because Java has only a finite number of these resources and you do not know when the garbage collection is going to kick in to release these non-memory resources through the finalize() method.
    Example.
    protected void finalize() throws Throwable {
       try {
          close();
       } catch(Exception e) {

       } finally {
          super.finalize();
       }
    }

Posted in , , , , , , ,

Explain how congestion control works in the TCP protocol.

Full Question:
Explain how congestion control works in the TCP protocol.

TCP (Transmission Control Panel) uses a number of mechanisms to achieve high performance and avoid 'congestion collapse', where network performance can fall by several orders of magnitude. These mechanisms control the rate of data entering the network, keeping the data flow below a rate that would trigger collapse. Acknowledgments for data sent, or lack of acknowledgments, are used by senders to infer network conditions between the TCP sender and receiver. Coupled with timers, TCP senders and receivers can alter the behavior of the flow of data. This is more generally referred to as congestion control and/or network congestion avoidance.

Modern implementations of TCP contain four intertwined algorithms:


  • Slow-start. A requirement for TCP software implementations is a mechanism used by the sender to control the transmission rate, otherwise known as sender-based flow control. This is accomplished through the return rate of acknowledgments from the receiver.
    Please see slow start sequence diagram
  • Congestion avoidance. There may be a point during Slow Start that the network is forced to drop one or more packets due to overload or congestion. If this happens, Congestion Avoidance is used to slow the transmission rate. However, Slow Start is used in conjunction with Congestion Avoidance as the means to get the data transfer going again so it doesn't slow down and stay slow. In the Congestion Avoidance algorithm a retransmission timer expiring or the reception of duplicate ACKs can implicitly signal the sender that a network congestion situation is occurring.
    Please see congestion avoidance simulation
  • Fast retransmit. When three or more duplicate ACKs are received, the sender does not even wait for a retransmission timer to expire before retransmitting the segment (as indicated by the position of the duplicate ACK in the byte stream). This process is called the Fast Retransmit algorithm.
  • Fast recovery. Since the Fast Retransmit algorithm is used when duplicate ACKs are being received, the TCP sender has implicit knowledge that there is data still flowing to the receiver. Rather than start at a window of one segment as in Slow Start mode, the sender resumes transmission with a larger window, incrementing as if in Congestion Avoidance mode. This allows for higher throughput under the condition of only moderate congestion.

Posted in , , , ,

You are given a the source to a application which is crashing when run.

Full Question:
You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

In most case, it should come from incorrect use of memory. If the codes is never changed while using debugger, time of random numbers are problematic. For example, for index of array, it might be using time, or perhaps random numbers. Or it does nasty things with memory. So 'out of bounds of array' might be shown.

Other possible answers can exist. For example,

There might be multiple recursions in the code which are causing a stack overflow, cause "Out Of Memory".

A probable cause would be an uninitialized pointer/variable being used. Or it is possible that pointer variables have wrong value.

Posted in , , , ,

Write a Regular Expression Which Matches an Email Address

Full Question:
Write a regular expression which matches an email address.

In computing, a regular expression, also referred to as regex or regexp, provides a concise and flexible means for matching strings of text, such as particular characters, words, or patterns of characters. A regular expression is written in a formal language that can be interpreted by a regular expression processor, a program that either serves as a parser generator or examines text and identifies parts that match the provided specification.

Following Table shows basic meta-character for regular expression.

MetacharacterDescription
.Matches any single character (many applications exclude newlines, and exactly which characters are considered newlines is flavor, character encoding, and platform specific, but it is safe to assume that the line feed character is included). Within POSIX bracket expressions, the dot character matches a literal dot. For example,a.c matches "abc", etc., but [a.c] matches only "a", ".", or "c".
[ ]A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z].
The - character is treated as a literal character if it is the last or the first (after the ^) character within the brackets: [abc-], [-abc]. Note that backslash escapes are not allowed. The ] character can be included in a bracket expression if it is the first (after the ^) character: []abc].
[^ ]Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". As above, literal characters and ranges can be mixed.
^Matches the starting position within the string. In line-based tools, it matches the starting position of any line.
$Matches the ending position of the string or the position just before a string-ending newline. In line-based tools, it matches the ending position of any line.
BRE: \( \)
ERE: ( )		Defines a marked subexpression. The string matched within the parentheses can be recalled later (see the next entry, \n). A marked subexpression is also called a block or capturing group.
\nMatches what the nth marked subexpression matched, where n is a digit from 1 to 9. This construct is theoretically irregular and was not adopted in the POSIX ERE syntax. Some tools allow referencing more than nine capturing groups.
*Matches the preceding element zero or more times. For example, ab*c matches "ac", "abc", "abbbc", etc. [xyz]* matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. \(ab\)* matches "", "ab", "abab", "ababab", and so on.
BRE: \{m,n\}
ERE: {m,n}		Matches the preceding element at least m and not more than n times. For example, a\{3,5\} matches only "aaa", "aaaa", and "aaaaa". This is not found in a few older instances of regular expressions.

Additionally, next three metacharacters are used to simplify regular expression.

MetacharacterDescription
?Matches the preceding element zero or one time. For example, ba? matches "b" or "ba".
+Matches the preceding element one or more times. For example, ba+ matches "ba", "baa", "baaa", and so on.
|The choice (aka alternation or set union) operator matches either the expression before or the expression after the operator. For example, abc|def matches "abc" or "def".

So, if username of Email address is allowed to use alphabets, digits, and some symbols, then a possible regular expressions is:
[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}
Assuming that [word] means combination of alphabets and allowed symbols, then
\word+@\word+\.[\word]{2,4}

If interviewer ask a particular format of Email address, you can modify/change this. For example, only digit is allowed for username and it should be ended com or net, then
\digit+@\word+.(com|net)

Posted in , , , , ,

Subscribe to: Posts (Atom)

Recent Posts

Archives