Amazon Interview Questions

0

Latest Amazon Interview Questions -1

1. How would you find the second largest element in an array using minimum no of comparisons?

2. Write a C program for level order traversal of a tree?

3. You are given: 3 types of vehicles: Motorbike, Car, and a special type of car for the handicapped.
3 types of parking: Motorbike parking, Car parking, handicapped car parking.

Motorbikes and cars can only park in their designated parkings, while the handicapped cars can park either in their own parking or the regular car parking.
How would you model this as classes? Explain your methods.

4. Given 2 tables: Employee(Employee_Name,Dept_No) Department(Dept_No, Dept_Name)

Write an SQL query which outputs all the employees, and their department nos and names, including all those departments which have no employees working for them.

6. Explain about Inodes?

7.Give a Linux shell command to find all files in a directory which contain ip addresses.

8. Given a table Employee which has columns name and salary, write an SQL query to find the employee with the second highest salary.

9. Given a table of Player which contains Sno and player name, write a query which finds all possible Table Tennis doubles pairings.

10.Given a string A, and a string B, and a dictionary, how would you convert A to B in the minimum no of operations, given that:

i) All the intermediate words must be from the dictionary

ii) An ‘operation’ is defined as:

a) Delete any character from a string ex dog → do

b) Insert any character into a string ex cat → cart

c) Replace any character in the string with another ex cat → cot

Latest Amazon Interview Questions -2

1.Given a string,find the first un-repeated character in it? Give some test cases
2.You are given a dictionary of all valid words. You have the following 3 operations permitted on a word:

a) Delete a character

b) Insert a character

c) Replace a character

Now given two words – word1 and word2 – find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)

3.Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.

4.What is a C array and illustrate the how is it different from a list.

5. What is the time and space complexities of merge sort and when is it preferred over quick sort?

6. Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.

7. Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.

8.Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.

9. Given an array of size n ,containing every element from 1 to n+1, except one. Find the missing element?

Amazon Intern Interview questions

  1. There are two urns A and B and an equal number of red balls and blue balls.How do u place the balls in the urns such that the probability of picking up the red ball is greater?
  2. Two trains enter at the opposite sides of a tunnel of length L with speeds ‘V’. A particle enters the tunnel at the same time with a speed ‘v’ and it vibrates in the tunnel[i.e. if it reaches the end of the tunnel then it comes back]. What is the position of the particle by the time the 2 trains meet?
  3. Write an sql query to sort a table according to the amounts in a row and find the second largest amount.
  4. How do you kill a process?
  5. What is the functionality of a top command?
  6. Given an array of size n+1 which contains all the numbers from 1 to n.Find the number which is repeated in O(n) time.How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?
  7. Design a datastructure to represent the movement of a knight on a chess board
  8. Write an algorithm to traverse a knight covering all the squares on a chessboard starting at a particular point.

Linux Interview Q&A

0

Linux Interview Q&A

Which command is used to check the number of files and disk space used and the each user’s defined quota?

repquota command is used to check the status of the user’s quota along with the disk space and number of files used. This command gives a summary of the user’s quota that how much space and files are left for the user. Every user has a defined quota in Linux. This is done mainly for the security, as some users have only limited access to files. This provides a security to the files from unwanted access. The quota can be given to a single user or to a group of users.

What is the name and path of the main system log?

By default the main system log is /var/log/messages. This file contains all the messages and the script written by the user. By default all scripts are saved in this file. This is the standard system log file, which contains messages from all system software, non-kernel boot issues, and messages that go to ‘dmesg’. dmesg is a system file that is written upon system boot.

How secured is Linux? Explain.

Security is the most important aspect of an operating system. Due to its unique authentication module, Linux is considered as more secured than other operating systems. Linux consists of PAM. PAM is Pluggable Authentication Modules. It provides a layer between applications and actual authentication mechanism. It is a library of loadable modules which are called by the application for authentication. It also allows the administrator to control when a user can log in. All PAM applications are configured in the directory “/etc/pam.d” or in a file “/etc/pam.conf”. PAM is controlled using the configuration file or the configuration directory.

Can Linux computer be made a router so that several machines may share a single Internet connection? How?

Yes a Linux machine can be made a router. This is called “IP Masquerade.” IP Masquerade is a networking function in Linux similar to the one-to-many (1: Many) NAT (Network Address Translation) servers found in many commercial firewalls and network routers. The IP Masquerade feature allows other “internal” computers connected to this Linux box (via PPP, Ethernet, etc.) to also reach the Internet as well. Linux IP Masquerading allows this functionality even if the internal computers do not have IP addresses.
The IP masquerading can be done by the following steps:

1. The Linux PC must have an internet connection and a connection to LAN. Typically, the Linux PC has two network interfaces-an Ethernet card for the LAN and a dial-up PPP connection to the Internet (through an ISP).

2. All other systems on your LAN use the Linux PC as the default gateway for TCP/IP networking. Use the same ISP-provided DNS addresses on all systems.

3. Enable IP forwarding in the kernel. By default the IP forwarding is not enabled. To ensure that IP forwarding is enabled when you reboot your system, place this command in the /etc/rc.d/rc.local file.

4. Run /sbin/iptables-the IP packet filter administration program-to set up the rules that enable the Linux PC to masquerade for your LAN.

What is the minimum number of partitions you need to install Linux?

Minimum 2 partitions are needed for installing Linux. The one is / or root which contains all the files and the other is swap. Linux file system is function specific which means that files and folders are organized according to their functionality. For example, all executables are in one folder, all devices in another, all libraries in another and so on. / or ‘root’ is the base of this file system. All the other folders are under this one. / can be consider as C: .Swap is a partition that will be used as virtual memory. If there is no more available RAM a Linux computer will use an area of the hard disk, called swap, to temporarily store data. In other words it is a way of expanding your computers RAM.

Which command is used to review boot messages?

dmesg command is used to review boot messages. This command will display system messages contained in the kernel ring buffer. We can use this command immediately after booting to see boot messages. A ring buffer is a buffer of fixed size for which any new data added to it overwrites the oldest data in it. Its basic syntax is

dmesg [options]

Invoking dmesg without any of its options causes it to write all the kernel messages to standard output. This usually produces far too many lines to fit into the display screen all at once, and thus only the final messages are visible. However, the output can be redirected to the less command through the use of a pipe, thereby allowing the startup messages to be viewed on one screen at a time
dmesg | less

Which utility is used to make automate rotation of a log?

logrotate command is used to make automate rotation of log.
Syntax of the command is:
logrotate [-dv] [-f|] [-s|] config_file+
It allows automatic rotation, compression, removal, and mailing of log files. This command is mainly used for rotating and compressing log files. This job is done every day when a log file becomes too large. This command can also be run by giving on command line. We can done force rotation by giving –f option with this command in command line. This command is also used for mailing. We can give –m option for mailing with this command. This option takes two arguments one is subject and other is recipient name.

What are the partitions created on the mail server hard drive?

The main partitions are done firstly which are root, swap and boot partition. But for the mail server three different partitions are also done which are as follows:
1. /var/spool- This is done so that if something goes wrong with the mail server or spool than the output cannot overrun the file system.
2. /tmp- putting this on its own partition prevents any user item or software from overrunning the system files.
3. /home- putting this on its own is useful for system upgrades or reinstalls. It allow not to wipe off the /home hierarchy along with other areas.

What are the fields in the/etc/passwd file?

It contains all the information of the users who log into the system. It contains a list of the system’s accounts, giving for each account some useful information like user ID, group ID, home directory, shell, etc. It should have general read permission as many utilities, like ls use it to map user IDs to user names, but write access only for the superuser (root). The main fields of /etc/passwd file are:
1. Username: It is used when user logs in. It should be between 1 and 32 characters in length.
2. Password: An x character indicates that encrypted password is stored in /etc/shadow file.
3. User ID (UID): Each user must be assigned a user ID (UID). UID 0 (zero) is reserved for root and UIDs 1-99 are reserved for other predefined accounts. Further UID 100-999 are reserved by system for administrative and system accounts/groups.
4. Group ID (GID): The primary group ID (stored in /etc/group file)
5. User ID Info: The comment field. It allow you to add extra information about the users such as user’s full name, phone number etc. This field use by finger command.
6. Home directory: The absolute path to the directory the user will be in when they log in. If this directory does not exists then users directory becomes /
7. Command/shell: The absolute path of a command or shell (/bin/bash). Typically, this is a shell.

Which commands are used to set a processor-intensive job to use less CPU time?

nice command is used for changing priority of the jobs.
Syntax: nice [OPTION] [COMMAND [ARG]…]
Range of priority goes from -20 (highest priority) to 19 (lowest).Priority is given to a job so that the most important job is executed first by the kernel and then the other least important jobs. This takes less CPU times as the jobs are scheduled and are given priorities so the CPU executes fast. The priority is given by numbers like -20 describe the highest priority and 19 describe the least priority.

How to change window manager by editing your home directory?

/.xinitrc file allows changing the window manager we want to use when logging into X from that account. The dot in the file name shows you that the file is a hidden file and doesn’t show when you do a normal directory listing. For setting a window manager we have to save a command in this file. The syntax of command is: exec windowmanager.After this, save the file. Next time when you run a startx a new window manager will open and become default. The commands for starting some popular window managers and desktop environments are:
-KDE = startkde
-Gnome = gnome-session
-Blackbox = blackbox
-FVWM = fvwm
-Window Maker = wmaker
-IceWM = icewm

How documentation of an application is stored?

When a new application is installed its documentation is also installed. This documentation is stored under the directory named for application. For example if my application name is App1 then the path of the documentation will be /user/doc/App1. It contains all the information about the application. It contains date of creating application, name of application and other important module of the application. We can get the basic information of application from the documentation.

How shadow passwords are given?

pwconv command is used for giving shadow passwords. Shadow passwords are given for better system security. The pwconv command creates the file /etc/shadow and changes all passwords to ‘x’ in the /etc/passwd file. First, entries in the shadowed file which don’t exist in the main file are removed. Then, shadowed entries which don’t have `x’ as the password in the main file are updated. Any missing shadowed entries are added. Finally, passwords in the main file are replaced with `x’. These programs can be used for initial conversion as well to update the shadowed file if the main file is edited by hand.

How do you create a new user account?

useradd command is used for creating a new user account. When invoked without the
-D option, the useradd command creates a new user account using the values specified on the command line and the default values from the system. The new user account will be entered into the system files as needed, and initial files copied, depending on the command line options. This command uses the system default as home directory. If –m option is given then the home directory is made.

Which password package is installed for the security of central password?

Shadow password packages are used for security of central passwords. Security is the most important aspect of every operating system. When this package is not installed the user information including passwords is stored in the /etc/passwd file. The password is stored in an encoded format. These encoded forms can be easily identified by the System crackers by randomly encoding the passwords from dictionaries. The Shadow Package solves the problem by relocating the passwords to another file (usually /etc/shadow). The /etc/shadow file is set so that it cannot be read by just anyone. Only root will be able to read and write to the /etc/shadow file.

Which shell do you assign to a POP3 mail-only account?

POP3 mail only account is assigned to the /bin/false shell. However, assigning bash shell to a POP3 mail only gives user login access, which is avoided. /bin/nologin can also be used. This shell is provided to the user when we don’t want to give shell access to the user. The user cannot access the shell and it reject shell login on the server like on telnet. It is mainly for the security of the shells. POP3 is basically used for downloading mail to mail program. So for illegal downloading of emails on the shell this account is assigned to the /bin/false shell or /bin/nologin. These both shells are same they both do the same work of rejecting the user login to the shell. The main difference between these two shells is that false shell shows the incorrect code and any unusual coding when user login with it. But the nologin shell simply tells that no such account is available. So nologin shell is used mostly in Linux.

Which daemon is responsible for tracking events on Linux system?

syslogd is responsible for tracking system information and save it to the desired log files. It provides two system utilities which provide system logging and kernel message trapping. Internet and UNIX domain sockets support enable this utility package to support both local and remote logging. Every logged message contains at least a time and a hostname field, normally a program name field, too. So to track these information this daemon is used. syslogd mainly reacts to the set of signals given by the user. These are the signals given to syslogd: SIGHUP: This lets syslogd perform a re-initialization. All open files are closed, the configuration file (default is /etc/syslog.conf) will be reread and the syslog facility is started again. SIGTERM: The syslogd will die. SIGINT, SIGQUIT: If debugging is enabled these are ignored, otherwise syslogd will die. SIGUSR1: Switch debugging on/off. This option can only be used if syslogd is started with the – d debug option. SIGCHLD: Wait for Childs if some were born, because of waiting messages.

Which daemon is used for scheduling of the commands?

The crontab command is used for scheduling of the commands to run at a later time. SYNTAX
crontab [ -u user ] file
crontab [ -u user ] { -l | -r | -e }

Options
-l List – display the current crontab entries.

-r Remove the current crontab.

-e Edit the current crontab using the editor specified by the VISUAL or EDITOR environment variables.
When user exits from the editor, the modified crontab will be installed automatically. Each user can have their own crontab, and though these are files in /var, they are not intended to be edited directly. If the –u option is given than the crontab gives the name of the user whose crontab is to be tweaked. If it is given without this then it will display the crontab of the user who is executing the command.

How environment variable is set so that the file permission can be automatically set to the newly created files?

umask command is used to set file permission on newly created files automatically.
Syntax
umask [-p] [-S] [mode]
It is represented in octal numbers. We can simply use this command without arguments to see the current file permissions. To change the permissions, mode is given in the arguments. The default umask used for normal user is 0002. The default umask for the root user is 0022. For calculating the original values, the values shown by the umask must be subtracted by the default values. It is mainly used for masking of the file and directory permission. The /etc/profile script is where the umask command is usually set for all users. The –S option can be used to see the current default permissions displayed in the alpha symbolic format.
For example, umask 022 ensures that new files will have at most 755 permissions (777 NAND 022).
The permissions can be calculated by taking the NAND of original value with the default values of files and directories.

Linux Interview Questions

0

Linux Interview Questions

  1. Which command is used to check the number of files and disk space used and the each user’s defined quota?
  2. What is the name and path of the main system log?
  3. How secured is Linux? Explain.
  4. Can Linux computer be made a router so that several machines may share a single Internet connection? How?
  5. What is the minimum number of partitions you need to install Linux?
  6. Which command is used to review boot messages?
  7. Which utility is used to make automate rotation of a log?
  8. What are the partitions created on the mail server hard drive?
  9. What are the fields in the/etc/passwd file?
  10. Which commands are used to set a processor-intensive job to use less CPU time?
  11. How to change window manager by editing your home directory?
  12. How documentation of an application is stored?
  13. How shadow passwords are given?
  14. How do you create a new user account?
  15. Which password package is installed for the security of central password?
  16. Which shell do you assign to a POP3 mail-only account?
  17. Which daemon is responsible for tracking events on Linux system?
  18. Which daemon is used for scheduling of the commands?
  19. How environment variable is set so that the file permission can be automatically set to the newly created files?

Email Server

0

The Real E-mail System

For the vast majority of people right now, the real e-mail system consists of two different servers running on a server machine. One is called the SMTP server, where SMTP stands for Simple Mail Transfer Protocol. The SMTP server handles outgoing mail. The other is either a POP3 server or an IMAP server, both of which handle incoming mail. POP stands for Post Office Protocol, and IMAP stands for Internet Mail Access Protocol. A typical e-mail server looks like this:

The SMTP server listens on well-known port number 25, POP3 listens on port 110 and IMAP uses port 143.

The SMTP Server

Whenever you send a piece of e-mail, your e-mail client interacts with the SMTP server to handle the sending. The SMTP server on your host may have conversations with other SMTP servers to deliver the e-mail.

Let’s assume that I want to send a piece of e-mail. My e-mail ID is brain, and I have my account on howstuffworks.com. I want to send e-mail to jsmith@mindspring.com. I am using a stand-alone e-mail client like Outlook Express.

When I set up my account at arpittak.com, I told Outlook Express the name of the mail server — mail.arpittak.com. When I compose a message and press the Send button, here’s what happens:

  1. Outlook Express connects to the SMTP server atmail.arpittak.com using port 25.
  2. Outlook Express has a conversation with the SMTP server, telling the SMTP server the address of the sender and the address of the recipient, as well as the body of the message.
  3. The SMTP server takes the “to” address (jsmith@mindspring.com) and breaks it into two parts: the recipient name (jsmith) and the domain name (mindspring.com). If the “to” address had been another user at  arpittak.com., the SMTP server would simply hand the message to the POP3 server for arpittak.com (using a little program called the delivery agent). Since the recipient is at another domain, SMTP needs to communicate with that domain.
  4. The SMTP server has a conversation with a Domain Name Server, or DNS. It says, “Can you give me the IP address of the SMTP server for mindspring.com?” The DNS replies with the one or more IP addresses for the SMTP server(s) that Mindspring operates.
  5. The SMTP server at arpittak.com connects with the SMTP server at Mindspring using port 25. It has the same simple text conversation that my e-mail client had with the SMTP server for arpittak, and gives the message to the Mindspring server. The Mindspring server recognizes that the domain name for jsmith is at Mindspring, so it hands the message to Mindspring’s POP3 server, which puts the message in jsmith’s mailbox.

If, for some reason, the SMTP server at arpittakcannot connect with the SMTP server at Mindspring, then the message goes into a queue. The SMTP server on most machines uses a program called sendmail to do the actual sending, so this queue is called the sendmail queue. Sendmail will periodically try to resend the messages in its queue. For example, it might retry every 15 minutes. After four hours, it will usually send you a piece of mail that tells you there is some sort of problem. After five days, most sendmail configurations give up and return the mail to you undelivered.

The SMTP server understands very simple text commands like HELO, MAIL, RCPT and DATA. The most common commands are:

  • HELO – introduce yourself
  • EHLO – introduce yourself and request extended mode
  • MAIL FROM: – specify the sender
  • RCPT TO: – specify the recipient

The POP3 and IMAP Servers

When you check your e-mail, your e-mail client connects to the POP3 server using port 110. The POP3 server requires an account name and a password. Once you’ve logged in, the POP3 server opens your text file and allows you to access it. Like the SMTP server, the POP3 server understands a very simple set of text commands. Here are the most common commands:

  • USER – enter your user ID
  • PASS – enter your password
  • QUIT – quit the POP3 server
  • LIST – list the messages and their size

The IMAP Server

As you can see, the POP3 protocol is very simple. It allows you to have a collection of messages stored in a text file on the server. Your e-mail client (e.g. Outlook Express) can connect to your POP3 e-mail server and download the messages from the POP3 text file onto your PC. That is about all that you can do with POP3.

Many users want to do far more than that with their e-mail, and they want their e-mail to remain on the server. The main reason for keeping your e-mail on the server is to allow users to connect from a variety of machines. With POP3, once you download your e-mail it’s stuck on the machine to which you downloaded it. If you want to read your e-mail both on your desktop machine and your laptop (depending on whether you’re working in the office or on the road), POP3 makes life difficult.

IMAP (Internet Mail Access Protocol) is a more advanced protocol that solves these problems. With IMAP, your mail stays on the e-mail server. You can organize your mail into folders, and all the folders live on the server as well. When you search your e-mail, the search occurs on the server machine, rather than on your machine. This approach makes it extremely easy for you to access your e-mail from any machine, and regardless of which machine you use, you have access to all of your mail in all of your folders.

Web Server

0

The Basic Process

Let’s say that you are sitting at your computer, surfing the Web, and you get a call from a friend who says, “I just read a great article! Type in this URL and check it out. It’s at http://arpittak.com .  So you type that URL into your browser and press return. And magically, no matter where in the world that URL lives, the page pops up on your screen.

Your browser formed a connection to a Web server, requested a page and received it.

The browser broke the URL into three parts:

  • The protocol (“http”)
  • The server name (“www.howstuffworks.com”)
  • The file name (“web-server.htm”)

The browser communicated with a name server to translate the server name “www.arpittak.com” into an IP Address, which it uses to connect to the server machine. The browser then formed a connection to the server at that IP address on port 80.

Following the HTTP protocol, the browser sent a GET request to the server, asking for the file “http://www.arpittak.com/index.htm.” (Note that cookies may be sent from browser to server with the GET request.)

The server then sent the HTML text for the Web page to the browser. (Cookies may also be sent from server to browser in the header for the page.) The browser read the HTML tags and formatted the page onto your screen.

Clients and Servers

In general, all of the machines on the Internet can be categorized as two types: servers and clients. Those machines that provide services (like Web servers or FTP servers) to other machines are servers. And the machines that are used to connect to those services are clients. When you connect to Yahoo! at http://www.yahoo.com to read a page, Yahoo! is providing a machine (probably a cluster of very large machines), for use on the Internet, to service your request. Yahoo! is providing a server. Your machine, on the other hand, is probably providing no services to anyone else on the Internet. Therefore, it is a user machine, also known as a client. It is possible and common for a machine to be both a server and a client, but for our purposes here you can think of most machines as one or the other.

A server machine may provide one or more services on the Internet. For example, a server machine might have software running on it that allows it to act as a Web server, an e-mail server and an FTP server. Clients that come to a server machine do so with a specific intent, so clients direct their requests to a specific software server running on the overall server machine. For example, if you are running a Web browser on your machine, it will most likely want to talk to the Web server on the server machine. Your Telnet application will want to talk to the Telnet server, your e-mail application will talk to the e-mail server, and so on…

IP Addresses

To keep all of these machines straight, each machine on the Internet is assigned a unique address called an IP address. IP stands for Internet protocol, and these addresses are 32-bit numbers, normally expressed as four “octets” in a “dotted decimal number.” A typical IP address looks like this:     216.27.61.137

The four numbers in an IP address are called octets because they can have values between 0 and 255, which is 28 possibilities per octet.

Every machine on the Internet has a unique IP address. A server has a static IP address that does not change very often. A home machine that is dialing up through a modem often has an IP address that is assigned by the ISP when the machine dials in. That IP address is unique for that session — it may be different the next time the machine dials in. This way, an ISP only needs one IP address for each modem it supports, rather than for each customer.

Domain Names

Because most people have trouble remembering the strings of numbers that make up IP addresses, and because IP addresses sometimes need to change, all servers on the Internet also have human-readable names, called domain names. For example, www.arppittak.com is a permanent, human-readable name.

The name http://www.arpittak.com actually has three parts:

  1. The host name (“www”)
  2. The domain name (“arpittak”)
  3. The top-level domain name (“com”)

Name Servers

A set of servers called domain name servers (DNS) maps the human-readable names to the IP addresses. These servers are simple databases that map names to IP addresses, and they are distributed all over the Internet. Most individual companies, ISPs and universities maintain small name servers to map host names to IP addresses. There are also central name servers that use data supplied by VeriSign to map domain names to IP addresses.

Ports

Any server machine makes its services available to the Internet using numbered ports, one for each service that is available on the server. For example, if a server machine is running a Web server and an FTP server, the Web server would typically be available on port 80, and the FTP server would be available on port 21. Clients connect to a service at a specific IP address and on a specific port.

Each of the most well-known services is available at a well-known port number. Here are some common port numbers:

  • echo 7
  • daytime 13
  • qotd 17 (Quote of the Day)
  • ftp 21
  • telnet 23
  • smtp 25 (Simple Mail Transfer, meaning e-mail)
  • time 37
  • nameserver 53

Protocols

Once a client has connected to a service on a particular port, it accesses the service using a specific protocol. The protocol is the pre-defined way that someone who wants to use a service talks with that service. The “someone” could be a person, but more often it is a computer program like a Web browser. Protocols are often text, and simply describe how the client and server will have their conversation.

Perhaps the simplest protocol is the daytime protocol. If you connect to port 13 on a machine that supports a daytime server, the server will send you its impression of the current date and time and then close the connection. The protocol is, “If you connect to me, I will send you the date and time and then disconnect.”

Control Flows

0

The If Statement

1
if (condition) statement;

or

1
2
3
if (condition) {
    zero to many statements;
}

Causes “one thing” to occur when a specified condition is met.

The one thing may be a single statement or a block of statements in curly braces. The remainder of the code (following the if and the statement or block it owns) is then executed regardless of the result of the condition.

The conditional expression is placed within parentheses.

The following flowchart shows the path of execution:

If Statement Flowchart

if Statement Examples

Absolute Value

If we needed the absolute value of a number (a number that would always be positive):

Code Sample:

Java-Control/Demos/If1.java
1
2
3
4
5
6
7
8
9
10
11
12
public class If1 {
  public static void main(String[] args) {
    int a = 5;
    System.out.println("original number is: " + a);
    if ( a < 0 ) { a = -a; }
    System.out.println("absolute value is: " + a);
    a = -10;
    System.out.println("original number is: " + a);
    if ( a < 0 ) { a = -a; }
    System.out.println("absolute value is: " + a);
  }
}

Random Selection

Task: write a brief program which generates a random number between 0 and 1. Print out that the value is in the low, middle, or high third of that range (Math.random() will produce a double value from 0.0 up to but not including 1.0).

  • Although it is a bit inefficient, just do three separate tests: (note that Math.random() will produce a number greater than or equal to 0.0 and less than 1.0).

Code Sample:

Java-Control/Demos/If2.java
1
2
3
4
5
6
7
8
9
10
11
12
public class If2 {
  public static void main(String[] args) {
    double d = Math.random();
    System.out.print("The number " + d);
    if (d < 1.0/3.0)
      System.out.println(" is low");
    if (d >= 1.0/3.0 && d < 2.0/3.0)
      System.out.println(" is middle");
    if (d >= 2.0/3.0)
      System.out.println(" is high");
  }
}

The if ... else Statement

1
2
3
if (condition) statement;
else if { block } statement;
else { block }

The if … else Statement does “one thing” if a condition is true, and a different thing if it is false.

It is never the case that both things are done. The “one thing” may be a single statement or a block of statements in curly braces.

A statement executed in a branch may be any statement, including another if or if ... else statement.

If ... Else Statement Flowchart

This program tells you that you are a winner on average once out of every four tries.

Code Sample:

Java-Control/Demos/IfElse1.java
1
2
3
4
5
6
7
public class IfElse1 {
  public static void main(String[] args) {
    double d = Math.random();
    if (d < .25) System.out.println("You are a winner!");
    else System.out.println("Sorry, try again!");
  }
}

Nested if ... else Statements – Comparing a Number of Mutually Exclusive Options

You can nestif ... else statements, so that an if or else clause contains another test. Both the if and the elseclause can contain any type of statement, including another if or if ... else.

You can test individual values or ranges of values. Once an if condition is true, the rest of the branches will be skipped. You could also use a sequence of if statements without the else clauses (but this doesn’t by itself force the branches to be mutually exclusive).

Here is the low/middle/high example rewritten using if ... else

Code Sample:

Java-Control/Demos/IfElse2.java
1
2
3
4
5
6
7
8
9
10
11
12
public class IfElse2 {
  public static void main(String[] args) {
    double d = Math.random();
    System.out.print("The number " + d);
    if (d < 1.0/3.0)
      System.out.println(" is low");
    else if (d < 2.0/3.0)
      System.out.println(" is middle");
    else
      System.out.println(" is high");
  }
}

Similarly, we do not test the high third at all. The original version worked because there was no chance that more than one message would print; that approach is slightly less efficient because all three tests will always be made. In the if ... else version, comparing stops once a match has been made.

The switch Statement

A switch expression (usually a variable) is compared against a number of possible values. It is used when the options are each a single, constant value that is exactly comparable (called a case).

The switch expression must be a bytecharshort, or int. Cases may only be bytecharshort, or int values; in addition, their magnitude must be within the range of the switch expression data type and cannot be used with floating-point datatypes or long and cannot compare an option that is a range of values, unless it can be stated as a list of possible values, each treated as a separate case.

Cases are listed under the switch control statement, within curly braces, using the case keyword. Once a match is found, all executable statements below that point are executed, including those belonging to later cases; this allows stacking of multiple cases that use the same code.

The break; statement is used to jump out of the switch block, thus skipping executable steps that are not desired. The default case keyword catches all cases not matched above – note that the default case does not need to be the last thing in the switch. Note that technically speaking, the cases are labeled lines; the switch jumps to the first label whose value matches the switch expression.

Usage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
switch ( <span class="Subst">expression</span> ) {
    case constant1:
        statements;
        break;
    case constant2:
        statements;
        break;
    . . .
    case constant3:
    case constant4:
        MeansTheSameAs3:
        statements;
        break;
    . . .
    [default:
        statements;]
}

switch Statement Examples

Code Sample:

Java-Control/Demos/Switch1.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import util.KeyboardReader;
public class Switch1 {
  public static void main(String[] args) {
    char c = 'X';
    c = KeyboardReader.getPromptedChar("Enter a letter a - d: ");
    switch (c) {
      case 'a':
      case 'A': System.out.println("A is for Aardvark");
                break;
      case 'b':
      case 'B': System.out.println("B is for Baboon");
                break;
      case 'c':
      case 'C': System.out.println("C is for Cat");
                break;
      case 'd':
      case 'D': System.out.println("D is for Dog");
                break;
      default:  System.out.println("Not a valid choice");
    }
  }
}

Three points to note:

  • Stacking of cases for uppercase and lowercase letters allows both possibilities.
  • break; statements used to separate code for different cases.
  • default: clause used to catch all other cases not explicitly handled.

Here is a revised version that moves the default to the top, so that a bad entry is flagged with an error message, but then treated as an ‘A’ – note that there is no break below the default case.

Code Sample:

Java-Control/Demos/Switch2.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import util.KeyboardReader;
public class Switch2 {
  public static void main(String[] args) {
    char c = 'X';
    c = KeyboardReader.getPromptedChar("Enter a letter a - d: ");
    switch (c) {
      default:  System.out.println("Not a valid choice - assuming 'A'");
      case 'a':
      case 'A': System.out.println("A is for Aardvark");
                break;
      case 'b':
      case 'B': System.out.println("B is for Baboon");
                break;
      case 'c':
      case 'C': System.out.println("C is for Cat");
                break;
      case 'd':
      case 'D': System.out.println("D is for Dog");
                break;
    }
  }
}

Another example is taking advantage of the “fall-though” behavior without a break statement.

Code Sample:

Java-Control/Demos/Christmas.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import util.KeyboardReader;
public class Christmas {
  public static void main(String[] args) {
    int day = KeyboardReader.getPromptedInt("What day of Christmas? ");
    System.out.println(
        "On the " + day + " day of Christmas, my true love gave to me:");
    switch (day) {
      case 12: System.out.println("Twelve drummers drumming,");
      case 11: System.out.println("Eleven pipers piping,");
      case 10: System.out.println("Ten lords a-leaping,");
      case 9: System.out.println("Nine ladies dancing,");
      case 8: System.out.println("Eight maids a-milking,");
      case 7: System.out.println("Seven swans a-swimming,");
      case 6: System.out.println("Six geese a-laying,");
      case 5: System.out.println("Five golden rings,");
      case 4: System.out.println("Four calling birds,");
      case 3: System.out.println("Three French hens,");
      case 2: System.out.println("Two turtle doves, and a ");
      case 1: System.out.println("Partridge in a pear tree!");
    }
  }
}

String

0

What is a String?

In java and unlike C++, the string data type is now an object type. Notice that the class name is starts with an uppercase. If you mess this up, Java will not know what you are referring to.

By it’s conception, a string is anything and everything grouped together between 2 double quotes. For example, “Hello world” is one string while “sdad anesd ccn ” is another.

Using Strings

Strings can be manipulated in numerous ways. The first is with some member functions of the string class. Let’s see an example first before we continue.

Example 1:
Different String functions

public class StringExample{

   public static void main(String args[]){

      String word;

      //assign the string to the variable:
      word = "Alexander";

      //preform some actions on the string:

      //1. retrieve the length by calling the
      //length method:
      int length = word.length();
      System.out.println("Length: " + length);

      //2. use the case functions:
      System.out.println("toUpperCase: " + word.toUpperCase());
      System.out.println("toLowerCase: " + word.toLowerCase());

      //3. use the trim function to eliminate leading
      //or trailing white spaces:
      word = word.trim();
      System.out.println("trim: " + word);

      //4. check for a certain character using indexOf()
      System.out.println("indexOf('s'): " + word.indexOf('s'));

      //5. print out the beginning character using charAt()
      System.out.println("first character: " + word.charAt(0));

      //6. make the string shorter
      word = word.substring(0, 4);
      System.out.println("shorter string: " + word);
   }
}

When you run the above program, here is the output that you will get:

Length: 9
toUpperCase: ALEXANDER
toLowerCase: alexander
trim: Alexander
indexOf('s'): -1
first character: A
shorter string: Alex

A lot certainly has happened in this program. Let’s observe some of the most used functions in the String class.

int length()

The length function will simply return the length of a string as an integer.

String toUpperCase()

The toUpperCase function will return the uppercase version of a string. Say you have a string “Welcome”. This function will return “WELCOME”.

String toLowerCase()

The toLowerCase function will return the lowercase version of a string. Say you have a string “Welcome TO Earth”. This function will return “welcome to earth”.

String trim()

The trim function will return the string without leading or trailing white space characters. Say that a string was ” hello “. There are 4 spaces in the front and 3 spaces at the end. The trim function would make this “hello”.

int indexOf(int ch)
int indexOf(int ch, int begin)
int indexOf(String ch)
int indexOf(String ch, int begin)

Notice that there are 4 different functions listed here. All of them preform the same overall action of returning an integer, which represents the FIRST OCCURRANCE of a character or String contained in that string. So say that we have the string “Hello” and we say indexOf(‘l’). This function will use the first function above and return 2. Notice it doesn’t reutrn 3.

We can also say, using the same string “Hello”, indexOf(“He”). It will return 0 as the string that you are searching for starts at index 0.

By default, if a string or character is not found in the string, the any of the functions will return -1.

char charAt(int index)

This function will look for a character at a specific index. It will return that character if it is found. Say we have the string “Hello” and we say charAt(4). It will return ‘o’ as that character is at index 4.

String substring(int begin)
String substring(int begin, int end)

Either of these functions will shorten a string when called. If no ending index is specified, it will return the rest of that string. Say we have the string “Hello there” and we say substring(4), the function will return “o there”. Let’s use substring(2,5), the function will return “llo”.

String Equalities

With Java, there are numerous methods they provide that check for two strings being equal. To show this, here is a small program that will check for a certain string as a command line argument.

Example 2:
String equalities

public class StringExample2{

   private static String word = null;
   private static String keyword = "HELLO";

   public static void main(String args[]){
	//standard error check:
	if(args.length < 1){
		System.out.println("Argument requires one word.");
		System.exit(1);
	}

	//retreive the sentence:
	word = args[0];

	//check for the keyword using different equals methods:
	if(word.equals(keyword)){
		System.out.println("equals true: "
                   + word);
	}
	if(word.equalsIgnoreCase(keyword)){
		System.out.println("ignoreCase true: "
                   + word);
	}

	//check for the keyword using different compareTo methods:
	if(word.compareTo(keyword) != -1){
		System.out.println("found using compareTo: " +
		   word.compareTo(keyword));
	}
	if(word.compareToIgnoreCase(keyword) != -1){
		System.out.println("found using compareToIgnoreCase: " +
		   word.compareToIgnoreCase(keyword));
	}
   }
}

This program will accept as a command-line argument, one word which we will call our “keyword”. It will then preform 4 checks using different member functions of the String class. Here is the output when you run the program with the argument “hello” SPELT EXACTLY AS IS (all lowercase).

ignoreCase true: hello
found using compareTo: 32
found using compareToIgnoreCase: 0

Let’s discover why. Here are the descriptions of the member functions:

boolean equals(String another)

The equals() function will take another String as its parameter and check if it is EXACTLY like the initial String. The initial string is what you called the member function from. So in the above program, the initial string is the variable word.

This method reutrns a boolean value. If true, the string parameter is an exact copy of the initial string. If false, the argument is not a copy as something differs in the string.

As noted, the above program returns false when the equals() method is used because of the case difference.

boolean equalsIgnoreCase(String another)

This method is similar to the regular equals() method with the exception of this method not taking into account the case (either upper or lower) of BOTH strings.

So in the program above, this function returns true because of the ignoring of the case. If the keyword above was “HelloA”, this function will return false because they are still different strings.

int compareTo(String another)

This method compares two Strings lexicographically, meaning it will compare the strings in alphabetical order character by character. The method will return a negative number of the differences between the strings, a 0 if they are equal or a positive number representing how much they differ. The negative return means that string comes before the other lexicographically while the positive return means it comes after the other.

So in the above program, the function returns a 32 because of the following reason; when they compare the first characters of both string (initial string = ‘h’ and argument string = ‘H’), they differ by an ASCII value of 32. The function returns 32 to the user. ASCII values are computer codes for different letters and numbers.

int compareToIgnoreCase(String another)

This method preforms the same actions of the regualr compareTo() method but this one will ignore any case difference. The method returns the same values as the compareTo().

Variables

0

Variables

Variables store data that your code can use.

There are two fundamental categories of variables, primitive data and references:

  • With primitive data, the compiler names a memory location and uses itto store the actual data – numeric values such as integers, floating point values, and the code values of single individual text characters are stored as primitives.
  • With references, the data is accessed indirectly – the compiler selects a memory location, associates it with the variable name, and stores in it a value that is effectively the memory address of the actual data – in Java, all objects and arrays are stored using references.

In the diagram below, the boxes are areas in memory:

Object storage and reference variable

Declaring Variables

Variables must be declared before they are used.

A declaration informs the compiler that you wish to:

  • Create an identifier that will be accepted by the compiler within a section of code (exactly what that section is depends on how and where the variable is declared; that is the concept of scope, which will be addressed later).
  • Associate that identifier with a specified type of data, and enforce restrictions related to that in the remainder of your code.
  • Create a memory location for the specified type of data.
  • Associate the identifier with that memory location.

Java uses many specific data types; each has different properties in terms of size required and handling by the compiler:

  • The declaration specifies the name and datatype.
  • Generally the declaration also defines the variable, meaning that it causes the compiler to allocate storage space in memory of the requested type’s size.
  • A declaration may also assign an initial value (to initialize the variable).
  • Multiple variables of the same type can be declared in a comma-separated list.

5 Essentials Interview Questions

0

Note: This article is written by Stevey’s Drunken (Has worked in Amazon and is a senior engineer and has taken many interviews , so read this article carefully and thinks how he approach to conclusion. I hope u like it.)

I’ve been on a lot of SDE interview loops lately where the candidate failed miserably: not-inclined votes all around, even from the phone screeners who brought the person in initially.

It’s usually pretty obvious when the candidate should have been eliminated during the phone screens. Well, it’s obvious in retrospect, anyway: during the interviews, we find some horrible flaw in the candidate which, had anyone thought to ask about it during the phone screen, would surely have disqualified the person.

But we didn’t ask. So the candidate came in for interviews and wound up wasting everyone’s time.

Antipatterns

I’ve done informal postmortems on at least a hundred phone screens, many of them my own. Whenever a candidate bombs the interviews, I want to know what went wrong with the screen. And guess what? A pattern has emerged. Two patterns, actually.

The first pattern is that for most failed phone screens, the candidate did most of the talking. The screener only asked about stuff on the candidate’s resume, and the candidate was able to talk with passion and enthusiasm about this incredibly cool thing they did, blah blah blah, and the screener was duly impressed.

That’s how many/most phone screens go wrong.

The right way to do a phone screen is to do most of the talking, or at least the driving. You look for specific answers, and you guide the conversation along until you’ve got the answer or you’ve decided the candidate doesn’t know it. Whenever I forget this, and get lazy and let the candidate drone on about their XML weasel-pin connector project, I wind up bringing in a dud.

The second pattern is that one-trick ponies only know one trick. Candidates who have programmed mostly in a single language (e.g. C/C++), platform (e.g. AIX) or framework (e.g. J2EE) usually have major, gaping holes in their skills lineup. These candidates will fail their interviews here because our interviews cover a broad range of skill areas.

These two phone screen (anti-)patterns are related: if you only ask the candidate about what they know, you’ve got a fairly narrow view of their abilities. And you’re setting yourself up for a postmortem on your phone screen.

Acid Tests

In an effort to make life simpler for phone screeners, I’ve put together this list of Five Essential Questions that you need to ask during an SDE screen. They won’t guarantee that your candidate will be great, but they will help eliminate a huge number of candidates who are slipping through our process today.

These five areas are litmus tests — very good ones. I’ve chosen them based on the following criteria:

1) They’re universal – every programmer needs to know them, regardless of experience, so you can use them in all SDE phone screens, from college hires through 30-year veterans.

2) They’re quick – they’re areas that you can probe very quickly, without eating too much into your phone-screen time. Each area can be assessed with 1 to 5 minutes of “weeder questions”, and each area has almost unlimited weeder questions to choose from.

3) They’re predictors – there are certain common “SDE profiles” that are easy to spot because they tend to fail (and I mean really fail) in one or more of these five areas. So the areas are amazingly good at weeding out bad candidates.

You have to probe all five areas; you can’t skip any of them. Each area is a proxy for a huge body of knowledge, and failing it very likely means failing the interviews, even though the candidate did fine in the other areas.

Without further ado, here they are: The Five Essential Questions for the first phone-screen with an SDE candidate:

1) Coding. The candidate has to write some simple code, with correct syntax, in C, C++, or Java.

2) OO design. The candidate has to define basic OO concepts, and come up with classes to model a simple problem.

3) Scripting and regexes. The candidate has to describe how to find the phone numbers in 50,000 HTML pages.

4) Data structures. The candidate has to demonstrate basic knowledge of the most common data structures.

5) Bits and bytes. The candidate has to answer simple questions about bits, bytes, and binary numbers.

Please understand: what I’m looking for here is a total vacuum in one of these areas. It’s OK if they struggle a little and then figure it out. It’s OK if they need some minor hints or prompting. I don’t mind if they’re rusty or slow. What you’re looking for is candidates who are utterly clueless, or horribly confused, about the area in question.

For example, you may find a candidate who decides that a Vehicle class should be a subclass of ParkingGarage, since garages contain cars. This is just busted, and it’s un-fixable in any reasonable amount of training time.

Or a candidate might decide, when asked to search for phone numbers in a bunch of text files, to write a 2000-line C++ program, at which point you discover they’ve never heard of “grep”, or at least never used it.

When a candidate is totally incompetent in one of these Big Five areas, the chances are very high that they’ll bomb horribly when presented with our typical interview questions. Last week I interviewed an SDE-2 candidate who made both of the mistakes above (a vehicle inheriting from garage, and the 2000-line C++ grep implementation.) He was by no means unusual, even for the past month. We’ve been bringing in many totally unqualified candidates.

The rest of this document describes each area in more detail, and gives example questions, and solutions.

Area Number One: Coding

The candidate has to write some code. Give them a coding problem that requires writing a short, straightforward function. They can write it in whatever language they like, as long as they don’t just call a library function that does it for them.

It should be a trivial problem, one that even a slow candidate can answer in 5 minutes or less.

(If the candidate seems insulted by the thought of having to get their hands dirty with a trivial coding question, after all their years of experience, patents, etc., tell them it’s required procedure and ask them to humor you. If they refuse, tell them we only interview people who can demonstrate coding skills over the phone, thank them for their time, and end the call.)

Give them a few minutes to write and hand-simulate the code. Tell them they need to make it syntactically correct and complete. Make them read the code to you over the phone. Copy down what they read back. Put it into your writeup. If they’re sloppy, or don’t want to give you exact details, give them one more chance to correct it, and then go with Not Inclined.

(Note added 10/6/04) — another good approach being used by many teams is to give the candidate “homework”. E.g. you can give them an hour to solve some coding problem (harder than the ones below) and email the solution to you. Works like a charm. Definitely preferable to reading code over the phone.

Anyway, here are some examples. I’ve given solutions in Java, mostly. I’ve gone back and forth on accepting solutions in other languages (e.g. Ruby, Perl, Python), and I’ve decided that candidates need to be able to code their answers in C, C++ or Java. It’s wonderful if they know other languages, and in fact those who do tend to do a lot better overall. But to be an Amazon SDE, you need to prove you can do C++ or Java first.

Example 1: Write a function to reverse a string.

Example Java code:

public static String reverse ( String s ) {

int length = s.length(), last = length – 1;

char[] chars = s.toCharArray();

for ( int i = 0; i < length/2; i++ ) {

char c = chars[i];

chars[i] = chars[last – i];

chars[last – i] = c;

}

return new String(chars);

}

Example output for “Madam, I’m Adam”: madA m’I ,madaM

Example 2: Write function to compute Nth fibonacci number:

Test harness output:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Example 3: Print out the grade-school multiplication table up to 12×12

Java: (similar for C/C++)

public static void multTables ( int max )

{

for ( int i = 1; i for ( int j = 1; j System.out.print ( String.format ( “%4d”, j * i ));

}

System.out.println();

}

}

Example output:

1 2 3 4 5 6 7 8 9 10 11 12

2 4 6 8 10 12 14 16 18 20 22 24

3 6 9 12 15 18 21 24 27 30 33 36

4 8 12 16 20 24 28 32 36 40 44 48

5 10 15 20 25 30 35 40 45 50 55 60

6 12 18 24 30 36 42 48 54 60 66 72

7 14 21 28 35 42 49 56 63 70 77 84

8 16 24 32 40 48 56 64 72 80 88 96

9 18 27 36 45 54 63 72 81 90 99 108

10 20 30 40 50 60 70 80 90 100 110 120

11 22 33 44 55 66 77 88 99 110 121 132

12 24 36 48 60 72 84 96 108 120 132 144

Example 4: Write a function that sums up integers from a text file, one int per line.

Java:

public static void sumFile ( String name ) {

try {

int total = 0;

BufferedReader in = new BufferedReader ( new FileReader ( name ));

for ( String s = in.readLine(); s != null; s = in.readLine() ) {

total += Integer.parseInt ( s );

}

System.out.println ( total );

in.close();

}

catch ( Exception xc ) {

xc.printStackTrace();

}

}

5: Write function to print the odd numbers from 1 to 99.

C/C++:

void printOdds() {

for (int i = 1; i < 100; i += 2) {

printf (“%dn”, i); // or cout << i << endl;

}

}

Java:

public static void printOdds() {

for (int i = 1; i < 100; i += 2) {

System.out.println ( i );

}

}

Example 6: Find the largest int value in an int array.

Java:

public static int largest ( int[] input ) {

int max = Integer.MIN_VALUE;

for ( int i = 0; i < input.length; i++ ) {

if ( input[i] > max ) max = input[i];

}

return max;

}

Example 7: Format an RGB value (three 1-byte numbers) as a 6-digit hexadecimal string.

Java:

public String formatRGB ( int r, int g, int b ) {

return (toHex(r) + toHex(g) + toHex(b)).toUpperCase();

}

public String toHex ( int c ) {

String s = Integer.toHexString ( c );

return ( s.length() == 1 ) ? “0” + s : s;

}

Or in Java 1.5:

public String formatRGB ( int r, int g, int b ) {

return String.format ( “%02X%02X%02X”, r, g, b );

}

Example output for (255, 0, 128):

You can ask any question you like; doesn’t have to be one of the ones above. They’re just examples.

Some properties of a good weeder phone-screen coding question are:

It’s simple. It has to be something that you should be able to solve, trivially, in about 2 minutes or less. Not too tricky. Basic stuff.

You’ve solved it. You shouldn’t ask a question unless you’ve solved it yourself recently, so you know it’s a reasonable question, and you can evaluate their answer to it. You should consider coding it yourself during the time you’ve given them to do it.

It has loops or recursion. Recursion is actually preferable. Being able to reason recursively or inductively is important for many areas of computing, including using heirarchical data representations (e.g. XML), distributed computing, searching, and sorting. Many candidates simply can’t think recursively, and this often goes undetected until interview-time. Try to find out at compile-time! Er, phone-screen time, that is.

It has formatted output. This is a basic skill, useful for debugging, simple report generation, and lots of other things. “printf” is a universal standard; it exists in C, C++, Java, Perl, Ruby, Python, and virtually every other mainstream language, at least as a library call. Like file I/O, it’s a good indicator as to whether the candidate has written “real” code before.

It has text-file I/O. Candidates who have worked in frameworks for too long often become unable to function as programmers outside that framework. Not being able to do simple file I/O is a common indicator that they’ve grown overly dependent on a particular framework.

It’s hard to cover all these things and still be a short weeder question. If you think of a question that has all these properties, let me know.

Area Number Two: Object-Oriented Programming

We shouldn’t hire SDEs (arguably excepting college hires) who aren’t at least somewhat proficient with OOP. I’m not claiming that OOP is good or bad; I’m just saying you have to know it, just like you have to know the things you can and can’t do at an airport security checkpoint.

Two reasons:

1) OO has been popular/mainstream for more than 20 years. Virtually every programming language supports OOP in some way. You can’t work on a big code base without running into it.

2) OO concepts are an important building block for creating good service interfaces. They represent a shared understanding and a common vocabulary that are sometimes useful when talking about architecture.

So you have to ask candidates some OO stuff on the phone.

a) Terminology

The candidate should be able to give satisfactory definitions for a random selection of the following terms:

  • class, object (and the difference between the two)
  • instantiation
  • method (as opposed to, say, a C function)
  • virtual method, pure virtual method
  • class/static method
  • static/class initializer
  • constructor
  • destructor/finalizer
  • superclass or base class
  • subclass or derived class
  • inheritance
  • encapsulation
  • multiple inheritance (and give an example)
  • delegation/forwarding
  • composition/aggregation
  • abstract class
  • interface/protocol (and different from abstract class)
  • method overriding
  • method overloading (and difference from overriding)
  • polymorphism (without resorting to examples)
  • is-a versus has-a relationships (with examples)
  • method signatures (what’s included in one)
  • method visibility (e.g. public/private/other)

These are just the bare basics of OO. Candidates should know this stuff cold. It’s not even a complete list; it’s just off the top of my head.

Again, I’m not advocating OOP, or saying anything about it, other than that it’s ubiquitious so you have to know it. You can learn this stuff by reading a single book and writing a little code, so no SDE candidate (except maybe a brand-new college hire) can be excused for not knowing this stuff.

I draw a distinction between “knows it” and “is smart enough to learn it.” Normally I allow people through for interviews if they’ve got a gap in their knowledge, as long as I think they’re smart enough to make it up on the job.

But for these five areas, I expect candidates to know them. It’s not just a matter of being smart enough to learn them. There’s a certain amount of common sense involved; I can’t imagine coming to interview at Amazon and not having brushed up on OOP, for example. But these areas are also so fundamental that they serve as real indicators of how the person will do on the job here.

b) OO Design

This is where most candidates fail with OO. They can recite the textbook definitions, and then go on to produce certifiably insane class designs for simple problems. For instance:

They may have Person multiple-inherit from Head, Body, Arm, and Leg.

They may have Car and Motorcycle inherit from Garage.

They may produce an elaborate class tree for Animals, and then declare an enum (“Lion = 1, Bear = 2”, etc.) to represent the type of each animal.

They may have exactly one static instance of every class in their system.

(All these examples are from real candidates I’ve interviewed in the past 3 weeks.)

Candidates who’ve only studied the terminology without ever doing any OOP often don’t really get it. When they go to produce classes or code, they don’t understand the difference between a static member and an instance member, and they’ll use them interchangeably.

Or they won’t understand when to use a subclass versus an attribute or property, and they’ll assert firmly that a car with a bumper sticker is a subclass of car. (Yep, 2 candidates have told me that in the last 2 weeks.)

Some don’t understand that objects are supposed to know how to take care of themselves. They’ll create a bunch of classes with nothing but data, getters, and setters (i.e., basically C structs), and some Manager classes that contain all the logic (i.e., basically C functions), and voila, they’ve implemented procedural programming perfectly using classes.

Or they won’t understand the difference between a char*, an object, and an enum. Or they’ll think polymorphism is the same as inheritance. Or they’ll have any number of other fuzzy, weird conceptual errors, and their designs will be fuzzy and weird as well.

For the OO-design weeder question, have them describe:

  • What classes they would define.
  • What methods go in each class (including signatures).
  • What the class constructors are responsible for.
  • What data structures the class will have to maintain.
  • Whether any Design Patterns are applicable to this problem.

Here are some examples:

Design a deck of cards that can be used for different card game applications.

Likely classes: a Deck, a Card, a Hand, a Board, and possibly Rank and Suit. Drill down on who’s responsible for creating new Decks, where they get shuffled, how you deal cards, etc. Do you need a different instance for every card in a casino in Vegas?

Model the Animal kingdom as a class system, for use in a Virtual Zoo program.

Possible sub-issues: do they know the animal kingdom at all? (I.e. common sense.) What properties and methods do they immediately think are the most important? Do they use abstract classes and/or interfaces to represent shared stuff? How do they handle the multiple-inheritance problem posed by, say, a tomato (fruit or veggie?), a sponge (animal or plant?), or a mule (donkey or horse?)

Create a class design to represent a filesystem.

Do they even know what a filesystem is, and what services it provides? Likely classes: Filesystem, Directory, File, Permission. What’s their relationship? How do you differentiate between text and binary files, or do you need to? What about executable files? How do they model a Directory containing many files? Do they use a data structure for it? Which one, and what performance tradeoffs does it have?

Design an OO representation to model HTML.

How do they represent tags and content? What about containment relationships? Bonus points if they know that this has already been done a bunch of times, e.g. with DOM. But they still have to describe it.

The following commonly-asked OO design interview questions are probably too involved to be good phone-screen weeders:

Design a parking garage.

Design a bank of elevators in a skyscraper.

Model the monorail system at Disney World.

Design a restaurant-reservation system.

Design a hotel room-reservation system.

A good OO design question can test coding, design, domain knowledge, OO principles, and so on. A good weeder question should probably just target whether they know when to use subtypes, attributes, and containment.

Area Number Three: Scripting and Regular Expressions

Many C/C++/Java candidates, even some with 10+ years of experience, would happily spend a week writing a 2,500-line program to do something you could do in 30 seconds with a simple Unix command.

I now pose the following question to ALL candidates, whether on the phone or in an interview, because it eliminates so many of them:

Last year my team had to remove all the phone numbers from 50,000 Amazon web page templates, since many of the numbers were no longer in service, and we also wanted to route all customer contacts through a single page.

Let’s say you’re on my team, and we have to identify the pages having probable U.S. phone numbers in them. To simplify the problem slightly, assume we have 50,000 HTML files in a Unix directory tree, under a directory called “/website”. We have 2 days to get a list of file paths to the editorial staff. You need to give me a list of the .html files in this directory tree that appear to contain phone numbers in the following two formats: (xxx) xxx-xxxx and xxx-xxx-xxxx.

How would you solve this problem? Keep in mind our team is on a short (2-day) timeline.

Here are some facts for you to ponder:

Our Contact Reduction team really did have exactly this problem in 2003. This isn’t a made-up example.

Someone on our team produced the list within an hour, and the list supported more than just the 2 formats above.

About 25% to 35% of all software development engineer candidates, independent of experience level, cannot solve this problem, even given the entire interview hour and lots of hints.

I take as much time as necessary to explain the problem to candidates, to ensure that they understand it and can paraphrase the problem requirements correctly.

For the record, I’m not being tricky here. Once candidates start down the wrong path (i.e. writing a gigantic C++ program to open every file and parse character by character, using a home-grown state machine), I stop them, tell them this will take too long, and ask if there are any other possibilities. I ask if there are any tools or utilities that might be of use. I give them plenty of hints, and ultimately I tell them the answer.

Even after I tell them the answer, they often still don’t get it.

Here’s one of many possible solutions to the problem:

grep -l -R –perl-regexp “b((d{3})s*|d{3}-)d{3}-d{4}b” * > output.txt

But I don’t even expect candidates to get that far, really. If they say, after hearing the question, “Um… grep?” then they’re probably OK. I can ask them for the approximate syntax for the regular expression to use, and as long as they have a reasonable clue, I’m fine with it. Heck, if they can tell me where they’d look to find the syntax, I’m fine with it.

They can also use find, or write a Perl script (or awk or bash or etc.). Anything that shows they have even the tiniest inkling of why Unix is Unix.

They can even write a Java or C++ program, provided they can actually write an entire working program in, say, half an hour or less, on the board, or at least convince me that they will get it working quickly. But I’ve only ever had that happen once; an insanely good C++ programmer burned through a 175-line C++ program on the whiteboard that more or less solved it. We made him an offer. But usually they throw in the towel when they find out they have to remember how to do file I/O, or traverse a directory tree.

For what it’s worth, this failure mode is unique to Java and C/C++ programmers. Perl programmers laugh and solve it in 30 seconds or less. I have some easy questions that make Perl programmers cry, but this isn’t one of them.

In my experience, a programmer who only knows one language (where C and C++ count as one language for this exercise) is usually completely lost in one of these Five Essential Areas.

You don’t necessarily have to ask the HTML phone-number question. Another one I used to ask, one that worked equally well, was:

Let’s say you’re on my team, and I’ve decided I’m a real stickler for code formatting. But I’ve got peculiar tastes, and one day I decide I want to have all parentheses stand out very clearly in your code.

So let’s say you’ve got a set of source files in C, C++, or Java. Your choice. And I want you to modify them so that in each source file, every open- and close-paren has exactly one space character before and after it. If there is any other whitespace around the paren, it’s collapsed into a single space character.

For instance, this code:

foo (bar ( new Point(x, graph.getY()) ));

Would be modified to look like this:

foo ( bar ( new Point ( x, graph.getY ( ) ) ) ) ;

I tell you (as your manager) that I don’t care how you solve this problem. You can take the code down to Kinko’s Copies and manually cut and paste the characters with scissors if you like.

How will you solve this problem?

Same thing, more or less. You’d do it with a Unix command like sed (using a regular expression), or do it in your editor using a regex, or write a quick Ruby script, whatever. I’d even accept having them use a source-code formatter, provided they can tell me in detail how to use it, during the interview (to a level of detail that convinces me they’ve used it before.)

There are all sorts of variations on this problem. Generally you want to come up with a real-life scenario that involves searching text files for patterns, and see if the candidate wants to solve it by writing a giant chunk of C++ or Java code.

Area Number Four: Data Structures

SDE candidates need to demonstrate a basic understanding of the most common data structures, and of the fundamentals of “big-O” algorithmic complexity analysis.

Here’s what they need to know about big-O. They need to know that algorithms usually fall into the following performance classes: constant-time, logarithmic, linear, polynomial, exponential, and factorial.

For the standard data structures in java.util, STL, or those built into a higher-level language, they need to know the big-O complexity for the operations on those data structures. Example: they should know that finding an element in a hashtable is usually constant-time, that finding an element in a balanced binary tree is order log(n), that finding an element in a linked list is order N, and that finding an element in a sorted array is order log(n). Similarly for insert/update/delete operations.

And they should be able to explain why each operation falls into a particular complexity class. For instance: “Computing a hash value doesn’t depend on the number of items in the hashtable.” Or: “you have to search the entire linked list, even if it’s sorted, to find an arbitrary element in it.” No math needed, no proofs, just explanations.

The (concrete) data structures they absolutely must understand are these:

1) arrays – I’m talking about C-language and Java-language arrays: fixed-sized, indexed, contiguous structures whose elements are all of the same type, and whose elements can be accessed in constant time given their indices.

2) vectors – also known as “growable arrays” or ArrayLists. Need to know that they’re objects that are backed by a fixed-size array, and that they resize themselves as necessary.

3) linked lists – lists made of nodes that contain a data item and a pointer/reference to the next (and possibly previous) node.

4) hashtables – amortized constant-time access data structures that map keys to values, and are backed by a real array in memory, with some form of collision handling for values that hash to the same location.

5) trees – data structures that consist of nodes with optional data elements and one or more child pointers/references, and possibly parent pointers, representing a heirarchical or ordered set of data elements.

6) graphs – data structures that represent arbitrary relationships between members of any data set, represented as networks of nodes and edges.

There are, to be sure, many other important data structures one should know about, but not knowing about the six listed above is inexcusable, and grounds for rejection in a phone screen.

Candidates should be able to describe, for any of the data structures above:

what you use them for (real-life examples)

why you prefer them for those examples

the operations they typically provide (e.g. insert, delete, find)

the big-O performance of those operations (e.g. logarithmic, exponential)

how you traverse them to visit all their elements, and what order they’re visited in

at least one typical implementation for the data structure

Candidates should know the difference between an abstract data type such as a Stack, Map, List or Set, and a concrete data structure such as a singly-linked list or a hash table. For a given abstract data type (e.g. a Queue), they should be able to suggest at least two possible concrete implementations, and explain the performance trade-offs between the two implementations.

Example weeder questions:

1) What are some really common data structures, e.g. in java.util?

2) When would you use a linked list vs. a vector?

3) Can you implement a Map with a tree? What about with a list?

4) How do you print out the nodes of a tree in level-order (i.e. first level, then 2nd level, then 3rd level, etc.)

5) What’s the worst-case insertion performance of a hashtable? Of a binary tree?

6) What are some options for implementing a priority queue?

And so on. Just a few quick questions should cover this area, provided you don’t focus exclusively on linear ordered sequences (lists, arrays, vectors and the like).

Area Number Five: Bits and Bytes

This area is fairly contentious, at least inasmuch as people who don’t know this area claim you don’t need to know it.

(Hint: that’s true for everything. Nobody likes to admit they don’t know something you need to know. I’ll start: I should know more about math; it’s inexcusable. I’m doing all kinds of stuff the long, slow, dumb way because of my rusty math skills. But at least I admit it, and I’ve been studying my math books semi-regularly in an attempt to repair my skills.)

Candidates do need to know about bits and bytes, at least at the level that I’m outlining here. Otherwise they’re prone to having an integer-overflow error in their code that brings the website down and costs us millions. Or spending a week trying to decode a serialized object they’re debugging. Or whatever. Computers don’t have ten fingers; they have one. So people need to know this stuff.

Candidates should know what bits and bytes are. They should be able to count in binary; e.g. they should be able to tell you what 2^5 or 2^10 is, in decimal. They shouldn’t stare blankly at you when you ask with 2^16 is. It’s a special number. They should know it.

They should know at least the logical operations AND, OR, NOT, and XOR, and how to express them in their favorite/strongest programming language.

They should understand the difference between a bitwise-AND and a logical-AND; similarly for the other operations.

Candidates should know the probable sizes of the primitive data types for a standard 32-bit (e.g. Intel) architecture.

If they’re a Java programmer, they should know exactly what the primitive types are (byte, short, int, long, float, double, char, boolean) and, except for boolean, exactly how much space is allocated for them per the Java Language specification.

Everyone should know the difference between signed and unsigned types, what it does to the range of representable values for that type, and whether their language supports signed vs. unsigned types.

Candidates should know the bitwise and logical operators for their language, and should be able to use them for simple things like setting or testing a specific bit, or set of bits.

Candidates should know about the bit-shift operators in their language, and should know why you would want to use them.

A good weeder question for this area is:

Tell me how to test whether the high-order bit is set in a byte.

Another, more involved one is:

Write a function to count all the bits in an int value; e.g. the function with the signature int countBits(int x)

Another good one is:

Describe a function that takes an int value, and returns true if the bit pattern of that int value is the same if you reverse it (i.e. it’s a palindrome); i.e. boolean isPalindrome(int x)

They don’t have to code the last two, just convince you they’d take the right approach. Although if you have them code it correctly, it can count for your Coding weeder question too.

C/C++ programmers should know about the sizeof operator and how (and why/when) to use it. Actually, come to think of it, everyone should know this.

All programmers should be able to count in hexadecimal, and should be able to convert between the binary, octal, and hex representations of a number.

Special Fast-Track Version

That’s it for the Five Essential Phone Screen Questions. Hope ya liked it.

As a special reward for reading this far, here’s a special Bonus Feature: a set of all-too-common answers that are almost always indicators of certain failure during our interviews. Even if I’m not on the loop!

Bad Sign #1:

Me: So! What languages have you used, starting with your strongest?

Them: (briskly) C, C++.

Me: (long, pregnant pause)

Them: (waiting patiently for me to continue)

Me: Any others?

Them: Nope. C, C++.

Translation: (in thick Southern drawl) “We got both kinds of music here: country and western.”

Probable failure modes for this candidate:

Will fail the HTML-phone-number question and the OO design question (but will get the OO terminology definitions mostly right.)

Bad Sign #1a:

Me: So! What languages are you most familiar/proficient with?

Them: (worried) I’ve done mostly Java lately.

Me: (long, pregnant pause)

Them: Yeah, um, Java.

Me: Any others?

Them: Um, I did C in school a long time ago, but… pretty much mostly Java now.

Translation: “Country and Western were both too hardcore for me. I got beat up in a bar.”

Probable failure modes for this candidate: Will fail the bits and bytes questions, the HTML-phone-number question, and most of the data structures questions.

Bad Sign #2:

Me: So! What data structures do we have available to us, as programmers?

Them: Arrays, queues, vectors, stacks, lists, um, linked lists…

Me: OK, any others?

Them: Um, doubly-linked lists, and, uh, array lists.

Me: Have you ever used a tree?

Them: Oh! (laughs) Yeah, um, I forgot about those.

Translation: “My family tree doesn’t branch.”

Probable failure modes for this candidate: Very likely to fail data structures questions. Will fail any recursive problem, even a simple one like printing the elements of a linked list recursively. Will fail the HTML-phone-number question, since they obviously haven’t ever used Perl if “hash” didn’t leap to mind.

Bad Sign #3:

Me: So! What the the primitive types in Java (or C++)?

Them: Ummmm, there’s, um, int. And, uh, double.

Me: Any others?

Them: Shoot, I’m drawing a blank right now. Um, String?

Translation: “C made my head hurt. Java is like sweet, sweet aspirin.”

Probable failure modes for this candidate: Will fail bits and bytes questions, and probably just about everything else as well.

Bad Sign #4:

Me: So! What text-editor do you use?

Them: Visual Studio.

Me: OK. What about on Unix?

Them: On Unix I use vi.

Me: Er, yeah, vi is cool… ever used VIM?

Them: No, just vi. Always worked just fine for me.

Translation: “Sometimes I type with my elbows when my hands are tired. It’s just as fast.”

Probable failure modes for this candidate: Will likely fail the HTML-phone-number question. Might pass the interviews, but will need to be scheduled in geologic eras.

Bad Sign #5:

Me: So! What did you study in your Operating Systems class?

Them: Oh, that was a long time ago. I can hardly remember. Hehe.

Me: How long ago was it?

Them: 2 years.

Translation: “I want to use my MBA skills in a dynamic management role. When’s lunch?”

Probable failure modes for this candidate: Will probably fail the coding question. Probably any OS questions, too.

All my Insta-Bad Signs above are cliches, in that I’ve heard these answers from at least 10 to 15 candidates (per question!), none of whom ever got an offer from us. I tend to ask questions like these as a matter of course now.

Summary

This stuff is the ABC’s for programmers. Actually it’s only going up through maybe J or K; it’s not even halfway through the alphabet. But most programmers out there in the Big Wide World will fail utterly in at least one of these areas.

Please cover all five areas if you’re a phone screener. If you’re the second screener, ask if you don’t see evidence of them in the first screener’s notes. (And then follow up and remind the first screener they should have asked these things.)

 

Arrays

0

Array Data Structure

Introduction

An array is an aggregate data structure that is designed to store a group of objects of the same or different types. Arrays can hold primitives as well as references. The array is the most efficient data structure for storing and accessing a sequence of objects.

Here is the list of most important array features you must know (i.e. be able to program)

  • copying and cloning
  • insertion and deletion
  • searching and sorting

You already know that the Java language has only two data types, primitives and references. Which one is an array? Is it primitive? An array is not a primitive data type – it has a field (and only one), called length. Formally speaking, an array is a reference type, though you cannot find such a class in the Java APIs. Therefore, you deal with arrays as you deal with references. One of the major diffeences between refeences and primituives is that you cannot copy arrays by assigning one to another:

int[] a = {9, 5, 4};
int[] b = a;

The assignment operator creates an alias to the object, like in the picture below

 

Since these two references a and b refer to the same object, comparing them with the double equal sign “==” will always return true. In the next code example,

int [] a = {1,2,3};
int [] b = {1,2,3};

a and b refer to two different objects (though with identical contents). Comparing them with the double equal sign will return false. How would you compare two objects with identical contents? In short, using theequals method. For array comparison, the Java APIs provides the Arrays class.

The Arrays class

The java.util.Arrays class is a convenience class for various array manipulations, like comparison, searching, printing, sorting and others. Basically, this class is a set of static methods that are all useful for working with arrays. The code below demonstrates a proper invocation of equals:

int[] a = {1,2,3};
int[] b = {1,2,3};
if( Arrays.equals(a, b) )
   System.out.println("arrays with identical contents");

Another commonly used method is toString() which takes care of of printing

int[] a = {1,2,3};
System.out.println(Arrays.toString(a));

Here is the example of sorting

int[] a = {3,2,1};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

In addition to that, the class has other utility methods for supporting operations over multidimensional arrays.

Copying arrays

There are four ways to copy arrays

  1. using a loop structure
  2. using Arrays.copyOf()
  3. using System.arraycopy()
  4. using clone()

The first way is very well known to you

int[] a = {1, 2, 3};
int[] b = new int[a.length];
for(int i = 0; i ‹ a.length; i++) b[i] = a[i];

The next choice is to use Arrays.copyOf()

int[] a = {1, 2, 3};
int[] b = Arrays.copyOf(a, a.length);

The second parameter specifies the length of the new array, which could either less or equal or bigger than the original length.

The most efficient copying data between arrays is provided by System.arraycopy() method. The method requires five arguments. Here is its signature

public static void arraycopy(Object source,
                             int srcIndex,
                             Object destination,
                             int destIndex,
                             int length)

The method copies length elements from a source array starting with the index srcIndex to a new array destination at the index destIndex.The above code example can be rewritten as it follows

int[] a = {1, 2, 3};
int[] b = new int[a.length];
System.arraycopy(a, 0, b, 0, 3)

And the last copying choice is the use of cloning. Cloning involves creating a new array of the same size and type and copying all the old elements into the new array. The clone() method is defined in the Objectclass and its invocation is demonstrated by this code segment

int[] a = {1, 2, 3};
int[] b = (int[]) a.clone();

Note, that casting (int[]) is the must.

Examine the code in ArrayCopyPrimitives.java for further details.

Insertion and Deletion

Arrays in Java have no methods and only one immutable field length. Once an array is created, its length is fixed and cannot be changed. What do you do to resize the array? You allocate the array with a different size and copy the contents of the old array to the new array. This code example demonstrates deletion from an array of primitives

public char[] delete(char[] data, int pos)
{
	if(pos >= 0 && pos < data.length)
	{
		char[] tmp = new char[data.length-1];
		System.arraycopy(data, 0, tmp, 0, pos);
		System.arraycopy(data, pos+1, tmp, pos, data.length-pos-1);
		return tmp;
	}
	else
		return data;
}

The first arraycopy copies the elements from index 0 to index pos-1, the second arraycopy copies the elements from index pos+1 to data.length.

Examine the code in ArrayDemo.java for further details.

The ArrayList class

The java.util.ArrayList class supports an idea of a dynamic array – an array that grows and shrinks on demand to accomodate the number of elements in the array. Below is a list of commonly used methods

  • add(object) – adds to the end
  • add(index, object) – inserts at the index
  • set(index, object) – replaces at the index
  • get(index) – returns the element at that index
  • remove(index) – deletes the element at that index
  • size() – returns the number of elements

The following code example will give you a heads up into how some of them are used.

/* ADD */
      ArrayList<Integer> num = new ArrayList<Integer>();
      for(int i = 0; i < 10; i++) num.add(i);
      System.out.println(num);

/* REMOVE even integers */
      for(int i = 0; i < num.size(); i++)
      	if(num.get(i)%2 == 0) num.remove(i);
      System.out.println(num);

Copying arrays of objects

This topic is more complex for understanding.. Let us start with a simple loop structure

Object[] obj1 = {new Integer(10),
                new StringBuffer("foobar"),
                new Double(12.95)};
Object[] obj2 = new Object[obj1.length];
for(int i = 0; i ‹ obj1.length; i++)
	obj2[i] = obj1[i];

At the first glance we might think that all data is copied. In reality, the internal data is shared between two arrays. The figure below illustrates the inner structure

The assignment operator obj2[i] = obj1[i] is a crucial part of understanding the concept. You cannot copy references by assigning one to another. The assignment creates an alias rather than a copy. Let us trace down changes in the above picture after execution the following statements

obj1[0] = new Integer(5);

and ((StringBuffer) obj1[1]).append('s');

As you see, obj1[0] and obj2[0] now refer to different objects. However, obj1[1] and obj2[1] refer to the same object (which is “foobars”). Since both arrays shares the data, you must be quite careful when you modify your data, because it might lead to unexpected effects.

The same behavior will take place again, if we use Arrays.copuyOf()System.arraycopy() and clone(). Examine the code example ArrayCopyReferences.java for further details.

Multi-dimensional arrays

In many practical application there is a need to use two- or multi-dimensional arrays. A two-dimensional array can be thought of as a table of rows and columns. This creates a table of 2 rows and 4 columns:

int[][] ar1 = new int[2][4];

You can create and initialize an array by using nested curcly braces. For example, this creates a table of 3 rows and 2 columns:

int[][] ar2 = {{1,2},{3,4},{5,6}};

Generally speaking, a two-dimensional array is not exactly a table – each row in such array can have a different length. Consider this code fragment

Object[][] obj = {{new Integer(1),new Integer(2)},
                  {new Integer(10), "bozo", new Double(1.95)}};

The accompanying picture sheds a bit of light on internal representation

 

From the picture you clearly see that a two-dimensional array in Java is an array of arrays. The array obj has two elements obj[0] and obj[1] that are arrays of length 2 and 3 respectively.

Cloning 2D arrays

The procedure is even more confusing and less expected. Consider the following code segment

Object[][] obj = {{new Integer(1),new Integer(2)},
                  {new Integer(10), "bozo", new Double(1.95)}};

Object[][] twin = (Object[][]) obj.clone();

The procedure of clonig 2d arrays is virtually the same as cloning an array of references. Unfortunately, built-in clone() method does not actualy clone each row, but rather creates references to them Here is a graphical interpretation of the above code

Let us change the value of obj[1][1]

obj[1][1] = "xyz";

This assignment effects the value of twin[1][1] as well

 

Such a copy is called a “shallow” copy. The default behavior of clone() is to return a shallow copy of the object. If we want a “deep” copy instead, we must provide our own implementation by overriding Object’sclone() method.

The idea of a “deep” copy is simple – it makes a distinct copy of each of the object’s fields, recursing through the entire object. A deep copy is thus a completely separate object from the original; changes to it don’t affect the original, and vise versa. In relevance to the above code, here is a deep clone graphically

 

Further, making a complete deep copy is not always needed. Consider an array of immutable objects. As we know, immutable objects cannot be modified, allowing clients to share the same instance without interfering with each other. In this case there is no need to clone them, which leads to the following picture

 

Always in this course we will create data structures of immutable objets, therefore implementing the clone method will require copying a structure (a shape) and sharing its internal data. We will discuss these issues later on in the course.


Victor S.Adamchik, CMU, 2009