CareerCup

John observers the following while driving to work.

•   4 were driving a red car. 
•   3 were driving a blue car.
•   3 were driving a black car.
He also notices that

•   3 of them were listining to Hip Hop
•   4 of them were listining to pop music.
•   3 of them were listining to Rock.
Additionally he notices that,

•   3 of them reached office before time on Friday.
•   3 of them reached office before time on Tuesday.
•   2 of them reached office before time on Wednesday.
•   2 of them reached office before time on Thursday.
Which of the following practice maximises his chance of getting to office before time.

a) He should drive a red car to work listining to pop music on a friday? 
b) He should drive a blue car to work listining to rock music on a Tuesday.
State how did you calculate the probabiltiy for both in your answer.

A very interesting Question to be done in C or C++ as platform:



Given two input files.
Input file1.csv

Each line in the file describes a websites.
The first field is unique identifier for the site, the second field is the minimum amount in cents, the third field is a string that is the site’s URL:

2181, 320, abc.com
3288, 450, pqr.com
9662, 567, xyz.com
2675, 721, lmn.com
6434, 500, rst.com
8123, 5000, jjj.com
Input file2.csv

Each line in the file describes an ad. The first field is a 32­bit unsigned integer which is the unique identifier for the ad , the second field which is the maximum amount in cents the ad is willing to pay to show on a site, the third field specifies the number of sites the ad wants to display on, followed by the site_ids of the sites.

9822, 450, 3, 2181, 9662, 66434
3421, 897, 3, 2675, 9662, 3288
8961, 342, 1, 9662
7623, 2000, 3, 2181, 2675, 9662

all integr fields are 32­bit unsigned integer
In the above example, ad 9822 is willing to play on 3 sites(abc.com, xyz.com and rst.com) and pay a maximum amount of 450 cents. WAP that decides the appropriate ad by applying the following rules

1. An ad can be shown on this site only if the site is in the list of sites that the ad is interested in.
if no ad id found for a ite, then no ad is returned
2. The ad that is returned is chosen an auction thats is called second price auction. For ads to qualify for the second price auction,
auction for a site their bid_price should be greater than or equal to the reserve_price of the
site. The winner of the auction is the ad that has the maximum bid_price among these ads, and this
winning ad pays the second highest ad’s bid_price. For instance, if two ads with bid_price 500
and 600 are competing for a site that has a reserve_price of 400, then the ad that bid 600 wins,
but pays 500 (the second highest ad’s bid price).

3. In case of a tie between two or more ads, the ad with the lower ad_id wins and pays it’s
bid_price. In case, the auction has only one ad that qualifies, then that ad wins and pays
reserve_price of that site.

4. In case there are no ads that qualify for the auction for a site ­ either because no ad expresses interest
in playing on that site or because none of the ads have bid_price greater than or equal to
reserve_price of that site then no ad is returned.

Your server should accept input file path,first.csv and the second.csv as
arguments and wait for input. The input is the site_id and the adserver should return the ad_id of the ad that wins the second price auction and price the ad pays for the display. An input of ­1 ends the program. example:



$ ./adserver sites.csv ads.csv
2675
7623 897
3288
3421 450
6434
0 0
9999
0 0
8123
0 0
­1
$
DIRECTIONS:
1. The code should compile at least on
http://www.compileonline.com/compile_cpp_online.php
2. Please note that will test your program on larger input files with 20K+ sites and
20K+ ads.
3. You have 1.5 hour to solve the problem, test and submit your solution. Your goal is to provide a working solution at least. You may submit additional code later if you think you can make it work better or faster.


For starters If I were to do this in Java:

Algo:

Step1: I/O

Store both the File Paths from STD IN

Take the SITE_ID as Input Then

Step 2: Pre Processing

Site_Map:

Create a Dictionary/HashMap of All the Site_ID and their Price

Ad_Map:

Create a Dictionary/HashMap of All the Ad_ID and the Ammount they Have

Site_to_Ad Map:

Create a Dictionary/HashMap of All the Site_ID and the Ad_IDs Interested to be on them.

Step 3: Auction Method

Iterate through the Site_to_Ad Map.

Fetch the Amount for Each ad_id from the Ad_Map

Compare it against the min price and if greater store it in a variable along with the ID. Fetch the Next ID and IF it is Higher, Replace and put this value in the variable. If there is a draw, compare the two ap_ids and store the one that has min ad_id value.

If min bid is not reached or if there are no ad_id values for that site, return no ad.

Add Constraints to the Auction block.

I believe in c++ we would use Dictionaries to achive this as we have HashMap in Java, can someone help m with the syntax.

How would you maintain concurrency on a shared page being edited by multiple users simultaneously.
What if the page is being shared using a client- server mechanism. Represent the classes and explain the thread safety mechnism to avoid editing conflicts.

Write a program to traverse and return all nodes of an n-ary tree(note: not a binary tree).

A very interesting question. Still awaiting answer so posting again.

What does this method do?

Stuff is a object in java with two members someStuff and anotherStuff


public static Stuff doSomeStuff (Stuff s0, Stuff s1) {
        Stuff someStuff = s1.getSomeStuff();
        if(someStuff != null){
            s1.setSomeStuff(doSomeStuff(null, someStuff));
        }



if(s1.getAnotherStuff()==null){
s1.setAnotherStuff(s0);
return s1;
} else {
Stuff myStuff = doSomeStuff(s1,s1.getAnotherStuff());
s1.setAnotherStuff(s0);
return myStuff;
}
}

Does it have any bugs or edge cases where it will not execute?
Describe the time complexity of the function and comment on its effectiveness.

While developing a globally distributed web application
that needs to manage time records for system internals
and for end-user usage (e.g. what date/time do i have the appointment?)
what best practices would you implement?
Hints - Server time versus user time. Distributed servers. Several timezones. Daylight savings time etc.

What does this method do?

Stuff is a object in java with two members someStuff and anotherStuff

public static Stuff doSomeStuff (Stuff s0, Stuff s1) {
        Stuff someStuff = s1.getSomeStuff();
        if(someStuff != null){
            s1.setSomeStuff(doSomeStuff(null, someStuff));
        }

        if(s1.getAnotherStuff()==null){
                s1.setAnotherStuff(s0);
                return s1;
        } else {
                Stuff myStuff = doSomeStuff(s1,s1.getAnotherStuff());
                s1.setAnotherStuff(s0);
                return myStuff;
        }
}

What does this method do? Does it have any bugs or edge cases where it will not execute?
Describe the time complexity of the function and comment on its effectiveness.

Here is a good one i recently came accorss.
Really appreciate if someone could help me code this in Java

Print elements of a n-ary tree(a tree which may have more than two elements per node) breadth first reverse starting with the last level
nodes and up. The code need to fit the following method and interface.

method name: void displayBFSReverse (Node head);

Where Node implements the interface:

interface Node {

public String getNodeData ();

public List<Node> getChildren ();

}


The Tree Structure is

34
                     /         |        \
                    3          56        12
             /         \                  |
          89            7               22
                                          |
                                         78

reverse in BFS and return should return



78 22 7 89 12 56 3 34

Here is a good one i recently came accorss.
Really appriciate if someone could help me code this in Java


The Tree Structure is

34
                       /       |      \
                    3        56      12
                  /    \                |
               89       7             22
                                        |
                                       78

Print elements of a n-ary tree(a tree which may have more than two elements) breadth first reverse starting with the last level
nodes and up. The code need to fit the following method and interface.

method name: void displayBFSReverse (Node head);

Where Node implements the interface:

interface Node {

public String getNodeData ();

public List<Node> getChildren ();

}

The function should return:
78 22 7 89 12 56 3 34

I was given a very interesting question.
You are given two very large files each containing integers in each line followed by a line break.

Produce a file with integers that are common in both files.

Estimate the time complexity of your code block?

Any edge cases and Bottlenecks?

Assumptions?
How would you solve this.

I did a little research on this and saw that some people suggested using Radix Sort for this and trying to split on large file into subsets and then using radix sort.

Here is the link

http://stackoverflow.com/questions/6520954/produce-a-file-that-has-integers-common-to-two-large-files-containing-integers

Can someone help me write this function. I read a lot of theories a lot of places but I am really looking for a code, preferably java for this.

This is a simple implementation of the same. I got a clarification that numbers are integers but the files are large but on one disk only.

I am using an approach as In case the file is too big to fit into memory on one go, break it into parts or read n integers at a time.and then use hashmaps to look for integers.

Cpmplexity: If the partition size is p and the file size is m then and no of rows per partition in n then ----- O(m/p * n) or O(N).

import java.io.*;
import java.util.*;
import java.io.FileWriter;

public class FileRead{

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
   
    File file1 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input1.txt");   
    File file2 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input2.txt");
    try{
       
    Map mymap = new HashMap();
    Scanner scan1 = new Scanner(file1);
    Scanner scan2 = new Scanner(file2);
    
    
    
    while(scan1.hasNextLine(    ))
    {
        int line = scan1.nextInt();
        mymap.put(line,1);
    }
   
    while(scan2.hasNextLine())
    {
        int line = scan2.nextInt();
        try{
        int val = (Integer) mymap.get(line);
             if(val==1)
            
             try{
                    FileWriter f1 = new FileWriter("C:\\Documents and Settings\\chaos\\Desktop\\output.txt");
                    BufferedWriter out = new BufferedWriter(f1);
                    out.write(line);
                    System.out.println(line);
                    }catch (IOException e){}
             
        }catch(NullPointerException e2){}
    
    }
    } catch(FileNotFoundException e){e.printStackTrace();}
    
    }

}

Reverse K elements of a linked list.
Solved on 31st May.
It still has one bug, if the number of elements in a linked list are not a multiple of K, then it truncates the linked list at a multiple of K.
1->2->3->4->5->6 becomes
3->2->1->6->5->4 for K=3

Eg. if K=5 and number of elements is 12, it will reverse till 10 th element and then truncate it. so when the reversed list is printed, only 10 elemtns with every 5 revesed is shown, need to fix this.

package ThreadPkg;

import java.util.*;

class link
{
    int data;
    public link nextlink;
    link(int d1)
    {
        data = d1;
    }}

class List{
    
    link head;
    static int rev;
    link revhead;
    List(){
    head = null;
    Scanner scan1 = new Scanner(System.in);
    rev = scan1.nextInt();
   }

    
    boolean isEmpty(link head)
    {
        return head==null;
    }
    
    void insert(int d1)
    {
        link templink = new link(d1);
        templink.nextlink = head;
        head = templink;
    }
    
    void printlist(){
        link head1 = head;
        while(!isEmpty(head1))
            {
            System.out.print(head1.data + " ");
            head1 = head1.nextlink;
            }
        System.out.println();
            }

    void reverse()
    {
        boolean flag=true;
        revhead = head;
        link previous=revhead,temp=null,temp2=null;int i=1;
        while(true)
    {
     i++;
        
    for(int j=0;j<(2*rev-1);j++)
    {
        if(isEmpty(previous))
        {
     // 	previous=temp2;
        	break;
        }
        temp2=previous;
        previous=previous.nextlink;
        
    }
        
            for(int k=0;k<rev;k++)
            {
       if(isEmpty(revhead))
        {
            return;
        }
             
        		temp = revhead.nextlink;
                revhead.nextlink = previous;
                previous = revhead;
                revhead = temp;
            }
            
        if(flag){
            head=previous;
        flag=false;
        }
         previous=temp;
        }
       
    }
    }

class RevKLinkedList {

    public static void main(String[] args) {
        
        
    	List list1 = new List();
        
        list1.insert(10);
        list1.insert(20);
        list1.insert(30);
        list1.insert(40);
        list1.insert(50);
        list1.insert(60);
        list1.insert(70);
        list1.insert(80);
        list1.insert(90);
        list1.insert(100);
        list1.insert(110);
        list1.insert(120);
        list1.printlist();
        list1.reverse();
        list1.printlist();
        }
}

Reverse K elements of a linked list.
Solved on 31st May.
It still has one bug, if the number of elements in a linked list are not a multiple of K, then it truncates the linked list at a multiple of K.
Eg. if K=5 and number of elements is 12, it will reverse till 10 th element and then truncate it. so when the reversed list is printed, only 10 elemtns with ever 5 revesed is shown, need to fix this.

import java.util.*;

class link
{
    int data;
    public link nextlink;
    link(int d1)
    {
        data = d1;
    }}

class List{
    
    link head;
    static int rev;
    link revhead;
    List(){
    head = null;
    Scanner scan1 = new Scanner(System.in);
    rev = scan1.nextInt();
   }

    
    boolean isEmpty(link head)
    {
        return head==null;
    }
    
    void insert(int d1)
    {
        link templink = new link(d1);
        templink.nextlink = head;
        head = templink;
    }
    
    void printlist(){
        link head1 = head;
        while(!isEmpty(head1))
            {
            System.out.print(head1.data + " ");
            head1 = head1.nextlink;
            }
        System.out.println();
            }

    void reverse()
    {
        boolean flag=true;
        revhead = head;
        link previous=revhead,temp=null,temp2=null;int i=1;
        while(true)
    {
     i++;
        
    for(int j=0;j<(2*rev-1);j++)
    {
        if(isEmpty(previous))
        {
     // 	previous=temp2;
        	break;
        }
        temp2=previous;
        previous=previous.nextlink;
        
    }
        
            for(int k=0;k<rev;k++)
            {
       if(isEmpty(revhead))
        {
            return;
        }
             
        		temp = revhead.nextlink;
                revhead.nextlink = previous;
                previous = revhead;
                revhead = temp;
            }
            
        if(flag){
            head=previous;
        flag=false;
        }
         previous=temp;
        }
       
    }
    }

class RevKLinkedList {

    public static void main(String[] args) {
        
        
    	List list1 = new List();
        
        list1.insert(10);
        list1.insert(20);
        list1.insert(30);
        list1.insert(40);
        list1.insert(50);
        list1.insert(60);
        list1.insert(70);
        list1.insert(80);
        list1.insert(90);
        list1.insert(100);
        list1.insert(110);
        list1.insert(120);
        list1.printlist();
        list1.reverse();
        list1.printlist();
        }
}

Q1: Reverse a linked list without using recursion.
1->2->3->4->5->6
should become
6->5->4->3->2->1

Q2: Then reverse every K elements of a linked list.
1->2->3->4->5->6
should become
3->2->1->6->5->4
for k=3

Ans1: I used this method, but when i try and run this back home, I am not able to print the reverse of the linked list even though the function looks good.
It goes on to print the linked list in the same way as it did earlier. (Now Solved)

Can someone help me understand what is wrong here.
//Figured out the error, look at the correction in comments below//

Ans 2: Working on it (Not Solved)

//Reverse a linked list without recursion.
class link
{
	int data;
	public link nextlink;
	
	link(int d1)
	{
		data = d1;
	}
}

class List{
	
	link head;
	link revhead;
	List(){
	head = null;
	}
	
	boolean isEmpty(link head)
	{
		return head==null;
	}
	
	void insert(int d1)
	{
		link templink = new link(d1);
		templink.nextlink = head;
		head = templink;
	}
	
	void printlist(){
		link head1 = head;
		while(!isEmpty(head1))
			{
			System.out.print(head1.data + " ");
			head1 = head1.nextlink;
			}
		System.out.println();
			}
	
	void reverse()
	{
		link previous=null,temp=null;
		while(isEmpty(head))
		{
			temp = head.nextlink;
			head.nextlink = previous;
			previous = head;
			head = temp;
		}
	
		}

}



public class LinkedList {

	public static void main(String[] args) {
		
		List list1 = new List();
		
		list1.insert(10);
		list1.insert(20);
		list1.insert(30);
		list1.insert(40);
		list1.insert(50);
		list1.printlist();
		list1.reverse();
		list1.printlist();
		}

}

Can someone Please help.


You need to write a code to Reverse a n-ary tree a return the leaf nodes. The given Input is the root node only. Code in Java using List.