Most Recent

TCS Codevita Round 2 Question : Collecting Candies (Answer)


Statement

Krishna loves candies a lot, so whenever he gets them, he stores them so that he can eat them later whenever he wants to.

He has recently received N boxes of candies each containing Ci candies where Ci represents the total number of candies in the ith box. Krishna wants to store them in a single box. The only constraint is that he can choose any two boxes and store their joint contents in an empty box only. Assume that there are infinite number of empty boxes available.

At a time he can pick up any two boxes for transferring and if both the boxes say contain X and Y number of candies respectively, then it takes him exactly X+Y seconds of time. As he is to eager to collect all of them he has approached you to tell him the minimum time in which all the candies can be collected.
Input Format:
  1. First line of input is number of test case T
  2. Each test case is comprised of two inputs
    1. First input of a test case is the number of boxes N
    2. Second input is N integers delimited by whitespace denoting number of candies in each box

Output Format:

Print minimum time required, in seconds, for each of the test case. Print each output on a new line.
Constraints:
  1. 1 ≤T≤10
  2. 1 ≤N≤ 10000
  3. 1 ≤ [Candies in each box] ≤ 100009

Sample Input and Output
SNo.InputOutputExplanation

1

1
4
1 2 3 4

19

4 boxes, each containing 1, 2, 3 and 4 candies respectively.
Adding 1 + 2 in a new box takes 3 seconds
Adding 3 + 3 in a new box takes 6 seconds
Adding 4 + 6 in a new box takes 10 seconds
Hence total time taken is 19 seconds. There could be other combinations also, but overall time does not go below 19 seconds.

2

1
5
1 2 3 4 5

33

5 boxes, each containing 1, 2, 3, 4 and 5 candies respectively.
Adding 1 + 2 in a new box takes 3 seconds
Adding 3 + 3 in a new box takes 6 seconds
Adding 4 + 5 in a new box takes 9 seconds
Adding 6 + 9 in a new box takes 15 seconds
Hence total time taken is 33 seconds. There could be other combinations also, but overall time does not go below 33 seconds.

                                                ANSWER HERE or In comment Box

Hardip Parmar
TCS Codevita Round 2 Question : Mate In Two (Answer)
Background

A Chess board position is accurately captured by Forsyth-Edwards notation and is abbreviated as FEN. A FEN "record" defines a particular game position, all in one line of text and using only the ASCII character set. A FEN record consists of six fields. A complete description of the FEN format to represent Chess positions can be found here

For the purpose of this problem, only consider first of the six fields of FEN. Before we describe the problem, let us look at how FEN maps to a board position. The following 5 images show board positions and its corresponding FEN representation.

                    Figure 1.




This board position depicts initial position before any side has made a move. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR








Let's say, White plays e4. Then the board position looks like shown below


                    Figure 2.




This board position depicts the Chess board after White has played e4. In FEN format this board position is represented as


rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR








Similarly, 3 more half-moves are depicted in following diagrams


Figure 3.Figure 4.Figure 5.



The FENs corresponding to Figure 3, 4 and 5 are represented as

           3. rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
           4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR
           5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR

Wikipedia describes first field of FEN format as follows

Piece placement (from white's perspective). Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks

Statement

Given a board position in FEN format, your task is to find out all move(s) that lead to a forced mate. White to play and win in 2 moves.


Input Format:
  1. First line contains single FEN record, which corresponds to a particular board position


Output Format:
  1. The output must be printed as follows
    1. A string in format by "< move format >-< move format >-< move format >", where first move is white move, second is black move and third is again a white move
    2. Where < move format > is move represented in format "fromSquaretoSquare"
  2. See Example section for better understanding of output format


Constraints:
  1. The board position will always be White to move and mate in 2
  2. Since we focus on only first part of the FEN, we are essentially ignoring possibility of Castling being a mating move. Hence our test cases don't contain FENs which give rise to such positions.
  3. There is no need to handle En Passant positions. There are no test cases involving En Passant moves.
  4. No need to implement pawn promotion rules. Our test cases do not contain positions which will lead to a pawn getting promoted and inflicting a mate.
  5. There is exactly one forced mating sequence in our test cases. So once a forced mating sequence is found, there is no need to process further.


Sample Input and Output

SNo.InputOutput
1
r1b2rk1/1p4pR/p2pppn1/6q1/3NP1P1/2N2P2/PPP4Q/1K5R

h7g7-g8g7-h2h7
2
5r1k/p4p1p/5P1N/1p1p4/2pP3P/8/PP4RK/8

g2g8-f8g8-h6f7


Explanation:

Board position for sample input 1: 


                    Figure 6.
Mate enforcing moves for input 1: 


                    Figure 7. 
Board position for sample input 2:                           


                    Figure 8.



Mate enforcing moves for input 2: 


                    Figure 9

ANSWER HERE or In comment Box

Hardip Parmar
TCS Codevita Round 2 Question : Decrypt the Crypt (Answer)
Statement

Walter uses multiple applications at his workplace. He was assigned a unique password of variable lengths for each application (maximum length being 10). The only common factor among them was that all the passwords were a combination of 10 distinct characters. Walter created an algorithm to encrypt these passwords and wrote the codes on his desk to avoid a situation in which he would not be able to recollect a password.

Given as an input, is an encoded password and a list of 10 unique characters. Write a program that obtains the password by reverting the algorithm used by Walter.

Algorithm used by Walter to encode his password is as follows:
  1. Walter observes all his passwords and lists down every distinct character. He assigns an index value to each character from 0 to 9. (Note: This list will be provided as an input to the program). This list MUST contain 10 DISTINCT characters.
  2. He then replaces every character in the password with the corresponding index value to convert the password to a 10 digit numeric value.
  3. The leftmost digit in this number sequence is noted; let's say 'A'. Now, starting from the leftmost position, every digit in the number is added to the digit on its right. The last digit in the sequence is added to 'A'.
  4. Step 3 provides new sequences of numbers. He then scans through each of the summations and if any of the summation results in a value greater than 9, it is subtracted by 10, and its position is noted (Say B).
  5. He then lists every digit from 0 to 9 separated by '|' character and prepends each digit with its position in the sequence as noted in 'B'. The resulting sequence after this step is saved (Say C).
  6. The encoded password would therefore be 
    < value_of_C >||< contents_of_array_B  > < Value_of_A >

Decrypt the encrypted password that has been created by Walter using the above algorithm to compute the actual password! 

Print -1 if there is any error in the inputs. 

Input Format:
  1. First line contains the encoded password as it should be according to Walter's algorithm
  2. Second line contains 10 unique characters


Output Format:

Obtained password by reverting the algorithm. Print -1 if there is any error in the inputs.
Constraints: 
  1. Second line of input MUST contain 10 DISTINCT characters.
  2. Encoded password should be in format 
    < value_of_C >|| < contents_of_array_B >


Sample Input and Output
SNo.InputOutput
1
0|1|2|43|14|5|6|7|308|29||0149
*Acf$Zd&T@ 

@@Z$$ 
2
0|1|2|43|14|5|6|7|308|29||0149
*Acf$Zd&T 

-1

Explanation of Test Case 1:

NOTE: - The following are the steps used to encrypt the password. Your task is to reverse the logic and decrypt the encrypted string provided as input, and get back the clear-text password.
  1. Consider input characters and its position
    Input character list:*Acf$Zd&T@
    Position:0 1 2 3 4 5 6 7 8 9

    (Note: The character list will not contain more than 10 characters and each character must be unique)
  2. Now replace the characters in the password with the position value of the respective character as defined in step 1, to convert the password into a numeric value.
    Password:@@Z$$
    Numeric value:9 9 5 4 4

    (Note: Remember leftmost value (Say A) = 9)
  3. Starting from the left most position, add each digit to the digit on its right. Add the last digit with the first digit in the sequence
    Numeric value of password
    Addition
    :
    :
    995 4 4
    18149813

  4. For each addition result equal to or greater than 10, subtract it by 10 and note its position.
    Additive step output
    Selective subtraction
    Numeric value
    :
    :
    :
    18 14 13
    84983
    014

    (Note: Remember the selective subtraction step positions obtained (Say B) = 014)
  5. The password will follow the following format
    Format:0|1|2|3|4|5|6|7|8|9
  6. Now, each number in this format is pre-appended with the positions of the occurrence of the respective number in the output obtained in selective subtraction step of Step 4.
    Encrypted password:0|1|2|43|14|5|6|7|038|29

    (Note: Say C = 0|1|2|43|14|5|6|7|038|29)
  7. The final encrypted password will be of the following format to account for the calculations performed in generating the encrypted password
    Encrypted password (format):< C >||< B >< A >
    Encrypted password:0|1|2|43|14|5|6|7|308|29||0149


Explanation of Test Case 2:

Second line of input contains 9 characters only hence prints -1


                               ANSWER HERE or In comment Box

Hardip Parmar
TCS Codevita Round 2 Question : Crack the Password (Answer)
Statement

Atul does lots of online transactions and has accounts in multiple banks, but to remember his passwords he created his own encryption technique and wrote down the enciphered passwords in a notepad. But he finds it very time consuming to decipher those passwords so he has asked for your help to develop a program to do the task quickly.

The approach he takes to encipher is,
  1. First he writes down his password in a square matrix P of dimension N, sequentially from the first element (see example for better explanation). He chooses N such that N^2 is the least number above the length of the password. He then starts filling the matrix row-wise from top to bottom. If any matrix element remains blank, he fills all those blanks with the last element e.g. if the last element filled is z then he fills all other remaining elements in the matrix by z .
  2. Then he creates new matrix A of the same dimensions such that every A(i,j) = P(j,i). Next he assigns the value of the alphabet in the password to that corresponding element in the matrix. So 'a' is substituted by 1, 'b' by 2, so on. Alphabets are only lower case. Also passwords contain characters from a to z only.
  3. Then he finds another matrix B such that, the solution to the following equation gives a matrix with all the elements of principal diagonal as 1 and rest as 0, which is also called the eMat( encrypted matrix ) .

Your are provided with the eMat (encrypted matrix) or the matrix B, your task is to find all possible passwords and print them. 

Example:
Let the password be "passwords" as it has 9 characters , the most appropriate matrix will be a 3X3 matrix, hence the matrix will be 

After Step 1: 

After step 2: 

After step 3: 

The eMat for the given matrix will be 

-0.783783783780.189189189190.70270270270
-0.118503118500.079002079000.09563409563
0.87733887734-0.25155925156-0.72557172557


Input Format:
  1. First line contains integer N, which is the dimension of square matrix eMat
  2. Next N lines contain N space separated values (11-digit precision after decimal point) representing the eMat.


Output Format:


In a single line print the password, if multiple password values are possible print them separated by space, sorted by ascending order of their lengths.
Constraints:
  1. When eMat is converted to Matrix A, round off the numbers in the matrix A to its nearest integer value to recover the alphabets in the password

Sample Input and Output
SNo.InputOutput

1

3
-0.78378378378 0.18918918919 0.70270270270
-0.11850311850 0.07900207900 0.09563409563
0.87733887734 -0.25155925156 -0.72557172557 

passwords

2

2
0.06666666667 -0.06666666667
-0.00350877193 0.05614035088 

pas pass
                                          ANSWER HERE or In comment Box

Hardip Parmar
TCS Codevita Round 2 Question : Verify JSON Object validity (Answer)

Problem : Verify JSON Object validity



Statement

A JSON object is a key-value pair data structure that is enclosed within { }. A sample JSON object would look like
{
"key1":"value1",
"key2":"value2",
"key3": {
"key4":"value4",
"key5":"value5"}
"key6":"value6",
"key7":[
{
"key8":"value8"
}]
}

Given a JSON object, ignore the literal values of the object and check whether the distinguishing characters and notation of the object are valid to determine if the JSON object is valid or not.

Note:
  1. Key3 points to another JSON object (Concept of nesting of JSON objects).
  2. Key7 points to an array of JSON objects.
You may wish to refer site1 to get a more formal description of JSON grammar. site2,site3; are also good resources to understand JSON specifications. 

Input Format:
  1. First line contains a pattern of JSON without any literal

Output Format:

Print 1 if pattern is valid, -1 otherwise.
Constraints:
  1. A JSON object should start with '{' and ends with a '}'.
  2. The key and value should be separated by a ':'.
  3. A ',' suggests an additional JSON property.
  4. An array only consists of JSON objects. It cannot contain a "key":"value" pair by itself.

Example 1:

Input
{:[{},{}]}

Output
1

Explanation
{
"Key": [{
"Key": "Value"
}, {
"Key": "Value"
}]
}
Pattern is following all constraints hence prints 1
Example 2:

Input
{:{[]},{}}

Output
-1

Explanation
Convert this pattern in a JSON Object

{
"Key": {
[
"Key": "Value"
]
},
{
"Key": "Value"
}
}

Constraint 4 "An array only consists of JSON objects. It cannot contain a "key":"value" pair by itself." not followed here, so it's a invalid pattern, hence prints -1

                                         ANSWER HERE or In Comment Box

Hardip Parmar
TCS Codevita Round 2 Question : The Mystery Of Sky (Answer)
Stark is a 10 year old kid and he loves stars. So, he decided every day he will capture a picture of a sky. After doing this for many days he found very interesting observations.

Every day the total number of stars in the sky is same as days completed for a calendar year. He noticed, on Saturday's and Sunday's that there are no stars in the sky. Stark's camera does not have wide angle capture feature so he could only capture maximum of 50 stars at a time. So, he assumed that there are only 50 stars in the sky that day. Also, the camera discharges every 4th day and he is not be able to click any picture that day. So let's say, if the first day of calendar (01/01/0001) starts on a Monday then on Thursday he can't click any pictures. Then resuming on Friday he can take pictures until Sunday, but can't take picture on Monday, followed by downtime on Friday, then Tuesday, then Saturday etc. When the camera discharges he considers 0 stars that day.



You are his programmer friend and want to help him. You need to write a code which will tell him on a particular date how many stars Stark's camera was able to click.

You can assume Stark has an ancient camera and your first input will be the day for date (01/01/0001) and then followed by any date on which Stark wants to find out the number of stars in the sky.
Input Format:

Every line of input will contain a Day at date 01/01/0001 in dd/mm/yyyy format followed by a Date in the same format (on which we have to count the stars)
Output Format:
For valid Input
Count of the number of stars in the sky on the given date

For Invalid Input
Print "Invalid Date" for invalid date

Print "Invalid Day" for invalid day
Sample Input and Output

SNo.InputOutputExplanation
1
Monday
30/02/1990

Invalid Date

2
Thursday

Invalid Day 

3
Wednesday
24/01/2056 

24

Its 24th day of the year and neither is Saturday/Sunday nor has the camera discharged on this day.



                                          ANSWER HERE or In comment Box








Hardip Parmar
.NET framework with comparison of various framework versions | HackHackers

Version
Version Number
Release Date
Visual Studio
Default in Windows
Add??
1.0.3705.0
2002-02-13
Visual Studio .NET 2002(1st release)
Windows XP Tablet and Media Center Editions

1.1.4322.573
2003-04-24
Visual Studio .NET 2003
Provider for Oracle
2.0.50727.42
2005-11-07
Visual Studio 2005
Generic were introduced
3.0.4506.30
2006-11-06
Visual Studio 2006
WPF,WCF,WF were introduced
3.5.21022.8
2007-11-19
Visual Studio 2008
LINQ & ADO.NET Entity Framework
4.0.30319.1
2010-04-12
Visual Studio 2010
Dynamic keyword introduced along with Task Parallel Library(TPL)
4.5.50709
2012-08-15
Visual Studio 2012
Asynchronous Programming support
4.5.1
2013-10-17
Visual Studio
2013
Windows Vista SP2, Windows 8, Windows Server 2012 R2




.NET Framework Version 2.0
Ø  Generic.
Ø  Anonymous Methods.
Ø  Partial class.
Ø  Nullable type.
Ø  The new API gives a fine grain control on the behaviour of the runtime with regards to multithreading
Ø  Memory allocation.
Ø  Assembly loading &more full 64-bit support for both the x64 & the IA64 hardware platforms.
Ø  New personalization features for ASP.NET such as supports for themes, skins&web parts.

.NET Framework Version3.0
Also called WinFX,includes a new set of managed code APIs that are an integral part of Windows Vista & Windows server 2008operating system.

Ø  Windows CommunicationFoundation (WCF) formally called Indigo.
Ø  A service oriented messaging system which allows programs to interoperate locally or remotely similar to web services.
Ø  Windows Presentation Foundation (WPF), formally called Avalon; a new user interface subsystem & API based onXML & vector graphics, which uses 3D computer graphics hardware & direct 3D technologies.
Ø  Windows workflow foundation (WF) allows for building of task automation & integrated transactions  using workflows.
Ø  Windows card space,formally called Info Card; a software component which securely stores a person’s digital identity for a particular transaction,such as logging in to a website.

.NET Framework Version 3.5
It implements Linq evolution in language. So we have the following evolution in class:

Ø  Linq for SQL,XML,Dataset,Object.
Ø  Addin System.
Ø  P2p base class.
Ø  Active directory.
Ø  ASP.NET Ajax.
Ø  Anonymous types with static type inference.
Ø  Paging support for ADO.NET.
Ø  ADO.NET synchronization API to synchronize local caches &server side data stores.
Ø  Support for HTTP pipelining & syndication feeds.
Ø  New system.CodeDom namespace.



.NET FrameworkVersion 4.0
.NET Framework 4.0 comes up with some of major changes as compare to previous versions of .Net Framework 3.5 & 2.0.
Following are list of major changes in .Net 4.0.

Ø  ControlRenderingCompatabilityVersion.
Ø  Setting in the Web.config File.
Ø  ClientIDMode Changes.
Ø  HTMLEncode &URLEncode now encode single quotation marks.
Ø  ASP.NETpage parser is stricter.
Ø  Browser Definition Files Updated.
Ø  System.Web.Mobile.dll Removed from Root.
Ø  Web Configuration File.
Ø  ASP.NET Request Validation.
Ø  Default Hashing Algorithm Is Now HMACSHA256.
Ø  Configuration Errors Related to New.
Ø  ASP.NET 4 Root Configurations.
Ø  ASP.NET 2.0 Application Might Generate HTTP Exception Errors that Reference eurl.axd.
Ø  Event Handlers Might not be not raised in a default document in IIS 7 OR IIS 7.5.
Ø  Integrated mode changes to the ASP.NET.  
Ø  Code Access Security (CAS) ImplementationMembership User& other Types in the System.Web.Security Namespace have been moved.
Ø  Output Caching Changes to very *HTTP Header.
Ø  System.Web.Security types for passport are Obsolete.
Ø  The MenuItem.PopOutImageUrl Property.
Ø  Fails to Reader an Image in ASP.NET 4.
Ø  Menu.StaticPopOutImageUrl & Menu.DnamicPopOutImageUrl Fail to Reader Images When Paths Contain Backslashes.




.NET Framework Version Comparision Table .

Version No.
Release Date
Visual Studio Version
Default in Windows
CLR Version
Features in Release
1.0
13 Feb 2002
Visual Studio .NET
NA
1.0
First Version of CLR and Base Class Library
1.1
24 Apr 2003
Visual Studio 2003
Windows Server 2003
1.1
1. First Major version of .NET Framework

2. Built-in support for mobile ASP.NET controls. Previously available as an add-on for .NET Framework, now part of the framework

3. Security changes – enable Windows Forms assemblies to execute in a semi-trusted manner from the Internet, and enable Code Access Security in ASP.NET applications

4. Built-in support for ODBC and Oracle databases. Previously available as an add-on for .NET Framework 1.0, now part of the framework

5. .NET Compact Framework – a version of the .NET Framework for small devices

6. Internet Protocol version 6 (ipv6) support
2.0
7 Nov 2005
Visual Studio 2005
Windows Server 2003 R2
2.0
1.  Generics

2.  Language support for generics built directly into the .NET CLR

3.  Full 64-bit support for both the x64 and the IA-64 hardware platforms

4.  SQL Server integration – .NET 2.0, VS 2005, and SQL Server 2005 are all tied together. This means that instead of using T-SQL, one can build stored procedures and triggers in any of the .NET-compatible languages

5.  A new hosting API for native applications wishing to host an instance of the .NET runtime. The new API gives a fine grain control on the behavior of the runtime with regards to multithreading, memory allocation, assembly loading and more

6.  Many additional and improved ASP.NET web controls

7.  New data controls with declarative data binding

8.  New personalization features for ASP.NET, such as support for themes, skins, master pages and webparts

9.  .NET Micro Framework – a version of the .NET Framework related to the Smart Personal Objects Technology initiative

10. Membership provider

11. Partial classes

12. Nullable types

13. Anonymous methods

14. Iterators

15. Data tables
3.0
6 Nov 2006
Visual Studio 2005
Windows Vista, Windows Server 2008
2.0
1. Windows Presentation Foundation (WPF), a new user interface subsystem and API based on XML and vector graphics, which uses 3D computer graphics hardware and Direct3D technologies

2. Windows Communication Foundation (WCF), a service-oriented messaging system which allows programs to interoperate locally or remotely similar to web services

3. Windows Workflow Foundation (WF) allows for building of task automation and integrated transactions using workflows

4. Windows cardspace, a software component which securely stores a person’s digital identities and provides a unified interface for choosing the identity for a particular transaction, such as logging in to a website
3.5
19 Nov 2007
Visual Studio 2008
Windows 7, Windows Server 2008 R2
2.0
1. Added new features such as AJAX-enabled Web sites and LINQ

2. The SP1 update added

    2.1. .NET Framework Client Profile

    2.2. Dynamic Data

    2.3. Two new data service components added, ADO.NET Entity Framework and ADO.NET Data Services

    2.4. Two new assemblies for web development, System.Web.Abstraction and System.Web.Routing

    2.5. New set of controls “Visual Basic Power Packs” introduced
4.0
12 Apr 2010
Visual Studio 2010
NA
4.0
1. New Version of CLR

2. Parallel Extensions to improve support for parallel computing, which target multi-core or distributed systems. To this end, technologies like PLINQ (Parallel LINQ), a parallel implementation of the LINQ engine, and Task Parallel Library, which exposes parallel constructs via method calls are included

3. New Visual Basic .NET and C# language features, such as implicit line continuations, dynamic dispatch, named parameters, and optional parameters

4. Code Contracts

5. Inclusion of new types to work with arbitrary-precision arithmetic (System.Numerics.biginteger) and complex numbers (System.Numerics.Complex)

6. Dynamic Language Runtime (DLR)

7. Managed Extensibility Framework (MEF)

8. Windows Server appfabric for application server capabilities in the form of appfabric hosting and in-memory distributed caching support
   4.5
17 oct 2013
Visual Studio 2013
Windows 8.1,Windows server 2012 R2
4.5.1
1. X64 edit and continue is now possible (with some restrictions, but now X86 and X64 are nearly handled the same, which is good news)
2. Async/Await debugging has been added (such as support in the Call Stack window, Tasks window, etc…)
3. Managed return value inspection has been added (in the Autos and Watch windows it allows for easier return value debugging)
4.  Windows Store application development improvements (compatibility with Windows 8.1, Win RT improvements, etc…)
5.  ADO.NET idle connection resiliency has been added (rebuild broken idle connections with SQL databases automatically and transparently)
6. ASP.NET application suspension has been added (Idle sites are suspended from CPU activity and are paged to disk)
7.  On-demand large object heap compaction (instruct the Garbage Collector to compact the large object heap, as part of the natural GC or a forced GC)
8. Multi-core JIT improvements (support for dynamically loaded assemblies)
9.Consistent performance after .NET Framework updates (application startup performance will be more consistent after a .NET Framework update)

Hardip Parmar