Program Square: Software Engineer Interview Question

Showing posts with label Software Engineer 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..

May 16, 2011

What is the C-language command for opening a connection with a foreign host over the internet?

Full Question:

What is the C-language command for opening a connection with a foreign host over the internet?

Intuitively, there's no such direct command built into the programming language. Sockets need to be used but they are platform dependent.

Actually, there's no single C command or function to open a connection to a foreign host.

To do this, first, you need a socket that is provided by the socket() function. Then, you need to call connect() to establish the connection with the host. However, that requires that all host names have been resolved, so you may have had to call gethostbyname() or similar, to turn a hostname into an IP address.

Simple Example codes here. It is a TCP client implementation.

#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <netdb.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>

int main(){
        int sock, bytes_recieved;  
        char send_data[1024],recv_data[1024];
        struct hostent *host;
        struct sockaddr_in server_addr;  

        host = gethostbyname("127.0.0.1");

        if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
            printf("Socket Error");
            exit(1);
        }

        server_addr.sin_family = AF_INET;     
        server_addr.sin_port = htons(5000);   
        server_addr.sin_addr = *((struct in_addr *)host->h_addr);
        bzero(&(server_addr.sin_zero),8); 

        if (connect(sock, (struct sockaddr *)&server_addr,
                    sizeof(struct sockaddr)) == -1) {
            perror("Connect");
            exit(1);
        }

        while(1) {
          bytes_recieved=recv(sock,recv_data,1024,0);
          recv_data[bytes_recieved] = '\0';
 
          if (strcmp(recv_data , "q") == 0 || strcmp(recv_data , "Q") == 0){
             close(sock);
             break;
          }
          else
             printf("\nRecieved data = %s " , recv_data);
           
          printf("\nSEND (q or Q to quit) : ");
          gets(send_data);
           
          if (strcmp(send_data , "q") != 0 && strcmp(send_data , "Q") != 0)
           send(sock,send_data,strlen(send_data), 0); 
          else {
           send(sock,send_data,strlen(send_data), 0);   
           close(sock);
           break;
          }
        }   
        return 0;
}

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.)

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.

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();
}
}

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.

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.

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.

Metacharacter	Description
`.`	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.
`\n`	Matches 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, `abc` 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.

Metacharacter	Description
`?`	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)

How are cookies passed in the HTTP protocol?

Full Question:

How are cookies passed in the HTTP protocol?

A cookie, also known as a web cookie, browser cookie, and HTTP cookie, is a piece of text stored on a user's computer by their web browser. A cookie can be used for authentication, storing site preferences, shopping cart contents, the identifier for a server-based session, or anything else that can be accomplished through storing text data.

A cookie consists of one or more name-value pairs containing bits of information, which may be encrypted for information privacy and data security purposes. The cookie is sent as a field in the header of the HTTP response by a web server to a web browser and then sent back unchanged by the browser each time it accesses that server.

Cookies may be set by the server with or without an expiration date. Cookies without an expiration date exist until the browser terminates, while cookies with an expiration date may be stored by the browser until the expiration date passes. Users may also manually delete cookies in order to save space or to address privacy issues.

As text, cookies are not executable. Because they are not executed, they cannot replicate themselves and are not viruses. However, due to the browser mechanism to set and read cookies, they can be used as spyware (see zombie cookie and evercookie for more details). Anti-spyware products may warn users about some cookies because cookies can be used to track computer activity—a privacy concern, later causing possible malware.

Most modern browsers allow users to decide whether to accept cookies, and the time frame to keep them, but rejecting cookies makes some websites unusable.

May 02, 2011

Describe the Algorithm for a Breath-First Graph Traversal.

Full Question:

Describe the Algorithm for a Breath-First Graph Traversal.

Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.

Breadth-First Search (BFS)
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

BFS is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic algorithm. From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed"

*must see Depth-First Search (DFS) to compare and understanding graph traversal deeply. Interviewer may ask DFS after BFS.

Below pseudo code shows the algorithm of BFS

algorithm BFS(x)
visit(start node)
queue <- start node
WHILE queue is not empty DO
x <- queue
FOR each y such that (x,y) is an edge and y has not been visited yet DO
visit(y)
queue <- y
END
END

Describe the Algorithm for a Depth-First Graph Traversal.

Full Question:

Describe the algorithm for a depth-first graph traversal.

Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root-like node that connects to all other nodes might not exist.

Depth-First Search (DFS)
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.

*must see Breadth-First Search (BFS) to compare and understanding graph traversal deeply. Interviewer may ask BFS after DFS.

Below pseudo code shows DFS algorithm.

algorithm DFT(G,v):
label v as visited
for all edges e in G.incidentEdges(v) do
if edge e is unvisited then
w ← G.opposite(v,e)
if vertex w is visited then
label e as a discovery edge
recursively call DFT(G,w)
else
label e as a back edge

Not considering edges, the algorithm can be simple.

algorithm DFT(x)
visit(x); x<-visited;
FOR each y such that (x,y) is an edge DO
IF y != visited THEN
DFT(y)

Write a C program which measures the speed of a context switch on a UNIX/Linux system.Context

Full Question:

Write a C program which measures the speed of a context switch on a UNIX/Linux system.Context

Context switching roughly happens when either:

User process enters the kernel via system call or a trap (e.g. page fault) and requested data (e.g. file contents) is not yet available, so the kernel puts said user process into sleep state and switches to another runnable process.
Kernel detects that given user process consumed its full time quanta (this happens in code invoked from timer interrupt.)
Data becomes available for higher current priority process that is presently sleeping (this happens from code invoked from/around IO interrupts.)

The switch itself is one-way, so the best we can do in userland (I assume that's what you are asking) is to measure sort of an RTT, from our process to another and back. The other process also takes time to do its work. We can of course make two or more processes cooperate on this, but the thing is that the kernel doesn't guarantee that one of our processes is going to be picked next.

Below code which shows a possible solution is from stackoverflow.

// Compile with g++ latencybench.cc -o latencybench -lboost_thread-mt
// Should also work on MSVC and other platforms supported by Boost.

#include <boost/format.hpp>
#include <boost/thread/thread.hpp>
#include <boost/date_time.hpp>
#include <algorithm>
#include <cstdlib>
#include <csignal>

volatile bool m_quit = false;

extern "C" void sighandler(int) {
   m_quit = true;
}

std::string num(unsigned val) {
   if (val == 1) return "one occurrence";
   return boost::lexical_cast<std::string>(val) + " occurrences";
}

int main(int argc, char** argv) {
   using namespace boost::posix_time;
   std::signal(SIGINT, sighandler);
   std::signal(SIGTERM, sighandler);
   time_duration duration = milliseconds(10);
   if (argc > 1) {
   try {
   if (argc != 2) throw 1;
   unsigned ms = boost::lexical_cast<unsigned>(argv[1]);
   if (ms > 1000) throw 2;
   duration = milliseconds(ms);
   } catch (...) {
   std::cerr << "Usage: " << argv[0] << " milliseconds" << std::endl;
   return EXIT_FAILURE;
   }
   }
   typedef std::map<long, unsigned> Durations;
   Durations durations;
   unsigned samples = 0, wrongsamples = 0;
   unsigned max = 0;
   long last = -1;
   std::cout << "Measuring actual sleep delays when requesting " << duration.total_milliseconds() << " ms: (Ctrl+C when done)" << std::endl;
   ptime begin = boost::get_system_time();
   while (!m_quit) {
   ptime start = boost::get_system_time();
   boost::this_thread::sleep(start + duration);
   long actual = (boost::get_system_time() - start).total_milliseconds();
   ++samples;
   unsigned num = ++durations[actual];
   if (actual != last) {
   std::cout << "\r " << actual << " ms " << std::flush;
   last = actual;
   }
   if (actual != duration.total_milliseconds()) {
   ++wrongsamples;
   if (num > max) max = num;
   std::cout << "spike at " << start - begin << std::endl;
   last = -1;
   }
   }
   if (samples == 0) return 0;
   std::cout << "\rTotal measurement duration: " << boost::get_system_time() - begin << "\n";
   std::cout << "Number of samples collected: " << samples << "\n";
   std::cout << "Incorrect delay count: " << wrongsamples << boost::format(" (%.2f %%)") % (100.0 * wrongsamples / samples) << "\n\n";
   std::cout << "Histogram of actual delays:\n\n";
   unsigned correctsamples = samples - wrongsamples;
   const unsigned line = 60;
   double scale = 1.0;
   char ch = '+';
   if (max > line) {
   scale = double(line) / max;
   ch = '*';
   }
   double correctscale = 1.0;
   if (correctsamples > line) correctscale = double(line) / correctsamples;
   for (Durations::const_iterator it = durations.begin(); it != durations.end(); ++it) {
   std::string bar;
   if (it->first == duration.total_milliseconds()) bar = std::string(correctscale * it->second, '>');
   else bar = std::string(scale * it->second, ch);
   std::cout << boost::format("%5d ms | %s %d") % it->first % bar % it->second << std::endl;
   }
   std::cout << "\n";
   std::string indent(30, ' ');
   std::cout << indent << "+-- Legend ----------------------------------\n";
   std::cout << indent << "| > " << num(1.0 / correctscale) << " (of " << duration.total_milliseconds() << " ms delay)\n";
   if (wrongsamples > 0) std::cout << indent << "| " << ch << " " << num(1.0 / scale) << " (of any other delay)\n";
}

Explain the Significance of "Dead Beef"

Full Question:

Explain the significance of "dead beef".

Dead Beef. It does not mean a real dead beef. Don't say I'm so sad of hearing about it.

0xDEADBEEF ("dead beef") is frequently used to indicate a software crash or deadlock in embedded systems. It is used by IBM RS/6000 systems, Mac OS on 32-bit PowerPC processors and the Commodore Amiga as a magic debug value. On Sun Microsystems' Solaris, it marks freed kernel memory. On OpenVMS running on Alpha processors, DEAD_BEEF can be seen by pressing CTRL-T. The DEC Alpha SRM console has a background process that traps memory errors, identified by PS as "BeefEater waiting on 0xdeadbeef".

DEADBEEF is a hexadecimal value that has was used in debugging back in the mainframe/assembly days because it was easy to see when marking and finding specific memory in pages of hex dumps. Most computer science graduates have seen this at least in their assembly language classes in college and that's why they expect software engineers to know it.

What is the Difference Between a Mutex and a Semaphore?

Full Question:

What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?

Mutex is typically used to serialize access to a common resource while a semaphore is a number of concurrent accesses.
Mutex is like a semaphore with a count of one.
Mutex only allows a single thread to have access while semaphores can be concurrently signaled by any thread or process.
Semaphores are ideal for synchronization and often used for event notification and mutual exclusion while mutex is only applied for mutual exclusion.
Both mutexes and semaphores are used to control access to a shared resource – most often in multithreading scenarios. A mutex is used when only one thread or process is allowed to access a resource and a semaphore is used when only a certain set limit of threads or processes can access the shared resource. Essentially a mutex is a semaphore where the limit is set to 1.
Which one would I use to protect access to an increment operation? In the general scenario I would use a mutex. But, in some programming languages support incremental function or methods for this kind of situation, for example Interlocked.Increment in C#.

April 29, 2011

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a.

Full Question:

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.

With double loop (order N²), it's easy to solve the problem. Just compare one from a and the other from b while looping. Be careful that the solution is required result string in th order of a. So, outer loop should be for string a.

Using boolean array, the problem can be solved in order N time. Since size of char is 256 (char is 1 byte(8 bits) data, so 2⁸ = 256), we just need boolean array whose size is 256. Then first check string b.( note again that result string should be in order of string a). For appearing character in b, set true element of boolean array. (simple use the char as index of array). And then, check string a and print. Done.

public class GoogleQuestion {
public static void main(String args[]) {
String a = "abcdefg";
String b = "afcbedf";

System.out.println(getCommonCharNSquard(a.toCharArray(), b.toCharArray()));
System.out.println(getCommonCharN(a.toCharArray(), b.toCharArray()));

}

public static char[] getCommonCharNSquard(char[] a, char[] b) {
String ret = new String();

for(int i = 0; i < a.length; i++)
for(int j=0; j <b.length; j++) {
if(a[i] == b[j]) {
if(ret.indexOf(a[i]) == -1)
ret += a[i]; // order of a
break; // it may reduce the processing time, but still NSquard
}
}

return ret.toCharArray();
}

public static char[] getCommonCharN(char[] a, char[] b) {
String ret = new String();
boolean[] flags = new boolean[256]; //sizeOf(char)=256

for(int i = 0; i < b.length; i++)
flags[b[i]] = true;

for(int j=0; j <a.length; j++)
if(flags[a[j]] == true) {
ret += a[j]; // order of a
flags[a[j]] = false;
}
return ret.toCharArray();
}

}

Generate a Random Number Between 1 and 7, Given a Method that Generates a Random Number Between 1 and 5.

Full Question:

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

The given function, let's call rand(5), generates a random number between 1 to 5 in uniform manner. So, we can generate a random number from 1 to 5ⁿ in also uniform manner. For example, 25*(rand(5)-1) + rand(5) generates a random number between 1 to 125, and 5*(rand(5)-1)+rand(5) generates a random number between 1 to 25 uniformly. From this derivation, we can get a random number between 1 to 7 under uniform distribution.

public static void main(String args[]) {
Random g = new Random(1929304);
int N = 100000000;
int num[] = {0, 0, 0, 0, 0, 0, 0};

for(int i=0; i<N; i++ ) {
int j;
do {
j = 5*g.nextInt(5) + (g.nextInt(5)+1); // uniform between 1 and 25
} while(j>21); // uniform between 1 and 21
num[(j%7)]++; // uniform between 1 and 7 (0 and 6)
}

for(int i=0; i< 7; i++ )
System.out.println(i+1 + ": " + num[i]);
}

Following box shows results after a hundred million times try.

1: 14289981
2: 14288932
3: 14286841
4: 14284775
5: 14283995
6: 14285958
7: 14279518

April 13, 2011

Write a function called to Excel that takes an excel column value and returns a corresponding integer value

Full Question:

Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).

The result should be like
A → 1,
Z → 26,
AA → 27, (Problem line indicates 'AA=26', but it's somehow strange. (i.e. Z=26)
ZBC → 17631.

When considering only capitals, following Java function converts alphabet to decimal. Excepting input.length, you can use in C program directly.

/* alphabet to decimal */
public int alphaToDecimal(char input[]){
  int ret = 0;  
  int a, b;  
  int i, j;  
  for (i=0; i<input.length; i++) {  
    a = input[i] - 'A' + 1;  
    b = 1; // you can use Math.pow();  
    for(j=0; j<input.length-i-1;j++)  
      b *= 'Z'-'A' + 1;  
    ret += a*b;  
  }  
  return ret; 
}

{ Program Square }

Home Racing Girls Blogger Tips Programming

July 01, 2011

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

May 16, 2011

What is the C-language command for opening a connection with a foreign host over the internet?

May 03, 2011

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

What is multithreaded programming? What is a deadlock?

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

Explain how congestion control works in the TCP protocol.

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

Write a Regular Expression Which Matches an Email Address

How are cookies passed in the HTTP protocol?

May 02, 2011

Describe the Algorithm for a Breath-First Graph Traversal.

Describe the Algorithm for a Depth-First Graph Traversal.

Write a C program which measures the speed of a context switch on a UNIX/Linux system.Context

Explain the Significance of "Dead Beef"

What is the Difference Between a Mutex and a Semaphore?

April 29, 2011

Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a.

Generate a Random Number Between 1 and 7, Given a Method that Generates a Random Number Between 1 and 5.

April 13, 2011

Write a function called to Excel that takes an excel column value and returns a corresponding integer value

Popular Posts

Recent Posts

Categories

Archives

Popular Tags