interview questions and answers

Computer System Structures Interview Questions Part5

2007-10-27T12:14:00.001-07:00

59) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of millisecs taken to transfer all the bytes in the hard disk?
1) 500 x 50 x 10 x 10
2) 500 x 50 x 150 x 10
3) 500 x 50 x 150 x 10 x10
4) 500 x 150 x 10 x10
Answer: 3
60) From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of millisecs taken to transfer the bytes from one single platter?
1) 500 x 50 x 150 x 10
2) 500 x 50 x 10
3) 500 x 150 x 50 x 10
4) 500 x 150 x 10 x10
Answer: 1
61) From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of milliseconds taken to transfer all the bytes from a cylinder cylinder?
1) 500 x 50 x 10 x 10
2) 500 x 150 x 50
3) 500 x 150 x 10 x10
4) 50 x 150 x 10 x10
Answer: 1
62) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
Total number of bytes in a cylinder is ________
13) 512X 63X 5
14) 512X 50X 5
15) 512X 63 X 50
16) 512 X 5
Answer: 1
63) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
The total number of bytes/platter is _____
17) 512X 63X 5
18) 512X 50X 5
19) 512X 63 X 50
20) 512 X 5
Answer: 3
64) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
The total number of cylinders in the hard disk is_______.
1) 63
2) 50
3) 512
4) 63 X 5
Answer: 2
65)The size of single unit of allocation on disk is called ____.
5) Sector size
6) Page size
7) Segment size
8) File size
Answer: 1
66) MS-DOS supports multiprogramming fully. True / False?
Answer: False
67) Which of the following is crucial time while accessing data on the disk?

1) Seek time
2) Rotational time
3) Transmission time
4) Waiting time

Ans: 1

68) A __________ is software that manages the time of a microprocessor to ensure that all time critical events are processed as efficiently as possible. This software allows the system activities to be divided into multiple independent elements called tasks.

1) Kernel
2) Shell
3) Processor
4) Device Driver

Ans: - 1

Computer System Structures Interview Questions Part4

2007-10-27T12:13:00.001-07:00

47) ________ is/are only storage media that the CPU can access directly.
1) Main memory
2) Storage memory
3) both
4) None
Answer: 1
Level:1

48) _________ is the extension of main memory that provides large non volatile storage capacity.
1) Secondary storage
2) RAM
3) Cache
4) None
Answer: 1
Level:1

49) Which of the following is a volatile storage medium?
1) Hard disc
2) RAM
3) Magnetic tapes
4) Compact disc
Answer: 2
Level:1

50) Which of the following is a non- volatile storage medium?
1) Cache
2) RAM
3) CPU Registers
4) Hard disc
Answer: 4
Level:1

51) DMA stands for______
1) Direct Memory Access
2) Directory Memory Access
3) Differential Memory Access
4) All the above
Answer: 1
Level:1

52) A _____ is a memory that stores data while they are transferred between two devices or between a device and an application.
1) Buffer
2) Cache
3) Hard disc
4) Compact disc
Answer: 1
Level:1

53) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Total number of bytes in the hard disk?
1) 500 x 50 x 10
2) 500 x 50 x 150
3) 500 x 50 x 150 x 10
4) 500 x 150 x 10
Answer: 3
54) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10

Total number bytes in a platter?
1) 500 x 50 x 150
2) 500 x 50 x 10
3) 500 x 150 x 50 x 10
4) 500 x 150 x 10
Answer: 1
55) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Total number of bytes per cylinder?
1) 500 x 50 x 10
2) 500 x 150 x 50
3) 500 x 150 x 10
4) 50 x 150 x 10
Answer: 1
56) Question: From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number of bytes in the hard disk?
1) 750 x 100 x 50
2) 750 x 100 x 150
3) 750 x 100 x 150 x 50
4) 750 x 150 x 50
Answer: 3
57) From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number bytes in a platter?
1) 750 x 100 x 150
2) 750 x 100 x 50
3) 750 x 150 x 100 x 50
4) 750 x 150 x 50
Answer: 1
58) From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number of bytes per cylinder?
1) 750 x 100 x 50
2) 750 x 150 x 100
3) 750 x 150 x 50
4) 100 x 150 x 50
Answer: 1

Computer System Structures Interview Questions Part3

2007-10-27T12:12:00.001-07:00

24) Recursion or large arrays of local variables avoided by kernel programmers because The kernel stack is usually a limited resource. A stack overflow crashes the entire machine.
T/F
Answer: True
Exp: by def
Level:1

25) What is the purpose of system calls?
a) system calls allow user-level processes to request services of the operating system.
b) system calls acts as traps.
c) both a and b
d) none of the above
answer : a
Exp: by def
Level:1

26) What are the major activities of an operating system in regard to process management?
a. The creation and deletion of both user and system processes
b. The suspension and resumption of processes
c. The provision of mechanisms for process synchronization
d. The provision of mechanisms for process communication
e. The provision of mechanisms for deadlock handling

a) a,b,c
b) a,b,d
c) a,b,c,e
d) a,b,c,d,e
answer:d
Level:1

27) What are the major activities of an operating system in regard to memory management?
a. Keep track of which parts of memory are currently being used and by whom.
b. Decide which processes are to be loaded into memory when memory space becomes available.
c. Allocate and deallocate memory space as needed.
d. Interrupt processes when executing

1) a and b
2) a,b and c
3) a and c
4) Only c

Answer:2
Level:1

28) The major activities of an operating system in regard to secondary-storage management?
a) Free-space management.
b) Storage allocation.
c) Interrupt processes while executing
d) Disk scheduling.

1) a and b
2) a,b and c
3) a,b and d
4) Only c

Answer:3
Level:1

29) Which of the following are true regarding the command interpreter?
a) the command interpreter reads commands from the user or from a file of commands and executes them
b) command interpreter is subject to changes
c) acts as an interface between primary and secondary memory

1) a and b
2) a,b and c
3) a and c
4) Only a

. Answer:1
It reads commands from the user or from a file of commands
and executes them, usually by turning them into one or more system
calls. It is usually not part of the kernel since the command interpreter
is subject to changes.
Level:2

30) What system calls have to be executed by a command interpreter or shell in order to start a new process in unix?
a) fork
b) ps
c) fork followed by exec
d) none of the above
Answer:c
process. The fork call clones the currently executing process, while the exec call overlays a new process based on a different executable over the calling process.
Level:1

31) Which of the following are trueregarding system programs and system calls?
a) System programs can be thought of as bundles of useful
system calls.
b) system calls provide basic functionality to users so that users do not need to write their own programs to solve common problems.
c) system calls can be defined by the user

1) a and b
2) a,b and c
3) a,b and d
4) Only b

Answer:1
Level:2

32) What is the main advantage of the layered approach to system design?
a) the system is easier to debug and modify because changes affect only limited sections of the system rather than touching all sections of the operating system.
b) Information is kept only where it is needed and is accessible only within a defined and restricted area, so any bugs affecting that data must be limited to a specific module or layer. c) microkernel approach helps increases the degree of multiprogramming.

1) a,b,c
2) a,b
3) Only a
4) None

Answer: 2
Level:2

33) what are the services provided by an operating system.
a. Program execution.
b. I/O handling
c. File-system manipulation.
d. commmunications
e. error detection

a) a,b,c,d
b) b,c,d,e
c) a,b,c,d,e
d) b,c,e
Answer:c
Level:1

34) What are the main advantages of the microkernel approach to system design?

a) adding a new service does not require modifying the kernel
(b) it is more secure as more operations are done in user mode than in kernel mode
(c) microkernel approach helps increases the degree of multiprogramming.
d) a simpler kernel design and functionality typically results in a more reliable operating system.

1) a,b,d
2) b,c,d
3) a,b,c,d
4) Only a

Answer:1
Level:2

35) some systems store the operating system in firmware, and others on disk?
for PDAs,cellular telephones etc a disk with a file system may be not be available for the device.hence they are stored in firmaware.
T/F.
Answer: True
Level:2

36) How could a system be designed to allow a choice of operating systems to boot from? What would the bootstrap program need to do?
a) during boot-up, a special program (which we will call the boot manager) will determine which operating system to boot into.
b) the boot-strap loader will load the operating system selected at the start-up.
c) only a
d) both a and b.

Answer:c

Exp: Consider a system that would like to run both Windows
XP and three different distributions of Linux (e.g., RedHat, Debian, and
Mandrake). Each operating system will be stored on disk. During system
boot-up, a special program (which we will call the boot manager) will
determine which operating system to boot into. This means that rather
initially booting to an operating system, the boot manager will first run
during system startup. It is this boot manager that is responsible for
determining which system to boot into. Typically boot managers must
be stored at certain locations of the hard disk to be recognized during
system startup. Boot managers often provide the user with a selection of
systems to boot into; boot managers are also typically designed to boot
into a default operating system if no choice is selected
Level:2

37) The following are the secondary storage media.
1) Magnetic tapes
2) Magnetic disks
3) Ram
4) None

Answer: 1 and 2
Level:1

38) Which of the following are Non volatile storage devices
a) Magnetic Tapes
b) Main memory
c) Optical disk
d) Secondary Memory

1) a and b
2) a,b and c
3) a,b and d
4) Only c

Answer: 3
Level:1

39) Electronic disk, Main memory, Magnetic disk and Cache are volatile. True/False
Answer: False
Level:1

40) ______: a secondary storage device, which holds data in bulk and it, holds data in magnetic medium of the disk.
1) Hard disc
2) Compact disc
3) RAM
4) CPU Registers
Answer: 1
Level:1

41) A ________ is a secondary (optical) storage device.
1) Hard disc
2) Compact disc
3) RAM
4) CPU Register
Answer: 2
Level:1

42) ________ is the type of memory access in main memory (RAM).
1) Sequential access
2) DMA
3) Both
4) None
Answer: 2
Level:1

43) Which of the following is a volatile storage medium?
1) Hard disc
2) Cache
3) Magnetic tapes
4) Compact disc
Answer: 2
Level:1

44) The _________ is the additional time waiting for the disc to rotate the desired sector to the disc head
1) Rotational latency
2) Bandwidth
3) Seek time
4) None
Answer: 1
Level:1

45) ________: keep in memory only those instructions and data that are needed at any given time.
Needed when the process is larger than the amount of memory allocated to it.
1) Overlays
2) Studs
3) Cache
4) None
Answer: 1
Level:2

46) For Virtual memory implementation the OS uses ________
1) Compact disc
2) Floppy drives
3) Hard disc
4) Cache
Answer: 3
Level:2

Computer System Structures Interview Questions Part12

2007-10-27T12:11:00.000-07:00

10) the memory hierarchy is
a. Registers, cache, main memory, magnetic disk, CDROM, tape
b. Cache, , main memo ry, magnetic disk, Registers, CDROM, tape
c. Cache, Registers, main memory, magnetic disk, CDROM, tape
4) Main memory, Registers, cache, magnetic disk, CDROM, tape
Answer: 1
Exp: internal architecture
Level:2

11) The CPU uses poling to watch the control bit, constantly looping to see whether the device is ready. This method of operations is called___________
1) Progrmmed I/O
2) I/O interrupt
3) I/O operation request
4) None
Answer: 1
Exp: by the definition of the Programmed I/O
Level:2

12) The memory buffer used to accommodate a speed differential is called a _____
1) Main memory
2) Cache memery
3) CPU Register
4) Optical disk
Answer: 2
Exp: by def
Level:1

13) The set of tracks that are at one arm position forms a ________
1) sector
2) cylinder
3) platter
4) Spindel
Answer: Cylinder
Exp: by def
Level:1

14) ____ is the rate at which data flow between the drive and the computer.
1) bit rate
2) transfer rate
3) data rate
4) None
Answer: Transfer rate
Exp: by def
Level:1
15) The positioning time is also called ___
a. Seek time
b. Rotational latency
c. Transfer rate
d. Random access time
Answer:4
Exp: ( by definition of random access time)
Level:1

16) Time to move the disc arm to the desired cylinder is called____
1) seek time
2) wait time
3) turn around time
4) None
Answer: Seek time
Exp: ( by definition of the seek time)
Level:1

17) The time for the desired sector to rotate to the disc head is called ____
1) seek time
2) rotational latency
3) sweep time
4) None
Answer: Rotational latency
Exp: ( by definition of rotational latency)
Level:1

18) Even though disc platters are coated with a thin protective layer, sometimes the head will damage the magnetic surface. This accident is called______
1) system crash
2) hardware crash
3) head crash
4) None
Answer: Head crash
Exp: by def
Level:1

19) EIDE stands for
1) Extended indexed directory extensions
2) Enhanced Integrated Drive Electronics
3) Enhanced Integrated Disk Electronics
4) None
Answer: 2
Exp: acronym
Level:2

20) Cache memory is divided into (and loaded in) blocks also called ________
a. Cache blocks
b. Cache lines
c. Both the above
d. None of the above
Answer: 2
Exp: by def
Level:1

21) Modem can convert
1) Digital data to analog signals
2) Analog signals to digital signals.
3) Both the above
4) 2 only
Answer: 3
Exp:n by def

Level:1

22) ______________is the rapid switching of the CPU between processes given the illusion of all processes running concurrently.
a. Multiprogramming
b. Multitasking
c. Timesharing
d. None
Answer: a and b
Exp: by def
Level:1

23) Which of the following instructions (or instruction sequences) should only be allowed in kernel mode?
1. Disable all interrupts.
2. Read the time of day clock.
3. Set the time of day clock.
4. Change the memory map.
5. Write to the hard disk controller register.
6. Write all buffered blocks associated with a file back to disk (fsync).
1) 1,3,4,5 need to be restricted to kernel mode.
2) 1, 6, 3, 2
3) 1, 2, 3, 4, 5
4) 3, 4, 1, 2
Answer: 1
Exp: properties of the kernel mode
Level:2

Computer System Structures Interview Questions Part1

2007-10-27T11:57:00.000-07:00

1) Which program gets loaded first when a computer is booted?
1) Operating System
2) Bootstrap loader
3) Device drivers
4) All of the above

Answer: 2
Exp: Bootstrap loader is the first program to be loaded into main memory from the ROM
Level:2

2) System Call is also known as?
1) Monitor call
2) User call
3) Software call
4) None of the above

Answer: 1
Exp: by def
Level:2

3) Modern OS are
1) procedure driven
2) Interrupt driven
3) Function call driven
4) None of the above

Answer: 2
Exp: derived from today’s application OS
Level:2

4) Exception is also known as
1) Interrupt
2) Handler
3) Trap
4) None of the above
Answer: 1 and 3
Exp: alternate names
Level:2

5) The smallest addressable portion of a disc is called
1) Track
2) Cylinder
3) Sector
4) Platter

Answer:3
Exp: by def
Level:1

6) SCSI stands for
1) Super Computer- Systems Interface
2) Small Computer- Systems Interface
3) Single Computer- Systems Interface
4) Simple Computer- Systems Interface

Answer: 2
Exp: by def
Level:1

7) DMA stands for
1) Disc Memory Allocation
2) Direct Memory Allocation
3) Dynamic Memory Allocation
4) Disc Memory Access

Answer: 3
Exp: by def
Level:1

8) DRAM stands for
1) Direct Random Access Memory
2) Dynamic Random Access Memory
3) Distributed Random Access Memory
4) Dynamic Random Allocation of Memory

Answer: 2
Exp: acronym
Level:1

9) An instruction will be stored in _____________
1) Instruction Register
2) Program Counter
3) Stack Pointer
4) Data Segment
Answer: 1
Exp: by def of instruction register
Level:1

Sorting Interview Questions Part 9

2007-10-27T11:01:00.002-07:00

36. According to the max-heap property, each node in a tree has a key which is _______ than or equal to the key of its parent.
Ans. less

37. A sort algorithm that repeatedly looks through remaining itemsto find the least one and moves it to its final location is
a. Quick sort
b. Insertion sort
c. Selection sort
d. Merge sort
Ans. c

38. __________ is a specialization of selection sort.
a. quick sort
b. selection sort
c. bingo sort
d. strand sort
Ans. c
Bingo sort is a variant of selection sort that orders items by repeatedly looking through remaining items to find the greatest value and moving all items with that value to their final location. This is more efficient if there are many duplicate values.

39. __________ can be seen as a variant of selection sort in which sorted items are arranged in a heap to quickly find the next item.
a. heap sort
b. bingo sort
c. shell sort
d.none of the above
Ans. a

40. ___________ is a kind of quicksort
a. balanced quicksort
b. multikey quicksort
c. retrospective sort
d. all the above
Ans. d

41. ___________ is a part of or used in quicksort.
a. divide and conquer
b. partition
c. recursion
d. all the above
Ans. d

42. Insertion sort is also known as __________.
Ans. Linear insertion sort

43. Given the following sequence of elements 11,2,9,13,57,25,17,1,90,3 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 11,2,9,13,25,57,17,1,90,3
b. 11,2,9,90,57,25,17,1,13,3
c. 11,90,9,13,57,25,17,1,2,3
d. 90,57,25,13,11,9,17,1,2,3
ans. c

44. Given the following set of elements 16,4,10,14,7,9,3,2,8,1 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 16,4,10,14,7,9,3,2,8,1
b. 16,14,10,4,7,9,3,2,8,1
c. 16,14,10,8,7,9,3,2,4,1
d. 16,14,10,8,7,3,9,2,4,1
Ans. c

45. Give the output of MAX_HEAPIFY(A,3) in the array A=( 27,17,3,16,13,10,1,5,7,12,4,8,9,0).
a. 27,17,3,16,13,10,1,5,7,12,4,8,9,0
b. 27,17,10,16,13,3,1,5,7,12,4,8,9,0
c. 27,17,10,16,13,9,1,5,7,12,4,8,3,0
d. 27,17,3,16,13,7,1,5,10,12,4,8,9,0
Ans. c

46. If the sequence: (2,2) (0,4) (1,4) (0,1) (1,2) (0,6) (2,1) (1,1) were sorted using a
stable sort by ascending order on the first key and then using the same method were
sorted again on the second key, the result would be:
8.a). (0,4) (0,1) (0,6) (1,4) (1,2) (1,1) (2,2) (2,1)
8.b). (0,1) (2,1) (1,1) (2,2) (1,2) (0,4) (1,4) (0,6)
8.c). (2,1) (1,1) (0,1) (2,2) (1,2) (1,4) (0,4) (0,6)
8.d). (0,1) (1,1) (2,1) (1,2) (2,2) (0,4) (1,4) (0,6) ***
8.e). (0,1) (0,4) (0,6) (1,1) (1,2) (1,4) (2,1) (2,2)

47. Mergesort always runs faster than bubblesort. (T/F)
false -- depends on the constants and the size of the input. Given a large enough input, mergesort will most likely run faster than bubblesort.
48. Selection sort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic
Ans:c

Sorting Interview Questions Part 8

2007-10-27T11:01:00.001-07:00

21. If p < r then
q Partition (A, p, r)
Recursive call to Sort (A, p, q)
Recursive call to Sort (A, q + r, r)
Which sorting algorithm does SORT represent
a.Selection sort b.quick sort c.Bubble sort d.Merge sort
Ans:b
22. _____Sort chooses as pivot one of the items in the array to be sorted.
a.Selection sort b.quick sort c.Bubble sort d.Merge sort
Ans:b
23.Selection sort is
a.inplace
b.noninplace
c.out place
d.none
Ans:a
24.Bubble sort is
a.inplace
b.noninplace
c.out place
d.none
Ans:a
25.Which of the following are stable algorithms
a.Bubble b.Insertion c.Both d.none
Ans:c

26. An array in sorted order is in __________.
a.Max-heap
b.Min-heap
c.Random heap
d.none
Ans:a

27. Assuming all the elements to be distinct, where in the Max-heap might the smallest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:d

28. Assuming all the elements to be distinct, where in the Min-heap might the smallest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:a

29. Assuming all the elements to be distinct, where in the Max-heap might the largest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:a

30. Assuming all the elements to be distinct, where in the Min-heap might the largest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:d

31.Which of the following is useful in implementing quick sort
a.Stack
b.List
c.Queue
d.Set
Ans:a

32.Which of the following algorithm design technique is used for quick sort
a.Dynamic programming
b.Backtracking
c.Divide and conquer
d.Greedy method
Ans:c

33. If the records that it's sorting are in main memory then the sort is called as
a. internal
b. external
c. stable
d. none of this
Ans. a

34. An array of elements is sorted by choosing a pivot element & by partition.The sorting process is called
a. Partition exchange sort
b. Quick sort
c. a and b
d. selection sort
Ans. c

35. In min-heap property,each node in a tree has a key which is _______ than or equal to the key of its parent.
Ans. greater

Sorting Interview Questions Part 7

2007-10-27T10:59:00.002-07:00

11. In bubble sort algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.(T/F)
Ans:True
12. The basic procedures related to heap are
a.Heapify, which runs in O(lg n) time.
b.Build-Heap, which runs in linear time.
c.Heap Sort, which runs in O(n lg n) time.
d.Extract-Max, which runs in O(lg n) time.
Ans:a,b,c,d
13. Heapify runs in O(lg n) time while build-heap runs in _____time.
Ans: linear
14. A process picks the largest child key and compares it to the parent key and if parent key is larger then the process quits, otherwise it swaps the parent key with the largest child key, so that the parent now becomes larger than its children.Such a process is called
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b
15. Process (A, i)
1. l ← left [i]
2. r ← right [i]
3. if l ≤ Process-size [A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ Process -size [A] and A[i] > A[largest]
7. then largest ← r
8. if largest ≠ i
9. then exchange A[i] ↔ A[largest]
10. Process (A, largest)
The above process indicates
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b

16.The output of heapify of the following tree is

a. 15 8 4 7 5 3 1 2 6 b. 8 15 4 7 5 3 1 2 6 c. 15 8 4 7 5 3 1 6 2 d. 15 8 4 5 7 3 1 2 6
Ans:a
17. Process (A)
1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The process here denotes
a.Selection sort b.Heap sort c.Bubble sort d.none
Ans:b

18. The time taken for build heap is
a.O(n)
b.O(log n)
c.O(nlogn)
d.none
Ans:a
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).
19. Process (A1, A2, A)
i.← j 1
A1[m+1], A2[n+1] ← INT_MAX
For k ←1 to m + n do
if A1[i] < A2[j]
then A[k] ← A1[i]
i ← i +1
else
A[k] ← A2[j]
j ← j + 1
SORT (A)
A1[1 . . n/2 ] ← A[1 . . n/2 ]
A2[1 . . n/2 ] ← A[1 + n/2 . . n]
Process (A1)
Process (A1)
Process (A1, A2, A)
Which sorting algorithm does SORT represent
a.Selection sort b.Heap sort c.Bubble sort d.Merge sort
Ans:d
20.Quick sort is recursive.(T/F)
Ans:True

Sorting Interview Questions Part 6

2007-10-27T10:59:00.001-07:00

1. Divide-and-conquer is a
a.top-down technique
b.Bottom-up technique
c.Both
d.none
Ans:a
2.The technique for designing algorithms that consists of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem is _____
Ans:Divide and conquer
3. Divide-and-conquer paradigm consists of following major phases:Arrange them in order
a.Solve the sub-problem recursively (successively and independently), and then
b.Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
c.Combine these solutions to subproblems to create a solution to the original problem.
a. bac
b. abc
c. cab
d. none
Ans:a
4. Bubble sort requires extra memory.(T/F)
Ans:False
5. Insertion sort is an example of
a.incremental sort
b.decremental sort
c.non-stable sort
d.none
Ans:a
Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time.
6. An algorithm considering the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted) is called
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:b
7.The following process depicts which sorting algorithm: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:a
8. Selection sort is quadratic in both the worst and the average case, and requires no extra memory.(T/F)
Ans:True
9. For each i from 1 to n - 1, there are ____ exchanges for selection sort.
a.1
b.n-1
c.n
d.none
Ans:a
10.For each i from 1 to n - 1, there is _______comparisons for selection sort.
a.n
b.n-i
c.i
d.n-1
Ans:b
For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n -1 exchanges and (n -1) + (n -2) + . . . + 2 + 1 = n(n -1)/2 comparisons. These observations hold no matter what the input data is.

Sorting Interview Questions Part 5

2007-10-27T10:58:00.001-07:00

68. Which of these is the correct big-O expression for 1+2+3+...+n?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
Ans:d

69. Consider the following polynomial

aknk+ak-1nk-1+………….a0 .

What is the Big –O representation of the above polynomial?
(a)O(n) (b) O(nk) (c) O(nk+1) (d) O(log k)
Ans:b
70. Consider the program segment given below:
Int i,j,sum;
for ( i=0 ; i < n; i++) {
for (j = 1,sum=a[0]; j < = i; j++)
Sum+=a[j];
printf(“ sum for sub-array through %d is %d”,i , sum);
}

The running time of the above algorithm is

(a) n. (b) n log n . (c) log n. (d) n2.
Ans:d

71. Consider the following algorithm:

Step 1 : If S has zero or one element, return S immediately; it is already sorted. Otherwise, split S into two parts S1 and S2, such that S1 contains the first [n/2] elements of S, and S2 contains the remaining elements of S.
Step 2: Recursively sort sequences S1 and S2
Step 3: put back the elements into S by merging the sorted sequences S1 and S2 into a sorted sequence.

Which of the following describe(s) the above algorithm?

(a) Sorting by insertion
(b) Sorting by selection
(c) Sorting by exchange
(d) Divide and conquer
Ans:d

72. Consider the following algorithm :
abc(data[])
Transform data into a heap
for ( i=data.length-1; i> 1 ; i--)
Swap the root with the element in position i;
Restore the heap property for the tree data[0],…….. data[i-1];
Which of the following are not the intermediate functions of the above algorithm?
(a) Transforming data into either an ascending order or descending order of a heap
(b) Transforming data into a maximum heap
(c) The 1st step of the sorting process is exchanging the last element and the first element, and decreasing the array size by one.
(d) Finally, get either the ascending order or the descending order of nodes
Ans: b

Sorting Interview Questions Part 4

2007-10-27T10:57:00.000-07:00

61.How many passes are required to sort the set of integers using the bubble sort algorithm? {20,60,50,37,16,92,70,35}.

(a) 6 (b) 7 (c) 8
(d) 9 (e) 5
Ans. b

62.Consider the following pseudo code algorithm
found = false;
i=1;
while (i =< n ) and ( not found)
{
if key=k[i] then
{
search =i;
found =true;
else
i++;
}
}
if not found
{
search=0;
}
What is the above algorithm intended to do?
(a) Sequential Search (b) Depth First Algorithm
(c) Shell sort algorithm (d) Index sequential search
(e) Breadth first search
Ans. a

63. Consider the following (iv) conditions:
(i) Sorts which cannot be performed in the main memory, can be done on disk or tape. These are also quite important. This type of sorting is called external sorting.
(ii) The simplest algorithms usually take O(n2) time to sort in objects and are only useful for sorting short lists.
(iii) One of the most popular sorting algorithm is quicksort; which takes O(log n) time on average.
(iv) Merge sort is well suited for external sorting.
Which of the above conditions are applied for the sorting algorithm?
a. (i),(ii) and (iii) only
b. (i),(ii) and (iv) only
c. (ii),(iii) and (iv) only
d. (i) and (iii) only

Ans. b

64. Which sorting method(s) runs fastest for file which is already sorted?
a.Selection sort
b.insertion sort
c.quick sort
d.bubble sort
Ans:b
65.
(i) Quick Sort can be implemented in recursive way.
(ii) Heap Sort is the best sorting method compared to bubble, selection, insertion sort on the basis of complexity.

Correct statement(s) is/are?
A(i) only
b (ii) only
c.(i) and (ii)
d.none
Ans:c
66. In calculating the time complexity of an algorithm, we use some rules.

Rule 1.
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N) + T2 (N)=Max(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N)*g(N))
Rule 2
If T1(N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N)+ T2(N)=Min(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N))+O(g(N))
Rule 3
O(C f(N))=O(f(N)) if C is a constant
Rule 4
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) and If g(N) < = f(N) then
T1(N)+ T2(N)=O(f(N))

What are the correct rules out of the above?
a.Rule 1 , Rule 2 and Rule 3 only
b.Rule 1 and Rule 4 only
c.Rule 1 , Rule 3 and Rule 4 only
d.Rule 2, Rule 3 and Rule 4 only
Ans:c

67. What is the name of the following algorithm?

Initialize marker to 1 (2nd element in the list)
If element[marker1] < element [marker1-1] , store element[marker1] in a temporary location temp, initialize marker2 to marker1-1 (the location just before marker1).
While element [marker2] > temp and marker2 >= 0 shift element [marker2] to location marker2+1. [this slides the element over to make room to its left) Decrease marker2 by 1.
Insert temp into the location just vacated by a shift.
Increase marker1 by 1.
a. Insertion sort b. bubble sort c. selection sort d. none
Ans: d

Sorting Interview Questions Part 3

2007-10-27T10:56:00.000-07:00

41.Sorting is not useful for
a. report generation
b. minimizing the storage needed
c. making searching easier and efficient
d. responding to queries easily
Ans. b

42. Choose the correct statements
a. Internal sorting is used if the number of items to be sorted is very large
b. External sorting is used if the number of items to be sorted is very large
c. External sorting does not need auxiliary storage
d. Internal sorting need auxiliary storage
Ans. b

43. A sorting technique that guarantees that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
a. stable b. consistent c. external d. linear
Ans. a

44.The running time of an algorithm is given by
T(n) = T(n-1) + T(n-2) – T(n-3),if n>3
= n,otherwise.
The order is
a. n b. log n c. n^n d. n^2
Ans. a
Let us find what is T(4) and T(5)
T(4) = T(3) + T(2) – T(1) = 3+2-1=4
T(5) = T(4)+ T(3) –(2) = 4+3-2=5
By induction it can be proved that T(n) = n.Hence order is n.

45.The order of an algorithm that finds whether a given Boolean function of ‘n’ variables,produces a 1 is
a. constant b. linear c. logarithmic d. exponential
Ans. d
In the worst case it has to be check all the 2^n possible input combinations,which is exponential .

46.You want to check whether a given set of items is sorted or not.Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. Bubble sort b. Selection sort c. Insertion sort d.Merge sort
Ans. c

47. The average number of comparisons performed by the merge sort algorithm,in merging two sorted lists of length 2 is
a. 8/3 b. 8/5 c. 11/7 d.11/6
Ans. a
Merge sort combines 2 given sorted lists into one sorted list.For this problem let the final sorted order be a,b,c and d.The 2 lists(of length 2 each) should fall into one of the following 3 categories:
i)a,b and c,d ii)a,c and b,d iii)a,d and b,c
The number of comparisons needed in each case will be 2,3,3.So,average number of comparisons will be (2+3+3)/3=8/3.

48.Which of the following sorting methods will be the best if the number of swappings done is the only measure of efficiency?
a. bubble sort b. selection sort c. insertion sort d.quick sort
Ans. b

49.You are asked to sort 15 numbers randomly.You should prefer
a. bubble sort b. quick sort c. merge sort d. heap sort
Ans. a

50. As part of the maintenance work,you are entrusted with the work of rearranging the library books in a shelf in proper order,at the end of each day.The ideal choice will be
a. bubble sort b. insertion sort c. selection sort d. heap sort
Ans. b

51. Which of the following algorithms exhibits the unnatural behavior that,minimum number of comparisons are neede if the list to be sorted is in the reverse order and maximum number of comparisons are neede if they are already in order.
a. heap sort b. radix sort c. binary insertion sort d. there can’t be any such sorting method.
Ans. c

52.Which of the following sorting methods sorts a given set of items that is already in order or in reverse order with equal speed?
a. Heap sort b. Quick sort c. Insertion sort d. selection sort
Ans. b

53. A machine needs a minimum of 100 sec to sort 1000 names by quick sort.The minimum time needed to sort 100 names will be approx
a. 50.2 sec b. 6.7 sec c.72.7 sec d. 11.2 sec
Ans. b
In the best case quick sort algorithm makes nlogn comparisons.so,1000 * log(1000) = 9000 comparisons,which takes 100s.To sort 100 names a minimum of 100 * log(100)=600 comparisons are needed.This takes 100*600/9000 = 6.7 sec

54.A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort
a. 400 names b. 800 names c. 750 names d. 850 names
Ans. a
For sorting 200 anmes bubble sort makes 200 * 199/2 = 19900 comparisons.So,the time needed for 1 comparison is 200 sec approx.In 800 sec it can make 80,000 comparisons.We have to find n,such that n(n-1)/2=80,000.solving n is approx 400.

55.The correct order of arrangement of the names Bradman,Lamb,May,Boon,Border,Underwood and Boycott,so that the quicksort algorithm makes the least number of comparisons is
a. Bradman,Border,Boon,Boycott,May,Lamb,Underwood
b. Bradman,Border,Boycott,Boon,May,Underwood,Lamb
c. Underwood,Border,Boon,Boycott,May,Lamb,Bradman
d. Bradman,May,Lamb,Border,Boon,Boycott,Underwood
Ans. a and b
Let the first element be the pivot element always.The best way is the one that splits the list into two equal parts each time.This is possible if the pivot elemnt is the median.Consider the given set of names or the equivalent set 1,2,3,4,5,6,7.4 is the median and hence should be the pivot element.Since the first element is the pivot element,4 should be the first element.so after the first pass,4 will be put in the correct place and we are left with 2 sublists 1,2,3 and 5,6,7.Since 2 is the median of 1,2,3 the list should be rearranged as 2,1,3 or 2,3,1.For similar reasons 5,6,7 should be rearranged as 6,5,7 or 6,7,5.Hence the answer.

56. Which of the following is/are correct in connection with sorting methods?
(a) Bubble sort uses sorting by an insertion technique to sort a file of numbers.
(b) Quick sort uses sorting by an exchange technique to sort a file of numbers.
(c) Shell sort uses sorting by an exchange technique to sort a file of numbers.
(d) Heap sort does not use sorting by an exchange technique to sort a file of numbers.
Ans. b

{2,8,13,6,7,27,18}
57)the maximum heap is created using the above set of integers, what would be the value at the 6th
position of the heap?
(a) 2 (b) 8 (c) 6
(d) 13 (e) 7
Ans. b

58.If one uses the quick sort algorithm to sort the following integers, how many pivot values are
required? You may assume that the pivot element is always selected as the last element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. d

59.If one uses the quick sort algorithm to sort the following set of integers how many pivot values are required?You may assume that the pivot element is always selected as the first element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. e

60.If one uses the bubble sort algorithm in ascending order ,in which of the following pairs will the data values not interchange during the first pass? {20,60,50,37,16,92,70,35}.
(a) 20,60 (b) 60,50 (c) 60,37
(d) 50,37 (e) 60,16
Ans. a

Sorting Interview Questions Part 2

2007-10-27T10:55:00.000-07:00

25.Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic.
Ans:C
26. Which of the following is applicable for any constant ‘c’
a.c*log n=O(1)
b.c*log n =O(logn)
c.c*log n =O(nlogn)
d.c*log n =O(n)
Ans:b
27.Which of the following is applicable for any constants‘c,k’
a.c*(n^k)=O(n^k)
b.c*(n^k) =O(logn)
c.c*(n^k) =O(nlogn)
d.c*(n^k) =O(1)
Ans:a
28.The process of combining two or more sorted files into a third sorted file is _____
Ans:merging

29.Which Sort Algorithm has same time complexity as Heap sort in all cases?
a.Merge sort
b.Bubble sort
c.Selection sort
d.none of these
Ans:a

30.Selection sort is faster than bubble sort(T/F)
Ans:True
Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.

31.The worst-case time complexity of heap sort is same as the average-case time complexity of quick sort.
a. True
b. False
Ans. b

32.Which of the following statements is FALSE?
a. Merge Sort is an unstable sort
b. Worst case time complexity of Merge Sort is O(NlogN)
c. Merge Sort takes more space than Quick Sort
d. Average case time complexity of Merge Sort is O(NlogN)
Ans. c

33.Both merge sort and quick sort are in-place sorts.
a. True
b. False
Ans. b

34.Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion

Ans:d
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

35.What are the methods available in storing sequential files ?
a.Straight merging,
b.Natural merging,
c.Polyphase sort,
d. all the above
Ans: d

36.An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and M2 is g(n) then the order of the algorithm is
a.max(f(n),g(n))
b.min(f(n),g(n))
c.f(n)+g(n)
d.f(n)*g(n)
Ans:a
By definition of order,there exists constants c1,c2,n1,n2 such that
T(n)<=c1*f(n),for all n>=n1
T(n)<=c2*g(n),for all n>=n2
Let N=max(n1,n2) and C=max(c1,c2),so
T(n)<=c*f(n),for all n>=N
T(n)<=c*g(n),for all n>=N
Adding
T(n)<=c/2 (f(n)+g(n))
Let max(f(n),g(n))=f(n)
T(n)<=c/2 (f(n)+f(n))<=c*f(n)
So order is f(n) which is max(f(n),g(n)) by the assumption.

37.The concept of order (Big O) is important because
a.It can be used to decide the best algorithm that solves a given problem
b.It determines the maximum size of a problem that can be solved in a given system in a given amount of time.
c.it is the lower bound of the growth rate of the algorithm
d. a and b
Ans: d

38.The running time T(n) where n is the input size of a recursive algorithm is
T(n)=c+T(n-1),if n>1
d,if n<=1
The order of the algorithm is
a.n*n b.n c.n^3 d.n^n
Ans:b

By recursively applying the relation we can arrive at
T(n-1)=c(n-1)+d
So,order is n

39.There are four different algorithms A1,A2,A3 and A4 to solve a given problem with the order log(n),loglog(n),nlog(n),n/log(n) respectively.Which is the best algorithm?
a. A1 b.A2 c.A3 d.A4
Ans. b

40.The time complexity of an algorithm T(n),where n is the input size is given by
T(n)=T(n-1)+1/n,if n>1
= 1,otherwise
The order of this algorithm is
a. log n b. n c. n^2 d. n^n
Ans. a

Sorting Interview Questions Part 1

2007-10-27T10:54:00.000-07:00

1.Which of the following algorithms can be used for sorting large data sets based on time complexity?
a. Bubble sort b. Merge sort c. Heap sort d. Quick sort
Ans:c
Heap sort does not require massive recursion or multiple arrays.

2. Which of the following algorithms is the slowest
a. Bubble sort b. Merge sort c. Quick sort d. Heap sort
Ans:a
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items

3.The sorting algorithms belonging to quadratic complexity includes
a. bubble sort b. insertion sort c .selection sort d. All the above
Ans:d
4. The sorting algorithms not having complexity O(n log n)includes
a. heap sort b. quick sort c. bubble sort d.merge sort
Ans: a

5.An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted,directed graph..
a.Dijkstra’s b.Prim’s c. Kruskal d.none of the above
Ans:a

6.Time complexity of Dijkstra’s algorithm
a.O(VlogV) b.O(E+VlogV) c.O(ElogV) d.none of the above
Ans:b

7.In the time complexity O(E+VlogV) V is the number of _____
Ans:vertices

8.In the time complexity O(E+VlogV) E is the number of _____
Ans:edges

9.In Dijkstra’s algorithm,all weights must be nonnegative(T/F)
Ans:True

10.A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps is called
a.Structure b.Queue c.Algorithm d.Data structure
Ans:c

11.Big O notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:a

12. θ notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:c

13.Ω notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:b

14.For inplace sorting no extra memory is required.(T/F)
Ans:True

15.Which of the following do not use inplace sorting
a.Selection b.Bubble c.Insertion d.Merge
Ans: d

16.The operations which directly affect the output of an algorithm are ______
Ans:Key operations

17.Number of times a key operation executes is
a.Complexity b.Frequency count c.Time d.None
Ans:b

18.What are the advantages of sorting
a.Used in algorithms as a key subroutine.
b.Used for engineering issues.
c.Both
d.None
Ans:c

19.A sorting technique where some of the records are in auxiliary storage is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:b

20.A sorting technique where the records are in main memory is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:a

21.Each item in a file is called a record.(T/F)
Ans:True

22.A sort takes place either on the records themselves or on an auxiliary table of pointers.(T/F)
Ans:True

23.Suppose the amount of data stored in the records is so large that the overhead involved in moving the actual data is prohibitive,then the auxiliary table of pointers may be used so that these pointers are moved instead of the actual data,this is called _______
Ans:sorting by address

24.Which of the following is applicable for any constant ‘c’
a.c=O(1)
b.c=O(logn)
c.c=O(nlogn)
d.c=O(n)
Ans:a

Linear Search Interview Questions Part 2

2007-10-27T10:53:00.000-07:00

23.The average successful search time for sequential search on ‘n’ items is
a. n/2
b. (n-1)/2
c. (n+1)/2
d. log (n) + 1
Ans. c
If the search key matches the very first item, with one comparison we can terminate.If it is second,two comparisons ,etc.So,average is (1+2+3+…+n)/n , i.e.,(n+1)/2

24. 6 files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 number of records respectively.In what order should they be stored so as to optimize access time .Assume each file is accessed with the same frequency.
a. F3,F4,F1,F5,F6,F2
b. F2,F6,F5,F1,F4,F3
c. F1,F2,F3,F4,F5,F6
d. Ordering is immaterial as all files are accessed with the same frequency
Ans. a
Since the access is sequential,greater the distance,greater will be the access time.Since all the files are referenced with equal frequency,overall access time can be reduced by arranging them as in option (a).

25. For small arrays, _____________ is a good solution because it's straightforward.
a. binary search
b. linear search
c. fibonacci search
d. none of the above
Ans. b

26. If the loop in a linear search finishes without finding a match,the search is failed and _____ is returned.
Ans. -1
If the loop finishes without finding a match, the search failed and -1 is returned.

27. What is the output of the following program using linear search
#include
using namespace std;

int LinearSearch(const int *Array, const int Size, const int ValToSearch)
{
bool NotFound = true;
int i = 0;

while(i < Size && NotFound)
{
if(ValToSearch != Array[i])
i++;
else
NotFound = false;
}

if( NotFound == false )
return i;
else
return -1;
}

int main()
{
int Number[] = { 67, 278, 463, 2, 4683, 812, 236, 38 };
int Quantity = sizeof(Number) / sizeof(int);
int NumberToSearch = 0;

cout << "Enter the number to search: "; cin >> NumberToSearch;
int i = LinearSearch(Number, Quantity, NumberToSearch);

if(i == -1)
cout << NumberToSearch << " was not found in the collection\n\n";
else
{
cout << NumberToSearch << " is at the " << i+1;
if( i == 0 )
cout<< "st position of the collection\n\n";
else if( i == 1 )
cout<< "nd position of the collection\n\n";
else if( i == 2 )
cout<< "rd position of the collection\n\n";
else
cout<< "th position of the collection\n\n";
}

return 0;
}

Enter the number to search: 278
a. 278 is at the 1st position of the collection
b. 278 is at the 2nd position of the collection
c. 278 is at the 3rd position of the collection
d. 278 was not found in the collection
Ans:b

28.For the above program what is the output for
Enter the number to search: 288
a. 288 is at the 1st position of the collection
b. 288 is at the 2nd position of the collection
c. 288 is at the 3rd position of the collection
d. 288 was not found in the collection
Ans:d

Linear Search Interview Questions Part 1

2007-10-27T10:52:00.000-07:00

1.The sequential search, also known as the linear search.

2.Every element in the data set is examined in the order presented until the value being searched for is found, the following technique is called as
a. Binary search.
b. Quick search.
c. Linear search.
d. None of these.
Ans:c

3.Best case time complexity of Sequential search is
a. O(1)
b. O(n)
c. O(n×n)
d. None of these.
Ans:a
4.Average case time complexity of Sequential search is
e. O(1)
f. O(n)
g. O(n×n)
h. None of these.
Ans:b
5. Worst case time complexity of Sequential search is
i. O(1)
j. O(n)
k. O(n×n)
l. None of these.
Ans:b
6. Best case time complexity of linear search is
m. O(1)
n. O(n)
o. O(n×n)
p. None of these.
Ans:a
7.Average case time complexity of Linear search is
q. O(1)
r. O(n)
s. O(n×n)
t. None of these.
Ans:b
8.Worst case time complexity of Linear search is
u. O(1)
v. O(n)
w. O(n×n)
x. None of these.
Ans:b
9. Efficiency is usually measured in terms of abstract computations, such as data moves and the memory used. True.

10.Sorting is the process of putting items in a predetermined order, such as increasing or decreasing order.

11.The simplest form of search is …
y. Binary search
z. Linear search
aa. Both
bb. None of these
Ans:b

12.Linear search is applicable to a table organized in
cc. Array
dd. Linked list
ee. Tree
ff. None of these
Ans:a,b
13.Sequential search is applicable to a table organized in
gg. Array
hh. Linked list
ii. Tree
jj. None of these
kk. Ans:a,b

14.The algorithm for sequential search is…
ll. for(i=0;iif (key != k (i))
return (i);
return (-1);
mm. for(i=0;iif (key == k (i))
return (i);
return (-1);
nn. None of these
oo. All of these
Ans:b

15.An efficient linear search method involves inserting the argument key at the end of the array before beginning the search, thus guaranteeing that the key will be found. The algorithm for this is …
pp. for(i=0;iif (key == k (i))
return (i);
return (-1);
qq. k(n) = key;
for (i=0;key != k(i);i++);
if( ireturn( i );
else
return (-1);
rr. None of these
ss. All of these
Ans:b

16.The efficiency of searching a list is ___________ by adding a sentinel node containing the argument key at the end of the list.
tt. Decreased
uu. Improved (as the for loop condition is simplified “k(p) != key”)
vv. None of these
ww. All of these
Ans:b

17.An efficient linear search method involves inserting the argument key at the end of the array before beginning the search, thus guaranteeing that the key will be found. The extra key inserted at the end of the array is called as
xx. Metical
yy. Sentinel
zz. Ultimo
aaa. All of these
Ans:b

18.The sentinel method of linear search requires an…
bbb. Additional external pointer
ccc. Additional internal pointer
ddd. None of these
eee. All of these
Ans:a
19.Linear search is a kind of _____________ .
Ans. search

20.Transpose sequential search is a kind of ___________
fff. linear search
ggg. binary search
hhh. sequential search
iii. none of the above
Ans:a,c
21._______________ is a part of or used in linear search.
Ans. move-to-front heuristic.

22.______________ is a part of or used in sequential search.
Ans. move-to-front heuristic.

Hashing Interview Question Part 3

2007-10-27T10:51:00.000-07:00

24. Which of the following are not hash functions?
a. division
b. coupling
c. folding
d. extraction
e. mid square
Ans. c

25. The following paragraph is connected with hashing:
The process of mapping large amounts of data into a smaller table is called …… (i) ……. A good hash function should satisfy two criteria, namely quickness to compute and minimisation of the number of …… (ii) ……. Minimization of …… (iii) …… can be achieved by choosing a hash function that spreads the incoming data as evenly as possible over the hash table.

Correct terms for the blanks positions are:
(a) (i) indexing (ii) collisions (iii) couplings
(b) (i) hashing (ii) collisions (iii) couplings
(c) (i) hashing (ii) collisions (iii) collisions
(d) (i) indexing (ii) collisions (iii) collisions

Ans. c

26. What is the best definition of a collision in a hash table?
a. Two entries are identical except for their keys.
b. Two entries with different data have the exact same key.
c. Two entries with different keys have the same exact hash value.
d. Two entries with the exact same key have different hash values.
Ans. c
27. The phenomenon wherein two keys that hash into different values compete with each other in successive rehashes is called ____________ .
Ans. primary clustering
28. ________ is a collision resolution technique that puts all the elements that hash to the same slot in a linked list.
a. chaining
b. open addressing
c. closed addressing
d. hashing
Ans. a
29. Given a hash table T with m slots that stores n elements,the load factor is
a. α = m*n
b. α = n/m
c. α = m+n
d. α = m/n
Ans. b
30. If a hash table in which collision are resolved by chaining, a successful search takes ______ time on the average, under the assumption of simple uniform hashing.
a. Q(1+a)
b. θ(1+α)
c. Ω(1+α)
d. O(1+α)
Ans. a
31. Inserting an element into an open-address hash table with load factor a requires at most ______ probes on average, assuming uniform hashing.
a. 1/(1+α)
b. 1/(1-α)
c. 1+α
d. 1/α
Ans. b

32. One of the collision resolution techniques and the methods used is open addressing include __________ .
Ans. Overflow block

33. The collision resolution techniques and methods used in closed addressing include
i)linked list
ii) binary tree
iii) overflow block
The correct options are
a. i and ii only
b. i only
c. ii only
d. i,ii and iii only
Ans. a

Hashing Interview Question Part 2

2007-10-27T10:50:00.000-07:00

11. A hash table that grows to handle more items is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.none
Ans:b
12. The associated hash function must change as the table grows in dynamic hashing.(T/F)
Ans:True
13. A hash table in which the hash function is the last few bits of the key and the table refers to buckets is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.Extendible hashing
Ans:d
14. A dynamic hashing table that grows one slot at a time is called
a.linear hashing
b.dynamic hashing
c.minimal perfect hashing
d.Extendible hashing
Ans:a
15.Linear hashing is also known as
a.Decremental hashing
b.Incremental hashing
c.Extendible hashing
d.none
Ans:b
16. A dictionary implemented with two hash tables of equal size, T1 and T2, and two different hash functions, h1 and h2.
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.2-left hashing
Ans:d
17. A variant of a hash table in which keys are added by hashing with two hash functions is called
a.optimal hashing
b.2-choice hashing
c.minimal perfect hashing
d.2-left hashing
Ans:b
18. The average-case cost of a successful search is__________ for 2-choice hashing where m is the number of keys and n is the size of the array
a. O(2 + (m-1)/n)
b.O(1+(m-1)/n)
c.O(3+(m-1)/n)
d.none
Ans:a
19. A conceptual method of open addressing for a hash table is called
a.Universal hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:b
20. The assumption or goal that items are equally likely to hash to any value is called
a.Simple uniform hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:a
21. A method of open addressing for a hash table in which a collision is resolved by searching the table for an empty place at intervals given by a different hash function, thus minimizing clustering is called
a.double hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:a
22.Double hashing is also known as rehashing(T/F)
Ans:True
23. A scheme that chooses randomly from a set of hash functions is called
a.double hashing
b.Uniform hashing
c.Optimal hashing
d.universal hashing
Ans:d

Hashing Interview Question Part 1

2007-10-27T10:48:00.002-07:00

1. A function that maps keys to integers, usually to get an even distribution on a smaller set of values is called ______
Ans: Hash function
2. A dictionary in which keys are mapped to array positions by hash functions is called
a.hash table
b.view table
c.Both
d.none
Ans:a
3.A hash function f defined as f(key) = key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,11,56,into a table indexed from 0 to 6. 11 will be stored in the location
a.3 b.4 c.5 d.6
Ans:c
f(37)=37 mod 7 =2.
So,37 will be put in location 2.f(38)=3.
So,38 will be in third location.
F(72)=2. This results in a collision. With linear probing as the collision resolving strategy, the alternate location for 72 will be the location 4. Continuing this way, the final configuration will be 98,56,37,38,72,11,48.
Hence the answer.

4. Having the keys of more than one item map to the same position is called a __________
Ans: collision.
5. A hash function that maps each different key to a distinct integer is called
a.perfect hashing
b.internal hashing
c.external hashing
d.none
Ans:a
6. Usually all possible keys must be known beforehand in perfect hashing.(T/F)
Ans:True
7. A hash table that uses a perfect hash has
a. 1 collision
b.no collisions
c.Multiple collisions
d.none
Ans:b
8.Perfect hashing is also called
a.optimal hashing
b.dynamic hashing
c.cuckoo hashing
d.none
Ans:a
9. A perfect hashing function that maps each different key to a distinct integer and has the same number of possible integers as keys is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.none
Ans:c
10. A minimal perfect hashing function for keys in S such that if k1, k2 ∈ S and k1 > k2, then f(k1) > f(k2) is called ____
Ans:Order preserving minimal perfect hashing

Greedy Strategy Interview Question Part 5

2007-10-27T10:48:00.001-07:00

44. The minimum spanning tree of a graph give the shortest distance between any 2 specified nodes.(True or False)
Ans. False
Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

45. Dijkstra’s algorithm solves the _____________ shortest path problem.
Ans. single- source

46. The time required to run Dijkstra’s algorithm is ___________
a. O( ElogV)
b. O( |E| logV)
c. O( |E| log |V| )
d. O( log V)
Ans. c

47. Dijkstra algorithm finds the shortest path from a source to all the other nodes in a
weighted graph. Can you use Dijksta algorithm to find the shortest path from a source
node to all the other nodes in non-weighted graph?
a) No, because I wouldn’t know which edge to include in the cloud at each step
b) Yes, I could associate weight 0 to each edge and apply Dijkstra
c) No, because I wouldn’t be able to label the nodes
d) Yes, I could associate weight 1 to each edge and apply Dijkstra ***
e) None of the above

48. Suppose I want to find a spanning tree of a ring graph (see an example of ring graph
below) represented by an adjacency list. Can I use a BFS traversal? What would be the
complexity of BFS traversal as a function of n (number of nodes)?
a) yes, for a ring with n nodes the complexity would be always O(n) ***
b) yes, for a ring with n nodes the complexity would be always O(n2)
c) yes, for a ring with n nodes the complexity would be O(n2) in the worst case
d) yes, for a ring with n nodes the complexity would be O(n log n)
e) no, BFS is an algorithm to visit the nodes, not to construct a spanning tree. I could use
Prim to construct a spanning tree

49. What would be the complexity of Prim algorithm on a graph with n nodes and m
edges, if the priority queue is implemented with a sorted sequence based on an array.
a) O(n2+ n)
b) O(n2 + m)
c) O( n + mn)
d) O( n + n2)
Ans:c

50. You are given the following graph. If you use Dijkstra algorithm from node v you
will obtain a shortest path spanning tree from v. Which of the following algorithms
could also create a shortest path spanning tree starting from node v?
a) DFS and BFS
b) Prim and BFS
c) BFS only
d) DFS only
Ans:b

Greedy Strategy Interview Question Part 4

2007-10-27T10:47:00.001-07:00

32. Lossless compression refers to
a. data that can be uncompressed exactly as it was before compression
b. Huffman coding
c. The assumption that data need not be stored perfectly
d. a and b
Ans. d
Huffman coding is an example of lossless compression wherein the characters are converted into a binary code such that the original text can be retrieved as it was.

33. State whether the following statement is true or false
The basic idea in Huffman coding is to assign short codewords to those input blocks with low probabilities and long codewords to those with high probabilities.
Ans. False
The basic idea in Huffman coding is to assign short codewords to those input blocks with high probabilities and long codewords to those with low probabilities.

34. Dijkstra’s Algorithm determines
a. Shortest Path between every pair of vertices
b. Paths between every pair of vertices
c. Paths between every pair of vertices
d. Shortest path only between a given source and multiple destinations
Ans. d

35. Which is an example of a minimum spanning tree algorithm?
a. Kruskal's
b. Huffman
c. Euler's
d. Fibonacci
Ans. a

36.. Kruskal's Algorithm can be solved on the Bases of __________.
a. Cost
b. Nodes
c. Edges
d. Tree
Ans. a

37. Huffman code is a
a. fixed-to-variable length code
b. variable-to-fixed length code
c. variable-to-variable length code
d. fixed-to-fixed length code
Ans. a

38. An edge of a spanning tree is called a ________
Ans. branch

39. An edge in the graph that is not in the spanning tree is called a ________
a. tree
b. branch
c. chord
d. root
Ans. c

40. Spanning trees are important because of following reasons.
i)Spanning trees construct a sparse sub graph that tells a lot about the original graph.
ii)Spanning trees a very important in designing efficient routing algorithms.
iii)Some hard problems (e.g., Steiner tree problem and traveling salesman problem) can be solved approximately by using spanning trees.
iv)Spanning trees have wide applications in many areas, such as network design, etc. Which of the following options are correct?
a. i,ii and iii
b. i and iii
c. all the above
d. ii and iv
Ans. c
41. A minimum spanning tree is a graph that has the following properties:
● it spans the graph
● it is a minimum
State whether the above statement is true or false.
Ans. True
42. Which of the following algorithms solves the all-pair shortest path problem?
a. Dijkstra’s algorithm
b. Floyd’s algorithm
c. Prim’s algorithm
d. Warshall’s algorithm
Ans. b
Dijkstra’s algorithm solves single source shortest path problem.Warshall’s algorithm finds transitive closure of a given graph.Prim’s algorithm constructs a minimum cost spanning tree for a given weighted graph
43. In kruskal’s algorithm
i)the selection function chooses edges in increasing order of their length
ii)cycle has to be formed
iii)result is a forest of trees that grows until all the trees merge into one.
The correct options are
a. i and ii
b. i,ii and iii
c. i and iii
d. ii and iii
Ans. c
In kruskal's algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree

Greedy Strategy Interview Question Part 3

2007-10-27T10:46:00.000-07:00

23. ___________ is to be sent with Huffman code for its decompression.
a. Original string
b. only tree
c. Only frequent occurring characters
d. Coded string
Ans. d
24. In Huffman coding,the code with highest frequency character contains _________ bit(s).
a. Maximum
b. Minimum
c. One
d. Equal
Ans. b
25. Greedy algorithms are
a. simple and straightforward
b. longsighted in approach
c. many problems can be solved correctly by greedy approach
d. all of the above
Ans. a
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems
26. To construct the solution in an optimal way,Greedy algorithm maintains two sets. One contains ___________ and the other contains ___________ .
Ans. chosen items and rejected items .
27. The greedy algorithm consists of following functions.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.
The correct options are
a. 1 and 2
b. 2 and 4
c. 1,2 and 3
d. All the above
Ans. d
The greedy algorithm consists of four (4) function.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.

28. The ____________ and _________________ are two ingredients in the problem that lend to a greedy strategy .
Ans. Greedy-choice property and optimal substructure.
The "greedy-choice property" and "optimal substructure" are two ingredients in the problem that lend to a greedy strategy.
29. A greedy strategy usually progresses in a _____________, making one greedy choice after another.
a. bottom-up fashion
b. linear fashion
c. top-down fashion
d. none of the above
Ans. c
A greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each problem to a smaller one.
30. Greedy-Choice Property says that a globally optimal solution can be arrived at by making a ________ optimal choice.
Ans. locally
Greedy-Choice Property says that a globally optimal solution can be arrived at by making a locally optimal choice .
31. A spanning tree of a graph is any tree that includes every ________ in the graph.
Ans. vertex

Greedy Strategy Interview Question Part 2

2007-10-27T10:45:00.000-07:00

11. Lossless encoding techniques include
i) Run length encoding
ii) Huffman encoding
iii) Transform coding
The correct option is
a. i
b. i and ii
c. all of the above
d. only ii
Ans. b
12. Disjoint sets are __________ sets.
Ans. mutually exclusive/independent
13. The disjoint set is an abstract data type that supports ___________ and _________ operations.
Ans. Union and find
14. Union(x,y) is an operation in disjoint set which means merge the set containing x with the set containing y. (True or False)
Ans. True
15.Find(x) should return some representation of the set containing x. (True or False)
Ans. True
16.Running time of find(i) is proportional to the _________of the tree containing node i.
Ans. height
17. Minimum spanning tree gives shortest distance between
a. any two nodes
b. source and destination
c. source and any node
d. none
Ans. b
In minimum spanning tree,we get the shortest path between the source and the destination.
18. The shortest path algorithm gives minimum distance between
a. any two nodes
b. source and destination
c. all of the above
d. source and any node
Ans. a
19. The cost of a path between two vertices is the sum of the _________ of the edges in that path.
Ans. costs
20. Huffman’s coding technique uses ____________ algorithm.
Ans. Greedy algorithm
21. Huffman coding uses __________
a. tree
b. graph
c. linked list
d. stack
Ans. a
22. The data structure used for the implementation of Kruskal’s algorithm is
a. Graph
b. Linked list
c. stack
d. disjoint set
Ans. d

Greedy Strategy Interview Question Part 1

2007-10-27T10:43:00.000-07:00

1. Huffman’s greedy algorithm
a is a lossy compression technique
b. computes frequency of occurrence of characters
c. assigns binary codes to a string of characters
d. b and c
Ans. d

2. Huffman’s greedy algorithm has a total running time of
a. O(log n)
b.O(n)
c. O(nlogn)
d. O(n*n)
Ans. c

3. Greedy algorithms are used for
i)optimization problems
ii)always make a locally optimal choice
iii)widely applied:Dijkstra’s algorithm and MST
The correct options are
a)i and ii
b)i and iii
c)all of the above
d)only i
Ans. c
4. A graph may have ________ number of spanning trees.
Ans. many
5. Kruskal’s algorithm is also known as _________ algorithm.
Ans. Greedy algorithm
6. Kruskal’s algorithm works faster on sparse graphs.( True or False).
Ans. True
7. Every spanning tree on n points contains exactly
a. n edges
b. n-1 edges
c. n(n-1) edges
d. n-2 edges
Ans . b
8. the time required by Kruskal’s algorithm is _______ where E stands for edges and V for vertices
a. O( |E| + log |V| )
b. O( ElogV)
c. O( |E|log|V| )
d. O( log |V| )
Ans. c
9. A minimum spanning tree is a minimum-weight tree in a ________ graph which contains all of the graph’s vertices.
Ans. weighted
10. Travelling salesman problem can be best solved by using a
a. Minimum spanning tree algorithm
b. Dijkstra algorithm
c. Floyd algorithm
d. None of the above
Ans. a

Selection Sort Interview Question Part 3

2007-10-27T10:42:00.002-07:00

27. What is the output of selection sort for the following numbers after the 8th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 6 7 8 9 10
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

28. What is the output of selection sort for the following numbers after the 9th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 6 7 8 9 10
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

29. What is the output of selection sort after the 1st pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:a

30. What is the output of selection sort after the 2nd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:b

31. What is the output of selection sort after the 3rd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:c

32. What is the output of selection sort after the 4th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:d

33. What is the output of selection sort after the 5th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 6 8 7 9
Ans:d

34. What is the output of selection sort after the 6th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 3 4 5 6 7 8 9
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:a

Selection Sort Interview Question Part 2

2007-10-27T10:42:00.001-07:00

14.The efficiency of selection sort is
a.n*(n/2)
b.n*n
c.n(n-1)/2
d.none
Ans:a
The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).
15.The frequency count of selection sort is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b
(n-1)+(n-2)+……+3+2+1=n(n+1)/2 – n =n(n-1)/2

16.The total number of iterations in selection sort is
a.n-1
b.n
c.n*n
d.2*n
Ans:a

17. For a List with L elements numbered from 0 to L-1 , the selection sort algorithm is

Set marker to L-1 (begin with the last element in the list)
While marker>0
Find the largest element in the range numbered from 0 to marker.
Swap that element with the element at location marker.
Increase marker back by 1
Assume the initial list is 3, 9, 1,7 ,2

What are the correct intermediate output values during the process of sorting?
a.3, 2, 1, 7, 9
b.3, 9, 1, 2, 7
c.1, 2, 3, 7, 9
d.9, 3, 1, 2, 7
Ans:a

18. Consider the following selection sort algorithm and the integer data set given thereafter.
For a list with L elements numbered from 0 to L-1, the selection sort algorithms is :
1. Set marker to L-1 (beginning with the last element in the list)
2. While marker >0 ;
i. Find the largest element in the range numbered from 0 to marker.
ii. Swap the largest element with the element at the location marker.
iii. Increase marker back by 1
Data set: { 4 10 2 8 3 }
If the above algorithm works on the given data set , what would not be the pair of swapping values during the
process of sorting?
(a) (3,10) (b) (4,2) (c) (2,3) (d) (10,2)
Ans: d

19. Let there be a list with L elements numbered from 0 to L-1, and consider the following algorithm:

Step 1: set marker1 to L-1 (begin with the location of the last element in the list)
Step 2: While marker > 0
Step 3: find the largest element in the range numbered from 0 to marker
Step 4: swap that element with the element at location marker.
Step 5: Increase marker by 1
The above algorithm describes
(a) Bubble sort. (b) Selection sort. (c) Insertion sort. (d)Merge sort
Ans:b
20.What is the output of selection sort for the following numbers after the first pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 6 9 3 7 2 10 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 6 9 7 3 10 2 5 8 4
Ans:c

21. What is the output of selection sort for the following numbers after the 2nd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:b

22. What is the output of selection sort for the following numbers after the 3rd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:a

23. What is the output of selection sort for the following numbers after the 4th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 3 4 7 10 9 6 8 5
Ans:d

24. What is the output of selection sort for the following numbers after the 5th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

25. What is the output of selection sort for the following numbers after the 6th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:a

26.What is the output of selection sort for the following numbers after the 7th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:b

Selection Sort Interview Question Part 1

2007-10-27T10:41:00.000-07:00

1.What is the output of selection sort after the 1st iteration given the following sequence of numbers: 14 9 4 18 45 2 37 63
a. 4 14 9 18 45 2 37 63
b. 2 9 14 18 45 4 37 63
c. 4 9 14 18 45 2 37 63
d.2 14 9 18 45 4 37 63
Ans:d

2. What is the worst case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

3.What is the average case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

4.What is the output of selection sort after the 2nd iteration given the following sequence of numbers: 16 3 46 9 28 14
a.3 9 46 16 28 14
b.3 9 14 16 28 46
c.3 9 16 14 46 28
d.none of the above
Ans:a

5.What is the best case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

6.The following loop is used for
For i<- 1 to N
For j<- i+1 to N
If(a(i)>a(j))
{
Temp=a(i);
A(i)=a(j);
A(j)=temp;
}
a.bubble sort b.selection sort c.insertion sort d.merge sort
Ans:b

7.Here is an array of six integers:
5 3 8 9 1 7
This array after the FIRST iteration in a selection sort (sorting from smallest to largest) is
a. 5 1 8 4 3 7
b. 1 8 5 4 3 7
c.1 5 8 4 3 7
d. 1 5 8 4 7 3
Ans:c
8.In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log n
D. n²
Ans:B
9.A sorting technique in which successive elements are selected in order and placed into their proper sorted positions is called
a.selection sort
b.quick sort
c.bubble sort
d.merge sort
Ans:a

10.The selection sort that uses descending priority queue as an unordered array is_____
Ans:straight selection sort

11.Straight selection sort is also called
a.Push-down sort
b. Push-up sort
c.both
d.none
Ans:a

12.The types of selection sort are
a.General selection sort b.Pull-up selection sort c. Push-up selection sort d.none
Ans:a

13.In which cases are the time complexities same in selection sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

Quick Sort Interview Question Part 2

2007-10-27T10:40:00.000-07:00

17. Which of the following statement(s) best describes the quicksort algorithm
(a)Partitioning the file into two subfiles, selecting some pivot value, sorting the two sub-files sequentially.
(b)Selecting some pivot value, partitioning the file into N sub-files and sorting independently, merging all sub-files into single file.
(c)Selecting some pivot value, partitioning the file into two sub-files, sorting the two sub-files independently in recursive way.
(d)Partitioning the file into two sub-files, sorting these two sub-files independently, then partitioning two sub-files into four sub-files, sorting these four sub-files independently. This process is repeating until entire file becomes sorted.
Ans:c

18. If one chooses the middle key as the pivot, what would be the Big-O value for the Best case of the Quick Sort Algorithm? (a) n*n (b) n (c) a constant (d) n log n
Ans:d

19. Which of the following is/are correct in connection with the time complexity of the quick sort algorithm in the worst case, best case and average case respectively? (a) n*n, n, nlog n (b) nlog n, nlog n, nlog n (c) n*n, nlog n, nlog n (d) n, n, nlog n
Ans:c
20. The basic quicksort algorithm is recursive and consists of four steps, but the following steps are in incorrect order.
(i) Pick any element v in S. This element is called pivot.
(ii) Return the result of Quicksort(L), followed by v, followed by quicksort(R)
(iii) Partition S – {v} (the remaining elements in S) into two disjoint groups: L={x S – {v} | x =< v} and R={x S – {v} | x >v }
(iv) If the number of elements in S is 0 or 1 then return.

Which of the following is the correct order of steps in the quicksort algorithm?
(a) (iv), (iii),(i),(ii)
(b) (i),(ii),(iii),(iv)
(c) (iv), (i),(iii),(ii)
(d) (i),(iii),(ii),(iv)
Ans:c

21. Which of the following activities is/are not relevant to the quick sort algorithm?
(a) Initially divide the entire file into N sub-files.
(b) Choose a pivot value and store it in a correct place.
(c) The sorting technique is sorting by exchange.
(d) The sorting technique is sorting by selection.
Ans:a,d
22. If the last element is chosen as the pivot at each iteration, the Quick-sort tree for
the sequence in question 1 will have height:
a)1
b) 2
c) 3
d)4
Ans:c

23. If Quick-sort were implemented so that the element at position n/2 is chosen as
the pivot, which of the following sequences would be the worst input?
a) 1 2 3 4 5 6 7
b) 2 3 4 1 5 6 7
c) 7 6 5 4 3 2 1
d) 5 6 7 1 2 3 4
e) 6 4 2 7 1 3 5
Ans:d

24. Given a large amount of highly random data which fits into the computers RAM,
the best choice for sorting would be:
a) Bubble-sort
b) Insertion-sort
c) Merge-sort
d) Quick-sort
Ans:d

25. In Quick sort , after the completion of every pass the pivot/key element moves to the ________ position. a.first b.second c.middle d.exact sorted position
Ans:d

Quick Sort Interview Question Part 1

2007-10-27T10:39:00.002-07:00

1.Quick sort is 1.in-place 2.non in-place 3.stable 4.non-stable a.1 and 3 b.1 and 4 c.2 and 3 d.2 and 4
Ans:b

2.What is the average case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

3.What is the worst case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

4.What is the best case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

5.Quick sort is also known as a. Pointer sort b.External sorting c.Both d.none
Ans:c

6.What is the output of quick sort after the 1st iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45 a. 60 45 50 55 65 85 80 70 75 b.60 45 50 55 65 85 80 75 70 c. 45 60 50 55 65 85 80 75 70 d. 60 45 50 65 55 85 80 75 70
Ans:b

7.Which sorting technique is also called partition exchange sort? a.selection sort b.quick sort c.bubble sort d.merge sort
Ans:b

8. In which cases are the time complexities same in quick sort? a. Worst and Best b. Best and Average c. Worst and Average d. Worst, average and Best
Ans:b

9. Quick sort uses ___________. a. Divide and Conquer Technique b. Greedy Approach c. Back Tracking d. None of the above
Ans. a

10. What pattern of splits gives the worst-case performance for quick sort? a. Ascending order. b. Descending order.
c. Any order.
d. None of the above.
Ans. b

11.In quick sort the pivot value is usually the
a.first element
b.last element
c.middle element
d.any element
Ans: d

12. What is the output of quick sort after the 2nd iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 60 45 50 55 65 85 80 70 75
b.60 45 50 55 65 85 80 75 70
c.55 45 50 60 65 70 80 75 85
d. 60 45 50 65 55 85 80 75 70
Ans:c

13.What is the output of quick sort after the 3rd iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 60 45 50 55 65 85 80 70 75 b.60 45 50 55 65 85 80 75 70 c.55 45 50 60 65 70 80 75 85 d. 50 45 55 60 65 70 80 75 85
Ans:d

14.What is the output of quick sort after the 4th iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 45 50 55 60 65 70 75 80 85
b.60 45 50 55 65 85 80 75 70
c.55 45 50 60 65 70 80 75 85
d. 50 45 55 60 65 70 80 75 85
Ans:a

15. Which of the following statements about Quick sort is/are incorrect?
a. Average running time is O(N log N).
b. The best case always occurs when the pivot partitions the set of numbers to be sorted into two equal-sized subsets.
c. The worst case always occurs when the pivot partitions the set of numbers to be sorted into two equal-sized subsets.
d. The worst case always occurs when the smallest item is selected from the items to be sorted as the pivot.
Ans. c

16. Which statement(s) is/are correct for the Quick sort algorithm?
(i) Quick Sort is still best sorting algorithms, known for sequential computers
(ii) It works by partitioning the file into two sub files and sorting two sub files independently.
(iii) The pivot value can be chosen in an arbitrary way.
a.(i) only
b.(i) and (iii) only
c.(i), (ii) and (iii).
d.(ii) and (iii)
Ans:c

Merge Sort Interview Question Part 2

2007-10-27T10:39:00.001-07:00

16. Given the initial sequence : 3,41,52,26,38,57,9,49 ,at the last step in the merge sort .the sequences to be merged are
a.{ 3,26,52,41} and {38,49,57,9}
b.{ 3,26,41,52} and {9,38,49,57}
c. {3,9,41,52} and {26,38,49,57}
d. {3,9,26,38} and {41,49,52,57}
Ans. b

17. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
a. The array elements form a heap
b. Elements in each half of the array are sorted among themselves
c. Elements in the first half of the array are less than or equal to elements in the second half of the array
d. . Elements in the first half of the array are greater than or equal to elements in the second half of the array
Ans. b
18. Given the initial sequence: {85 24 63 47 17 31 96 50}, at the last step in the
merge sort, the sequences to be merged are:
a). {24 47 63 85} and {17 31 50 96}
b). {17 24 31 47} and {50 63 85 96}
c). {24 85} {47 63} {17 31} and {50 96}
d). {17 24 31 47 63 85 96} and {50}
e). depends on choice of pivot
Ans. a
19.On each iteration,the size of the sorted lists in a merge sort
a. doubles
b. halves
c.remains the same
d. increases 4 times
Ans. a
On each iteration, the size of the sorted lists doubles, form 1 to 2 to 4 to 8 to 16 ...to n.

20. What is the output of merge sort after the 1st pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:a

21. What is the output of merge sort after the 2nd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:b

22. What is the output of merge sort after the 3rd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:c

23. In every pass, maximum number of comparisons in the merge sort is _________.
a.n-1
b.n
c.log n
d.n*n
Ans:a

24.What does the following pseudocode do?

function sort(m)
var list left, right
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = sort(left)
right = sort(right)
result = app(left, right)
return result
end if
a. quick sort
b. selection sort
c. insertion sort
d. merge sort
Ans. d

Merge Sort Interview Question Part 1

2007-10-27T10:20:00.002-07:00

1. What is the average case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

2. What is the worst case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

3. What is the best case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

4. What is the output of merge sort after the 1st pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 12 25 33 37 48 57 86 92
c.12 25 33 37 48 57 86 92
d. 25 57 37 48 12 92 33 86
Ans:d

5. What is the output of merge sort after the 2nd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 12 25 33 37 48 57 86 92
c.25 37 48 57 12 33 86 92
d. 25 57 37 48 12 92 33 86
Ans:c

6. What is the output of merge sort after the 3rd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 12 25 33 37 48 57 86 92
b. 12 25 33 37 48 57 86 92
c.12 25 33 37 48 57 86 92
d. 25 57 37 48 12 92 33 86
Ans:a

7. In which cases are the time complexities same in merge sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

8.Total numbers of passes in merge sort of 'n' numbers is _______.
a.n
b.n-1
c.log(n)
d.nlogn
Ans:c

9.Merge sort is based on the divide and conquer strategy.it consists of the following steps
a. Divide,Recursive and Conquer
b. Divide and Conquer
c. Divide and Recursive
d. None of the above
Ans. a

10.Given two sorted lists of size m,n ,the number of comparisons needed in the worst case by the merge sort algorithm is
a.mn b.max(m,n) c.min(m,n) d.m+n-1
Ans:d
Each comparison puts 1 element in the final sorted array. So,in the worst case m+n-1 comparisons are needed.

11. Suppose the array A contains 14 elements as follows:
A = [66, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77, 30]
How many Passes are required to sort the above array A using the Merge sort algorithm?
a. 3
b. 4
c. 5
d. 7
e. 14
Ans. c

12. If you are provided with two files whose contents are sorted and the requirement is to copy the contents of both the files into a third file which should be sorted. In this case which of the sorting techniques can be an appropriate one?
a.Selection sort
b.Bubble sort
c.Merge sort
d.insertion sort
Ans:c

13. The merge sort algorithm involves the following steps.
(i) Recursively sort the 1st and 2nd halves separately
(ii) Merge the two-sorted halves into a sorted group.
(iii) If the number of items to sort is 0 or 1, return.

Which is the correct order of instructions in merge sort algorithm?
(a) (i),(ii),(iii)
(b) (ii),(iii),(i)
(c) (iii),(ii),(i)
(d) (iii),(i),(ii)
Ans:d

14. What is the output of merge sort after the 1st pass given the following sequence of numbers : 3,41,52,26,38,57,9,49
a. 3,41,26,52,38,57,9,49
b. 3,41,52,26,38,57,9,49
c. 3,41,52,26,38,57,9,49
d. 3,41,38,26,52,9,49,57
Ans. a

15. What is the output of merge sort after the 2nd pass given the following sequence of numbers : 3,41,52,26,38,57,9,49
a. 3,26,41,52,38,9,49,57
b. 3,26,41,52,9,38,49,57
c. 3,26,38,9,49,57,41,52
d. 3,26,41,52,38,49,57,9
Ans. b

Insertion Sort Interview Question Part 4

2007-10-27T10:20:00.001-07:00

37. The output of 7th iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a. 0 2 3 4 5 7 6 1
b.0 2 3 4 5 6 7 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:b

38. The output of 8th iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a. 0 2 3 4 5 7 6 1
b.0 2 3 4 5 6 7 1

c. 0 1 2 3 4 5 6 7

d. 0 3 4 5 7 2 6 1
Ans:c

39. The number of positions the inserted element has moved after the 1st iteration is
a.0 b.2 c.4 d.6
Ans:a

40. The number of positions the inserted element has moved after the 2nd iteration is
a.0 b.2 c.4 d.6
Ans:a

41. The number of positions the inserted element has moved after the 3rd iteration is
a.0 b.2 c.4 d.6
Ans:b

42. The number of positions the inserted element has moved after the 4th iteration is
a.0 b.2 c.4 d.6
Ans:b

43. The number of positions the inserted element has moved after the 5th iteration is
a.0 b.2 c.4 d.6
Ans:b

44. The number of positions the inserted element has moved after the 6th iteration is
a.0 b.2 c.4 d.6
Ans:c

45. The number of positions the inserted element has moved after the 7th iteration is
a.0 b.1 c.4 d.6
Ans:b

46. The number of positions the inserted element has moved after the 8th iteration is
a.0 b.2 c.4 d.6
Ans:d

5 7 0 3 4 2 6 1 (0)
5 7 0 3 4 2 6 1 (0)
0 5 7 3 4 2 6 1 (2)
0 3 5 7 4 2 6 1 (2)
0 3 4 5 7 2 6 1 (2)
0 2 3 4 5 7 6 1 (4)
0 2 3 4 5 6 7 1 (1)
0 1 2 3 4 5 6 7 (6)

On the left side the sorted part of the sequence is shown in red. For each iteration, the number of positions the inserted element has moved is shown in brackets. Altogether this amounts to 17 steps.

47. What is the output of insertion sort after the 7th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 4 5 6 7 8 9
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 9 8
Ans:b

48. What is the output of insertion sort after the 9th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
A.1 2 3 4 6 7 8 9 10 5
b. 2 3 4 6 7 8 9 10 1 5
c. 1 2 3 4 5 6 7 8 9 10
d. 3 4 6 8 9 10 7 2 1 5
Ans:c

49. ________ is a sorting technique that sorts a set of records by inserting records into an existing sorted file.
a. quick sort
b. insertion sort
c. selection sort
d. merge sort
Ans. b

Insertion Sort Interview Question Part 3

2007-10-27T10:19:00.002-07:00

25. What is the output of insertion sort after the 4th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 6 8 10 9 7 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 6 8 9 10 7 2 1 5
Ans:a

26. What is the output of insertion sort after the 5th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 6 8 10 9 7 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 4 6 7 8 9 10 2 1 5
d. 3 4 6 8 9 10 7 2 1 5
Ans:d

27. What is the output of insertion sort after the 6th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 6 8 10 9 7 2 1 5
b. 3 4 6 7 8 9 10 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 6 8 9 10 7 2 1 5
Ans:b

28. What is the output of insertion sort after the 7th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
A.1 2 3 4 6 7 8 9 10 5
b. 2 3 4 6 7 8 9 10 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 6 8 9 10 7 2 1 5
Ans:b

29. What is the output of insertion sort after the 8th iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
A.1 2 3 4 6 7 8 9 10 5
b. 2 3 4 6 7 8 9 10 1 5
c. 1 2 3 4 5 6 7 8 9 10
d. 3 4 6 8 9 10 7 2 1 5
Ans:a

30. Consider the following insertion sort algorithm and the Data set of integers given thereafter:

Setp 1 : initialise marker1 to 1 ( the location of the second element in the list)
Step 2 : while marker1 < L
Setp 3 : if Element[marker1] < Element[marker1- 1 ] , store Element [marker1] in a temporary location temp. Initialise marker2 to marker1 – 1 ( the location just before the marker1)
Step 4 : while Element[marker2] > temp and marker2 >= 0. Shift Element[marker2] to location marker2+1.( this slides the element over to make room to its left). Decrease marker2 by 1
Step 5 : insert temp into the location last vacated by a shift
Setp 6 : increase marker1 by 1.

Data set: 3 9 1 7 2
Note: There are L elements numbered from 0 to L-1 stored in the array.

Which of the following values are not the temp values during the process of sorting?
(a) 1 (b)3 (c)7 (d)2
Ans: b

31. The output of 1st iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a. 5 7 0 3 4 2 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:a

32. The output of 2nd iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a.5 7 0 3 4 2 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:a

33. The output of 3rd iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a.5 7 0 3 4 2 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:b

34. The output of 4th iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a.5 7 0 3 4 2 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:c

35. The output of 5th iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a.5 7 0 3 4 2 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:d

36. The output of 6th iteration for the sequence 5 7 0 3 4 2 6 1 using insertion sort is
a.0 2 3 4 5 7 6 1
b. 0 5 7 3 4 2 6 1

c. 0 3 5 7 4 2 6 1

d. 0 3 4 5 7 2 6 1
Ans:a

Insertion Sort Interview Question Part 2

2007-10-27T10:19:00.001-07:00

13. What is the output of insertion sort after the 4th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 5 7 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:b

14. What is the output of insertion sort after the 5th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 4 5 7 9 8 6
c. 3 4 1 5 6 8 7 9
d. 1 3 5 7 8 9 4 6
Ans:d

15. What is the output of insertion sort after the 6th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 4 5 7 8 9 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 9 8
Ans:b

16.The frequency count of insertion sort in the worst case is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b

17.The frequency count of insertion sort in the average case is
a.n*n
b.n(n-1)/2
c.n(n-1)/4
d.logn
Ans:c

18.Insertion sort is an example of
a.incremental algorithm
b.decremental algorithm
c.both
d.none
Ans:a

19.The best case running time T(n) for insertion sort is
a.a quadratic function of n
b.a linear function of n
c.a logarithmic function of n
d.none
Ans:b
Complexity is O(n)

20. The worst case running time T(n) for insertion sort is
a.a quadratic function of n
b.a linear function of n
c.a logarithmic function of n
d.none
Ans:a
Complexity is O(n*n)

21. The sort that keeps making the left side of the array sorted until the whole array is sorted and which sorts the values seen so far and repeatedly inserts unseen values in the array into the left sorted array is called
a.selection sort
b.bubble sort
c.insertion sort
d.heap sort
Ans:c
22. What is the output of insertion sort after the 1st iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 10 6 8 7 9 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 10 4 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:c

23. What is the output of insertion sort after the 2nd iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 10 6 8 7 9 2 1 5
b. 3 4 10 6 8 9 7 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:b

24. What is the output of insertion sort after the 3rd iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 6 8 10 9 7 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:b

Insertion Sort Interview Question Part 1

2007-10-27T10:17:00.002-07:00

1.Insertion sort is 1.in-place 2.out-place 3.stable 4.non-stable
a.1 and 3 b.1 and 4 c.2 and 3 d.2 and 4
Ans:a
The array is sorted in-place because no extra memory is required. Stable sort retains the original ordering of keys when identical keys are present in the input data.

2.Sorting of playing cards is an example of
a.Bubble sort b. Insertion sort c.Selection sort d.Quick sort
Ans:b

3. For insertion sort, the number of entries we must index through when there are n elements in the array is
a. n entries b.n*n entries c.n-1 entries d.none of the above
Ans:c
Assuming there are n elements in the array we must index through n - 1 entries. For each entry we may need to examine and shift up to n - 1 other entries resulting in a O(n2) algorithm.

4.What is the average case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

5.What is the worst case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

6. What is the best case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:a

7.What is the output of insertion sort after the 1st iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:a

8. The following loop is used for
For i<- 1 to N-1
{
For j<- i+1 to N
{
If(a(j) {
Temp=a(j);
For k<- j to i+1
A[k]=a[k-1];
}
}
A(i)=temp;
}
a.bubble sort b.selection sort c.insertion sort d.merge sort
Ans:c

9. Total number of comparisons for insertion sort is
a.n(n-1)/2
b. n(n+1)/2
c.n
d.n*n
Ans:a

10. In which cases are the time complexities same in insertion sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:c

11. What is the output of insertion sort after the 2nd iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 7 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:a

12.What is the output of insertion sort after the 3rd iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 5 7 9 8 4 6
Ans:d

Heap Sort Interview Question Part 2

2007-10-27T10:17:00.001-07:00

17. The __________ data structure is a n array object that can be viewed as a nearly complete binary tree.
a. stack
b. queue
c. binary heap
d.linked list
Ans. c

18. The MAX-HEAPIFY procedure has running time
a. O(n)
b. O(n log n)
c. O(log n)
d. O(n²)
Ans. c

19. The worst case running time of MAX-HEAPIFY on a heap of size n is ______
a. O(lg n)
b. θ (lg n)
c. Ω (lg n)
d. O(n)
Ans. c

20. The worst case running time of heapsort is
a. O(n log n)
b. O(log n)
c. Θ(log n)
d. Ω(n log n)
Ans. d

21. Which of the following arrays represent descending (max) heaps?
a. [10,7,7,2,4,6]
b. [10,7,6,2,4,7]
c. [10]
d. [10,6,7,2,4,6]
Ans. c

22. Which of the following is/are incorrect?
a. The worst case complexity of Heap Sort is O(n2).
b. A heap can be easily constructed in an array so that the left and right children of a node at index k have indexes 2k and 2k+1 respectively.
c. The worst case complexity of Heap Sort is O(n log n).
d. A binary tree can be transformed into a heap by systematically moving items up in the binary tree, starting from the leaf nodes.
Ans. a

23. Consider the following statements:
(i) In a max heap, the value of each non-leaf node is strictly less than the values of its children.
(ii) A binary heap is a complete binary tree.
(iii) All complete binary trees are heaps.

Which of the above statement(s) is/are correct?
a. (i) only
b. (ii) only
c. (iii) only
d. (i) and (ii) only
Ans. b

24. Which of the following statement(s) describe properties of a Heap

(i) A heap is a special kind of binary tree, that does not leave any gap in the array implementation.
(ii) The value stored at any node is larger than the value stored in it’s children.
(iii) A heap may be easily constructed from an array. The left child of a node k has index 2k and right child has index 2k+1.
(iv) Level of all leaf nodes must be last level or last level-1.
a.(i), (ii), (iii) and (iv) only.
b.(i) and (ii) only.
c.(i) and (iii) only.
d.(i), (ii) and (iii) only.
Ans:d

25. {2,8,6,1,10,15,3,12,11} is a set of integers. If you create a maximum heap and store it in an array, what would be the final values in the array?

(a)1,2,3,6,8,10,11,12,15
(b)15,12,11,10,8,6,3,2,1
(c) 15,12,6,11,10,2,3,8,1
(d)15,12,10,11,2,6,3,1,8
Ans:d

26. Consider the following statements:
(i) In a max heap, root value is always higher than its children (if any).
(ii) A heap is fully filled from level 1 to level last –1.

Which of the above statements is/are correct?
a.only 1 b.only 2 c.both 1 and 2 d.none
Ans:c
27. The following sequence represents a max heap stored in an array: 60 40 50 35 32
30 20 34 10 25. What would be the content of the array after 3 removeMax (& reheap)
operations of a heap-sort algorithm implemented in place?
a). 35 34 30 10 32 25 20 40 50 60
b). 35 34 30 10 32 25 20 60 50 40
c). 60 50 40 35 32 30 20 34 10 25
d). 40 10 50 34 60 32 35 25 30 20
Ans:a

28. Inserting an item into a heap takes O(n2) time.(T/F)
false -- O(lg n)

Heap Sort Interview Question Part 1

2007-10-27T10:15:00.002-07:00

1. What is the average case complexity for heap sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

2.What is the best case complexity for heap sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

3.The condition applicable for max-heap is
a.A[Parent(i)]>=A[i]
b. A[Parent(i)]<=A[i]
c. A[Parent(i+1)]>A[i]
d. A[Parent(i+1)]Ans:a

4.The condition applicable for min-heap is
a.A[Parent(i)]>=A[i]
b. A[Parent(i)]<=A[i]
c. A[Parent(i+1)]>A[i]
d. A[Parent(i+1)] Ans:b

5.The number of operations required for heap sort regardless of the order of input
a.O(1)
b.O(logn)
c.O(nlogn)
d.O(n*n)
Ans:c

6.In which cases are the time complexities same in heap sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

7.The heap sort property is __________.
a. A[Parent(I)] >=A[I]
b. A[Parent(I)] <=A[I]
c. A[Parent(I)]!=A[I]
d. None of the above
Ans. a

8.If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? (most appropriate answer)
a. data[0]
b. data[n-1]
c. data[n]
d. data[2*n + 1]
e. data[2*n + 2]
Ans. a

9.What is the worst-case time for heapsort to sort an array of n elements?
a. O(log n)
b. O(n)
c. O(n log n)
d. O(n²)
Ans. c

10.The frequency count for heapify process is(all logarithms are to the base 2)
a.log n
b.n log n
c.n*n
d.none
Ans:a

11. The frequency count for heap sort process is(all logarithms are to the base 2)
a.log n
b.n log n
c.n*n
d.none
Ans:b

12.The process of converting an array into a heap by executing heapify progressively closer to the root is called _________
Ans:build-heap
13.For an array of n nodes, build heap takes _______ time
A.O(logn)
b.O(n)
c.O(nlogn)
d.none
Ans:b
14. The Time Complexity of the Huffman code generation algorithm, when the forest is represented as a minHeap is:
(i) O(n² )
(ii) O(log n)
(iii) O(n log n)
(iv) O(n)
Answer: O(n log n) where the forest is stored as a minHeap. Each time the minimum element is deleted from the heap it costs log n. Since there are 2 deletions and one insertion during each iteration until the forest is empty,it costs n log n to build the tree.

15. The Time Complexity to list all the elements in a Heap is
(i) O(log n)
(ii) O(n log n)
(iii) O(1)
(iv) O(n)
Answer: Perform any order traversal of the tree - cost is O(n)

16. Draw the min-max heap after insertion of the following sequence of numbers 6, 3, 2, 5, 1, 1, 3.
Answer:
Order of nodes is:
level 1: 1
Level 2: 6 3
Level 3: 5 2 1 3

Graphs Interview Questions Part 7

2007-10-27T10:15:00.001-07:00

62. Given the graph ,the resulting breadth-first traversal will be

a. ABCDEFGH
b. ACDGBFEH
c. ACDBEFGH
d. ACDGBEFH
Ans. b
Refer pg-565 fig.b of Data Structures Using C and C++ by Tanenbaum

63. Using adjacency matrix representation,the efficiency of breadth-first search is
a. O(n+n²) or O(n²)
b. O(e)
c. O(n)
d. O(n+e)
Where n is the number of graph nodes and e is the number of edges in the graph
Ans. a

64. Using adjacency list representation,the efficiency of breadth-first traversal is
a. O(n+n²)
b. O(e)
c. O(n)
d. O(n+e)
Ans. d
Traversing all successors of all nodes is O(e) and assuming that the graph nodes are organized as an array or a linked list ,visiting all n nodes is O(n).hence,efficiency is O(n+e).

65. The adjacency matrix representation size is equal to the number of nodes available in the graph.(T/F)
Ans:True

66.A weighted graph has a weight/cost of construction for
a.no edge
b.1 edge
c.2 edges
d.each edge
Ans:d

67.The adjacency matrix representation mat[i][j] has a value ____ when there is an edge from ith to jth node
a.0
b.1
c.2
d.can be any value
Ans:b

68. The adjacency matrix representation mat[i][j] has a value ____ when there is no edge from ith to jth node
a.0
b.1
c.2
d.can be any value
Ans:a

69. If there is a solution breadth-first search will find it regardless of the kind of graph. However, if the graph is infinite and there is no solution breadth-first search will diverge.What does this property mean?
a. BFS is complete
b. BFS is incomplete
c. BFS is optimal
d. BFS implements queue
Ans. a
Breadth-first search is complete. This means that if there is a solution breadth-first search will find it regardless of the kind of graph. However, if the graph is infinite and there is no solution breadth-first search will diverge.
70. Breadth-first search is _______ since it always returns the result with the fewest edges between the start node and the goal node.
a. optimal
b. not optimal
c. complete
d. incomplete
Ans. b
In general breadth-first search is not optimal since it always returns the result with the fewest edges between the start node and the goal node. If the graph is a weighted graph and therefore has costs associated with each step a goal next to the start does not have to be the cheapest goal available.
71. _________ is a good technique for graph when there are many possible solutions, and you only want one.
a. Breadth first search
b. Depth first search
c. Postorder
d. Inorder
Ans. b
Depth first search is good when there are many possible solutions, and you only want one (and you don't care which one). It may be less appropriate when there is only one solution, or if you want the shortest one.

Graphs Interview Questions Part 6

2007-10-27T10:14:00.003-07:00

49. Determining the shortest path from every vertex to every other vertex in a weighted graph (with non-negative weights) using Dijkstra's algorithm takes O(V3) time. (T/F)
Ans. True -- determining the shortest path from a single vertex s to every other vertex takes O(V2) time. So determining the shortest path for every vertex will take O(V3) time.
51. Which one of the following is a faster technique to test if (x,y) is in a graph?
a. adjacency list
b. adjacency matrix
c. Kruskal’s algorithm
d. Dijkstra’s algorithm
Ans. b

52. Adjacency lists are faster to find the degree of a vertex as compared to adjacency matrix. True or False
Ans. True

53. _________ is a graph representation that occupies less memory on small graphs.
a. forest
b. adjacency list
c. adjacency matrix
d. tree
Ans. b because for adjacency list its (m+n) whereas for matrix its n^2.

54. _________ is a graph representation that occupies less memory on big graphs.
a. adjacency matrix
b. adjacency list
c. forest
d. queue
Ans. a

55. Faster traversal in a graph is possible in which representation?
a. forest
b. adjacency list
c. adjacency matrix
d. tree
Ans. b
adjacency lists vs. adjacency matrix
56. Edge insertion or deletion is better in adjacency matrices as compared to adjacency list. (True or False)
Ans. True
adjacency matrices O(1) vs. O(d)

57. Given the graph, the depth-first traversal will be

a. ACGBEFHD
b. ABCDEFGH
c. ACDBEFHG
d. ACGDEFBH
Ans. a

58. Given the following graph,the resulting depth-first traversal will be

a. BEFGHCAD b. BFEGHCAD c. BEGHFCAD d. BEFHGCAD
Ans. a

Refer Pg-565 for the resulting tree (Data Structures Using C and C++ by Tanenbaum)

59. Depth-first traversal method in a graph
i. creates a spanning forest
ii. can be used to determine if an undirected graph is connected
iii. to identify the connected components of an undirected graph
The correct options are
a. i only
b. i and ii only
c. ii only
d. i,ii and iii
Ans. d

60. Using adjacency matrix representation,the efficiency of depth-first search is
a. O(n+n²) or O(n²)
b. O(e)
c. O(n)
d. O(n+e)
Where n is the number of graph nodes and e is the number of edges in the graph.
Ans. a
Refer Pg-573 of Data Structures in c and C++ by tanenbaum
61. Using adjacency list representation,the efficiency of depth-first traversal is
a. O(n+n²)
b. O(e)
c. O(n)
d. O(n+e)
Ans. d
Traversing all successors of all nodes is O(e) and assuming that the graph nodes are organized as an array or a linked list ,visiting all n nodes is O(n).hence,efficiency is O(n+e).

Graphs Interview Questions Part 5

2007-10-27T10:14:00.001-07:00

36. A structure for representing a graph in which the presence of arcs between nodes is is indicated by an entry in a matrix is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. c

37. A structure for representing a graph in which the arcs are stored as lists of connections between nodes is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. d

38. The amount of space required to store an adjacency-matrix is ____ where V is a vertex set whose elements are vertices.
a. O(V)
b. O(V+E)
c. O(V²)
d. O(V*E)
Ans. c

39. Any edge in an adjacency matrix representation can be accessed,added or removed in ______ time.
a. O(V)
b. O(1)
c. O(E)
d. O(V²)
Ans. b

40. For sparse graphs,the amount of memory required to store an adjacency list is ______
a. O(V)
b. O(V²)
c. O(V+E)
d. O(V*E)
Ans. c

41. A technique that picks the next adjacent unvisited vertex until reaching a vertex that has no unvisited adjacent vertices is ________
a. Breadth-first search
b. Depth-first search
c. Adjacency matrix
d. Adjacency list
Ans. b

42. Consider the graph represented by the following adjacency list:
1: 2—3—6
2: 5—1—3
3: 2—1—7—5—6
4: 5—7
5: 2—4—3—6
6: 3—5—1
7: 3—4
Perform a Breadth First Search in the graph starting from node 1 and processing the
edges adjacent to a node in the order they appear in the adjacency list.
What is the order in which the nodes are visited?
a) 1,2,3,6,4,7,5
b) 1,2,3,6,7,5,4
c) 1,2,3,6,5,4,7
d) 1,2,3,6,5,7,4
e) 1,2,3,6,7,4,5
Ans. d

44. If you perform a Depth First Search in a binary tree, what traversal will you obtain?
a) pre-order
b) in-order
c) post-order
d) Eulerian
Ans. a

45. Given a graph G with n nodes, you want to find the node that has maximum degree.
What would be the complexity using an adjacency matrix?
a) O(1) b) O(log n) c) O(n) d) O(n log n) e) O(n2)
Ans. e

46. Given a graph G with n nodes and m edges, you want to find all the nodes with
degree 5. What would be the complexity using an adjacency list (where the degree of
each node is not stored)?
a) O(n) b) O(log m) c) O(log n) d) O(m) e) O(n logn )
Ans. d

47. Which of the following statements is incorrect?
a) A tree with n nodes has n-1 edges
b) Dijkstra does not work if some weights are negative
c) BSF finds whether a graph is connected
d) All nodes in a graph must have degree at least 1
Ans. d

48.Depth first search of a graph is
i.recursive
ii.can be parallelized
a.only I b.only ii c.i and ii d.neither I nor ii
Ans:a
Some problems have no parallel algorithms, and are called inherently serial problems. Those problems cannot be solved faster by employing more processors. One such example is depth-first search of a graph, which happens to be recursive, but can not be parallelized

Graphs Interview Questions Part 4

2007-10-27T10:13:00.001-07:00

23. For the following graph, using breadth first search, which of the following elements are present at level 3

a.8,6 b.4,5 c.8,7,6 d.2,3
Ans:a
24. For the following graph, using breadth first search, which of the following elements are present at level 4

a.8,7,6 b.4,5 c.8,6 d.7
Ans:d

25. Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree.(T/F)
Ans:True
26.Choose the right statement from the following
a.Depth first search is closely related to traveling salesman problem
b. Breadth first search is closely related to traveling salesman problem
c. Breadth first search can be thought of as being like Dijkstra's algorithm for shortest paths
d. Depth first search can be thought of as being like Dijkstra's algorithm for shortest paths
Ans:a,c
27. Depth First Search is a generalization of the ________.
a.Inorder traversal
bPreorder traversal
c.Postorder traversal
d.none
Ans:b
28. For a graph with n nodes to be Cyclic, the minimum number of edges required are________.
a.n/2
b.n+1
c.n-1
d.n
Ans:d
29. For a Graph with v nodes and e edges, the running time of DFS is given by ________.
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
30. Breadth First Search algorithm can be used in Prim's MST algorithm. (T/F)
Ans:True
31. Breadth First Search algorithm cannot be used in Dijkstra’s single source shortest path algorithm. (T/F)
Ans:False

32. A graph with V vertices and E edges can be represented with an adjacency matrix using O(V2) space. (T/F)
true.

33. Consider the following pseudo code.
void PQR(Vertex v)
{ v.visited = true ;
For each w adjacent to v
if (!w.visited)
PQR(w); }
Which of the following is/are it intended to do?
a. Finding the adjacency matrix
b. Depth first search
c. Finding the path matrix
d. Breadth first search
e. Calculating the shortest path
Ans. Depth first search
34. Depth first search is a generalization of
a. Inorder traversal
b. Preorder traversal
c. Postorder traversal
d. none of the above
Ans. b

35. Traversing a graph by visiting all the nodes attached directly to a starting node first is called ___________
a. Depth-first search
b. Breadth-first search
c. Adjacency list
d. Adjacency matrix
Ans. b

Graphs Interview Questions Part 3

2007-10-27T10:12:00.001-07:00

18. Time complexity of breadth-first search where v is the no. of nodes and e is the no. of edges is
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
Since in the worst case breadth-first search has to consider all paths to all possible nodes the time complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph.
19. Applications of BFS are
a.Finding all connected components in a graph.
b.Finding all nodes within one connected component
c.Finding the shortest path between two nodes u and v (unweighted nodes)
d.All the above
Ans:d
20.For the following graph, using breadth first search, which of the following elements are present at level 0

a.1,2,3 b.1 c.1,2 d.2,3
Ans:b
21. For the following graph, using breadth first search, which of the following elements are present at level 1

a.1,2,3 b.1 c.1,2 d.2,3
Ans:d
22. For the following graph, using breadth first search, which of the following elements are present at level 2

a.1,2,3 b.4,5 c.3,4,5 d.2,3
Ans:b

Graphs Interview Questions Part 2

2007-10-27T10:11:00.000-07:00

10. For the following graph:

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them, will visit the nodes in the following order:
a. A, B, D, F, E, C, G b. A, B, C, F, E, D, G c. A, B, D, E, F, C, G d. A, B, D, F, E, G, C
Ans:a
11. For the following graph:

Performing the depth first search without remembering previously visited nodes results in visiting nodes in the order
a. B , A, D, F, E, B , A , D, F, E, etc. forever
b. A, D,B, F, E, A, D , B , F, E, etc. forever
c. A, B, D, E, F, A, B, D, E , F etc. forever
d. A, B, D, F, E, A, B, D, F, E, etc. forever
Ans:d
Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.
12. code(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L is not full)
remove edge (v, w) from end of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}

search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to end of L
}
The code here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a Level:3

13. function (Start, Goal) {
Push(Stack,Start)
while notEmpty(Stack) {
Node := Pop(Stack)
if Node = Goal {
return Node /*the code below does not get executed*/
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
Push(Stack, Child)
}
}
}
}
The function here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a Level:3

14.The following algorithm represents
1. Put the starting node (the root node) in the queue.
2. Pull a node from the beginning of the queue and examine it.
o If the searched element is found in this node, quit the search and return a result.
o Otherwise push all the (so-far-unexamined) successors of this node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
4. repeat from step 2.
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

15. function (Start, Goal) {
enqueue(Queue,Start)
while notEmpty(Queue) {
Node := dequeue(Queue)
if Node = Goal {
return Node /*the code below does not get executed*/
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}

The function here can represent
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b
16. The immense demand for space is the reason why breadth-first search is impractical for larger problems(T/F)
Ans:True
17. Space complexity of breadth-first search where v is the no. of nodes and e is the no. of edges is
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
Since all nodes discovered so far have to be saved, the space complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph

Graphs Interview Questions Part 1

2007-10-27T10:10:00.000-07:00

1.Any search algorithm that considers outgoing edges of a vertex before any neighbors of the vertex, that is, outgoing edges of the vertex's predecessor in the search, where extremes are searched first is called
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a

2. Depth first search can be implemented with recursion.(T/F)
Ans:True

3. A search algorithm that considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex, where extremes are searched last is called
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

4. Depth first search can be implemented with
a.stack
b.queue
c.tree
d.priority queue
Ans:a

5. Breadth first search can be implemented with
a.stack
b.queue
c.tree
d.forest
Ans:b

6. For tree search, depth first search tends to require_____ memory, as compared to breadth first search.
a.less
b.more
c.same
d.cannot say
Ans:a

For tree search at least, depth first search tends to require less memory, as you only need to record nodes on the `current' path. If there are lots of solutions, but all at a comparable `depth' in the tree, then you may hit on a solution having only explored a very small part of the tree.

7. __________ may use more memory, but will not get stuck in blind alleys, and will always find the shortest path first (or at least, the path that involves the least number of steps).
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

Breadth first search may use more memory, but will not get stuck in blind alleys, and will always find the shortest path first (or at least, the path that involves the least number of steps). It may be more appropriate when exploring very large search spaces where there is an expected solution which takes a relatively small number of steps, or when you are interested in all the solutions (perhaps up to some depth limit).

8.What is the output of pre-order traversal using DFS for the given graph

a. 1 2 3 4 8 7 5 6 b. 1 2 3 4 7 8 6 5 c.1 2 3 4 8 7 6 5 d. 1 2 3 4 8 6 7 5
Ans:c

http://www.cs.duke.edu/csed/jawaa/DFSanim.html

9. What is the output of post-order traversal using DFS for the given graph

a. 2 7 8 5 6 4 1 3 b.2 7 8 5 6 4 3 1 c. 2 7 8 5 4 6 3 1 d. 2 7 5 8 6 4 3 1
Ans:b

http://www.cs.duke.edu/csed/jawaa/DFSanim.html

Bubble Sort Interview Question Part 4

2007-10-27T10:09:00.001-07:00

32. What is the output of bubble sort after the 5th pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 25 48 37 12 57 86 33 23 15 92
c. 12 25 33 23 15 37 48 57 86 92
d. 25 12 37 33 23 15 48 57 86 92
Ans:c

33. What is the output of bubble sort after the 6th pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 12 25 23 15 33 37 48 57 86 92
c. 12 25 33 23 15 37 48 57 86 92
d. 25 12 37 33 23 15 48 57 86 92
Ans:b

34. What is the output of bubble sort after the 7th pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 12 23 15 25 33 37 48 57 86 92
b. 12 25 23 15 33 37 48 57 86 92
c. 12 25 33 23 15 37 48 57 86 92
d. 25 12 37 33 23 15 48 57 86 92
Ans:a

35. What is the output of bubble sort after the 8th pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 12 15 23 25 33 37 48 57 86 92
b. 12 25 23 15 33 37 48 57 86 92
c. 12 25 33 23 15 37 48 57 86 92
d. 25 12 37 33 23 15 48 57 86 92
Ans:a

36. What is the output of bubble sort after the 1st pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 1 7 8 4 6 9
b. 3 1 5 7 4 6 8 9
c. 1 3 5 4 6 7 8 9
d. 1 3 4 5 6 7 8 9

Ans:a

37. What is the output of bubble sort after the 2nd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 1 7 8 4 6 9
b. 3 1 5 7 4 6 8 9
c. 1 3 5 4 6 7 8 9
d. 1 3 4 5 6 7 8 9

Ans:b

38. What is the output of bubble sort after the 3rd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 1 7 8 4 6 9
b. 3 1 5 7 4 6 8 9
c. 1 3 5 4 6 7 8 9
d. 1 3 4 5 6 7 8 9

Ans:c

39. What is the output of bubble sort after the 4th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 1 7 8 4 6 9
b. 3 1 5 7 4 6 8 9
c. 1 3 5 4 6 7 8 9
d. 1 3 4 5 6 7 8 9

Ans:d

40. What is the output of bubble sort after the 5th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 1 7 8 4 6 9
b. 3 1 5 7 4 6 8 9
c. 1 3 5 4 6 7 8 9
d. 1 3 4 5 6 7 8 9

Ans:d

41.What will the output after 1st pass when Bubble sorting technique is used on the following set of numbers? 76,36,17,58,45,13, 66, 54
a. 76,17,36,45,66,13,54,58
b. 17,36,45,66,13,54,76,58
c. 36,17,45,66,13,54,76,58
d. 36,17,58,45,13,66,54,76
Ans:d

42. What will the output after 2nd pass when Bubble sorting technique is used on the following set of numbers? 76,36,17,58,45,13, 66, 54
a. 76,17,36,45,66,13,54,58
b. 17,36,45,13,58,54,66,76
c. 36,17,45,66,13,54,76,58
d. 36,17,58,45,13,66,54,76
Ans: b

43. What will the output after 3rd pass when Bubble sorting technique is used on the following set of numbers? 76,36,17,58,45,13, 66, 54
a. 76,17,36,45,66,13,54,58
b. 17,36,13,45,54,58,66,76
c. 36,17,45,66,13,54,76,58
d. 36,17,58,45,13,66,54,76
Ans: b

44. What will the output after 4th pass when Bubble sorting technique is used on the following set of numbers? 76,36,17,58,45,13, 66, 54
a. 76,17,36,45,66,13,54,58
b. 17,36,13,45,54,58,66,76
c. 17,13,36,45,54,58,66,76
d. 36,17,58,45,13,66,54,76
Ans: c

45. What will the output after 5th pass when Bubble sorting technique is used on the following set of numbers? 76,36,17,58,45,13, 66, 54
a. 76,17,36,45,66,13,54,58
b. 13,17,36,45,54,58,66,76
c. 17,13,36,45,54,58,66,76
d. 36,17,58,45,13,66,54,76
Ans: b

Bubble Sort Interview Question Part 3

2007-10-27T10:08:00.000-07:00

24.Bubble sort is also called
a.Exchange sort b.Sinking sort c.Both D.none
Ans:c
25. Which of the following correctly describe(s) the bubble sort algorithm?
a. public void bubblesort(int[ ] data)
{ int temp;
int i, j ;
for (i = 1; i < data.length; i++)
{ temp = data[i] ;
for (j = i; j>0 temp < data[j – 1]; j--)
data[j] = data[j – 1] ;
data[j] = temp ; } }
b. public void bubblesort(object[ ] data)
{ int i, j, least
for ( i = 0; i< data.length; j++)
if (((comparable[j]).compareTo(data[least])<0)
least = j ;
swap (data, least, i); }
c. public void bubblesort(object[ ] data)
{ int i, j
for (i = 0; i < data.length-1; i++)
for ( j = data.length-1; j>i; --j )
if (((comparable) data[j]).compareTo(data[j-1] <0)
swap (data, j, j-1) }
d. void bubblesort(object[ ] data)
{ for (int i = data.length/2 –1;i)> = 0; --i)
movedown(data. i, data.length – 1) ;
for (int i = data.length –1; i > = 1 ;--i)
{ swap(data, 0, i)
movedown(data, 0, i-1) ; } }

Ans. e

26.The number of nested loops in a bubble sort algorithm
a.1 b.2 c.3 d.4
Ans:b

27. Let A be a list of n numbers. Sorting A refers to the operation of re-arranging the elements of A so that they are in increasing order.

If A= { 32, 51, 27, 85, 66, 23, 13, 5} and method of sorting is bubble sort, Which is/are the correct intermediate output values during the process of sorting.
a.23, 13, 5, 27, 32, 51, 66, 85
b.27, 32, 23, 13 ,5, 51 66, 85
c.32, 27, 51, 66, 23, 13, 5, 85
d.32, 51, 85, 27, 66, 23, 13, 5
Ans:a,c,d,

28. What is the output of bubble sort after the 1st pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 25 48 37 12 57 86 33 23 15 92
c.12 25 33 37 48 57 86 92 23 15
d. 25 57 37 48 12 92 33 86 23 15
Ans:b

29. What is the output of bubble sort after the 2nd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 25 48 37 12 57 86 33 23 15 92
c. 25 37 12 48 57 33 23 15 86 92
d. 25 57 37 48 12 92 33 86 23 15
Ans:c

30. What is the output of bubble sort after the 3rd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 25 48 37 12 57 86 33 23 15 92
c. 25 37 12 48 57 33 23 15 86 92
d. 25 37 12 48 33 23 15 57 86 92
Ans:d

31. What is the output of bubble sort after the 4th pass given the following sequence of numbers: 25 57 48 37 12 92 86 33 23 15
a. 48 25 37 12 57 86 33 92 23 15
b. 25 48 37 12 57 86 33 23 15 92
c. 25 37 12 48 57 33 23 15 86 92
d. 25 12 37 33 23 15 48 57 86 92
Ans:d

Bubble Sort Interview Question Part 2

2007-10-27T10:07:00.001-07:00

14.When does the best case for Bubble sort occur?
a. When the numbers are placed in random
b. When the numbers are placed in descending order
c. When the numbers are placed in ascending order
d. When all the numbers are same
Ans:c

15.In which cases are the time complexities same in Bubble sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. none of the above
Ans:c

16.The sort which works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary is

a.Merge sort
b.Bubble sort
c.Selection sort
d.none of these
Ans:b

17.The most exchanges that will be necessary for bubble sort for an array of length n is
a.n
b.n+1
c.n-1
d.n*n
Ans:a

18. The best case order for modified bubble sort algorithm is
a.O(n)
b.O(n*n)
c.O(nlogn)
d.O(logn)
Ans:a
A better version of bubble sort, known as modified bubble sort, includes a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it should be clear that the array is already in order because no two elements need to be switched. In that case, the sort should end. The new best case order for this algorithm is O(n), as if the array is already sorted, then no exchanges are made.
19. The frequency count of bubble sort is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b
(n-1)+(n-2)+……+3+2+1=n(n+1)/2 – n =n(n-1)/2

20.In bubble sort,after the 1st iteration, the element which is at the bottom is
a.the smallest
b.the largest
c.the 2nd largest
d.none
Ans:b

21. In bubble sort,after the 2nd iteration, the element which is at the bottom is
a.the smallest
b.the largest
c.the 2nd largest
d.none
Ans:c

22.The number of swappings required to sort the numbers 8,22,7,9,31,19,5,13 in ascending order using bubble sort
a.11 b.12 c.13 d.14
Ans:d

23.Which of the following sort is known as sinking sort?
a.Bubble sort
b.Selection sort
c.Quick sort
d.none
Ans:a

Bubble Sort Interview Question Part 1

2007-10-27T10:06:00.001-07:00

1.What is the output of bubble sort after the 1st iteration given the following sequence of numbers: 13 2 9 4 18 45 37 63
a.2 4 9 13 18 37 45 63
b.2 9 4 13 18 37 45 63
c.13 2 4 9 18 45 37 63
d.2 4 9 13 18 45 37 63
Ans:b

2.What is the worst case complexity for bubble sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

3.What is the average case complexity for bubble sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

4.What is the best case complexity for bubble sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:a

5.The following loop is used for
For i<- N-1 to 1
For j<- 1 to i
If(a(j)>a(j+1))
{
Temp=a(j);
A(j)=a(j+1);
A(j+1)=temp;
}
a.bubble sort b.selection sort c.insertion sort d.merge sort
Ans:a

6. What is the output of bubble sort after the 1st iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 25 48 12 37 57 86 33 92
c.25 48 37 12 57 86 33 92
d. 25 48 37 12 57 33 86 92
Ans:c

7.What is the output of bubble sort after the 2nd iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 25 48 12 37 57 86 33 92
c.25 48 37 12 57 86 33 92
d. 25 37 12 48 57 33 86 92
Ans:d

8.What is the output of bubble sort after the 3rd iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 25 12 37 48 33 57 86 92
c.25 48 37 12 57 86 33 92
d. 25 37 12 48 57 33 86 92
Ans:b

9.What is the output of bubble sort after the 4th iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 25 48 12 37 57 86 33 92
c.25 48 37 12 57 86 33 92
d. 12 25 37 33 48 57 86 92
Ans:d

10.What is the output of bubble sort after the 5th iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 12 25 33 37 48 57 86 92
b. 25 48 12 37 57 86 33 92
c.25 48 37 12 57 86 33 92
d. 25 37 12 48 57 33 86 92
Ans:a

11.What is the output of bubble sort after the 6th iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 25 48 12 37 57 86 33 92
c.12 25 33 37 48 57 86 92
d. 25 37 12 48 57 33 86 92
Ans:c

12.What is the output of bubble sort after the 7th iteration given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 12 25 33 37 48 57 86 92
c.12 25 37 33 48 57 86 92
d. 25 37 12 48 57 33 86 92
Ans:b

13.When does the worst case for Bubble sort occur?
a. When the numbers are placed in random
b. When the numbers are placed in descending order
c. When the numbers are placed in ascending order
d. When all the numbers are same
Ans:b

Binary Search Interview Question Part 2

2007-10-27T10:04:00.000-07:00

17.Which of the following searching method runs most efficiently utilising the memory for already sorted file?
a. Binary search
b. Index sequential search
c. Sequential search with array implementation
d. Sequential search with linked list implementation
Ans. a

18.To search a single item from a group of 8 sorted items how many checks are required in Binary Search
a.8 b.4 c.3 d.2
Ans:c
Since 2*2*2=8

19.To search a page number 364 in a book containing 500 pages which of the following Searching technique should be used to reach the page in minimum time?
a.Linear search
b.Fibonacci search
c.Binary search
d.Random search
Ans:c

20. Consider the set of integers given below.

2,3,5, 7,11, 13, 17 ,19, 23, 29
How many comparisons are required to search when key value is equal to 23 using a binary search algorithm.
a.1 b.2 c.3 d.4
Ans:c

First comparison identifies middle element 0+9/2=4.5
4th element is 11.
2nd comparison gives 19 and 3rd 23.

21.What kind of search is used in a telephone directory?
a.Linear search
b.Binary search
c.Hashing
d.none
Ans:b

22. Which of the following statements is/are incorrect in connection with the binary search algorithm?
(a) The most efficient method of searching a sequential table without the use of auxiliary indices or tables is the binary search algorithm.
(b) Basically, the argument is compared with the key of the middle element of the table. If they are equal, the search is successful; otherwise, either the upper half or the lower half of the table must be searched in a similar manner.
(c) Any kind of data set can be used.
(d) Time complexity is O (n log n).
Ans: c
23. Binary search algorithm works best with
a) Arrays
b) trees
c) Binary Search trees
d) None
Ans:c

24. What additional requirement is placed on an array, so that binary search may be used to locate an entry?
A. The array elements must form a heap.
B. The array must have at least 2 entries.
C. The array must be sorted.
D. The array's size must be a power of two.
Ans:c
25. What is the worst-case time for serial search finding a single item in an array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
Ans:c

26. If there are 17 elements in an array, how many maximum comparisons are required to search an element using binary search?
a.3 b.4 c.5 d.6
Ans:c

27.If there are 34 elements in an array, how many maximum comparisons are required to search an element using binary search?
a.3 b.4 c.5 d.6
Ans:d

Binary Search Interview Question Part 1

2007-10-27T10:03:00.002-07:00

1. Binary search is a more specialized algorithm than sequential search as it takes advantage of data that has been
a. Sorted
b. Not Sorted
c. random
d. none of the above
Ans:a
2. The underlying idea of binary search is to divide the sorted data into two halves and to examine the data at the point of the split. True.

3. Binary search when compared to linear search is
a. More efficient
b. Less efficient
c. slower
d. none
Ans:a

4. A search algorithm is an algorithm that accepts an argument a and tries to find a record in the file with the primary key as a. True.

5. Binary search is a part of or used in which of the following
a. binary insertion sort
b. ideal search
c. suffix array
d. all the above
Ans:d

6. Binary search is a kind of ________________ .
Ans. dichotomic search

7. _________________ strategy is a part of or used in binary search.
Ans. Divide and conquer

8. The run time of binary search is _______
a. O(ln n)
b. O(n ln n)
c. O(log n)
d. O(n)
Ans. a
The run time of binary search is O(ln n) which is log n to the base e.

9. For finding the middle element in a binary search to avoid overflows the formula used is __________ where high and low are non-negative.
Ans. mid = low + (high-low)/2

10. The mid element of a binary search can be found by using the relation ________________ .
Ans. mid = (high + low)/2

11. The average successful search time taken by binary search on a sorted array of 10 items is _____
a. 2.6
b. 2.7
c. 2.8
d. 2.9
Ans. d
The items I1,I2,….I10 may be arranged in a binary search tree as shown below.So,to match I5,the number of comparisons needed is 1;for I2,it is 2, for I8 it is 2,for I1 it is 3 and so on.So,the average is (1+(2+2)+(3+3+3+3)+(4+4+4))/10 = 2.9

12. A fast way to search a sorted array is to use a __________.
Ans. Binary search

13. For an array of million items,________ search operation is better than _____________ search.
a. linear,binary
b. binary,linear
c. linear,fibonacci
d. none of the above
Ans. b
For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element.

14. In case of a binary search,the array must be __________ before it is searched.
Ans. sorted

15. Which of the following statement(s) is/are not correct?
a. In sequential search, the time complexity of an unsuccessful search is O(N).
b.The average case time complexity of sequential search algorithm is O(N). . c. In binary search,an unsuccessful search requires examining every in the array
d. In Binary search, the time complexity of a successful search in the worst case is O(log N).
Ans. c

16. Consider the following algorithm.
(i) Compare the given Name with the Name in the middle of the list
(ii) This tells which half of the list contains Name
(iii) Then compare Name with the Name in the middle of the correct half to Determine which quarter of the list contains Name
(iv) Continue the process until finding Name in the list
What does the above algorithm describe?
a. Sequential search
b. Index sequential search
c. Merge sort
d. Binary search
Ans. d

a

2007-10-27T10:03:00.001-07:00

Algorithms Interview Question Part 8

2007-10-27T10:01:00.000-07:00

83. An algorithm designed for a computer which executes one instruction at a time is called
a.Serial algorithm
b.Parallel algorithm
c.Random algorithm
d.Deterministic algorithm
84. Algorithms, which take advantage of computer architectures where several processors can work on a problem at the same time are called
a.Serial algorithm
b.Parallel algorithm
c.Random algorithm
d.Deterministic algorithm
Ans:b
85. Serial algorithms divide the problem into more symmetrical or asymmetrical sub problems and pass them to many processors and put the results back together at one end.(T/F)
Ans:False
86.The resource consumption in parallel algorithms is
i.processor cycles on each processors ii.the communication overhead between the processors.
a.only I b.only ii c.i and ii d.neither I nor ii
Ans:c
87.Sorting algorithms can be parallelized efficiently, but their communication overhead is expensive.(T/F)
Ans:True
88.Recursive algorithms are not parallelizable. (T/F)
Ans:False

89. The Order of the expression : 5*2n-n*log(n)-3*n3-1 is________.
a. O(n3)
b. O(n*log(n))
c. O(2n)
d. O(n*log(n))
Ans:c

90. Which of the following Orders of algorithm is considered efficient ?
a. O (n * log (n))
b. O(2n)
c. O(n2)
d.O (log (n))
Ans:d

91. Which one depicts the correct order of efficiency from best to worst among the following ?
a. O(n*n) , O(2n), O(log(n)), O(n)
b. O(n*n)O(n),O(2n),O(log(n)
c. O(log(n)), O(n), O(n*n), O(2n )
d. O(n*n), O(2n), O(log(n)), O(n)
Ans:c

92. (A) In O(n*log(n)), multiplying the file size by 100 will multiply the sorting time by less than 200. (B) In O(n*n), multiplying the file size by 100 will multiply the sorting time by a factor of 10000. What is correct about above statements?
a.A is TRUE, B is FALSE
b. B is TRUE, A is FALSE
c. Both are TRUE
d. Both are FALSE
Ans:c

Nlog n=100log100 < 200
100*100=10000

Algorithms Interview Question Part 7

2007-10-27T10:00:00.000-07:00

63. In a proper binary tree with n nodes, the number of internal nodes is:
a). n/2
b). (n+1)/2
c). (n-1)/2
d). (n+1)/2 –1
Ans:c

True false quest

64. n2 = O(n3)
True ( Transitive property )
65. n3 = O(n2)
False
66.3n = o(n)
False [Remember, little-o means "less than" not "less than or equal."]
67.n/3 = O(n)
True
68`.n! = O (n log n)
False [But if it were big-Omega, it would be true!]
69.3n = (2n)
False [Because exponentials differ by more than just a constant factor]
70.n2 + 3n + sin n = (n2)
True
71.2n = (2n+4)
True
72.loga n = (logb n), for a and b constant, a!=b
True
73.na = (nb), for a and b constant, a!=b
False
74.It is possible to do a general purpose comparison sort on n items using O(n) comparisons.
False
75.In the worst case, access to the maximum element of a heap takes (ln n) time.
False [it's just constant time]
76.Merge sort is asymptotically faster than bubble sort in the best case.
False [bubble sort is linear in the best case!]
77.Radix sort is a stable sort.
True

78.Invoking the sort on an already sorted array is an example of a situation
Where bubble sort is faster than Quick sort.

True [ bubble sort is O(n) while Quick sort is O(n2).]

Fill in the blanks

79. ---------------- is the least number of nodes possible in an almost complete binary tree
of height h

Ans: 2^h [ This is the case where there is one lone leaf hanging off the left side of the tree.This is just one more than the number of nodes in a complete binary tree of height h-1. ]

80. Which of the following should an algorithm consist of
i. Zero or more Inputs
ii. One or more Outputs
iii. Infiniteness
iv. Definitiveness or Preciseness
a.i,ii,iii b.i,ii,iv c.ii,iii,iv d.i,iii,iv
Ans:b
An algorithm should have the following:
• Zero or more Inputs
• One or more Outputs
• Finiteness or computability
• Definitiveness or Preciseness

81. An algorithm that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming is called
a. recursive algorithm
b. iterative algorithm
c. random
d. deterministic
Ans:a
82. Algorithms which use repetitive constructs like loops and possibly with data structures like stack to solve the problems are called
a. recursive algorithm
b. iterative algorithm
c. random
d. deterministic
Ans:b
Recursion vs. Iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming. Iterative algorithms use repetitive constructs like loops and possibly with data structures like stack to solve the problems. Some problems are naturally suited for one implementation to other. For example, towers of hanoi is well understood in recursive implementation. Every recursive version has an equivalent (but possibly more complex) iterative version

Algorithms Interview Question Part 6

2007-10-27T09:59:00.000-07:00

46. Consider the following four terms given in Part A and some definitions given in Part B.
Part A Part B
(i) Big O (p) The notation used to capture the most dominant term in a function
(ii) Big Omega (q) A guarantee over all inputs of some size
(iii) Average case bound (r) The bound in which running time is measured as an average
over all the possible inputs of size N
(iv) Worst case bound (s) An algorithm that causes the running time to grow as O(N)
(v) Linear time algorithm (t) The notation similar to greater than or equal to when
considering growth rates
Choose the best definition from Part B for the above five hash operations respectively in Part A.
(a) (i)􀃆(p) (ii)􀃆(r) (iii)􀃆(t) (iv)􀃆(q) (v)􀃆(s) (b) (i)􀃆(s) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(p)
(c) (i)􀃆(p) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(s) (d) (i)􀃆(p) (ii)􀃆(s) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(t)
(e) (i)􀃆(p) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(s) (v)􀃆(q)

Ans. c

47. There are the three main measures of efficiency that can be applied to most algorithms: best, worst and average cases.

Part A Part B
(i) Best case P This case is when the target is either a
last item in the list or is not in the list at all
(ii) Worst case Q This case occurs when the target for which
you are searching is the first item in the list
(iii) Average case R This case is found by considering all possible
outcomes of a search and averaging the number
of companions over all these cases.
Choose the best definition from part B for the above three cases.
a. (i)  R (ii)  P (iii)  Q
b. (i)  R (ii)  Q (iii)  P
c. (i)  Q (ii)  P (iii)  R
d. (i)  Q (ii)  R (iii)  P
Ans. d

48. Consider the following characteristics connected with a program.
(i) The input to the program
(ii) The time complexity of the algorithm underlying the program
(iii) The quality of the Compiler
(iv) The nature and speed of the machine
On which of the above does the running time of a program depend?
a. (i) and (ii) only
b. (i),(ii) and (iii) only
c. (i),(iii) and (iv) only
d. (i),(ii) and (iv) only
Ans. d

49. We may find several algorithms for solving a problem; for each algorithm, the measure to calculate the proportionate time taken to solve that particular problem is called ____________.

a. Time Complexity
b. Space Complexity
c. Algorithm complexity
d. Design Complexity
Ans: a
50. If an algorithm takes the largest possible execution time for a certain set of input values, then it is called ________ of the algorithm.
a. Best case
b. Worst Case
c. Average case
d. none
Ans:b
51. Which of the following is not a feature of algorithm
a. Step wise implementation of large problems
b. Calculation of time and space complexity
c. Analyzing the efficiency of the code
d. Complex representation of problems
Ans:d

52. The correct order of sequential search algorithm is
(i) marker ++.
(ii) else, throw an exception.
(iii) if target == key at location marker, then return.
(iv) While target = = key at location marker and not at the end of the list.
(v) Read in target, initialize marker to first array index(0).
a.(v), (iv), (i), (ii), and (iii).
b.(iv), (i), (iii), (iv) and (ii).
d.(v), (iv), (iii), (i) and (ii). c.(v), (iv), (i), (iii) and (ii)

Ans:c

53. Running time of an algorithm does not depend on which of the following statement(s)
(i) Time taken by each instruction in the algorithm.
(ii) Number of times each instruction is executed.
(iii) Processor speed and its machine language instruction set.
(iv) Size of the input
a.(iii) only b.(iii) and (iv) c. (i) and (iii) only d. (iv) only e.none of these
Ans:e
54. Consider the following program code.

Public static int sum (int n)

{ int Partialsum
Partialsum=0;
for (int i=1; i<=n ;i++)
Partialsum += i *i *i ;

return Partialsum;
}

The time complexity of the above algorithm is?
a.log n b.nlogn c.n d.constant
Ans:c

55.The minimal spanning tree of a graph gives the shortest distance between any two nodes. (True or False)
Ans. False
Minimal spanning tree assures that the total weight of the tree is kept at its minimum.But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.
56.What is the simplest file structure?
a. Sequential
b. Indexed
c. Random
Ans. Sequential
57. Computational procedure is an algorithm that
d. does not terminate
e. terminates
f. computes
g. analyzes
Ans. a
58.An algorithm consists of the following areas
i) to devise the algorithm
ii) to validate the algorithm
iii) to express the algorithm
iv) to analyze the algorithm
v) to test the programs for the algorithm
The correct options are
a. (i),(ii),(iii) only
b. (ii),(iii),(iv) and (v) only
c. (i),(ii),(iii),(iv) only
d. All of the above
Ans. d
59.An algorithm is said to be recursive if the same algorithm is invoked in the body of the algorithm. (True or False)
Ans. True
.
60.______________ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
Ans. Dynamic programming
61.The two parameters that can be taken as cost of an algorithm include
running time and amount of memory used .

62. Given a list implemented with a linked list, the operation remove(p) runs in:
a) O(1)
b) O(log n)
c) O(n)
d). O(nlog n)
Ans:c

Algorithms Interview Question Part 5

2007-10-27T09:56:00.002-07:00

27. An algorithm which is given the entire sequence of inputs in advance. (practice test question)
a.On-line algorithm
b.Off line algorithm
c.Adversary algorithm
d.Deterministic algorithm
Ans:b
An algorithm that must process each input in turn, without detailed knowledge of future inputs is called on-line algorithm.
28. To combine multiple sorted data streams into a single sorted stream using external storage.
a.External merge
b.Internal merge
c.both
d.none
Ans:a
29 .Let m,n be positive integers.Define Q(m,n) as Q(m,n)=0, if mQ(m,3) is (a div b, gives the quotient when a is divided by b)
a.a constant b.p*(m mod 3) c.p*(m div 3) d. 3*p
Ans:c
Let m>n .Let m/n yield a quotient x and remainder y. So, m=n*x+y and y30. _________ is the number of times a key operation will execute.
a. Frequency count
b. Running time
c. Space complexity
d. Time complexity
Ans. a
31. When an algorithm contains a recursive call to itself,its running time can often be described by a ___________
Ans. recurrence equation or recurrence
32. A function f(n) is strictly increasing if _________ implies ________ where m and n are the two parameters.
Ans. m 33. A function f(n) is strictly decreasing if _________ implies ________ where m and n are the two parameters.
Ans. m>n , f(m)>f(n)
34. The substitution method for solving recurrences entails the following steps:
a. Guess the form of the solution
b. Use mathematical induction to find the constants and show that the solution works. True or False
Ans. True
35. The various methods for solving recurrences are
a. substitution method
b. recursion-tree method
c. master method
d. all of the above
Ans. d
36. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. True or False
Ans. True
37. The master theorem does not apply to the recurrence of the form
a. T(n) = 2T(n/2) + n lg n
b. T(n) = aT(n/b) + f(n)
c. T(n) = aT(n) + f(n)
d. None of the above
Ans. a
Here a=2,b=2,f(n)=nlgn and n^log a = n but f(n)=n lg n is not polynomially larger than n^log a = n.the ratio f(n)/n^log a = (n lg n)/n =lg n is asymptotically less than n^є for any positive constant є.
38.Which of the following is a way of classifying algorithms based on implementation.
a.Recursion vs iteration
b.Serial vs parallel
c.Random vs deterministic
d.All the above
Ans:d

39.Searching can be used with
i.lists ii.graphs iii.trees
a.i ,ii b.i,iii c.i,ii,iii d.ii,iii
Ans:c
40. _______ consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.
Ans: instance of a problem
41. Which of the following factors decides which algorithm is best for a given application?
a.Number of items to be sorted
b.extent to which items are already sorted
c.possible restrictions on the item values
d.All the above
Ans:d
42. Probabilistic analysis is the use of ___________ in the analysis of problems.
Ans. probability
43. Probabilistic analysis
a. is used to analyze the running time of an algorithm
b. requires the knowledge of the distribution of inputs
c. all the above
d. none of the above
Ans. c
44. In randomized algorithm,the behavior of the algorithm is determined only by its input but not by values produced by a randon-number generator. True or False
Ans. False
In randomized algorithm,the behavior of the algorithm is determined not only by its input but also by values produced by a randon-number generator.
45. The running time of an algorithm on a particular input is the number of primitive operations or steps executed. True or False
Ans. True

Algorithms Interview Question Part 4

2007-10-27T09:56:00.001-07:00

22. An algorithm whose behavior can be completely predicted from the input. (practice test question)
a.Probabilistic algorithm
b.Randomized algorithm
c.Deterministic algorithm
d.Non deterministic algorithm
Ans:c
Any algorithm that makes some random (or pseudorandom) choices is called randomized algorithm.
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong is called probabilistic algorithm.
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior is called non-deterministic algorithm.

23. A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior. (practice test question)
a.Probabilistic algorithm
b.Randomized algorithm
c.Deterministic algorithm
d.Non deterministic algorithm
Ans:d
Any algorithm that makes some random (or pseudorandom) choices is called randomized algorithm.
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong is called probabilistic algorithm.
An algorithm whose behavior can be completely predicted from the input is called deterministic algorithm.
24. An algorithm that usually, but not always, works or that gives nearly the right answer. (practice test question)
a.Probabilistic algorithm
b.Heuristic algorithm
c.Deterministic algorithm
d.Non deterministic
Ans:b
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong is called probabilistic algorithm.
An algorithm whose behavior can be completely predicted from the input is called deterministic algorithm.
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior is called non-deterministic algorithm.

25. A high-level algorithmic framework or approach that can be specialized to solve optimization problems and a high-level strategy that guides other heuristics in a search for feasible solutions. (practice test question)
a.Probabilistic algorithm
b.Heuristic algorithm
c.Meta hueristic algorithm
d.Non deterministic
Ans:c
An algorithm that usually, but not always, works or that gives nearly the right answer is called heuristic algorithm.
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong is called probabilistic algorithm.
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior is called non-deterministic algorithm.

26. An algorithm that must process each input in turn, without detailed knowledge of future inputs. (practice test question)
a.On-line algorithm
b.Off line algorithm
c.Adversary algorithm
d.Deterministic algorithm
Ans:a
An algorithm which is given the entire sequence of inputs in advance is called an off-line algorithm.

Algorithms Interview Question Part 3

2007-10-27T09:54:00.002-07:00

18. The algorithms that test for a solution, if one is found the algorithm is solved, if not it recurs once and tests again, continuing until a solution is found is (practice test question)
a. Dynamic Programming Algorithms
b. Branch and Bound Algorithms
c. Simple Recursive Algorithms
d. Backtracking Algorithms
Ans:d
The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called dynamic programming algorithm.
The algorithms that form a tree of subproblems to the primary problem, following each branch until it is either solved or lumped in with another branch is called branch and bound algorithm.
This type of algorithm goes for a direct solution first, then backtracks to find a simpler solution is called simple recursive algorithm.
The algorithms that test for a solution, if one is found the algorithm is solved, if not it recurs once and tests again, continuing until a solution is found is called backtracking algorithm.

19. An algorithm that is similar to a branch and bound algorithm, except that it uses the backtracking method of recurring in tandem with dividing a problem into subproblems.
(practice test question)
a. Dynamic Programming Algorithms
b. Divide and Conquer Algorithms
c. Simple Recursive Algorithms
d. Backtracking Algorithms
Ans:b
The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called dynamic programming algorithm.
This type of algorithm goes for a direct solution first, then backtracks to find a simpler solution is called simple recursive algorithm.

20. Any algorithm that works for all practical purposes but has a theoretical chance of being wrong. (practice test question)
a.Probabilistic algorithm
b.Randomized algorithm
c.Deterministic algorithm
d.Non deterministic algorithm
Ans:a
Any algorithm that makes some random (or pseudorandom) choices is called randomized algorithm.
An algorithm whose behavior can be completely predicted from the input is called deterministic algorithm.
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior is called non-deterministic algorithm.
21. Any algorithm that makes some random (or pseudorandom) choices
(practice test question)
a.Probabilistic algorithm
b.Randomized algorithm
c.Deterministic algorithm
d.Non deterministic algorithm
Ans:b
Any algorithm that works for all practical purposes but has a theoretical chance of being wrong is called probabilistic algorithm.
An algorithm whose behavior can be completely predicted from the input is called deterministic algorithm.
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It has the super computational characteristic of choosing the optimal behavior is called non-deterministic algorithm

Algorithms Interview Question Part2

2007-10-27T09:54:00.001-07:00

13. Searches in which the entire table is constantly not in main memory is called as
a. External search
b. Internal search
c. None of these
d. All of these
Ans:a

14. The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called (practice test question)
a. Dynamic Programming Algorithms
b. Greedy Algorithms
c. Backtracking Algorithms
d. Divide and Conquer Algorithms
Ans:a
The algorithms that test for a solution, if one is found the algorithm is solved, if not it recurs once and tests again, continuing until a solution is found is called backtracking algorithm.

15. The class of algorithms that includes any algorithm that uses a random number at any point during its process. (practice test question)
a. Dynamic Programming Algorithms
b.Randomized Algorithms
c.Backtracking Algorithms
d.Divide and Conquer Algorithms
Ans:b
The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called dynamic programming algorithm.
The algorithms that test for a solution, if one is found the algorithm is solved, if not it recurs once and tests again, continuing until a solution is found is called backtracking algorithm.

16. The algorithms that form a tree of subproblems to the primary problem, following each branch until it is either solved or lumped in with another branch. (practice test question)
a. Dynamic Programming Algorithms
b. Branch and Bound Algorithms
c.Backtracking Algorithms
d.Divide and Conquer Algorithms
Ans:b
The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called dynamic programming algorithm.
The algorithms that test for a solution, if one is found the algorithm is solved, if not it recurs once and tests again, continuing until a solution is found is called backtracking algorithm.

17. This type of algorithm goes for a direct solution first, then backtracks to find a simpler solution. (practice test question)
a. Dynamic Programming Algorithms
b. Branch and Bound Algorithms
c. Simple Recursive Algorithms
d.Divide and Conquer Algorithms
Ans:c
The class of algorithms that remembers older results and attempts to use this to speed the process of finding new results is called dynamic programming algorithm.
The algorithms that form a tree of subproblems to the primary problem, following each branch until it is either solved or lumped in with another branch is called branch and bound algorithm.

Algorithms Interview Question Part1

2007-10-27T09:48:00.000-07:00

1. An algorithm is a sequence of computational steps that transform the input into the output. True
2. An algorithm is a tool for solving a well specified computational problem. True.
3. An algorithm describes a specific computational procedure for achieving the input/output relationship. True.
4. An algorithm is said to be correct if, for every input instance, it halts with the correct output. True.
5. The study of algorithm is called as algorithmics.
6. What is the purpose of algorithm validation?
a. To assure that the algorithm produces the correct output for all legal inputs.
b. To assure that the algorithm is accepting the legal inputs.
c. To assure that the algorithm is not working.
d. None of these.
Ans:a
7. Which of the following is not true…?
a. An algorithm is a set of rules for carrying out calculation either by hand or on a machine.
b. An algorithm is a finite step-by-step procedure to achieve a required result.
c. An algorithm is a sequence of computational steps that transform the input into the output.
d. None
Ans:d

8. Which of the following is true about Euclid’s Algorithm …
a. Calculating the lowest common multiple of two integers.
b. Calculating the greatest common divisor of two integers.
c. Calculating the number of common factors between the two integers.
d. None of these.
Ans:b

9. Two important ways to characterize the effectiveness of an algorithm…
a. Time, space Complexity.
b. Space,power Complexity
c. Power, time Complexity.
d. None of these.
Ans:a

10. A table of records in which a key is used for retrieval is often called as a
a. Search table
b. Dictionary
c. None of these
d. All of these
Ans:a,b

11. A table or file can be organized in the form of
a. Array
b. Linked list
c. Tree
d. Graph
Ans:a,b,c,d

12. Searches in which the entire table is constantly in main memory is called as
a. External search
b. Internal search
c. None of these
d. All of these
Ans:b

Java interview questions Part31

2007-10-26T12:53:00.001-07:00

10. State the transactional behavior in a given scenario for an enterprise bean method with a specified transactional deployment descriptor.
11.Given a requirement specification detailing security and flexibility needs, identify architectures that would fulfill those requirements.
12. Identify costs and benefits of using an intermediate data-access object between an entity bean and the data resource.
13. State the benefits of bean pooling in an EJB container.
14. State the benefits of Passivation in an EJB container.
15. State the benefit of monitoring of resources in an EJB container.
16. Explain how the EJB container does lifecycle management and has the capability to increase scalability.
17. Given a scenario description, distinguish appropriate from inappropriate protocols to implement that scenario.
18. Identify a protocol, given a list of some of its features, where the protocol is one of the following: HTTP, HTTPS, IIOP, JRMP.
19. Select from a list, common firewall features that might interfere with the normal operation of a given protocol.
20. State the benefits of using design patterns.

Given that 1119280000000L is roughly the number of milliseconds from Jan. 1, 1970, to June 20, 2005, and that you want to print that date in German, using the LONG style such that "June" will be displayed as "juni", complete the code using the fragments below. Note: you can use each fragment either zero or one times, and you might not need to fill all of the slots.

Code:

import Java.___________

import Java.___________

class DateTwo {
public static void main(String[] args) {
Date d = new Date(1119280000000L);

DateFormat df =__________________________

_____________ , ______________ ) ;

System.out.println(_____________
}
}

Fragments:

io.*; new DateFormat( Locale.LONG
nio.*; DateFormat.getlnstance( Locale.GERMANY
util.*; DateFormat.getDatelnstance( DateFormat.LONG
text.*; util.regex; DateFormat.GERMANY
date.*; df.format(d)); d.format(df));

12.
Given:

import java.io.*;
class Directories {
static String [] dirs = {"dirl", "dir2"};
public static void main(String [] args){
for (String d : dirs) {

// insert code 1 here

File file = new File(path, args[0]) ;

// insert code 2 here
}
}
}

and that the invocation

java Directories file2.txt

is issued from a directory that has two subdirectories "dir1" and "dir1", and that "dir1" has a file "file1.txt" and "dir2" has a file "file2.txt", and the output is "false true"; which set(s) of code fragments must be inserted? (Choose all that apply.)

String path = d;

System.out.print (file.exists() + " ");

String path = d;

System.out .print (file . isFile() + " ");

String path = File.separator + d;

System.out .print (file . exists() + " ");

String path = File.separator + d;

System.out.print(file.isFile() +

13.
Given:

class Polish {
public static void main(String[] args) {
int x = 4 ;
StringBuffer sb = new StringBuffer("..fedcba");
sb.delete(3,6);
sb.insert(3, "az");
if(sb.length() > 6) x = sb.indexOf("b");
sb.delete((x-3), (x-2));
System.out.println(sb);
} }

What is the result?

.faza

.fzba

..azba

.fazba

..fezba

Compilation fails.

An exception is thrown at runtime.

14.
Given:

1. import java.util.*;
2. class Brain {
3. public static void main(String[] args) {

4. // insert code block here

5. }
6. }

Which, inserted independently at line 4, compile and produce the output "123 82"? (Choose all that apply.)

Scanner sc = new Scanner("123 A 3b c,45, x5x,76 82 L");

while(sc.hasNextInt()) System.out.print(sc.nextlnt() + " ");

Scanner sc = new Scanner("123 A 3b c,45, x5x,76 82 L").

useDelimiter(" ");

while(sc.hasNextlnt()) System.out.print(sc.nextlnt() + " ");

Scanner sc = new Scanner("123 A 3b c,45, x5x,76 82 L");

useDelimiter(" ");

while(sc.hasNext()) {

if (sc.hasNextlnt()) System.out.print(sc.nextlnt() + " ") ;

else sc.next(); }

Scanner sc = new Scanner("123 A 3b c,45, x5x,76 82 L").

useDelimiter(" ");

while(sc.hasNext()) }

if (sc.hasNextlnt()) System.out.print(sc.nextlnt() + " ") ;

else sc.next(); }

Scanner sc = new Scanner ("123 A 3b c,45, x5x, 76 82 L");

do {

if (sc.hasNextInt()) System.out.print (sc.nextInt() + "");

} while (sc.hasNext());

Scanner sc = new Scanner("12,3 A 3b c,45, x5x, 76 82 L").

useDelimiter(" ");

do {

if(sc.hasNextlnt()) System.out.print(sc.nextInt() + " ");

} while ( sc.hasNext() );

15.
Given:

import java.io.*;

public class TestSer {
public static void main(String[] args) {
SpecialSerial s = new SpecialSerial() ;
try {
ObjectOutputStream os = new ObjectOutputStream(
new FileOutputStream("myFile"));
os.writeObject(s); os. close();
System.out.print( + + s.z + " ");

ObjectlnputStream is = new ObjectlnputStream(
new FileInputStream("myFile"));
SpecialSerial s2 = (SpecialSerial)is.readObject();
is.close();
System.out.println(s2.y + " " + s2.z);
} catch (Exception x) {System.out.println("exc"); }
}
}
class SpecialSerial implements Serializable {
transient int y = 7;
static int z = 9;
}

Which are true? (Choose all that apply.)

Compilation fails.

The output is 10 0 9

The output is 10 0 10

The Output is 10 7 9

The output is 10 7 10

In order to alter the standard deserialization process you would override the readobject() method in SpecialSerial.

In order to alter the standard deserialization process you would override the defaultReadObject() method in SpecialSerial.

Java interview questions Part30

2007-10-26T12:51:00.000-07:00

1. What do you understand by UML. How to interpret UML diagrams?
2. State the effect of encapsulation, inheritance, and use of interfaces on architectural characteristics?
3. Differentiate between 2 tier, 3 tier and n-tier architectures.
4. How do the following characteristics scalability,performance, high availabilty behave based on the above architecture selected.
5. In what all ways (methods/concepts) can we achieve integration with legacy/n-n-legacy applications using JAVA technologies.
6. List the required classes/interfaces that must be provided for an EJB technology.
7. Distinguish stateful and stateless Session beans.
8. Distinguish Session and Entity beans.
7.
Using the fewest fragments possible (and filling the fewest slots possible), complete the code below so that the class builds a directory named "dir3" and creates a file named "file3" inside "dir3". Note you can use each fragment either zero or one times.

Code:

import java.io.________________

class Maker {
public static void main(String [] args) {
___________ ___________ ___________
___________ ___________ ___________
___________ ___________ ___________
___________ ___________ ___________
___________ ___________ ___________
___________ ___________ ___________
___________ ___________ ___________
}
}

Fragments:

File; FileDescriptor; FileWriter; Directory;
try { .createNewDir(); File dir File
{ } (Exception x) ("dir3"); file
file .createNewFile(); = new File = new File
dir (dir, "file3"); (dir, file); .createFile() ;
} catch ("dir3", "file3"); .mkdir(); File file

8.
Which are true? (Choose all that apply.)

The DateFormat.getDate() is used to convert a String to a Date instance.

Both DateFormat and NumberFormat objects can be constructed to be Locale specific.

Both Currency and NumberFormat objects must be constructed using static methods.

If a NumberFormat instance's Locale is to be different than the current Locale, it must be specified at creation time.

A single instance of NumberFormat can be used to create Number objects from Strings and to create formatted numbers from numbers.

9.
Which will compile and run without exception? (Choose all that apply.)

System.out.format("%b", 123);

System.out.format("%c", "x");

System.out.printf("%d", 123);

System.out.printf("%f", 123);

System.out.printf("%d", 123.45);

System out. printf ("%f", 123.45);

System.out.format("%s", new Long("123"));

10.
Which about the three java.lang classes String, StringBuilder, and StringBuffer are true? (Choose all that apply.)

All three classes have a length() method.

Objects of type StringBuffer are thread-safe.

All three classes have overloaded append() methods.

The "+" is an overloaded operator for all three classes.

According to the API, StringBuffer will be faster than StringBuilder under most implementations.

The value of an instance of any of these three types can be modified through various methods in the API.

Java interview questions Part30

2007-10-26T12:50:00.001-07:00

Given:

import java.util.regex.*;
class Regex2 {
public static void main(String[] args) {
Pattern p = Pattern.compile(args[o]);
Matcher m = p.matcher(args[1]);
boolean b = false;
while(b = m.find()) {
System.out.print(m.start() + m.group());
}
}
}

And the command line:

java Regex2 "\d*" ab34ef

What is the result?

234

334

2334

0123456

01234456

12334567

Compilation fails.

2.
Given:

import java.io.*;
class Player {
Player() { System.out.print("p"); }
}
class CardPlayer extends Player implements Serializable {
CardPlayer() { System.out.print("c"); }
public static void main(String[] args){
CardPlayer cl = new CardPlayer();

try {
FileOutputStream fos = new FileOutputStream("play.txt");
ObjectOutputStream os = new ObjectOutputStream(fos);
os.writeObject(c1);
os.close() ;
FileInputStream fis = new FileInputStream("play.txt");
ObjectInputStream is = new ObjectInputStream(fis);
CardPlayer c2 = (CardPlayer) is.readObject();
is.close();
} catch (Exception x ) { }
}
}

What is the result?

pc

pcc

pcp

pcpc

Compilation fails.

An exception is thrown at runtime.

3.
Given that bw is a reference to a valid BufferedWriter

And the snippet:

15. BufferedWriter b1 = new BufferedWriter(new File("f"));
16. BufferedWriter b2 = new BufferedWriter(new FileWriter("f1"));
17. BufferedWriter b3 = new BufferedWriter(new PrintWriter("f2"));
18. BufferedWriter b4 = new BufferedWriter(new BufferedWriter(bw));

What is the result?

Compilation succeeds.

Compilation fails due only to an error on line 15.

Compilation fails due only to an error on line 16.

Compilation fails due only to an error on line 17.

Compilation fails due only to an error on line 18.

Compilation fails due to errors on multiple lines.

4.
Given:

Class TKO {
public static void main(String[] args) {
String s = "-";
Integer x = 343;
long L343 = 343L;
if(x.equals(L343)) s += ".e1 ";
if(x.equals(343)) s += ".e2 ";
Short s1 = (short)((new Short((short)343)) / (new Short((short)49)));
if (s1 == 7) s += "=s ";
if(sl < new Integer(7+1)) s += "fly ";
System.out.println(s);
}
}

Which of the following will be included in the output String s? (Choose all that apply.)

.e1

.e2

=s

fly

None of the above.

Compilation fails.

An exception is thrown at runtime.

5.
Given:

1. import java.text.*;
2. class DateOne {
3. public static void main(String[] args) {
4. Date d = new Date(1123631685981L);
5. DateFormat df = new DateFormat();
6. System.out.println(df.format(d));
7. }
8. }

And given that 1123631685981L is the number of milliseconds between Jan. 1, 1970, and sometime on Aug. 9, 2005, what is the result? (Note: the time of day in option A may vary.)

8/9/05 5:54 PM

1123631685981L,

An exception is thrown at runtime.

Compilation fails due to a single error in the code.

Compilation fails due to multiple errors in the code.

6.
Given:

import java.io.*;

class Keyboard { }
public class Computer implements Serializable {
private Keyboard k = new Keyboard();
public static void main(String[] args)
Computer c = new Computer();
c.storeIt(c) ;
}
void storeIt(Computer c) {
try {
ObjectOutputStream os = new ObjectOutputStream(
new FileOutputStream("myFile"));
os.writeObject(c);
os.close() ;
System.out.println("done");
} catch (Exception x) {System.out.println("exc"); } }
}
}

What is the result? (Choose all that apply.)

exc

done

Compilation fails.

Exactly one object is serialized.

Exactly two objects are serialized

Java interview questions Part29

2007-10-26T12:49:00.002-07:00

Given:

class Emu {
static String s = "-";
public static void main(String[] args) {
try {
throw new Exception();
} catch (Exception e) {
try {
try { throw new Exception();
} catch (Exception ex) { s += "ic "; }
throw new Exception(); }
catch (Exception x) { s += "mc "; }
finally { s += "mf "; }
} finally { s += "of "; }
System.out.println(s);
} }

What is the result?

-ic of

-mf of

-mc mf

-ic mf of

-ic mc mf of

-ic mc of mf

Compilation fails.

15.
Given:

class Mineral { }
class Gem extends Mineral { }
class Miner {
static int x = 7;
static String s = null;
public static void getWeight(Mineral m) {
int y = 0 / x;
System.out.print(s + " ");
}
public static void main(String[] args) {
Mineral[] ma = {new Mineral(), new Gem()};

for(Object o : ma)
getWeight((Mineral) o);
}
}

And the command-line invocation:

java Miner.java

What is the result?

null

null null

A ClassCastException is thrown.

A NullPointerException is thrown.

A NoClassDefFoundError is thrown.

An ArithmeticException is thrown.

An IllegalArgumentException is thrown.

An ArrayIndexOutOfBoundsException is thrown.

16.
Which are most typically thrown by an API developer or an application developer as opposed to being thrown by the JVM? (Choose all that apply.)

ClassCastException

IllegalStateException

NumberFormatException

IllegalArgumentException

ExceptionInInitializerError

Java interview questions Part27

2007-10-26T12:49:00.001-07:00

Given:

1. class Crivitch {
2. public static void main(String [] args) {
3. int x = 0;
4. // insert code here
5. do { } while (x++ < y);
6. System.out.println(x);
7. }
8. }

Which, inserted at line 4, produces the output 12?

int y = x;

int y = 10;

int y = 11;

int y = 12;

int y = 13;

None of the above will allow compilation to succeed.

6.
Given:

class Plane {
static String s = "-";
public static void main(String[] args) {
new Plane().s1() ;
System.out.println(s);
}
void sl() {
try { s2();
catch (Exception e) { s += "c"; }
}
void s2() throws Exception {
s3(); s += "2";
s3(); s += "2b";
}
void s3() throws Exception {
throw new Exception();
}
}

What is the result?

-

-c

-c2

-2c

-c22b

-2c2b

-2c2bc

Compilation fails.

7.
Given:

try { int x = Integer.parselnt("two"); }

Which could be used to create an appropriate catch block? (Choose all that apply.)

ClassCastException

IllegalStateException

NumberFormatException

IllegalArgumentException

ExceptionInInitializerError

ArrayIndexOutOfBoundsException

8.
Given:

1. class Ping extends Utils {
2. public static void main(String [] args) {
3. Utils u = new Ping();
4. System.out.print(u.getInt(args[0]));
5. }
6. int getInt(String arg) {
7. return Integer.parseInt(arg);
8. }
9. }
10. class Utils {
11. int getInt(String x) throws Exception { return 7; }
12. }

And the following three possible changes:

C1. Declare that main() throws an Exception.

C2. Declare that Ping.getInt() throws an Exception.

C3. Wrap the invocation of getInt() in a try / catch block.

Which change(s) allow the code to compile? (Choose all that apply.)

Just C1 is sufficient.

Just C2 is sufficient.

Just C3 is sufficient.

Both C1 and C2 are required.

Both C1 and C3 are required.

Both C2 and C3 are required.

All three changes are required.

9.
Given:

class Swill {
public static void main(String[] args) {
String s = "-";
switch(TimeZone.CST) {
case EST: s += "e";
case CST: s += "c";
case MST: s += "m";
default: s += "X";
case PST: s += "p";
}
System.out.println(s);
}
}
enum TimeZone {EST, CST, MST, PST }

What is the result?

-c

-X

-cm

-cmp

-cmXp

Compilation fails.

An exception is thrown at runtime.

10.
Given:

class Circus {
public static void main(String[] args) {
int x = 9;
int y = 6;
for(int z = 0; z < 6; z++, y--) {
if(x > 2) x--;
label:
if(x > 5) {
System.out.print(x + " "};
--X;
continue label;

}
X--;
}
}
}

What is the result?

8

8 7

8 7 6

Compilation fails.

An exception is thrown at runtime.

11.
Which are true? (Choose all that apply.)

It is appropriate to use assertions to validate arguments to methods marked public.

It is appropriate to catch and handle assertion errors.

It is NOT appropriate to use assertions to validate command-line arguments.

It is appropriate to use assertions to generate alerts when you reach code that should not be reachable.

It is NOT appropriate for assertions to change a program's state.

12.
Given:

1. class Loopy {
2. public static void main(String[] args) {
3. int[] x = {7,6,5,4,3,2,1};
4. // insert code here
5. System.out.print(y + " ");
6. }
7. }
8. }

Which, inserted independently at line 4, compiles? (Choose all that apply.)

for(int y : x) {

for(x : Int y) {

int y = 0; for(y : x) {

for(int y=0, z=0; z
for(int y=0, int z=0, int z=0; z
int y = 0; for(int z=0; z

13.
Given:

1. class Ring {
2. final static int x2 = 7;
3. final static Integer x4 = 8;
4. public static void main(String[] args) {
5. Integer x1 = 5;
6. String s = "a";
7. if(xl < 9) s += "b";
8. switch(x1) {
9. case 5: s += "c";
10. case x2: s += "d";
11. case x4: s += "e";
12. }
13. System.out.println(s);
14. }
15. }

What is the result?

abc

abcde

Compilation fails due only to an error on line 7.

Compilation fails due only to an error on line 8.

Compilation fails due only to an error on line 10.

Compilation fails due only to an error on line 11.

Compilation fails due to errors on multiple lines.

Java interview questions Part22

2007-10-26T12:48:00.001-07:00

Given the following code:

public class OrtegorumFunction {
public int computeDiscontinuous(int x) {
int r = 1;
r += X;
if ((x > 4) && (x < 10)) {
r += 2 * x;
} else (x <= 4) {
r += 3 * x;
} else {
r += 4 * x;
}
r += 5 * x;
return r;
}

public static void main(String [] args) {
OrtegorumFunction o = new OrtegorumFunction();
System.out.println("OF(11) is: " + o.computeDiscontinuous (11));
}
}

What is the result?

OF(11) is: 45

OF(11) is: 56

OF(11) is: 89

OF(11) is: 111

Compilation fails.

An exception is thrown at runtime.

2.
Given two files:

1. class One {
2. public static void main(String[] args) {
3. int assert = 0;
4. }
5. }

1. class Two {
2. public static void main(String[] args) {

3. assert(false);
4. }
5. }

And the four command-line invocations:

javac -source 1.3 One.java
javac -source 1.4 One.java
javac -source 1.3 Two.java
javac -source 1.4 Two.java

What is the result? (Choose all that apply.)

Only one compilation will succeed.

Exactly two compilations will succeed.

Exactly three compilations will succeed.

All four compilations will succeed.

No compiler warnings will be produced.

At least one compiler warning will be produced.

3.
Given:

import java.io.*;
class Master {
String doFileStuff() throws FileNotFoundException { return "a"; }
}
class Slave extends Master {
public static void main(String[] args) {
String s = null;
try { s = new Slave().doFileStuff();
} catch ( Exception x) {
s = "b"; }
System.out.println(s);
}
// insert code here
}

Which, inserted independently at // insert code here, will compile, and produce the output b? (Choose all that apply.)

String doFileStuff() { return "b"; }

String doFileStuff() throws IOException ( return "b"; }

String doFileStuff(int. x) throws IOException ( return "b"; }

String doFileStuff() throws FileNotFoundException { return "b"; }

String doFileStuff() throws NumberFormatException { return "b"; }

String doFileStuff() throws NumberFormatException, FileNotFoundException { return "b"; }

4.
Given:

class Input {
public static void main(String[] args) {
String s = "- " ;
try {
doMath(args[0]);
s += "t "; // line 6
}
finally { System.out.println(s += "f "); }
}
public static void doMath(String a) {
int y = 7 / Integer.parseInt(a);
} }

And the command-line invocations:

java Input
java Input 0

Which are true? (Choose all that apply.)

Line 6 is executed exactly 0 times.

Line 6 is executed exactly 1 time.

Line 6 is executed exactly 2 times.

The finally block is executed exactly 0 times.

The finally block is executed exactly 1 time.

The finally block is executed exactly 2 times.

Both invocations produce the same exceptions.

Each invocation produces a different exception.

Java interview questions Part26

2007-10-26T12:46:00.000-07:00

Given:

class Foozit {
public static void main(String[] args) {
Integer x = 0;
Integer y = 0;
for(Short z = 0; z < 5; z++)
if((++x > 2) || (++y > 2))
X++ ;
System.out.println (x + " " + y);
}
}

What is the result?

5 1

5 2

5 3

8 1

8 2

8 3

10 2

10 3

6.
Given:

class Titanic {
public static void main(String[] args) {
Boolean bl = true;
boolean b2 = false;
boolean b3 = true;
if((bl & b2) | (b2 & b3) & b3)
System.out.print("alpha ");
if((bl = false) | (b1 & b3) | (bl | b2))
System.out.print("beta "};
}
}

What is the result?

beta

alpha

alpha beta

Compilation fails.

No output is produced.

An exception is thrown at runtime.

7.
Given:

class Feline {
public static void main(String[] args) {
Long x = 42L;
Long y = 44L;
System.out.print (" " + 7 + 2 + " ") ;
System.out.print(foo () + x + 5 + " ");
System.out.println(x + y + foo());
}
static String foo() { return "foo"; }
}

What is the result?

9 foo47 86foo

9 foo47 4244foo

9 foo425 86foo

9 foo425 4244foo

72 foo47 86foo

72 foo47 4244foo

72 foo425 86foo

72 foo425 4244foo

Compilation fails.

8.
Place the fragments into the code to produce the output 33. Note, you must use each fragment exactly once.

CODE:

class Incr {
public static void main(String[] args) {
Integer x = 7;
int y = 2 ;

X ___ ___;
___ ___ ___;
___ ___ ___;
___ ___ ___;

System.out.println(x);
}
}

FRAGMENTS:

Y
Y
Y
Y

y
x
x

-=
*=
*=
*=

9.
Given:

1. class Maybe {
2. public static void main(String[] args) {
3. boolean bl = true;
4. boolean b2 = false;
5. System.out.print(!false ^ false);
6. System.out.print(" " + (!b1 & (b2 = true)));
7. System.out.println(" " + (b2 ^ b1));
8. }
9. }

Which are true?

Line 5 produces true.

Line 5 produces false.

Line 6 produces true.

Line 6 produces false.

Line 7 produces true.

Line 7 produces false.

10.
Given:

class Sixties {
public static void main(String[] args) {
int x = 5; int y = 7 ;
System.out.print(((y * 2) % x));
System.out.print(" " + (y % x));
}
}

What is the result?

1 1

1 2

2 1

2 2

4 1

4 2

Compilation fails.

An exception is thrown at runtime

Java interview questions Part26

2007-10-26T12:45:00.004-07:00

Given:

class Hexy {
public static void main(String[] args) {
Integer i = 42;
String s = (i<40)?"life":(i>50)?"universe":"everything";
System.out.println(s);
}
}

What is the result?

null

life

universe

everything

Compilation fails.

An exception is thrown at runtime.

2.
Given:

1. class Example {
2. public static void main(String[] args) {
3. Short s = 15;
4. Boolean b;
5. // insert code here
6. }
7. }

Which, inserted independently at line 5, will compile? (Choose all that apply.)

b = (Number instanceof s);

b = (s instanceof Short);

b = s.instanceof(Short);

b = (s instanceof Number);

b = s.instanceof(Object);

b = (s instanceof String);

3.
Given:

1. class Comp2 {
2. public static void main(String[] args) {
3. float f1 = 2.3f;
4. float[][] f2 = {{42.Of}, {l.7f, 2.3f}, {2.6f, 2.7f}};
5. float[] f3 = {2.7f};
6. Long x = 42L;
7. // insert code here
8. System.out.println("true");
9. }
10. }

And the following five code fragments:

F1. if (f1 == f2)
F2. if (f1 == f2[2][1])
F3. if (x == f2[0][0])
F4. if (f1 == f2 [1,1] )
F5. if (f3 == f2 [2] )

What is true?

One of them will compile, only one will be true.

Two of them will compile, only one will be true.

Two of them will compile, two will be true.

Three of them will compile, only one will be true.

Three of them will compile, exactly two will be true.

Three of them will compile, exactly three will be true.

4.
Given:

class Fork {
public static void main(String[] args) {
if(args.length == 1 | args[1] .equals("test")) {
System.out.println ("test case");
} else {
System.out.println("production " + args[0]) ;
}
}
}

And the command-line invocation:

java Fork live2

What is the result?

test case

production

test case live2

Compilation fails.

An exception is thrown at runtime.

5.
Given:

Java interview questions Part25

2007-10-26T12:45:00.003-07:00

14.
Given:

class Bird {
{ System.out.print("bl "); }
public Bird() { System.out.print("b2 "); }
}
class Raptor extends Bird {
static { System.out.print("r1 "); }
public Raptor() { System.out.print("r2 "); }
{ System.out.print("r3 "); }
static { System.out.print("r4 "); }
}
class Hawk extends Raptor {
public static void main(String[] args) {
System.out.print("pre ");
new Hawk();
System.out.println("hawk ");
}
}

What is the result?

pre b1 b2 r3 r2 hawk

pre b2 b1 r2 r3 hawk

pre b2 b1 r2 r3 hawk r1 r4

r1 r4 pre b1 b2 r3 r2 hawk

r1 r4 pre b2 b1 r2 r3 hawk

pre r1 r4 b1 b2 r3 r2 hawk

pre r1 r4 b2 b1 r2 r3 hawk

The order of output cannot be predicted.

Compilation fails.

Java interview questions Part22

2007-10-26T12:45:00.001-07:00

6.
Given:

class Mixer {
Mixer() { }
Mixer(Mixer m) { ml = m;}
Mixer m1;
public static void main(String[] args) {
Mixer m2 = new Mixer();
Mixer m3 = new Mixer(m2); m3.go();
Mixer m4 = m3.m1; m4.go();
Mixer m5 = m2.m1; m5.go();
}
void go() { System.out.print("hi "); }
}

What is the result?

hi

hi hi

hi hi hi

Compilation fails

hi, followed by an exception

hi hi, followed by an exception

7.
Given:

1. class Zippy {
2. String[] x;
3. int[] a [] = {{1,2}, {l}};
4. Object c = new long [4] ;
5. Object[] d = x;
6. }

What is the result?

Compilation succeeds.

Compilation fails due only to an error on line 3.

Compilation fails due only to an error on line 4.

Compilation fails due only to an error on line 5.

Compilation fails due to errors on lines 3 and 5.

Compilation fails due to errors on lines 3, 4, and 5.

8.
Given:

class Fizz {
int x = 5;
public static void main(String[] args) {
final Fizz f1 = new Fizz();
Fizz f2 = new Fizz();
Fizz f3 = FizzSwitch(f1,f2);
System.out.println((f1 == f3) + " " + (f1.x == f3.x));
}
static Fizz FizzSwitch(Fizz x, Fizz y) {
final Fizz z = x;
z.x = 6;
return z;
} }

What is the result?

true true

false true

true false

false false

Compilation fails.

An exception is thrown at runtime.

9.
Given:

class Knowing {
static final long tooth = 343L;
static long doIt(long tooth) {
System.out.print(++tooth + " ");

return ++tooth;
}
public static void main(String[] args) {
System.out.print(tooth + " ");
final long tooth = 340L;
new Knowing().doIt(tooth);
System.out.println(tooth);
}
}

What is the result?

343 340 340

343 340 342

343 341 342

343 341 340

343 341 343

Compilation fails.

An exception is thrown at runtime.

10.
Which is true? (Choose all that apply.)

The invocation of an object's finalize() method is always the last thing that happens before an object is garbage collected (GCed).

When a stack variable goes out of scope it is eligible for GC.

Some reference variables live on the stack, and some live on the heap.

Only objects that have no reference variables referring to them can be eligible for GC.

It's possible to request the GC via methods in either java. lang. Runtime or java.lang.System classes.

11.
Given:

1. class Convert {
2. public static void main(String[] args) {
3. Long xL = new Long(456L);
4. long x1 = Long.valueOf("123");
5. Long x2 = Long.valueOf("123");
6. long x3 = xL.longValue();
7. Long x4 = xL.longValue();
8. Long x5 = Long.parseLong("456");
9. long x6 = Long.parseLong("123");
10. }
11. }

Which will compile using Java 5, but will NOT compile using Java 1.4? (Choose all that apply.)

Line 4

Line 5

Line 6

Line 7

Line 8

Line 9

12.
Given:

1. class Eco {
2. public static void main(String[] args) {
3. Eco e1 = new Eco();
4. Eco e2 = new Eco();
5. Eco e3 = new Eco();
6. e3.e = e2;
7. e1.e = e3;
8. e2 = null;
9. e3 = null;
10. e2.e = el;
11. e1 = null;
12. }
13. Eco e;
14. }

At what point is only a single object eligible for GC?

After line 8 runs.

After line 9 runs.

After line 10 runs.

After line 11 runs.

Compilation fails.

Never in this program.

An exception is thrown at runtime.

13.
Given:

1. class Bigger {
2. public static void main(String[] args) {
3. // insert code here
4. }
5. }
6. class Better {
7. enum Faster {Higher, Longer};
8. }

Which, inserted independently at line 3, will compile? (Choose all that apply.)

Faster f = Faster.Higher;

Faster f = Better.Faster.Higher;

Better.Faster f = Better.Faster.Higher;

Bigger.Faster f = Bigger.Faster.Higher;

Better. Faster f2; f2 = Better.Faster.Longer;

Better b; b.Faster = f3; f3 = Better.Faster.Longer;

Java interview questions Part23

2007-10-26T12:44:00.001-07:00

1.
Given:

class Scoop {
static int thrower() throws Exception { return 42; }
public static void main(String [] args) {
try {
int x = thrower();
} catch (Exception e) {
X++;
} finally {
System.out.printIn("x = " + ++x);
} } }

What is the result?

x = 42

x = 43

x = 44

Compilation fails.

The code runs with no output.

2.
Given:

class CardBoard {
Short story = 5;
CardBoard go(CardBoard cb) {
cb = null;
return cb;
}
public static void main(String[] args) {
CardBoard c1 = new CardBoard();
CardBoard c2 = new CardBoard();
CardBoard c3 = c1.go(c2);
c1 = null;
// do Stuff
} }

When // doStuff is reached, how many objects are eligible for GC?

0

1

2

Compilation fails.

It is not possible to know.

An exception is thrown at runtime.

3.
Given:

class Alien {
String invade(short ships) { return "a few"; }
String invade(short... ships) { return "many"; }
}
class Defender {
public static void main(String [] args) {
System.out.println(new Alien().invade(7));
}
}

What is the result?

many

a few

Compilation fails.

The output is not predictable.

An exception is thrown at runtime.

4.
Given:

1. class Dims {
2. public static void main(String[] args) {
3. int[] [] a = {{1,2,}, {3,4}};
4. int [] b = (int [] ) a [1] ;
5. Object o1 = a;
6. int [] [] a2 = (int[] [] ) o1;
7. int [] b2 = (int []) o1;
8. System.out.println(b[1]);
9. } }

What is the result?

2

4

An exception is thrown at runtime.

Compilation fails due to an error on line 4.

Compilation fails due to an error on line 5.

Compilation fails due to an error on line 6.

Compilation fails due to an error on line 7.

5.
Given:

class Eggs {
int doX(Long x, Long y) { return 1; }
int doX(long... x) { return 2; }
int doX(Integer x, Integer y) { return 3; }
int doX(Number n, Number m) { return 4; }
public static void main(String[] args) {
new Eggs().go();
}
void go () {
short s = 7;
System.out.print(doX(s,s) + " ");
System.out.println(doX(7,7));
} }

What is the result?

1 1

2 1

3 1

4 1

2 3

3 3

4 3

Java interview questions Part22

2007-10-26T12:42:00.002-07:00

7.
Using the fragments below, complete the following code so it compiles. Note, you may not have to fill all of the slots.

Code:

class AgedP {
__________ _________ _________ _________ _________
public AgedP(int x) {
_ ________ _ ________ _ ________ _________ ___________
}
}
public class Kinder extends AgedP {
_________ _________ _________ _________ _________ _________
public Kinder(int x) {
_________ _________ _________ _________ ___________() ;
}
}

Fragments: Use the following fragments zero or more times:

AgedP
super
this

(
)
{
}

;

8.
Given:

1. class Plant {
2. String getName() { return "plant"; }
3. Plant getType() { return this; }
4. }
5. class Flower extends Plant {
6. // insert code here
7. }
8. class Tulip extends Flower {}

Which statement(s), inserted at line 6, will compile? (Choose all that apply.)

Flower getType() { return this; }

String getType() { return "this"; }

Plant getType() { return this; }

Tulip getType() { return new Tulip() ;}

9.
Given:

1. class Zing {
2. protected Hmpf h;
3. }
4. class Woop extends Zing { }
5. class Hmpf { }

Which is true? (Choose all that apply.)

Woop is-a Hmpf and has-a zing.

zing is-a Woop and has-a Hmpf.

Hmpf has-a Woop and Woop is-a Zing.

Woop has-a Hmpf and Woop is-a zing.

Zing has-a Hmpf and Zing is-a Woop.

10.
Given:

1. class Programmer {
2. Programmer debug() { return this; }
3. }
4. class SCJP extends Programmer {
5. // insert code here
6. }

Which, inserted at line 5, will compile? (Choose all that apply.)

Programmer debug() { return this; }

SCJP debug() { return this; }

Object debug() { return this; }

int debug() { return 1; }

int debug(int x) { return 1; }

Object debug (int x) { return this; }

11.
Given:

class Uber {
static int y = 2;
Uber(int x) { this(); y = y * 2; }
Uber() { y++; }
}
class Minor extends Uber {
Minor() { super(y); y = y + 3; }
public static void main(String [] args) {
new Minor();
System.out.println(y);
} }

What is the result?

6

7

8

9

Compilation fails.

An exception is thrown.

12.
Which statement(s) are true? (Choose all that apply.)

Cohesion is the OO principle most closely associated with hiding implementation details.

Cohesion is the OO principle most closely associated with making sure that classes know about other classes only through their APIs.

Cohesion is the OO principle most closely associated with making sure that a class is designed with a single, well-focused purpose.

Cohesion is the OO principle most closely associated with allowing a single object to be seen as having many types.

13.
Given:

1. class Dog { }
2. class Beagle extends Dog { }
3.
4. class Kennel {
5. public static void main(String [] arfs) {
6. Beagle bl = new Beagle();
7. Dog dogl = new Dog();
8. Dog dog2 = bl;
9. // insert code here
10. } }

Which, inserted at line 9, will compile? (Choose all that apply.)

Beagle b2 = (Beagle) dog1;

Beagle b3 = (Beagle) dog2;

Beagle b4 = dog2;

None of the above statements will compile.

14.
Given the following,

1. class X { void dol() { } }
2. class Y extends X { void do2() { } }
3.
4. class Chrome {
5. public static void main(String [] args) {
6. X x1 = new X();
7. X x2 = new Y();
8. Y y1 = new Y();
9. // insert code here
10. } }

Which, inserted at line 9, will compile? (Choose all that apply.)

x2.do2( );

(Y) x2. do2( );

((Y)x2).do2();

None of the above statements will compile.

Java interview questions Part21

2007-10-26T12:42:00.001-07:00

1.
Which statement(s) are true? (Choose all that apply.)

Has-a relationships always rely on inheritance.

Has-a relationships always rely on instance variables.

Has-a relationships always require at least two class types.

Has-a relationships always rely on polymorphism.

Has-a relationships are always tightly coupled.

2.
Given:

class Clidders {
public final void flipper() { System.out.println("Clidder"); }
}
public class Clidlets extends Clidders {
public void flipper() {
System.out.println("Flip a Clidlet");
super.flipper();
}
public static void main(String [] args) {
new Clidlets().flipper();
}
}

What is the result?

Flip a Clidlet

Flip a Clidder

Flip a Clidder

Flip a Clidlet

Flip a Clidlet

Flip a Clidder

Compilation fails.

3.
Given:

public abstract interface Frobnicate { public void twiddle(String s) ; }

Which is a correct class? (Choose all that apply.)

public abstract class Frob implements Frobnicate {

public abstract void twiddle(String s){}

}

public abstract class Frob implements Frobnicate { }

public class Frob extends Frobnicate {

public void twiddle(Integer i) { }

}

public class Frob implements Frobnicate {

public void twiddle(Integer i) { }

}

public class Frob implements Frobnicate {

public void twiddle(String i) { }

public void twiddle(Integer s) { }

}

4.
Given:

class Top {
public Top(String s) { System.out.print("B"); }
}
public class Bottom2 extends Top {
public Bottom2(String s) { System.out.print("D"); }
public static void main(String [] args) {
new Bottom2("C");
System.out.println(" ");
}
}

What is the result?

BD

DB

BDC

DBC

Compilation fails.

5.
Select the two statements that best indicate a situation with low coupling. (Choose two.)

The attributes of the class are all private.

The class refers to a small number of other objects.

The object contains only a small number of variables.

The object is referred to using an anonymous variable, not directly.

The reference variable is declared for an interface type, not a class. The interface provides a small number of methods.

It is unlikely that changes made to one class will require any changes in another.

6.
Given:

class Clidder {
private final void flipper() { System.out.println ("Clidder"); }
}

public class Clidlet extends Clidder {
public final void flipper() { System.out.println("Clidlet"); }
public static void main(String [] args) {
new Clidlet().flipper();
}
}

What is the result?

Clidlet

Clidder

Clidder

Clidlet

Clidlet

Clidder

Compilation fails.

Java interview questions Part21

2007-10-26T12:39:00.000-07:00

3.
Which is true? (Choose all that apply. )

"X extends Y" is correct if and only if X is a class and Y is an interface.

"X extends Y" is correct if and only if X is an interface and Y is a class.

"X extends Y" is correct if X and Y are either both classes or both interfaces.

"X extends Y" is correct for all combinations of X and Y being classes and/or interfaces.

4.
Which are valid declarations? (Choose all that apply.)

int $x;

int 123;

int _123;

int #dim;

int %percent;

int *divide;

int central_sales_region_Summer_2005_gross_sales;

5.
Which method names follow the JavaBeans standard? (Choose all that apply.)

addSize

getCust

deleteRep

isColorado

putDimensions

6.
Given:

1. class Voop {
2. public static void main(String [] args) {
3. doStuff(1);
4. doStuff(1, 2);
5. }
6. // insert code here
7. }

Which, inserted independently at line 6, will compile? (Choose all that apply.)

static void doStuff(int... doArgs) { }

static void doStuff (int [] doArgs) { }

static void doStuff(int doArgs...) { }

static void doStuff(int... doArgs, int y) { }

static void doStuff(int x, int... doArgs) { }

7.
Which are legal declarations? (Choose all that apply. )

short x [];

short [] y;

short [5] x2;

short z2 [5];

short [] z [] [];

short [] y2 = [5];

8.
Given:

1. enum Animals {
2. DOG ("woof"), CAT ("meow"), FISH ("burble");
3. String sound;
4. Animals(String s) { sound = s; }
5. }
6. class TestEnum {
7. static Animals a;
8. public static void main(String[] args) {
9. System.out.println(a.DOG.sound + " " + a.FISH.sound);
10. }
11. }

What is the result?

woof burble

Multiple compilation errors

Compilation fails due to an error on line 2

Compilation fails due to an error on line 3

Compilation fails due to an error on line 4

Compilation fails due to an error on line 9

9.
Given:

1. enum A { A }
2. class E2 {
3. enum B { B }
4. void C() {
5. enum D { D }
6. }
7. }

Which statements are true? (Choose all that apply.)

The code compiles.

If only line 1 is removed the code compiles.

If only line 3 is removed the code compiles.

If only line 5 is removed the code compiles.

If lines 1 and 3 are removed the code compiles

If lines 1, 3 and 5 are removed the code compiles

Java interview questions Part21

2007-10-26T12:34:00.000-07:00

Which declare a compilable abstract class? (Choose all that apply.)

public abstract class Canine { public Bark speak(); }

public abstract class Canine { public Bark speak() { } }

public class Canine { public abstract Bark speak(); }

public class Canine abstract { public abstract Bark speak(); }

Java interview questions Part20

2007-10-26T12:28:00.000-07:00

Given the following,

1. interface Base {
2. boolean m1 ();
3. byte m2(short s);
4. }

Which code fragments will compile? (Choose all that apply.)

interface Base2 implements Base { }

abstract class Class2 extends Base {

public boolean ml() { return true; } }

abstract class Class2 implements Base { }

abstract class Class2. implements Base {

public boolean m1() { return (true); } }

class Class2 implements Base {

boolean m1( ) { return false; }

XML Interview Question Part4

2007-10-25T11:27:00.000-07:00

50. How to transform an XML document to an HTML document?

To perform the transformation, you need to obtain an XSLT transformer and use it to apply the style sheet to the XML data. The following code fragment obtains a transformer by instantiating a TransformerFactory object, reading in the style sheet and XML files, creating a file for the HTML output, and then finally obtaining the Transformer object transformer from the TransformerFactory object tFactory.

TransformerFactory tFactory = TransformerFactory.newInstance();

String stylesheet = "xxx.xsl";

String sourceId = "newXML.xml";

File yyyHTML = new File("yyyHTML.html");

FileOutputStream os = new FileOutputStream(yyyHTML);

Transformer transformer = tFactory.newTransformer(new StreamSource(stylesheet));

transformer.transform(new StreamSource(sourceId), new StreamResult(os));

51. What are major subcomponents of XSL?

The XML Stylesheet Language (XSL) has three major subcomponents:

1. XSL-FO -- The largest subcomponent. It describes font sizes, page layouts, and how information "flows" from one page to another.

2. XSLT -- A transformation language that lets you define a transformation from XML into some other format. Like producing HTML, a different XML structure, a plain text or other document format.

3. XPath -- A specification that lets you specify a path to an element.

52. What is transformation language in XSL?

Extensible Styles Language(XSL) has two parts:

a transformation language(XSLT) and a formatting language.

The transformation language lets you transform documents into different forms, while the formatting language actually formats and styles documents in various ways.

53. What is JAX-RPC?

JAX-RPC stands for Java API for XML-based RPC(Remote Procedure Call). It is an API for building Web services and clients that use RPC and XML.

In JAX-RPC, a remote procedure call is represented by an XML-based protocol such as SOAP. The SOAP specification defines the envelope structure, encoding rules, and convention for representing remote procedure calls and responses. These calls and responses are transmitted as SOAP messages (XML files) over HTTP.

With JAX-RPC, the developer does not generate or parse SOAP messages. It is the JAX-RPC runtime system that converts the API calls and responses to and from SOAP messages.

54. What is value type?

A value type is a class whose state may be passed between a client and remote service as a method parameter or return value. For example, an account class may have account number, account owner and amount field. These information may be passed between client and server as a method deposit parameter and a return value of method account query.

55. What kind of rules do the value type must follow?

To be supported by JAX-RPC, a value type must conform to the following rules:

o It must have a public default constructor.

o It must not implement (either directly or indirectly) the java.rmi.Remote interface.

o Its fields must be supported JAX-RPC types.

o The value type may contain public, private, or protected fields. The field of a value type must meet these requirements:

 A public field cannot be final or transient.

 A non-public field must have corresponding getter and setter methods.

Return to top

________________________________________

56. What is SAAJ?

SAAJ stands for SOAP(Simple Object Access Protocal) with Attachments API for Java. SAAJ is used mainly for the SOAP messaging that goes on behind the scenes in JAX-RPC and JAXR implementations.

Secondarily, it is an API that developers can use when they choose to write SOAP messaging applications directly rather than using JAX-RPC.

57. What is XML Registry?

An XML registry is an infrastructure that enables the building, deployment, and discovery of Web services. It is a neutral third party that facilitates dynamic and loosely coupled business-to-business (B2B) interactions. A registry is available to organizations as a shared resource, often in the form of a Web-based service.

There are many kinds of specifications for XML registries, including ebXML Registry and Repository and The Universal Description, Discovery, and Integration (UDDI).

58. What is JAXR?

JAXR stands for Java API for XML Registries. It enables Java software programmers to use an API to access a variety of XML registries. The current version of the JAXR specification can be found at http://java.sun.com/xml/downloads/jaxr.html

59. What is XHTML?

XHTML is an application of XML that tries to make XML documents look and act like HTML documents. The XHTML specification is a reformulation of HTML 4.0 into XML. The following is code of XHTML.

1.

2.
3. "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

4.

5. Welcome to see xhtml

6.

7.

Welcome to XHTML!

8.

9.

The following is the display on your browser.

________________________________________

XML Interview Question 4

2007-10-25T11:26:00.000-07:00

35. How to declare an image tag in a DTD file?

You can declare an image tag in the following form:

1.

2.
alt CDATA #IMPLIED

src CDATA #REQUIRED

type CDATA "image/gif"

>

3.

4.

The line one declares image as an optional element. The line 2 declares attributes of an image tag. For the moment, you can not declare an image tag like type ("image/gif", "image/jpeg"). The line 3 declares a notation named GIF that stands for the image/gif MIME type. The line 4 creates an external unparsed entity named some to refer to the external image file, image.gif.

36. What is conditional section?

Conditional section is a way to let XML document to choose which dtd should be "included" or "ignored". Use as an end. For example, you want to use a different versions of a DTD for xml document or sgml document, you may code as follows:

... XML-only definitions

]]>

... SGML-only definitions

]]>

... common definitions

37. How many entities are catagorized in dtd?

o Internal entity: An entity that is referenced in its own document content.

o External entity: An entity that is referenced in another file.

o General entity: including internal or external entity

o Parameter entity: An entity that contains DTD specifications that are referenced from within the DTD.

o Parsed entity: An entity that contains XML(text and markup) and is therefore parsed.

o Unparsed entity: An entity that contains binary data(like images)

Return to top

________________________________________

38. What is xmlns?

The xmlns stands for XML NameSpace. It is an attribute for a tag. It is used in DTD to prevent conflicts. For example, the following tells us the title element will use designated DTD.

xmlns CDATA #FIXED "http://www.example.com/slideshow">

...

or

<br /><br /> Overview<br /><br />

or

...>

...

or

...>

...

Overview

...

or

xmlns:xhtml='urn:...'>

...

Here we use "http:", you may use "urn:" instead.

39. What is xsi?

The "xsi" stands for XML Schema Instance like:

xsi:noNamespaceSchemaLocation='YourSchemaDefinition.xsd'

The line specifies the schema to use for elements in the document that do not have a namespace prefix.

40. Where to use XML?

XML can be used in many places:

o Data representation in Web, especially for Java client/server web.

o Data interchange in all sorts of transactions as long as both sides agree on.

o Document-Driven Programming(DDP)

o Binding

o Archiving

41. What is JAXP?

JAXP stands for Java APIs for XML, which let you write your Web application entirely in the Java programming language. There are two broad categories:

o Document-oriented -- processes XML documents using various parsers.

o Procedure-oriented -- including JAX-RPC, JAXM, and JAXR.

42. What is RELAX NG?

RELAX NG stands for Regular Language description for XML. It is simpler than XML structure schema and an emerging standard under the auspices of OASIS. NG stands for Next Generation. For more information on RELAX NG, see www.oasis-open.org/committees/relax-ng/

43. What is XML schema

XML Schema is a large, complex standard that has two parts. One part specifies structure relationships. (This is the largest and most complex part.) The other part specifies mechanisms for validating the content of XML elements by specifying a (potentially very sophisticated) datatype for each element. For more information on XML schema, visit www.w3c.org/XML/Schema

44. What is JAXM?

JAXM stands for Java APIs for XML Messaging. It provides a standard way to send XML documents over the internet form the Java platform. It is based on the SOAP 1.1 and SOAP with Attaqchements specifications which define a basic framework for exchanging XML messages. It can make one-way (asynchronous) messaging, rout of a message to more than one party and guarantee the delivery, whereas the JAX-RPC cannot.

45. How to get a Point-to-Point connection via JAXM?

All JAXM connections are created by using connection factory methods.

SOAPConnectionFactory factory = SOAPConnectionFactory.newInstance();

SOAPConnection con = factory.createConnection();

46. How to get a connection to the Messaging Provider via JAXM?

There are two ways to obtain this connection.

ProviderConnectionFactory pcFactory = ProviderConnectionFactory.newInstance();

ProviderConnection pcCon = pcFactory.createConnection();

or

Context ctx = getInitialContext();

ProviderConnectionFactory pcFactory = (ProviderConnectionFactory)ctx.lookup("SomeMsgProvider");

ProviderConnection con = pcFactory.createConnection();

47. How XML is related with other technologies?

There are many XML related technologies directly or non-directly:

o SAX -- Simple API for XML: reads and writes XML data in a server.

o DOM -- Document Object Model: converts an XML document into a collection of objects.

o JDOM -- Java DOM: processes more data-oriented structures.

o dom4j -- DOM for Java: a factory-based implementation, easier to modify for complex, special-purpose apps.

o DTD -- Document Type Definition: specifies the kinds of tags that can be included in XML document.

o Namespace -- writes an XML document that uses two or more sets of XML tags in modular fashion.

o XSL -- Extensible Stylesheet Language: specifies how to identify data, not how to display it.

o XSLT -- Extensible Stylesheet Language for Transformations: specifies what to convert an XML tag into.

o XSL-FO -- Extensible Stylesheet Language for Formatting Objects: specifies how to link multiple areas on a page.

o SAAJ -- SOAP with Attachments API for Java.

o JAXR -- Java API for XML Registries, used to look and find web services.

o TREX -- Tree Regular Expressions for XML, part of RELAX NG

o SOX -- Schema for Object-Oriented XML

o Schematron -- Schema for Object-Oriented XML, an assetion based schema by www.ascc.net.

o ebXML -- Electronic Business with XML developed by UN/CEFACT and OASIS

o cxml -- Commerce XML, more info at www.rosettanet.org

o etc.

48. What is the difference between SAX and DOM?

The Simple API for XML(SAX) and the Document Object Model(DOM) are both defined by the W3C. Unlike a SAX parser, a DOM parser allows random access to particular pieces of data in an XML document. Another difference is that with a SAX parser, you can only read an XML document, but with a DOM parser, you can build an object representation of the document and manipulate it in memory, adding a new element or deleting an existing one.

49. How to transform a DOM tree to an XML document?

Use the following code:

DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();

DocumentBuilder builder = factory.newDocumentBuilder();

Document document = builder.parse("xxxList.xml");

Node rootNode = document.getDocumentElement();

NodeList list = document.getElementsByTagName("xxxx");

//add node

Text tnNode = document.createTextNode("yyyy");

newNameNode.appendChild(tnNode);

....

TransformerFactory transFactory = TransformerFactory.newInstance();

Transformer transformer = transFactory.newTransformer();

DOMSource source = new DOMSource(document);

File newXML = new File("newXML.xml");

FileOutputStream os = new FileOutputStream(newXML);

StreamResult result = new StreamResult(os);

transformer.transform(source, result);

Java EJB Interview questions Part2

2007-10-25T11:25:00.000-07:00

25. What syntax should be used to describe a more children elements?

For example, if a and b represent child elements:

o a+ -- one or more occurences of a

o a* -- zero or more occurences of a

o a? -- a or nothing

o a, b -- a followed by b

o a | b -- a or b, but not both

o (expression) -- a unit may have more of above expressions

26. What the following tells us in a dtd file?

1.

2.

3.

4.

5.

The first line says that a slideshow element contains one or more slide elements. The second line says that a slide element consists of a title followed by zero or more item elements. The third line says that a title element consists entirely of parsed character data(PCDATA). The "#" sign that precedes PCDATA indicates that what follows is a special word. The fourth line says the item element is either PCDATA or an item. The asterisk at the end says that either one can occur zero or more times in succession. The fifth line says that content is a parameter entity reference.

27. What is mixed-content model?

The content of a tag in the xml file can be #PCDATA or any number of item elements like the fourth line above.

28. Is DTD definition hierarchical?

No. The DTD definition is not hierarchical. But you can work around to make your xml tags hierarchical. For example, if you have a title for slideshow and a title for each slide, you can use slide-title to represent the title in slide and make a definition for slide-title. It is so called "hyphenation hierarchy. Otherwise, the title definition will work for every title in xml file.

29. What is special element value and how to use it?

There are two special values: ANY or EMPTY. The "ANY" notation says that the element may contain any other defined element, or PCDATA. The "EMPTY" notation says that the element contains no contents. For example an empty tag contains no contents.

30. How to reference a DTD file?

If the DTD definition is in a separate file from the XML document, you have to write something to reference it from the XML document. For example, if your slideshow.dtd is ready for use, then, in your xml document file, after the xml declaration, write:

The above statement says that the element slideshow tag will use definition in slideshow.dtd. The SYSTEM identifier specifies the location of the DTD file and the path is relative to the location of the xml document. You may use http:// or file:/ to indicate the path of the DTD file.

Or you can reference a definition within the XML document by using a square brackets like the following, rather than referring to an external DTD file.

...local subset definitions here...

]>

31. How to declare a public DTD?

Replace SYSTEM to PUBLIC and give url to that dtd.

"http://www.somewhere.com/someones/slideshow1.dtd" >

32. What is the meaning of ATTLIST? What do the following statements tell us?

ATTLIST means attribute list. The name that follows ATTLIST specifies the element for which the attributes are being defined. For example, you have a slideshow tag with title, date and author attributes, you may code as:

title CDATA #REQUIRED

date CDATA #IMPLIED

author CDATA "unknown"

>

The DTD tag ATTLIST begins the series of attribute definitions. The slideshow element has three attributes. The title, date and author are the names of attributes of slideshow. CDATA is a type of the attribute; it means unparsed charater data or a text string.

The #REQUIRED means the attribute value must be specified in the document. The #IMPLIED means the value need not be specified in the document.

33. What does the & sign mean in dtd file?

The & sign means an entity variable name. Note it should be ended with semicolon ";" sign. For example:

...

]>

...

©right; ...

Wherever the ©right; is parsed, it will be replaced with entity copyright sign ©.

34. How to declare a parameter entity reference?

Use to declare it and use an & as start and ; as end to enclose the parameter entity reference. For example, TODAY is a parameter entity reference.

]>

HELLO FROM HTML

WELCOME TO THE WILD WORLD

&TODAY;

Save above file as greeting.xml, use your browser to look at it. You may get a similar display, except that the tag will display "NOV 1, 2003". Or you can click here to see the result.

Note: It is possible that your browser may not support XML. If you use MS IE 5.5 above, or NS 5.0 above, you may be able to see it.

XML Interview Question Part3

2007-10-25T11:24:00.001-07:00

18. How to use JavaScript to display XML document?

To illustrate it, we use a simple XML document hello.xml as follows:

Hello guys!

In an HTML file called getxml.html:

Get data from XML document

Here comes:

Here is the display in your browser. Click the button to see what happens? Press the "F5" button on your keyboard to refresh the display. If you cannot see the result from your browser, check if your browser blocks active contents or not.

________________________________________

Get data from XML document

Here comes:

________________________________________

19. What is DTD tag?

A DTD tag is a tag used in DTD definition file. It starts with . It tells parser how to handle xml file.

20. What is CDATA?

A CDATA is a section mark which works like

...

in HTML, only more so--all whitespace in a CDATA section is significant, and characters in it are not interpreted as XML. A CDATA section starts with . If you have a section which contains many & or <, you can mark it, so the XML processor will not parse it.

21. What is the basic syntax for the document type declaration?

The basic syntax:

where the is part of a document's prolog; the root-name is the name of root tag; the DTD is a document type definition. It can be internal or external.

The document type declaration may have the following forms:

22. How the internal DTD looks like?

]>

....

23. What is the syntax of element declaration?

where name is the name of the element; CONTENT_MODEL can be set to EMPTY or ANY, or it can hold mixed content or child elements.

24. What is the meaning of the following statement?

This is a DTD tag definition. The notation says that a slideshow element consists of one or more slide elements. If there is no plus sign after slide, it says that a slideshow has only one slide element. If the plus sign is replaced with question mark "?", it says there may be zero or one slide. If the plus sign is replaced with asterisk "*", it say that there may be zero or more slide elements.

XML Interview Question Part2

2007-10-25T11:23:00.001-07:00

11. What is Unicode?

Unicode uses 2 bytes to represent characters, extending from 0 to 65,535. ASCII(American Standard Code for Information Interchange) code uses 1 byte to represent characters, extending from 0 to 255. The Unicodes 0 to 255 correspond to the ASCII 0 to 255 codes. Therefore, Unicode can include many of the symbols commonly used in worldwide character and ideograph sets.

UTF-8 means using a compressed version of Unicode that uses 8 bits to represent characters. UTF-16 is a special encoding that represents UCS(Universal Character System) symbols using 2 bytes to represent characters.

12. How to write XML processing instructions?

The XML processing instructions give commands or information to an application that is processing the XML data; it is application specific. It has the following format:

where is the end of procession instruction, the "target" is the name of the application that is expected to do the processing, and "instructions" is a string of characters that embodies the information or commands for the application to process. Note: there cannot be any space between the initial

An XML file may have multiple processing instructions to tell different applications to do similar things.

13. How XML treats with whitespace?

The spaces, carriage returns, line feeds and tabs are all treated as whitespace in XML. XML document uses the UNIX convention for line endings, which means that lines are ended with a linefeed character only -- ASCII code 10(DOS file uses a pair of ASCII codes 13 and 10). When parsed, that is treated simply as a single linefeed.

If you want to preserve whitespace, use a special attribute xml:space or set attribute to default to indicate it in a element declaration.

14. Is XML tag case-sensitive?

Yes. XML tags are case-sensitive. The start and end tags should be matched exactly.

15. Why do people say that XML is portable?

There are several reasons. First, it is written in a text format, which is readable by both human beings and text-editing software. Second, applications can parse and process XML documents, and human beings can also read them in case there is an error in processing. Third, XML document does not include formatting instructions, it can be displayed in various ways. Keeping data separate from formatting instructions means that the same data can be published to different media.

16. How to let browser display XML file?

There are two ways to do so:

o Use a style sheet to indicate to a browser how you want the content of the elements to be displayed, like Cascading Style Sheet(CSS) or Extensible Style Sheet Language(XSL).

o use a programming language to handle the XML document in programming code,like Java or JavaScript.

17. Which is better to store data using elements or using attributes?

There is no clear-cut to say which is better. It depends on the case. But it is worth noting that too many attributes make documents hard to read and attribute names must be unique. If more than 4 attributes in a tag are used, think about breaking up the tag into a number of enclosed tags.

XML Interview Question Part1

2007-10-25T11:22:00.000-07:00

7. What is an empty tag?

Empty tag is a tag with ending "/>" and used to mark something in your well-formed tags. It doesn't contain any content, so it is called "empty tag". It has two forms:

Note: not

or

or

8. What comments should be used in XML?

Comments are ignored by XML parsers. A program will never see them in fact, unless you activate special settings in the parser. XML comments are very much like HTML comments.

It is worth noting that Comments must not come before an XML declaration or inside markups. You cannot use "--" between your comments. You can use comments to hide or remove parts of documents as long as the enclosed parts do not themselves contain any comments.

9. How to deal with special characters in XML like < or &, etc.?

Like HTML, you should use entity reference to replace them, even if in embeded JavaScript code.

10. What is XML Prolog?

Prologs come at the very beginning of XML documents. Like HTML's tag , XML prolog is a declaration that is used to indicate the start of XML file like the following:

or

or

It contains some or all of three attributes:

o version -- not optional

o encoding -- default UTF-8

o standalone -- "yes" or "no"

It is a good practice to include XML prolog whenever you create an XML file, though it is optional.

XML Interview Question

2007-10-25T11:20:00.000-07:00

1. What Is XML?

XML stands for Extensible Markup Language. It is a text-based meta-markup language defined by the World Wide Web Consortium. It has become the standard for data interchange on the Web.

2. Why do we need to learn XML?

Because XML is a meta-markup language, it lets you create your own markup language.

It is easy for data exchange, customization, self-describing, structured and integrated.

3. What does XML look like?

Hello guys!

4. What is the difference between HTML and XML?

HTML and XML both are based on Standard Generalized Markup Language(SGML), but

o HTML uses predefined tags, whereas XML uses user-defined tags which can be used to identify data relationships like hierarchical structure(elements, subelements, subsubelements,and so on.)

o HTML specifies its representation, whereas XML identifies the content for the data.

o Unlike HTML, XML tags are well-formed. XML data is searchable, format-free and reusable.

5. What is XML attribute?

Attribute is an additional information attached to a tag. For example

subject="Discuss XML issues">

here we go

The "to", "from" and "subject" are attributes of "message" tag.

6. How to deal with double quotes in attribute assignment?

Use a single quote to enclose a double quotes, for example,

Java Newworking questions Part2

2007-10-25T11:19:00.003-07:00

5. What are the two important TCP Socket classes?
Socket and ServerSocket. ServerSocket is used for normal two-way socket communication. Socket class allows us to read and write through the sockets. getInputStream() and getOutputStream() are the two methods available in Socket class.
________________________________________
6. When MalformedURLException and UnknownHostException throws?
When the specified URL is not connected then the URL throw MalformedURLException and If InetAddress? methods getByName and getLocalHost are unable to resolve the host name they throw an UnknownHostException.
________________________________________
7. What does RMI stand for?
It stands for Remote Method Invocation.
________________________________________
8. What is RMI?
RMI is a set of APIs that allows to build distributed applications. RMI uses interfaces to define remote objects to turn local method invocations into remote method invocations.
________________________________________

Java Newworking questions Part1

2007-10-25T11:19:00.001-07:00

1. What is the difference between URL instance and URLConnection instance?
A URL instance represents the location of a resource, and a URLConnection instance represents a link for accessing or communicating with the resource at the location.
________________________________________
2. How do I make a connection to URL?
You obtain a URL instance and then invoke openConnection on it. URLConnection is an abstract class, which means you can't directly create instances of it using a constructor. We have to invoke openConnection method on a URL instance, to get the right kind of connection for your URL. Eg. URL url;
URLConnection connection;
try{ url = new URL("...");
connection = url.openConnection();
}catch (MalFormedURLException e) { }
________________________________________
3. What Is a Socket?
A socket is one end-point of a two-way communication link between two programs running on the network. A socket is bound to a port number so that the TCP layer can identify the application that data is destined to be sent. Socket classes are used to represent the connection between a client program and a server program. The java.net package provides two classes--Socket and ServerSocket--which implement the client side of the connection and the server side of the connection, respectively.
________________________________________
4. What information is needed to create a TCP Socket?
The Local System?s IP Address and Port Number. And the Remote System's IPAddress and Port Number.
________________________________________

Java MVC

2007-10-25T11:18:00.001-07:00

MVC
The MVC (Model-View-Controller) architecture the client request is first intercepted by a servlet referred as controller servlet. this servlet handles the initial processing of the request and determines which JSP page to display next. Here the controller servlet is the single point of entry, there is a clear sepration of business logic, presentation output and request processing. MCV architecture is a way of decomposing an application into three parts:

The model maintains the state and data that the application represents.
The view allows the display of information about the model to the user.
The controller allows the user to manipulate the application.
the model, the view and the controller.

MVC was originally applied in the graphical user interaction model of input, processing and output.

In Struts, the view is handled by JSPs and presentation components, the model is represented by Java Beans and the controller uses Servlets to perform its action.

Model
A model represents an application’s data and contains the logic for accessing and manipulating that data. Any data that is part of the persistent state of the application should reside in the model objects. The business objects update the application state. ActionForm bean represents the Model state at a session or request level, and not at a persistent level. Model services are accessed by the controller for either querying or effecting a change in the model state. The model notifies the view when a state change occurs in the model.The JSP file reads information from the ActionForm bean using JSP tags.

View
The view is responsible for rendering the state of the model. The presentation semantics are encapsulated within the view, therefore model data can be adapted for several different kinds of clients.The view modifies itself when a change in the model is communicated to the view. A view forwards user input to the controller.The view is simply a JSP or HTML file. There is no flow logic, no business logic, and no model information -- just tags. Tags are one of the things that make Struts unique compared to other frameworks like Velocity.

Controller
The controller is responsible for intercepting and translating user input into actions to
be performed by the model. The controller is responsible for selecting the next view based on user input and the outcome of model operations.The Controller receives the request from the browser, and makes the decision where to send the request. With Struts, the Controller is a command design pattern implemented as a servlet. The struts-config.xml file configures the Controller.

JMS Interview Questions

2007-10-25T11:17:00.001-07:00

Q: What is the use of Message object?
A: Message is a light weight message having only header and properties and no payload. Thus if the received are to be notified abt an event, and no data needs to be exchanged then using Message can be very efficient.
[ Received from Sandesh Sadhale]

Q: What is the basic difference between Publish Subscribe model and P2P model?
A: Publish Subscribe model is typically used in one-to-many situation. It is unreliable but very fast. P2P model is used in one-to-one situation. It is highly reliable.

Q: What is the use of BytesMessage?
A: BytesMessage contains an array of primitive bytes in it's payload. Thus it can be used for transfer of data between two applications in their native format which may not be compatible with other Message types. It is also useful where JMS is used purely as a transport between two systems and the message payload is opaque to the JMS client. Whenever you store any primitive type, it is converted into it's byte representation and then stored in the payload. There is no boundary line between the different data types stored. Thus you can even read a long as short. This would result in erroneous data and hence it is advisable that the payload be read in the same order and using the same type in which it was created by the sender.

Q: What is the use of StreamMessage?
A: StreamMessage carries a stream of Java primitive types as it's payload. It contains some conveient methods for reading the data stored in the payload. However StreamMessage prevents reading a long value as short, something that is allwed in case of BytesMessage. This is so because the StreamMessage also writes the type information alonwgith the value of the primitive type and enforces a set of strict conversion rules which actually prevents reading of one primitive type as another.

Q: What is the use of TextMessage?
A: TextMessage contains instance of java.lang.String as it's payload. Thus it is very useful for exchanging textual data. It can also be used for exchanging complex character data such as an XML document.

Q: What is the use of ObjectMessage?
A: ObjectMessage contains a Serializable java object as it's payload. Thus it allows exchange of Java objects between applications. This in itself mandates that both the applications be Java applications. The consumer of the message must typecast the object received to it's appropriate type. Thus the consumer should before hand know the actual type of the object sent by the sender. Wrong type casting would result in ClassCastException. Moreover the class definition of the object set in the payload should be available on both the machine, the sender as well as the consumer. If the class definition is not available in the consumer machine, an attempt to type cast would result in ClassNotFoundException. Some of the MOMs might support dynamic loading of the desired class over the network, but the JMS specification does not mandate this behavior and would be a value added service if provided by your vendor. And relying on any such vendor specific functionality would hamper the portability of your application. Most of the time the class need to be put in the classpath of both, the sender and the consumer, manually by the developer.

Q: What is the use of MapMessage?
A: A MapMessage carries name-value pair as it's payload. Thus it's payload is similar to the java.util.Properties object of Java. The values can be Java primitives or their wrappers.

Q: What is the difference between BytesMessage and StreamMessage??
A: BytesMessage stores the primitive data types by converting them to their byte representation. Thus the message is one contiguous stream of bytes. While the StreamMessage maintains a boundary between the different data types stored because it also stores the type information along with the value of the primitive being stored. BytesMessage allows data to be read using any type. Thus even if your payload contains a long value, you can invoke a method to read a short and it will return you something. It will not give you a semantically correct data but the call will succeed in reading the first two bytes of data. This is strictly prohibited in the StreamMessage. It maintains the type information of the data being stored and enforces strict conversion rules on the data being read.

JMS Interview Questions

2007-10-25T11:16:00.001-07:00

Q: What is JMS?
A: JMS is an acronym used for Java Messaging Service. It is Java's answer to creating software using asynchronous messaging. It is one of the official specifications of the J2EE technologies and is a key technology.

Q: How JMS is different from RPC?
A: In RPC the method invoker waits for the method to finish execution and return the control back to the invoker. Thus it is completely synchronous in nature. While in JMS the message sender just sends the message to the destination and continues it's own processing. The sender does not wait for the receiver to respond. This is asynchronous behavior.

Q: What are the advantages of JMS?
A: JMS is asynchronous in nature. Thus not all the pieces need to be up all the time for the application to function as a whole. Even if the receiver is down the MOM will store the messages on it's behalf and will send them once it comes back up. Thus at least a part of application can still function as there is no blocking.

Q: Are you aware of any major JMS products available in the market?
A: IBM's MQ Series is one of the most popular product used as Message Oriented Middleware. Some of the other products are SonicMQ, iBus etc. Weblogic application server also comes with built in support for JMS messaging.

Q: What are the different types of messages available in the JMS API?
A: Message, TextMessage, BytesMessage, StreamMessage, ObjectMessage, MapMessage are the different messages available in the JMS API.

Q: What are the different messaging paradigms JMS supports?
A: Publish and Subscribe i.e. pub/suc and Point to Point i.e. p2p.

Q: What is the difference between topic and queue?
A: A topic is typically used for one to many messaging i.e. it supports publish subscribe model of messaging. While queue is used for one-to-one messaging i.e. it supports Point to Point Messaging.

Q: What is the role of JMS in enterprise solution development?
A: JMS is typically used in the following scenarios
1. Enterprise Application Integration: - Where a legacy application is integrated with a new application via messaging.
2. B2B or Business to Business: - Businesses can interact with each other via messaging because JMS allows organizations to cooperate without tightly coupling their business systems.
3. Geographically dispersed units: - JMS can ensure safe exchange of data amongst the geographically dispersed units of an organization.
4. One to many applications: - The applications that have to push data in packet to huge number of clients in a one-to-many fashion are good candidates for the use JMS. Typical such applications are Auction Sites, Stock Quote Services etc.

Jdbc Interview Questions Part4

2007-10-25T11:12:00.002-07:00

31. How to store and retrive an object?
A class can be serialized to a binary database field in much the same way as the image. You may use the code above to store and retrive an object.
________________________________________
32. How to use meta data to check a column type?
Use getMetaData().getColumnType() method to check data type. For example to retrieve an Integer, you may check it first:
int count=0;
Connection con=getConnection();
Statement stmt= con.createStatement();
stmt.executeQuery("select counter from aTable");
ResultSet rs = stmt.getResultSet();
if(rs.next()) {
if(rs.getMetaData().getColumnType(1) == Types.INTEGER) {
Integer i=(Integer)rs.getObject(1);
count=i.intValue();
}
}
rs.close();
________________________________________
33. Why cannot java.util.Date match with java.sql.Date?
Because java.util.Date represents both date and time. SQL has three types to represent date and time.
o java.sql.Date -- (00/00/00)
o java.sql.Time -- (00:00:00)
o java.sql.Timestamp -- in nanoseconds
Note that they are subclasses of java.util.Date.
________________________________________
34. How to convert java.util.Date value to java.sql.Date?
Use the code below:
Calendar currenttime=Calendar.getInstance();
java.sql.Date startdate= new java.sql.Date((currenttime.getTime()).getTime());

or

SimpleDateFormat template = new SimpleDateFormat("yyyy-MM-dd");
java.util.Date enddate = new java.util.Date("10/31/99");
java.sql.Date sqlDate = java.sql.Date.valueOf(template.format(enddate));
________________________________________
Note: Most of sample codes are cited from Sun's JDBC tutorials.

Jdbc Interview Questions Part3

2007-10-25T11:12:00.001-07:00

21. How to make an update?
Creates a Statement object and calls the Statement.executeUpdate method.

String updateString = "INSERT INTO aDatabase VALUES (some text)";
int count = stmt.executeUpdate(updateString);
________________________________________
22. How to update a ResultSet?
You can update a value in a result set by calling the ResultSet.update method on the row where the cursor is positioned. The type value here is the same used when retrieving a value from the result set, for example, updateString updates a String value and updateDouble updates a double value in the result set.
rs.first();
updateDouble("balance", rs.getDouble("balance") - 5.00);
The update applies only to the result set until the call to rs.updateRow(), which updates the underlying database.
To delete the current row, use rs.deleteRow().
To insert a new row, use rs.moveToInsertRow().
________________________________________
23. How can you use PreparedStatement?
This special type of statement is derived from the more general class, Statement. If you want to execute a Statement object many times, it will normally reduce execution time to use a PreparedStatement object instead. The advantage to this is that in most cases, this SQL statement will be sent to the DBMS right away, where it will be compiled. As a result, the PreparedStatement object contains not just an SQL statement, but an SQL statement that has been precompiled. This means that when the PreparedStatement is executed, the DBMS can just run the PreparedStatement 's SQL statement without having to compile it first.
PreparedStatement updateSales = con.prepareStatement("UPDATE COFFEES SET SALES = ? WHERE COF_NAME LIKE ?");
________________________________________
24. How to call a Stored Procedure from JDBC?
The first step is to create a CallableStatement object. As with Statement an and PreparedStatement objects, this is done with an open Connection object. A CallableStatement object contains a call to a stored procedure;
E.g.
CallableStatement cs = con.prepareCall("{call SHOW_SUPPLIERS}");
ResultSet rs = cs.executeQuery();
________________________________________
25. How to Retrieve Warnings?
SQLWarning objects are a subclass of SQLException that deal with database access warnings. Warnings do not stop the execution of an application, as exceptions do; they simply alert the user that something did not happen as planned. A warning can be reported on a Connection object, a Statement object (including PreparedStatement and CallableStatement objects), or a ResultSet object. Each of these classes has a getWarnings method, which you must invoke in order to see the first warning reported on the calling object
SQLWarning warning = stmt.getWarnings();
if (warning != null) {

while (warning != null) {
System.out.println("Message: " + warning.getMessage());
System.out.println("SQLState: " + warning.getSQLState());
System.out.print("Vendor error code: ");
System.out.println(warning.getErrorCode());
warning = warning.getNextWarning();
}
}
________________________________________
26. How to Make Updates to Update ResultSets?
Another new feature in the JDBC 2.0 API is the ability to update rows in a result set using methods in the Java programming language rather than having to send an SQL command. But before you can take advantage of this capability, you need to create a ResultSet object that is updatable. In order to do this, you supply the ResultSet constant CONCUR_UPDATABLE to the createStatement method.
Connection con = DriverManager.getConnection("jdbc:mySubprotocol:mySubName");
Statement stmt = con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,
ResultSet.CONCUR_UPDATABLE);
ResultSet uprs = ("SELECT COF_NAME, PRICE FROM COFFEES");
________________________________________
27. How to set a scroll type?
Both Statements and PreparedStatements have an additional constructor that accepts a scroll type and an update type parameter. The scroll type value can be one of the following values:
o ResultSet.TYPE_FORWARD_ONLY
Default behavior in JDBC 1.0, application can only call next() on the result set.
o ResultSet.SCROLL_SENSITIVE
ResultSet is fully navigable and updates are reflected in the result set as they occur.
o ResultSet.SCROLL_INSENSITIVE
Result set is fully navigable, but updates are only visible after the result set is closed. You need to create a new result set to see the results.
________________________________________
28. How to set update type parameter?
In the constructors of Statements and PreparedStatements, you may use
o ResultSet.CONCUR_READ_ONLY
The result set is read only.
o ResultSet.CONCUR_UPDATABLE
The result set can be updated.
You may verify that your database supports these types by calling con.getMetaData().supportsResultSetConcurrency(ResultSet.SCROLL_INSENSITIVE, ResultSet.CONCUR_UPDATABLE);
________________________________________
29. How to do a batch job?
By default, every JDBC statement is sent to the database individually. To send multiple statements at one time , use addBatch() method to append statements to the original statement and call executeBatch() method to submit entire statement.
Statement stmt = con.createStatement();
stmt.addBatch("update registration set balance=balance-5.00 where theuser="+theuser);
stmt.addBatch("insert into auctionitems(description, startprice) values("+description+","+startprice+")");
...
int[] results = stmt.executeBatch();
The return result of the addBatch() method is an array of row counts affected for each statement executed in the batch job. If a problem occurred, a java.sql.BatchUpdateException is thrown. An incomplete array of row counts can be obtained from BatchUpdateException by calling its getUpdateCounts() method.
30. How to store and retrieve an image?
To store an image, you may use the code:
int itemnumber=400456;

File file = new File(itemnumber+".jpg");
FileInputStream fis = new FileInputStream(file);
PreparedStatement pstmt = con.prepareStatement("update auctionitems set theimage=? where id= ?");
pstmt.setBinaryStream(1, fis, (int)file.length()):
pstmt.setInt(2, itemnumber);
pstmt.executeUpdate();
pstmt.close();
fis.close();
To retrieve an image:
int itemnumber=400456;
byte[] imageBytes;//hold an image bytes to pass to createImage().

PreparedStatement pstmt = con.prepareStatement("select theimage from auctionitems where id= ?");
pstmt.setInt(1, itemnumber);
ResultSet rs=pstmt.executeQuery();
if(rs.next()) {
imageBytes = rs.getBytes(1);
}
pstmt.close();
rs.close();

Image auctionimage = Toolkit.getDefaultToolkit().createImage(imageBytes);
________________________________________

Jdbc Interview Questions Part2

2007-10-25T11:11:00.001-07:00

15. How to make a query?
Create a Statement object and calls the Statement.executeQuery method to select data from the database. The results of the query are returned in a ResultSet object.
Statement stmt = con.createStatement();
ResultSet results = stmt.executeQuery("SELECT data FROM aDatabase ");
________________________________________
16. How can you retrieve data from the ResultSet?
Use get methods to retrieve data from returned ResultSet object.
ResultSet rs = stmt.executeQuery("SELECT COF_NAME, PRICE FROM COFFEES");
String s = rs.getString("COF_NAME");
The method getString is invoked on the ResultSet object rs , so getString will retrieve (get) the value stored in the column COF_NAME in the current row of rs
________________________________________
17. How to navigate the ResultSet?
By default the result set cursor points to the row before the first row of the result set. A call to next() retrieves the first result set row. The cursor can also be moved by calling one of the following ResultSet methods:
o beforeFirst(): Default position. Puts cursor before the first row of the result set.
o first(): Puts cursor on the first row of the result set.
o last(): Puts cursor before the last row of the result set.
o afterLast() Puts cursor beyond last row of the result set. Calls to previous moves backwards through the ResultSet.
o absolute(pos): Puts cursor at the row number position where absolute(1) is the first row and absolute(-1) is the last row.
o relative(pos): Puts cursor at a row relative to its current position where relative(1) moves row cursor one row forward.
________________________________________
18. What are the different types of Statements?
0. Statement (use createStatement method)
1. Prepared Statement (Use prepareStatement method)
2. Callable Statement (Use prepareCall)
________________________________________
19. If you want to use the percent sign (%) as the percent sign and not have it interpreted as the SQL wildcard used in SQL LIKE queries, how to do that?
Use escape keyword. For example:
stmt.executeQuery("select tax from sales where tax like '10\%' {escape '\'}");
________________________________________
20. How to escape ' symbol found in the input line?
You may use a method to do so:
static public String escapeLine(String s) {
String retvalue = s;
if (s.indexOf ("'") != -1 ) {
StringBuffer hold = new StringBuffer();
char c;
for(int i=0; i < s.length(); i++ ) {
if ((c=s.charAt(i)) == '\'' ) {
hold.append ("''");
}else {
hold.append(c);
}
}
retvalue = hold.toString();
}
return retvalue;
}
Note that such method can be extended to escape any other characters that the database driver may interprete another way.
________________________________________

Jdbc Interview Questions Part1

2007-10-25T11:09:00.002-07:00

6. What are four types of JDBC driver?
1. Type 1 Drivers
Bridge drivers such as the jdbc-odbc bridge. They rely on an intermediary such as ODBC to transfer the SQL calls to the database and also often rely on native code.
2. Type 2 Drivers
Use the existing database API to communicate with the database on the client. Faster than Type 1, but need native code and require additional permissions to work in an applet. Good for client-side connection.
3. Type 3 Drivers
Call the database API on the server.Flexible. Pure Java and no native code.
4. Type 4 Drivers
The hightest level of driver reimplements the database network API in Java. No native code.
________________________________________
7. What packages are used by JDBC?
There are at least 8 packages:
0. java.sql.Driver
1. Connection
2. Statement
3. PreparedStatement
4. CallableStatement
5. ResultSet
6. ResultSetMetaData
7. DatabaseMetaData
________________________________________
8. There are three basic types of SQL statements, what are they?
0. Statement
1. callableStatement
2. PreparedStatement
________________________________________
9. What are the flow statements of JDBC?
A URL string -->getConnection-->DriverManager-->Driver-->Connection-->Statement-->executeQuery-->ResultSet.
________________________________________
10. What are the steps involved in establishing a connection?
This involves two steps: (1) loading the driver and (2) making the connection.
________________________________________
11. How can you load the drivers?
Loading the driver or drivers you want to use is very simple and involves just one line of code. If, for example, you want to use the JDBC-ODBC Bridge driver, the following code will load it:
Eg.
Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
Your driver documentation will give you the class name to use. For instance, if the class name is jdbc.DriverXYZ , you would load the driver with the following line of code:
E.g.
Class.forName("jdbc.DriverXYZ");
________________________________________
12. What Class.forName will do while loading drivers?
It is used to create an instance of a driver and register it with the DriverManager. When you have loaded a driver, it is available for making a connection with a DBMS.
________________________________________
13. How can you make the connection?
In establishing a connection is to have the appropriate driver connect to the DBMS. The following line of code illustrates the general idea:
E.g.
String url = "jdbc:odbc:Fred";
Connection con = DriverManager.getConnection(url, "Fernanda", "J8");
________________________________________
14. How can you create JDBC statements?
A Statement object is what sends your SQL statement to the DBMS. You simply create a Statement object and then execute it, supplying the appropriate execute method with the SQL statement you want to send. For a SELECT statement, the method to use is executeQuery. For statements that create or modify tables, the method to use is executeUpdate. E.g. It takes an instance of an active connection to create a Statement object. In the following example, we use our Connection object con to create the Statement object stmt :
Statement stmt = con.createStatement();
________________________________________

Jdbc Interview Questions

2007-10-25T11:09:00.001-07:00

1. What is JDBC?
JDBC may stand for Java Database Connectivity. It is also a trade mark. JDBC is a layer of abstraction that allows users to choose between databases. It allows you to change to a different database engine and to write to a single API. JDBC allows you to write database applications in Java without having to concern yourself with the underlying details of a particular database.
________________________________________
2. What are the two major components of JDBC?
One implementation interface for database manufacturers, the other implementation interface for application and applet writers.
________________________________________
3. What is JDBC Driver interface?
The JDBC Driver interface provides vendor-specific implementations of the abstract classes provided by the JDBC API. Each vendors driver must provide implementations of the java.sql.Connection,Statement,PreparedStatement, CallableStatement, ResultSet and Driver.
________________________________________
4. What are the common tasks of JDBC?
o Create an instance of a JDBC driver or load JDBC drivers through jdbc.drivers
o Register a driver
o Specify a database
o Open a database connection
o Submit a query
o Receive results

java Servelet Exampel

2007-10-25T11:05:00.000-07:00

Java Servlets
Java Servlets are server side components that provides a powerful mechanism for developing server side of web application. Earlier CGI was developed to provide server side capabilities to the web applications. Although CGI played a major role in the explosion of the Internet, its performance, scalability and reusability issues make it less than optimal solutions. Java Servlets changes all that. Built from ground up using Sun's write once run anywhere technology java servlets provide excellent framework for server side processing.
With Java servlets web developers can create fast and efficient server side application and can run it on any Servlet enabled web server. Servlets runs entirely inside the Java Virtual Machine. Because the Servlet is running on the server side, it does not depend on browser compatibility. I just sends the result in html formats.
Java Servlets have a number of advantages over CGI and other API's. They are:
1. Platform Independence
Java Servlets are 100% pure Java, so it is platform independence. It can run on any Servlet enabled web server. For example if you develop an web application in windows machine running Java web server. You can easily run the same on apache web server (if Apache Serve is installed) without modification or compilation of code. Platform independency of servlets provide a great advantages over alternatives of servlets.
2. Performance
Due to interpreted nature of java, programs written in java are slow. But the java servlets runs very fast. These are due to the way servlets run on web server. For any program initialization takes significant amount of time. But in case of servlets initialization takes place very first time it receives a request and remains in memory till times out or server shut downs. After servlet is loaded, to handle a new request it simply creates a new thread and runs service method of servlet. In comparison to traditional CGI scripts which creates a new process to serve the request. This intuitive method of servlets could be use to develop high speed data driven web sites.
3. Extensibility
Java Servlets are developed in java which is robust, well-designed and object oriented language which can be extended or polymorphed into new objects. So the java servlets takes all these advantages and can be extended from existing class the provide the ideal solutions.
4. Safety
Java provides a very good safety features like memory management, exception handling etc. Servlets inherits all these features and emerged as a very powerful web server extension.
5. Secure
Servlets are server side components, so it inherits the security provided by the web server. Servlets are also benefited with Java Security Manager.
Java Servlet API Java Servlet API contains two core packages:
• javax.servlet
• javax.servlet.http
Servlets implement the javax.servlet.Servlet interface. The javax.servlet package contains the generic interfaces and classes that are implemented and extended by all servlets. While the javax.servlet.http package contains the classes that are used when developing HTTP - specific servlets. The HttpServlet is extended from GenericServlet base class and it implements the Servlet interface. HttpServlet class provides a framework for handling the HTTP requests.
The javax.servlet.Servlet defines five methods:
1. service() metho called by servlet to handle the client request in a new thead. service() methos accepts ServletRequest and a ServletResponse ohjects as parameters. ServletRequest object represents the client request. It contains the data sent in name/value pairs. ServletResponse object is used to send the response to the client.
2. init() is called once when servlet is loaded. It is a good place to initialize global variables. This methos accepts ServletConfig as parameter which provides initialization arguments for the servlet.
3. getServletConfig() returns the ServletConfig object passed to init().
4. destory() is called when wervlet is unloaded from memory. This is a good place to clean up any resources(such as open files or database connections).
5. getServletInfo() returns a string with version, copyright informations etc.

Installing Servlets The servlet run inside a Web Server program. After it has been compiled, it must be installed onto Web Server in order to test it. Thus we have to follow the following steps:
1. Install the servlet in a hosting server
2. Request the servlet through web browser.
Java servlets are supported by a number of web servers. Java Web Server from JavaSoft was first servlet enabled web server. Now a days a number of web server supports java servlets. In this article we will use Java Web Server, whose evaluation copy can be downloaded from http://jserv.javasoft.com . In order to compile your servlet you also need Java Servlet Development Kit (JSDK) which is available at same place.

Installing on Windows95 and Win NT
1. Download the distribution of Java Web Server from http://www.javasoft.com/products . Distribution is in the form of self-extracting file.
2. The Java Web Server can be installed in any directory, so you can choose your favorite directory for installation. Move the downloaded file into your favorite directory.
3. To begin the installation just double-click on the self-extracting file and the file extract itself and then installation begins.
4. Follow the instruction and complete the installation.
To run the Web Server go to your installation directory and then to bin directory and then double click httpd.exe. To test the Web Server open your browser and type http://localhost:8080 in address bar and then press enter. Browser should display default index.html into browser.