Skip to main content

Interview Experience in a search based tech start up



once  i had an interview with a tech startup;  there were few programming problems; i am sharing one from that interview.

Interview Location :Bangalore
Company: A product based start up that works on search and big data.
Round : 2nd
Level: semi difficult
Program & Algo written on: white board
Problem statement:  
Given an array like
A
B
C
A
A
Z
K
I
A
Z
Sort  the array based on frequency of character, if frequency is same sort them based on ASCII.
{a=4,b=1,c=1,z=2,k=1,i=1}
Out put :

A
A
A
A
Z
Z
B
C
I
K

What i did  during that interview i am writing here:

Algo To solve the problem:
      
      1. Find their frequency  using hashtable.
      2.  Prepare a class with {data : frequency } and put them in a list.
      3. Sort  list using  Collections.sort(); to do that we should  implement comparable interface.
      now prepare an array  using sorted list so that it gives desired output like "AAAAZZBCIK"

 click on the below link:


Next  was a brainstorming  session with lead of the product division to optimize the above program.

Note:

I am  prone to  typo; please report them and I will try to update the posts accordingly.




Labels:

Comments

Post a Comment

Popular posts from this blog

Greedy algorithms for Job Scheduling

In this programming problem and the next you'll code up the greedy algorithms from lecture for minimizing the weighted sum of completion times.. This file describes a set of jobs with positive and integral weights and lengths. It has the format [number_of_jobs] [job_1_weight] [job_1_length] [job_2_weight] [job_2_length] ... For example, the third line of the file is "74 59", indicating that the second job has weight 74 and length 59. You should NOT assume that edge weights or lengths are distinct. Your task in this problem is to run the greedy algorithm that schedules jobs in decreasing order of the difference (weight - length). This algorithm is not always optimal. IMPORTANT: if two jobs have equal difference (weight - length), you should schedule the job with higher weight first. Beware: if you break ties in a different way, you are likely to get the wrong answer. You should report the sum of weighted completion times of the resulting schedule --- a posi
1 comment
Read more
You are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows: If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'. You are not allowed to use any conditional operator (including ternary operator).  Possible Solutions: 1. y = (1 - x) * a + x * b; 2.y = a ^ ((a ^ b) & (x))
Post a Comment
Read more

Anomalies with Double check locking

Already we have a nice article about about problems with double check locking. we will see two nice quick workarounds  and its pros and cons . Double-checked locking: Clever, but broken and Double-Checked Locking is Broken . before getting into solution, classic singleton uses the following signature for get instance:      public static  Resource getResource() {     if (resource == null)       resource = new Resource();     return resource;   } so the above code will only create the new resource object if  no instance of resource is found. This mechanism is  called lazy loading more preciously need based loading we only load resources if and only if it is required. Benefit associated with this approach is performance  improvement, if resource creation is a heavy process and we do not want it to be carried when class is loading t  then this classic approach does make sense. public static synchronized Resource getResource() {     if (resource == null)       resource = n
Post a Comment
Read more