Elevator Interview Problem OOP - Revised Elevator program code challenge, revised:

Can someone please critique my Elevator problem - I wanted to use OOP principles and coding standards. Also, does logic make sense?

internal enum Status
{
    GoingUp,
    GoingDown,
    Stopped
}

internal class Elevator
{
    private readonly SortedList<int, bool> _sorted = new SortedList<int, bool>();
    public readonly int TopFloor;

    public Elevator(int topFloor)
    {
        TopFloor = topFloor;
    }

    public int CurrentFloor { get; set; } = 1;
    public Status Status { get; set; } = Status.Stopped;

    public void AddRequest(int floor)
    {
        if (!_sorted.ContainsKey(floor))
            _sorted.Add(floor, false);

        switch (Status) {
            case Status.GoingDown:
                MoveDown();
                break;

            case Status.Stopped:
                if (CurrentFloor < floor)
                    MoveUp();
                else
                    MoveDown();
                break;

            case Status.GoingUp:
                MoveUp();
                break;

            default:
                break;
        }
    }

    public void MoveUp()
    {
        var max = _sorted.OrderByDescending(x => x.Key).First();
        for (var i = CurrentFloor; i <= max.Key; i++) // Go to top most requested floor
            if (_sorted.ContainsKey(i))
                Stop(i);
            else
                continue;

        Status = Status.Stopped;
    }

    public void MoveDown()
    {
        var min = _sorted.OrderBy(x => x.Key).First();
        for (var i = CurrentFloor; i >= min.Key; i--)
            if (_sorted.ContainsKey(i))
                Stop(i);
            else
                continue;

        Status = Status.Stopped;
    }

    public void Stop(int floor)
    {
        _sorted.Remove(floor);
        CurrentFloor = floor;
        Console.WriteLine("Stopped at: {0}", CurrentFloor);
    }
}

internal class Manager
{
    private readonly Elevator _elevator = new Elevator(10);

    public void ButtonPressed(int floor)
    {
         // testing...
        _elevator.AddRequest(10);
        _elevator.AddRequest(10);
        _elevator.AddRequest(5);
        _elevator.AddRequest(2);
        _elevator.AddRequest(9);
        _elevator.AddRequest(6);
    }
}

Elevator program code challenge, revised:

where is that?

_sorted is a very very bad name. I have to read all the code to figure out exactly what that is.

public void AddRequest(int floor)

Rename the parameter to something like requestedFloor
Rename the method to something like CallElevator or RequestFloor

Does not account for which floor a call is coming from. I think it would matter if the elevator passing 2nd floor for the 7th, then a request comes for the 5th - originating from the 1st floor.

Looks like the code throws away requests for floors already in the list. But if I'm on the 1st floor asking for the 5th, why ignore my request just because the elevator is carrying someone to 5 already?

Fuzzy code

It is hard to tell exactly what the elevator logic is. And harder to tell if it meets requirements.

var min = _sorted.OrderBy(x => x.Key).First();

Clever but not clear. What is the elevator doing? What is the floor-stop choosing logic? This is "the bowels of the code" exposed at the highest logic level. I should be reading what the elevator is doing, not googling MSDN.

public int CurrentFloor { get; set; } = 1;
public Status Status { get; set; } = Status.Stopped;

Why are these public? In principle a well made OO class hides state and exposes functionality.

case Status.Stopped:
    if (CurrentFloor < floor)
        MoveUp();
    else
        MoveDown();
    break;

Flawed logic. If the floor (requested floor?) is the same as the current floor, the elevator goes down. Even if this code works is not the point. I should not have to use a debugger to know if the code covers edge cases.

P.S. what happens when we're on the 1st floor? Does it still go down?

Two collections makes sense: a queue of floor requests and an ordered list of floors the elevator is traversing. This fundamentally decouples two things that should not be conflated, but are so in this code.

Edit

Decisions on fundamental data structures strongly influences higher level design. In this case I think floor decision/prioritzation functionality would more likely end up in it's own class(es) - decoupling the decision logic from the elevator's movement.

This decoupling would make it easier to fix any issues due to incomplete/vague requirements. With the current code, things would break and change everywhere.

end Edit

Does not use TopFloor.

Does not check the floor is in a valid range.

Does not use the bool in the SortedList. Why even use SortList?  You are not using access by index. You could just have an array with bool for floor request.

The queues is not allowed to build up - it just goes to the floor.  You have logic about stopping on floors that really does nothing.
This is all your call actually does:

public void AddRequest(int floor)
{
    CurrentFloor = floor;
    Status = Status.Stopped;
}

If your queue did really work like a queue.  You decide the top/bottom floor and don't allow for a new top/bottom during the trip.

You need the elevator operating on a separate thread.  Start with something like this:

System.Collections.Concurrent.ConcurrentBag<int> floors = new System.Collections.Concurrent.ConcurrentBag<int>();
Task t = Task.Factory.StartNew(() => {
            // Just loop.
            for(int i = 0; i < 100; i++)
            {
                Thread.Sleep(1000);
                Console.Write(floors.Count);
            }
        });
for (int i = 0; i < 100; i++)
{
    Thread.Sleep(1000);
    floors.Add(i);
}
t.Wait();

More complete.  Needs some OO work but it works like an elevator.  It looks for the next floor every time. When it does not find a next then it reverses direction.  The ConcurrentDictionary is thread safe.  ConcurrentBag does not like to remove.

public class Elevator
{
    Random rand = new Random();
    System.Collections.Concurrent.ConcurrentDictionary<int, int> floors = new System.Collections.Concurrent.ConcurrentDictionary<int, int>();
    public int TopFloor { get;  }
    public bool UpDown { get; private set; }
    public int Floor { get; private set; } = 1;
    public int? NextFloor { get; private set; } = null;
    public void RequestFloor (int requestFloor)
    {
        if (requestFloor < 1 || requestFloor > TopFloor)
            throw new IndexOutOfRangeException();
        floors[requestFloor]++;
    }
    private void RunElevator()
    {
        Task t = Task.Factory.StartNew(() =>
        {
            for (int i = 0; i < 1000; i++)
            {
                Thread.Sleep(3000);
                Console.WriteLine("");
                if (floors.Count > 0)
                {
                    Console.WriteLine("On   floor {0}", Floor);
                    bool haveDestination = false;
                    if (UpDown)
                    {
                        for (int f = Floor + 1; f <= TopFloor; f++)
                        {
                            if(floors[f] > 0)
                            {
                                NextFloor = f;
                                haveDestination = true;
                                break;
                            }
                        }
                    }
                    else
                    {
                        for (int f = Floor - 1; f >= 1; f--)
                        {
                            if (floors[f] > 0)
                            {
                                NextFloor = f;
                                haveDestination = true;
                                break;
                            }
                        }
                    }
                    if(haveDestination)
                    {
                        floors[(int)NextFloor] = 0;  //empty the floor
                        Console.WriteLine("Next floor {0}", NextFloor);
                        Floor = (int)NextFloor;
                    }
                    else
                    {
                        Console.WriteLine("Queue is clear");
                        NextFloor = null;
                        UpDown = !UpDown;
                    }
                }
            }
        });
    }
    public void TestElevator()
    {
        for (int i = 0; i <= 1000; i++)
        {
            Thread.Sleep(2000);
            RequestFloor(rand.Next(1, TopFloor + 1));
        }
    }
    public Elevator(int topFloor = 20)
    {
        if (topFloor <= 1 || topFloor > 100)
            throw new IndexOutOfRangeException();
        TopFloor = topFloor;
        for (int i = 1; i <= TopFloor; i++)
        {
            floors.TryAdd(i, 0);
        }
        RunElevator();
        TestElevator();
    }
}


"Spread the Word" CodeChef challenge I am solving the "Spread the Word" problem on CodeChef:

  Snackdown 2019 is coming! People have started to spread the word and tell other people about the contest. There are \$N\$ people numbered 1 through \$N\$. Initially, only person 1 knows about Snackdown. On each day, everyone who already knows about Snackdown tells other people about it. For each valid \$i\$, person \$i\$ can tell up to \$A_i\$ people per day. People spread the information among the people who don't know about Snackdown in the ascending order of their indices; you may assume that no two people try to tell someone about Snackdown at the same moment. Each person is only allowed to start telling other people about Snackdown since the day after he/she gets to know about it (person 1 can start telling other people already on day 1). How many days does it take for all people to know about Snackdown?

But my code exceeds the given time limit. It solves the problem in 1.01 seconds, but the time limit in there, is 1.00 seconds. I am attaching the code snippet written in C++ below:

#include<iostream>
using namespace std;
int main()
{
    int t,n;
    cin>>t;
    for(int i = 0; i<t;i++)
        {
        int c = 0,f=0,p=1;
        cin>>n;
        int a[n];
        for(int i = 0; i<n; i++) cin>>a[i];
        f = a[0];
        while(p<n)
        {

            for(int i = 0; i<f; i++)
            {
                p += a[i];
            }
            c++;
            f = p;
        }
    cout<<c;
    }
}

It would be a great help if someone modifies the above code into an efficient one!

Do not do using namespace std; This is a bad habbit that pollutes your namespace needlessly. You are only using std in exaclty 4 places. Its really easy to be better here.
Please use sensible names. Your t is the number of test runs, so name it numTests or something similar. In a month you will never know the meaning of a given variable.
Stay consistent in your code style. You have different styles of for loop. This is really confusing and quite frankly annoying to read.
The question is marked as c++ but you use plain old C here. Rather than a C-style array you should use a std::vector<int>
You are getting timeouts because you use a brute force approach. You should realize, that you can directly calulate the number of infomred people directly. At the first day it is a[0]. At the second day it is a[0] + a[0] + ... a[a[0]]. Consequently you can determine the number of newly informed people for every day just once and reuse that value.

its runtime error brother not because of time limited exceeded,it might be that in some case you are having array index out of bound exception,in this case f might exceed the maximum index value.
still if there is a time limit exceeded issue
just a hint make a sum array.


FizzBuzz Implementation in Java Fairly new to learning interview questions and I saw this one and gave it a shot. I would very much appreciate some constructive criticism of how I went about it and what you would tell me if you were the interviewer and watched me implement it this way.

public class FizzBuzz {
  public static void main(String[] args) {
    // Go from 1 to 100
    for (int i = 1; i <= 100; i++) {
      String result = "";
      if (i % 3 == 0) { // If divisible by 3
        result += "Fizz";
      }
      if (i % 5 == 0) { // If divisible by 5
        result += "Buzz";
      }
      // If it was divisible by either 3 or 5 (or both), print Fizz, Buzz, or FizzBuzz accordingly.
      if (i % 3 == 0 || i % 5 == 0) {
        System.out.println(result);
      } else { // Or else just print the integer
        System.out.println(i);
      }
    }
  }

The point of FizzBuzz is to weed out obviously unqualified candidates, not to over-optimize the solution or to show off.  Your code is a fine interview answer.

Make sure that your braces all match up.  It would be more conventional to use 4 or 8 spaces per level of indentation.

My main suggestion — and this is an opinionated nitpick — is to tone down the comments, because comments that restate obvious code give the impression that you might be unfamiliar with the language.  Experienced programmers never write // Go from 1 to 100 to explain for (int i = 1; i <= 100; i++).  If you feel compelled to demonstrate your documentation skills, write some JavaDoc instead.

The "FizzBuzz" Programm is a coding kata.

Coding Katas are very simple problems which are easy to solve. And their main aim is not to solve the problem (since it is quite easy) but to train problem solving approaches.

One of this problem solving approaches (and the origin of Coding Katas) is Test Driven Developement (TDD).

So When I was the interviewer and you would not start the Coding by writing a Test you were not my first choice... ;o)


Constructor function, prototype and making a modal I'm playing around with prototypes, constructor functions and javascript - I'm not really a Javascript developer but am interested in this.

Am I on the right track with this code? I'm looking for a code review from a JS developer. I know the codes a bit funky.

I created an example of it working here.

function modal( width, height, backgroundColor, overlayColor, showOverlay, url )
{
    this.width = width; // a percentage based number %
    this.height = height; // optional, usually needs not to be set
    this.backgroundColor = backgroundColor; // set the background colour to the modal
    this.overlayColor = overlayColor; // as hex, to be converted to rgba
    this.url = url;
    this.showOverlay = showOverlay;
    this.createModal = function()
    {
        // create elements to add classes to and insert in to dom
        var modalOverlay = document.createElement('div')
        ,   modalContent = document.createElement('div')
        ,   modalInner = document.createElement('div');

        // build html structure
        modalOverlay.className = "modalOverlay";
        modalContent.className = "modalContent";
        modalOverlay.appendChild(modalContent);
        modalInner.className = "modalInner";
        modalContent.appendChild(modalInner);

        // add new html structure to body
        document.body.appendChild(modalOverlay);

        // Theme model
        this.themeModel();
    }
    this.themeModel = function() {

        // is there a background color?
        var overlayBgColor = this.showOverlay ? this.convertHext(this.overlayColor,50) : "transparent";

        $('.modalOverlay').css({
            'background-color': overlayBgColor
        });

        $('.modalContent').css({
            'background-color': this.backgroundColor,
            'width': this.width,
            'height': this.height
        });

        // load content
        this.loadContent();
    }
    this.loadContent = function(){
        if( url )
        {
            $('.modalInner').load(url);
        }
        else
        {
            $('.modalInner').html("please provide a url to load! close");
        }

    }
    this.showModal = function(){
        this.createModal();
        $('.modalOverlay').fadeIn(50);
        $('body').addClass('modalShow');
    }
    this.hideModal = function(){
        $('.modalOverlay').fadeOut(300, function(){
           $('.modalOverlay').remove();
        })
        $('body').removeClass('modalShow');
    }
    this.convertHext = function(hex,opacity)
    {
        hex = hex.replace('#','');
        r = parseInt(hex.substring(0,2), 16);
        g = parseInt(hex.substring(2,4), 16);
        b = parseInt(hex.substring(4,6), 16);
        result = 'rgba('+r+','+g+','+b+','+opacity/100+')';
        return result;
    }
}
body
{
    position: relative;
    margin: 0; /* reset margin */
    padding: 0; /* reset padding */
}

.modalShow .modalContent
{
    opacity: 1;
   overflow':'hidden';
  -webkit-transition: all .3s ease-out;
          transition: all .3s ease-out;
margin-top: 30px;
}

.modalOverlay
{
    display: none;
    overflow: auto;
    overflow-y: scroll;
    position: fixed;
    top: 0;
    right: 0;
    bottom: 0;
    left: 0;
    z-index: 9999;
    -webkit-overflow-scrolling: touch;
    outline: 0;
    background-color: #2d2d2d;
    background-color: rgba(45,45,45,0.2);

}
.modalContent
{
    width: 50%;
    height: auto;
    background-color: #FFFFFF;

    margin-top: 0;
    margin-bottom: 30px;
    margin-left: auto;
    margin-right: auto;
    opacity: 0;
  -webkit-transition: all .3s ease-out;
          transition: all .3s ease-out;
}

.modalInner
{
    padding: 20px;
}

    show modal

Here's some thoughts

function modal(width, height, backgroundColor, overlayColor, showOverlay, url) {

One problem some programmers rant with this is that if you forget a parameter, or forget the order. This would seriously impale your code. An alternative is to pass an object that contains the config.

new Modal({
  width : 100,
  height : 100
});

One advantage of this over the previous is that you become more verbose and don't need to remember the order of the params. Additionally, you can use $.extend to place in defaults, if they didn't exist on options.

function Modal(options){
  options = $.extend(options,{
    width : /*default width */,
    height : /*default height */
  });
  ...
}

this.createModal = function () {...};
this.themeModel = function () {...};

You lose the advantage of prototypal inheritance. Better put methods on the prototype so they are shared. Advantage is you save memory by not duplicating functions per instance. Disadvantage is you lose emulated private property - but everything is accessible one way or another, no point using privates.

$('.modalOverlay').css({
    'background-color': overlayBgColor
});

$('.modalContent').css({
  'background-color': this.backgroundColor,
  'width': this.width,
  'height': this.height
});

Suggesting you move this to CSS by adding/removing classes. That way, proper separation of concerns is attained. You don't want to be debugging and 1 hour later, realize that the styles were not in the CSS files but in JS files.

To clarify, this kind of code will bite back in the long run. Suggesting you add a class to the top-most element of your modal HTML, and then style relative to it. You can provide a custom class name to the constructor instead of the styles.

.blackish-modal a{/*style for links on modal with blackish-modal class*/}
.whitish-modal a{/*same goes, but for whitish-modal class*/}

$('.modalInner').load(url);

IMO, $.fn.load is just a convenience function. Suggesting you use the lower-level AJAX functions for more flexibility. But as a convenience function, if it works for you, that's fine.

result = 'rgba(' + r + ',' + g + ',' + b + ',' + opacity / 100 + ')';

String cocatenation in JS is really messy with all that quotes. Here's an alternative:

var rgba = [r,g,b,opacity/100].join(',');
result = 'rgba(' + rgba + ')';

var delegateLoginModal = new modal("90%", "", "", "", true, "");

// create your events
$('body').on('click', '.showModal', function (e) {
    e.preventDefault();
    delegateLoginModal.showModal();
});

Suggesting you look at how Bootstrap implemented their modal. It's in a form of a jQuery plugin. Your code looks cleaner if it did something as clean as:

$('someElement').modal(/*config|method*/);

Your code is more or less good.

this.hideModal = function(){
    $('.modalOverlay').fadeOut(300, function(){
       $('.modalOverlay').remove();

This part I don't think is right, try replacing it with

.fadeOut(300,

with maybe

.fadeOut(145,

I find that this works better.


Calculate all possible combinations of given characters I was asked in my textbook Lectures on Discrete Mathematics for Computer Science to construct a program that would take an alphabet ({a,b,c} or any combination of characters {1,4,s,a}) as well as a length value and calculate all possible combinations of this alphabet.

For example:

char[] alphabet = new char[] {'a','b'};
possibleStrings(3, alphabet,"");

This will output:

aaa
aab
aba
abb
baa
bab
bba
bbb

That is all combinations of the alphabet {a,b,c} with the string length set to 3.

The code I have written is functional, however I'd like to read what things I am doing wrong or could be doing better. The book didn't give an example program, so I only hope this is what it was looking for, but maybe there's a much better way to do it or way to improve how I'm doing it. Maybe this is fine, but I just need someone to look at it and tell me in that case.

public class Program {

    public static void main(String[] args) {

        // Create an alphabet to work with
        char[] alphabet = new char[] {'a','b'};
        // Find all possible combinations of this alphabet in the string size of 3
        StringExcersise.possibleStrings(3, alphabet,"");
    }

} class StringExcersise {

    public static void possibleStrings(int maxLength, char[] alphabet, String curr) {

        // If the current string has reached it's maximum length
        if(curr.length() == maxLength) {
            System.out.println(curr);

        // Else add each letter from the alphabet to new strings and process these new strings again
        } else {
            for(int i = 0; i < alphabet.length; i++) {
                String oldCurr = curr;
                curr += alphabet[i];
                possibleStrings(maxLength,alphabet,curr);
                curr = oldCurr;
            }
        }
    }
}

your code looks fine.

a slight performance improvement i'd do is pass a StringBuilder instead of a String - a String in java is immutable so every time you call curr += alphabet[i] youre actually allocating a new String object. instead you could append the character to a StringBuilder (and delete the last character when you leave) to save on the number of Objects created during the run
for(int i = 0; i < alphabet.length; i++) {} could be re-written as a more modern loop: for (char c : alphabet) {}, which would make for a more readable result

Instead of the oldCurr stuff, just create a newCurr each time.  e.g.

String newCurr = curr + alphabet[i];
possibleStrings(maxLength, alphabet, newCurr);

Would be shorter and, at least to my eyes, is much clearer.


Improve this function that compares jQuery versions Please help me improve this function that compares the jQuery version currently available (or not) with the one required.

function(need) {
    if (typeof(jQuery) != 'undefined') {
        if (!need) return true;
        var re = /(\d+)\.(\d+)\.(\d+)/,
            cur = re.exec(jQuery.fn.jquery),
            need = re.exec(need);
        return (need[1] <= cur[1] && need[2] <= cur[2] && need[3] <= cur[3]);
    } else return false;
}

I'm sorry, but that code is completely broken.

It doesn't work if either version contains only two numbers such as the current "1.6".
It uses string comparison instead of integer comparison, so that it will return true if you "need" (theoretical) version "1.4.10" but only "1.4.2" is included, because "10" < "2" is true.
It doesn't stop comparing minor version numbers, if the major number is already bigger. For example it will return false if "1.4.2" is "needed", but "1.5.1" is included, because "2" > "1"
And finally you should keep in mind that "newer" isn't necessarily better. For example, the new 1.6 version changes how .attr() works, and scripts that rely on the old functionality of .attr() may break.

I feel like I'm missing something, but I got it down to one line for a compressed version, or a few lines for a verbose explination.

Compressed version:

(parseInt(jQuery.fn.jquery.split('.').join('')) > 140) ? alert("Running jquery greater than 1.4.0") : alert("current jquery version is 1.4.0 or less");

Long version for clarity:

// get version as a string and get rid of the periods.
version = jQuery.fn.jquery.split('.').join('');

// Make into one long number for easy comparison.  Example, 171, or 141.
version = parseInt(version);
if(version > 141){
  alert("We're using a version greater than 1.4.1");
}else{
  alert("jQuery version is 1.4.1 or lower");
}


Optimize a parallelized program to optimize train schedules This loops through a vector of vector of A and adds a smaller array to a bigger one at a specified position+random shift.  Then it is checked if it is a better solution, and if yes, it is stored, else it is discarded.  I have already parallelized it.

Can this be improved to run faster?

I am not sure if a vector<vector<struct>> is a good idea, or maybe there is a better memory management to use better cache effects.  The struct is currently global and since it is only readable by the threads all threads use the same instance.

I am using C++11 threads.

Description of what the program does:

We have a big array, rand_val, and we have many small arrays, Leistungskurve. We can add these  array to rand_val at a fixed position + random shift. We want to find a valid position for each array so the max element in rand_val is minimized. In the array, rand is stated which position we have chosen.

#include <iostream>
#include <string>
#include <vector>
#include <time.h>
#include <cmath>
#include <iterator>

#include <algorithm>

#include <fstream>
#include <stdlib.h>
#include <sstream>

#include <stdlib.h>

#include <thread>
#include <random>

using namespace std;

struct Teilstrecke {
  int StreckenNr;
  int Fahrzeit;
  int Haltezeit;
  int FruehesteAbfahrt;
  int SpaetesteAbfahrt;
  int Abfahrtsintervall;
  double *Leistungskurve;
};

struct Zug {
  int ZugNr;
  int AnzahlStrecken;
  vector<Teilstrecke> Teilstrecken;
};

vector<Zug> Zuege;

int Planungsintervall;
int AnzahlZuege;
int AnzahlSchattenzuege;

inline double maxArray(double *arr, int size)
{
  double max = 0;
  int pos = 0;
  for (int i = 0; i < size; i++)
  {
    if (arr[i] > max)
    {
        max = arr[i];
        pos = i;
    }
  }
  return pos;
}

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2; i++)
  {
    arr1[pos+i] += arr2[i];
  }
}

inline void addArray(double *arr1, Teilstrecke ts, int shift)
{
    addArray(arr1, ts.Leistungskurve, ts.Fahrzeit*600+1, (ts.FruehesteAbfahrt+shift)*600);
}

inline void randomSolution(int *rand, double *rand_val);

inline int randomNumber(int low, int high) // has to be replaced to c++11 random
{
  return rand() % (high - low + 1) + low;
}

void wrapper()
{
  int size = Planungsintervall*600+1;
  int *rand = new int[AnzahlSchattenzuege];
  fill_n(rand, AnzahlSchattenzuege, 0);
  double *rand_val = new double[size];
  fill_n(rand_val, size, 0);
  int max_iter = 1000000;

  double best_max = 1e20;
  int *rand_best = new int[AnzahlSchattenzuege];
  for (int i = 0; i < max_iter; i++)
  {
    randomSolution(rand, rand_val);
    double max = maxArray(rand_val, size);
    //cout << max << '\n';
    if (max < best_max)
    {
      best_max = max;
      memcpy(rand_best, rand, sizeof(int)*AnzahlSchattenzuege);
    }
    fill_n(rand, AnzahlSchattenzuege, 0);
    fill_n(rand_val, size, 0);
  }
  cout << best_max <<  ' ' << '\n';
}

inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    for (int j = 0; j < Zuege.at(i).AnzahlStrecken; j++)
    {
      Teilstrecke ts = Zuege.at(i).Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}

void read_input(char *read_file);

int main(int argc, char** argv)
{
  read_input((char*)argv[1]);
  vector<thread> threads;
  for (int i = 0; i < 7; i++)
  {
    threads.push_back(thread(wrapper));
  }
  wrapper();
  for (int i = 0; i < 7; i++)
  {
    threads.at(i).join();
  }
}

Profiling

It seems that all work is done in addArray.

Do not use using namespace std as it could cause clashing issues, which will introduce bugs.  More info about that here.
This is very unorganized:

#include <iostream>
#include <string>
#include <vector>
#include <time.h>
#include <cmath>
#include <iterator>

#include <algorithm>

#include <fstream>
#include <stdlib.h>
#include <sstream>

#include <stdlib.h>

#include <thread>
#include <random>

Steps to improve this:

Make sure there aren't any libraries that you aren't currently using or have repeated.
Make sure you aren't using any C libraries (which end with .h).  They should be replaced with the equivalent C++ library so that everything will be in the std namespace.
Sort them in a certain order for organization, such as alphabetically.  This will make it easier to locate certain libraries during maintaining.

Assuming every library is still being used, this is what it could look like:

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <iterator>
#include <random>
#include <sstream>
#include <string>
#include <thread>
#include <vector>

This is one #include shorter because you've included <stdlib.h> twice.  Had this list been organized from the beginning, this wouldn't have been likely to happen.
Do not use global variables:

vector<Zug> Zuege;

int Planungsintervall;
int AnzahlZuege;
int AnzahlSchattenzuege;

They are accessible throughout the entire file or program, and can possibly be modified without your knowledge.  This can greatly hurt maintainability and also introduce bugs.  You should keep them in local scope, such as in a function, and pass them to other functions as needed.  This will make it much easier to keep track of their locality and determine how they're used.
The inline keyword likely won't offer you any benefit here.  The compiler is free to decide what should really be inlined and can ignore any explicit use of it.  It merely serves as a hint.
There is absolutely no need to call std::rand() when you're using C++11 and have already included <random>.  You should utilize this library and ditch std::rand() altogether.

Regarding the usage of std::rand() itself, you don't even call std::srand(), meaning you'll get the same random values with each call to std::rand().  Have you not even noticed this?
Why are you mixing std::vectors and dynamically-allocated arrays?  Vectors are the same type of array, but much more specialized.  You should ditch all the arrays and just use vectors (or any suitable storage container).  You end up passing these arrays (specifically the pointer to their first respective elements), which can get very nasty in C++, especially because memory-management will now be in your hands.  Just utilize storage containers and let them handle the dirty work for you (which is very necessary, as you fail to deallocate memory with delete, causing the whole program to leak memory).  They will also allow you to ditch the size variables since storage containers already keep track of their sizes (accessible via size()).
Since you use argv[1] in main() as the only command line argument, I assume that you're only expecting one additional argument.

In order to make sure that this argument is provided, check the value of argc at the start, before using argv[1].  If it's less than 2, terminate the program.  You may also print an error message to inform the user of this error.

if (argc < 2)
{
    std::cerr << "A filename argument is required!";
    return EXIT_FAILURE;
}

To sum it up:

This is quite broken and messy.  I'm sure there are other issues besides the ones I've mentioned, but this should address many of them.  Before worrying about optimization, I'd recommend cleaning this up and making sure it runs smoothly and correctly.

To see where the bottleneck is, you need to profile your code!

Here something which may be a little improvement:

replace:

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2; i++)
  {
    arr1[pos+i] += arr2[i];
  }
}

by

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2;)
  {
    arr1[pos++] += arr2[i++];
  }
}

and

replace

inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    for (int j = 0; j < Zuege.at(i).AnzahlStrecken; j++)
    {
      Teilstrecke ts = Zuege.at(i).Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}

by:

inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    Zug z=Zuege.at(i);
    int maxJ=z.AnzahlStrecken;
    for (int j = 0; j < maxJ; j++)
    {
      Teilstrecke ts = z.Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}


Insertion sort C++14 implementation I have implemented insertion sort using C++. Is there any way to improve my code and is it CppCoreGuideline compliant? As I passed the vector as const in print method, do I need to specify const in range for loop?

/*
 *  Insertion Sort
 */

#include <iostream>
#include <vector>

void insertionSort(std::vector<int> &v);
void print(const std::vector<int> &v);

int main()
{
    std::ios_base::sync_with_stdio(false);

    std::vector<int> v {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    // Print the vector before sorting.
    print(v);
    // Sort
    insertionSort(v);
    // Print the vector after sorting.
    print(v);

    return 0;
}

void insertionSort(std::vector<int> &v) {
    for (auto i = v.begin() + 1; i != v.end(); ++i) {
        int key = *i;

        auto j = i - 1;
        while (j >= v.begin() && *j > key) {
            *(j+1) = *j;
            --j;
        }
        *(j+1) = key;
    }
    return;
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

Advice 1

In your insertionSort you can remove the last statement (return).

Advice 2

Making your insertion sort generic is easy:

template<typename RandIt>
void insertion_sort(RandIt begin, RandIt end)
{
    for (auto i = begin + 1; i != end; ++i)
    {
        auto key = *i;
        auto j = i - 1;

        while (j >= begin and *j > key)
        {
            *(j + 1) = *j;
            --j;
        }

        *(j + 1) = key;
    }
}

template<typename Container>
void insertion_sort(Container& cont)
{
    insertion_sort(std::begin(cont), std::end(cont));
}

Advice 3

Making your print function generic is not hard either:

template<typename RandIt>
void print(RandIt begin, RandIt end)
{
    using value_type = typename std::iterator_traits<RandIt>::value_type;
    std::copy(begin, end, std::ostream_iterator<value_type>(std::cout, ", "));
    std::cout << std::endl;
}

template<typename Container>
void print(const Container& container)
{
    print(std::begin(container), std::end(container));
}

Hope that helps.

Your code looks fine, but it has a run time complexity of O(n*n), you can perform this in logarithmic time:

std::vector<int> to_insert_sort {2,3,5,6,1,1,3,2};

int to_insert {3};

std::sort(to_insert_sort.begin(), to_insert_sort.end()); //Log

auto pos = std::upper_bound(to_insert_sort.begin(), to_insert_sort.end(), 5); //Log

to_insert_sort.insert(pos, to_insert); //O(n)


Searching in an array in less than O(n) time I have an array where each element is either one less or one greater than the preceding element \$\{x_i = x_{i-1} \pm 1\}\$. I wish to find an element in it in less than \$O(n)\$ time. I've implemented it like this:

public int searchArray(int[] arr, int i, int elem) {

    if (i > arr.length - 1 || i < 0) {
        return -1;
    }

    if (arr[i] == elem) {
            return i;

    } else {
            int diff = Math.abs(elem - arr[i]);
            int index = searchArray(arr, i + diff, elem);
            if (index == -1) {
                index = searchArray(arr, i - diff, elem);
                if (index == -1) {
                    return -1;
                }
            }
            return index;
    }
}

And calling it like:

int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};
int index = searchArray(arr, 0, 3);

It is working fine, but can it be improved? Specifically, is there a way to do it iteratively? And is the current algorithm less than \$O(n)\$. I guess it is, but I'm not sure.

While other answers make good points, I have to wonder why you are using recursion. This is such a simple problem to solve with a for loop.

I assume that you are not supposed to start from any index other than index 0, so consider the following routine:

public int searchArray(int[] arr, int elem) {

    for (int i = 0; i < arr.length; ) {
        if (arr[i] == elem) {
            return i;
        }
        i += Math.abs(elem - arr[i]);
    }
    return -1;
}

(If you need to start the search part-way through the array then you can add the offset input parameter again and start i from that).

The bottom line is that recursion is overkill, this system is \$O(n)\$, but the cost of each cycle is less than the same thing using recursion.

I am not aware of any way to solve the given problem with a system of better than \$O(n)\$ complexity.

Discussion on complexity - why this is \$O(n)\$

This answer has generated a lot of discussion about complexity, that this method only ever scans, at most, half the members of the input array, and thus it should be complexity \$O \left( \frac{n}{2} \right )\$ instead of \$O(n)\$. The argument given is something like:

  Consider the worst-case data 1,2,1,2,1,2,1,2,1,2,1,2 and the search term 3. For this situation the method will start at data[0], and then skip to data[2], then data[4], and so on. It will never inspect data[1], and other odd-indexed data points. If the search term is even more 'different' than the actual data (e.g. 100) then the method will do only one comparison at data[0] and will then return 'not found' -1.

This is an interesting observation, that the method only ever needs to scan half the data at most. This is especially interesting considering a 'naive' method which just scans the data one-member-at-a-time and returns when it finds the value. That 'naive' method most certainly has \$ O\left(n\right) \$ 'performance' and complexity, and the 'skip-method' will be more than twice as fast.

The important thing to note though, is how the algorithms scale relative to the amount of data, not relative to each other!

So, consider a hypothetical set of worst-case data 1,2,1,2,1,2,.... and the search-term 3. This hypothetical happens to be searched in 4 milliseconds by the skip-method, and in 8 milliseconds by the naive-method. Now we double the amount of data, what happens? The processing time for both methods will double!

In both cases, the performance of the algorithms will double for each doubling of the data volume. This is what makes both algorithms \$ O(n) \$ complexity. From Wikipedia:

  In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.

Reversing the argument, by suggesting the skip-method has \$O \left( \frac{n}{2} \right) \$ complexity, I would then expect that, if I double the data, the execution time would only increase by a half, or 50%. This is 'obviously' not true for the skip-method (nor the naive-method).

Both methods have \$O(n)\$ complexity because they both scale the same way with increasing volumes of data.

But, just because they scale the same way, does not mean that one method is not better than the other... obviously.

Is there a restriction that says the array has to (or can't be) in a specific order? If you keep a sorted array you could perform a binary search which would run in O(log(n)). There are both recursive and iterative implementation. Of course the drawback is that the array has to be sorted but the pro is that you can search through millions of records in less than 10 iterations/recursions.

From Wikipedia's article on the binary search algorithm:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}


Temperature conversion table in C++14 I'm learning C++ and thought I would try my hand at writing a basic program in modern C++. I'm always looking for ways to reduce my code to STL algorithms and simplifying areas that would require refactoring. I'm also trying to make my code as readable as possible.

Limitation

I can't modify the precision in std::to_string as far as I can see, which affects the rest of the program.

What I want

Looking for ways to simplify stuff to STL algorithms
Ensure everything is modern C++
Readability. What if I want to modify the code 3 weeks from now?
Anything else?

Code:

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

auto fah_to_cel(double in)
{
    return (in - 32.) / 1.8;
}

int main()
{
    auto min = 0u;
    auto max = 100u;
    auto step = 5u;

    std::vector<double> temps;

    /* size_type is not necessarily the same
     * type as 0u
     */
    auto max_width = std::string::size_type(0);

    for (auto i = min; i < max; i += step)
    {
        auto width = std::to_string(i).size();
        max_width = std::max(width, max_width);
        temps.emplace_back(i);
    }

    auto header_width = sizeof("Fahrenheit") - 1;
    max_width = std::max(header_width, max_width);

    std::cout << "Fahrenheit"
              << std::string(5, ' ')
              << "Celsius"
              << "\n";

    std::cout << std::string(max_width, '-')
              << std::string(5, ' ')
              << std::string(max_width, '-')
              << "\n";

    for (auto& temp : temps)
    {
                  /* Fahrenheit column */
        std::cout << std::left  << std::setw(max_width)
                  << std::fixed << temp

                  /* Padding */
                  << std::string(5, ' ' )

                  /* Celsius column*/
                  << std::left  << std::setw(max_width)
                  << std::fixed << fah_to_cel(temp)
                  << "\n";
    }
}

Example output:

Fahrenheit     Celsius
----------     ----------
0.000000       -17.777778
5.000000       -15.000000
10.000000      -12.222222
15.000000      -9.444444
20.000000      -6.666667
25.000000      -3.888889
30.000000      -1.111111
35.000000      1.666667
40.000000      4.444444
45.000000      7.222222
50.000000      10.000000
55.000000      12.777778
60.000000      15.555556
65.000000      18.333333
70.000000      21.111111
75.000000      23.888889
80.000000      26.666667
85.000000      29.444444
90.000000      32.222222
95.000000      35.000000

I see some things that may help you improve your program and have provided answers to your questions.

Be clear about your program's purpose

What the program actually does is to print out a table of temperatures.  That much is quite clear, but what is less clear is whether you really wanted the std::vector to be created or not.  If that was just a means to the end goal of creating a table, then I'd suggest you could omit it entirely and simply use a loop to print the values rather than storing them.

Use named variables

The word "Fahrenheit" appears twice within the code.  It would be better to use named variables rather than risk, say, having a typo in one of the versions.  I'd do it like this:

const std::array<std::string, 2>column_labels{"Fahrenheit", "Celsius"};

Remove unecessary data structures

As noted above, the std::vector is not really needed.  If the code simply directly prints the values, the code becomes shorter and easier to read and understand.

Eliminate redundant I/O manipulators

Once the width and precision have been set, there's little reason to assert them again.  I'd write the main loop like this:

for (double temp=min; temp < max; temp += step) {
    std::cout << std::setw(col_width) << std::fixed
              << std::setprecision(4) << temp
              << fah_to_cel(temp) << '\n';
}

Note that the limitation of std::to_string is eliminated by this means because we can use std::setprecision().

Avoid construction/destruction overhead

Each time the code calls std::string(5, ' ') it represents a constructor call and somewhere later, a destructor call.  This can be avoided either by making it a named const variable which can be repeatedly used, or better still, eliminated entirely by simply using the std::setw() manipulator to set the columns to the size you want, automatically creating the required space.

Let the computer do the work

It seems to make more sense to me to let the computer figure out which label is longest.  Here's one simple way to do that:

const auto max_width = std::accumulate(
        column_labels.begin(), column_labels.end(), 0,
        [](std::string::size_type a, const std::string &str){
            return std::max(a, str.size());
        });

This uses a lambda to return the longest string length, but this could be done using a function if you wish.

Use const where practical

Things that don't change should be declared const which includes your min, max and many other variables within the code.

Consider whether to use a function or inline

The fah_to_cel routine is quite simple and only used once, so I'd be inclined to eliminate it in favor of simply putting the code inline instead.

An alternative implementation

Using these suggestions, here's an alternative approach:

#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>

int main()
{
    const auto min = 0u;
    const auto max = 100u;
    const auto step = 5u;
    const std::array<std::string, 2> column_labels{"Fahrenheit", "Celsius"};
    const auto max_width = std::accumulate(
            column_labels.begin(), column_labels.end(), 0,
            [](std::string::size_type a, const std::string &str){
                return std::max(a, str.size());
            });
    const auto col_width = max_width+5;
    std::cout.setf(std::ios_base::left, std::ios_base::adjustfield);
    // print column labels
    for (const auto &label : column_labels) {
        std::cout << std::setw(col_width) << label;
    }
    std::cout << '\n';
    // print column label underlines
    const std::string underline(max_width, '-');
    for (auto i=column_labels.size(); i; --i) {
        std::cout << std::setw(col_width) << underline;
    }
    std::cout << '\n';
    // print temperature table
    for (double temp=min; temp < max; temp += step) {
        std::cout << std::setw(col_width)
                  << std::fixed << std::setprecision(4)
                  << temp << (temp-32)/1.8 << '\n';
    }
}

nice code but what get my attention most

auto width = std::to_string(i).size();

width here is equal 3 based on the max if it was converted to string size. also, max_width will be always equal header_width. i don't think you need it here.

use const where it is possible you have few candidate for it like min, max and step. also in for-range loop it is better to consider  it for optimizing purpose like so, for (const auto& temp : temps)

for "Fahrenheit" since you going to use it often in your code, it will be nice if create std::string object for it.

std::string name = "Fahrenheit";
const auto max_width = name.length();

there are many ways fill std::vector by using STL one of which is:

std::vector<double> temps;
const auto size = max / step;
temps.reserve(size);
auto i = min;
auto comp = [&i, &step]()
{
    static bool firstRun = true;
    if(firstRun)
    {
         firstRun = false;
        return i;
    }
    else
    {
       return i += step;
    }
};
std::generate_n(std::back_inserter(temps), size, comp);

but personally, simple loop like yours will do the job and much better in term of readability.


Business rule updater I'm trying to increase the speed of my application at the moment. My inserting/updating methods were opening every time a new connection which took too much time. I read that it's better to create a connection object and pass it to different methods. It worked fine but I'm just curious if this is a good practice.

This is a part of my code I wrote:

public class BusinessRuleUpdaterDaoImplV2 extends OracleBaseDao implements BusinessRuleUpdaterDaoV2 {

    @Override
    public boolean updateBusinessRule(BusinessRule businessRule) {
        try(Connection con = super.getConnectionConfigDb()) {
            con.setAutoCommit(false);
            if (updateTableBusinessRule(con,businessRule)){
                return true;
            } else {
                con.rollback();
                return false;
            }
        } catch (SQLException e) {
            e.printStackTrace();
        }
        return false;
    }

    private boolean updateTableBusinessRule(Connection con, BusinessRule businessRule){
        String queryBr = "UPDATE BUSINESSRULE SET ERRORMESSAGE = ?, SQLCODE = ?, CUSTOMNAME = ?, OPERATOR_ID = ? WHERE BUSINESSRULE_ID = ?";
        try(PreparedStatement pstmtBr = con.prepareStatement(queryBr)) {
            pstmtBr.setString(1,businessRule.getErrorMessage());
            pstmtBr.setString(2,businessRule.getSqlQuery());
            pstmtBr.setString(3,businessRule.getName());
            pstmtBr.setInt(4,businessRule.getOperatorID());
            pstmtBr.setInt(5,businessRule.getBusinessRuleID());
            pstmtBr.executeUpdate();
            pstmtBr.close();
            return updateTableTargetTable(con,businessRule);
        } catch (SQLException e) {
            e.printStackTrace();
            return false;
        }
    }

    private boolean updateTableTargetTable(Connection con, BusinessRule businessRule){
        String queryTt = "UPDATE TARGETTABLE SET NAME = ? WHERE TABLE_ID = ?";
        for (int i = 0 ; i < businessRule.getTableListSize() ; i++) {
            try (PreparedStatement pstmtTt = con.prepareStatement(queryTt)) {
                pstmtTt.setString(1,businessRule.getListOfTables().get(i).getName());
                pstmtTt.setInt(1, businessRule.getListOfTables().get(i).getId());
                pstmtTt.executeUpdate();
                pstmtTt.close();
            } catch (SQLException e) {
                e.printStackTrace();
                return false;
            }
        }

        return false;
    }

    private boolean updateTableAttribute(Connection con, BusinessRule businessRule){
        // return updateTableValue(con, businessRule)
        return false;
    }

    private boolean updateTableValue(Connection con, BusinessRule businessRule){
        //return updateTableStack(con, businessRule)
        return false;
    }

    private boolean updateTableStack(Connection con, BusinessRule businessRule){
        return false;
    }
}

As you can see in the first method, updateBusinessRule(), I'm opening a connection and passing it to the next method. If one of the methods returns false, it will make a roll back in the first method.

I'm also curious about why intellij is telling me that pstmtTt.close() is redundant.

I think it is ok to re-use the Connection.

I would not try-catch all the SqlExceptions in the update* methods. Just let them throw. Then you don't need all the boolean logic either. Makes it simpler I guess.

You can use a connection pool like HikariCP or c3p0; it reduces the time for new connection setup.


Text file manipulation with Java 8 and Guava I am trying to do some translation of text files. I have a translation .csv file and a file I need to translate (tab delimited). The translation is creating a file with an extra column of the translation.

I'd like to hear any suggestions on this.

import com.google.common.base.Joiner;
import com.google.common.base.Splitter;
import com.google.common.collect.Lists;
import com.google.common.io.Files;

import java.io.File;
import java.io.IOException;
import java.nio.charset.Charset;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class TextFileManipulationExample {

  public static void main(String[] args) {
    new TextFileManipulationExample().translate();
  }

  private void translate() {
    List<String> translationFileContent = readFile("dictionary.csv");
    Stream<List<String>> translationLines = translationFileContent.stream().map(
      line -> Splitter.on(",").splitToList(line));
    Map<List<String>, String> translationMap = translationLines.collect(Collectors.toMap(l -> Lists.newArrayList(l.subList(0, 2)), l -> l.get(2)));
    List<String> toTranslateLines = readFile("file_to_translate.txt");
    Stream<List<String>> listWithTranslation = toTranslateLines.stream().map(line -> {
      List<String> list = Lists.newArrayList(Splitter.on("\t").splitToList(line));
      if (translationMap.containsKey(list)) {
        list.add(translationMap.get(list));
      }
      return list;
    });
    String contentToWrite = listWithTranslation.map(lineList -> Joiner.on(",").join(lineList)).collect(
      Collectors.toList()).stream().reduce((t, u) -> t + "\n" + u).get();
    writeFile(contentToWrite, "translated.csv");
  }

  private void writeFile(String contentToWrite, String fileName) {
    try {
      Files.write(contentToWrite, new File(fileName), Charset.defaultCharset());
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  private List<String> readFile(String fileName) {
    try {
      return Files.readLines(new File(fileName), Charset.defaultCharset());
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }
}

You are using Java 8's functional stream programming, but you leave out method chaining. Depending on how you chain methods, it could be more or it could be less readable. You might be imagining this:

readFile("dictionary.csv").stream().map(line -> Splitter.on(",").splitToList(line)).collect(Collectors.toMap(l -> Lists.newArrayList(l.subList(0, 2)), l -> l.get(2)));

There is no way I could read that. However, consider this:

Map<List<String>, String> translationMap = readFile("dictionary.csv").stream()
            .map(line -> Splitter.on(",").splitToList(line))
            .collect(
                Collectors.toMap(
                    l -> Lists.newArrayList(l.subList(0, 2)),
                    l -> l.get(2)
                )
            );

I find this much more readable. By simply reading vertically, I can determine that the code does this:

Reads dictionary.csv into a list of strings (via readFile).
Split each string in the dictionary on ",", into a List<String>.
Collect the List<String>s into a Map, where

The keys are the first two elements of each list, still in a List
The values are the 3rd element of each list.

On the other hand, your code as is is littered with type names; do I really need to know that that is a Stream<List<String>> when that's easily determined from context?:

List<String> translationFileContent = readFile("dictionary.csv");
Stream<List<String>> translationLines = translationFileContent.stream().map(
  line -> Splitter.on(",").splitToList(line));
Map<List<String>, String> translationMap = translationLines.collect(Collectors.toMap(l -> Lists.newArrayList(l.subList(0, 2)), l -> l.get(2)));

Alternatively, if you really like the temporary variables, put some empty lines in there to separate logical sections. Also, consider using Project Lombok, where you could just do this:

List<String> translationFileContent = readFile("dictionary.csv");
val translationLines = translationFileContent.stream().map(
    line -> Splitter.on(",").splitToList(line));
val translationMap = translationLines.collect(Collectors.toMap(l -> Lists.newArrayList(l.subList(0, 2)), l -> l.get(2)));

(Coder discretion advised on where you should use val).

You want to remove the function chaining and temporary variables by replacing it with other functions. I strongly recommend against this.

Breaking this into small methods, as you suggest, isn't good. Functional programming is designed to be highly readable as is like this. Hiding the details behind functions makes it hard to understand:

Map<List<String>, String> translationMap = convertTranslationLinesToMap(
    splitEachLineByComma(readFile("dictionary.csv"))
);

And each of those functions would be trivial one-two lines of code. That's not what functions are for.

Your IDE should format your code with newlines and indents, or leave the code unformatted when it is wrapped across lines. Making individual functions to do this would be the analogue of making individual functions the following pre-Java 8 code:

List<String> translationFileContent = readFile("dictionary.csv");
Map<List<String>, String> translationMap = new HashMap<>();

for (String line : translationFileContent) {
    List<String> list = Splitter.on(",").splitToList(line);
    translationMap.put(Lists.newArrayList(list.subList(0, 2)), list.get(2));
}

This code should not be moved into its own function as it's highly specific to this location and refactoring into a function just seems useless. Don't do this for the Java 8 code. In all honesty, separating each call into temporary variables is probably cleaner than making new functions for everything.

Additionally, formatting the Java 8 code across multiple lines isn't "relying on indentation and newlines" any more than the other code example is. Try reading this:

List<String> translationFileContent = readFile("dictionary.csv"); Map<List<String>, String> translationMap = new HashMap<>(); for (String line : translationFileContent) { List<String> list = Splitter.on(",").splitToList(line); translationMap.put(Lists.newArrayList(list.subList(0, 2)), list.get(2)); }

Similarly, Java 8 code is not meant to be formatted like that.

Regarding the concern of colleagues formatting away the line breaks, you could add a comment explaining why it is like that. But poorly chosen IDE format settings could still interfere, unless you did something like this (this isn't good in practice, though):

Map<List<String>, String> translationMap = readFile("dictionary.csv").stream()
                                                              // For each line,
            .map(line -> Splitter.on(",").splitToList(line))  // split on commas, then
            .collect(                                         // collect the result
                Collectors.toMap(                             // into a map
                    l -> Lists.newArrayList(l.subList(0, 2)), // whose keys are the first two elements of each line
                    l -> l.get(2)                             // and values are the third.
                )
            );

This isn't a good idea in general; we shouldn't need comments at the end of each line.


Print all possible sequences that could have created this BST I was working through Cracking The Coding interview, and I couldn't wrap my brain around their solution to one of the problems, so I ended up coming up with my own that, IMHO, is a lot cleaner and easier to read. Would love your feedback. Here is the actual problem:

"A binary search tree was created by traversing through an array from left to right and inserting each element. Given a binary search tree with distinct elements, print all of the arrays that could have led to this tree."

In other words, what are all of the possible sequences of values that could have led to this tree.

For reference, here is a link to the 'official' solution.

And here is what I came up with

public class AllSequences {
public LinkedList<LinkedList<TreeNode>> allSeqs;

public AllSequences(TreeNode root) {
    allSeqs = new LinkedList<>();
    LinkedList<TreeNode> pre = new LinkedList<>();
    LinkedList<TreeNode> poss = new LinkedList<>();

    buildSeqs(pre, poss, root);
    for (LinkedList<TreeNode> ll : allSeqs) {
        for (TreeNode n : ll) {
            System.out.print(n.data + " ");
        }
        System.out.println();
    }
}

private void buildSeqs(LinkedList<TreeNode> pre, LinkedList<TreeNode> poss, TreeNode root) {
    pre.add(root);
    if (root.left != null) {
        poss.add(root.left);
    }
    if (root.right != null) {
        poss.add(root.right);
    }

    if (poss.isEmpty()) {
        allSeqs.add(pre);
    }

    for (TreeNode n: poss) {
        LinkedList<TreeNode> temp = (LinkedList<TreeNode>) pre.clone();
        LinkedList<TreeNode> ptemp = (LinkedList<TreeNode>) poss.clone();
        ptemp.remove(n);
        buildSeqs(temp, ptemp, n);
    }
}

public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(15);
    root.left.right = new TreeNode(7);
    root.left.left = new TreeNode(3);

    AllSequences all = new AllSequences(root);
}
}

Granted mine ends up with a set of LinkedLists of possible input sequences, not arrays, but it would be easy enough to convert that if the interviewer was a stickler about it. It seems to correctly print out for all of my hand-coded, relatively small test cases.

public class Solution {
    ArrayList<LinkedList<Long>> result;
    /*Return the children of a node */
    ArrayList<TreeNode> getChilden(TreeNode parent) {
        ArrayList<TreeNode> child = new ArrayList<TreeNode>();
        if(parent.left != null) child.add(parent.left);
        if(parent.right != null) child.add(parent.right);
        return child;
    }
    /*Gets all the possible Compinations*/
    void getPermutations(ArrayList<TreeNode> permutations, LinkedList<Long> current) {
        if(permutations.size() == 0) {
            result.add(current);
            return;
        }
        int length = permutations.size();
        for(int i = 0; i < length; i++) {
            TreeNode node = permutations.get(i);
            permutations.remove(i);
            ArrayList<TreeNode> newPossibilities = new ArrayList<TreeNode>();
            newPossibilities.addAll(permutations);
            newPossibilities.addAll(getChilden(node));
            LinkedList<Long> newCur = new LinkedList<Long>();
            newCur.addAll(current);
            newCur.add(node.val);
            getPermutations(newPossibilities, newCur);
            permutations.add(i,node);
        }
    }

    /*This method returns a array of arrays which will lead to a given BST*/
    ArrayList<LinkedList<Long>> inputSequencesForBst(TreeNode node) {
        result = new ArrayList<LinkedList<Long>>();
        if(node == null)
            return result;
        ArrayList<TreeNode> permutations = getChilden(node);
        LinkedList<Long> current = new LinkedList<Long>();
        current.add(node.val);
        getPermutations(permutations, current);
        return result;
    }
}

My solution. Works perfectly.


Function that abbreviates a number (e.g. 1202 => 1.2K) Like Twitter and Instagram and others I wanted to display numbers like 1.2K and 3.8M etc. My function works well enough but I would appreciate any input you may have.

function abbrNum (num) {
    if(typeof num !== 'number') {
        throw new TypeError('Expected a number');
    }

    var shortNumber;
    var exponent;
    var suffixes = ['K', 'M', 'B', 'T'];
    var size = (num + '').length;

    exponent = size % 3 === 0 ? size - 3 : size - (size % 3);

    if(num < 1000) {
        return num;
    } else {
        shortNumber = Math.round(10 * (num / Math.pow(10, exponent))) / 10;
    }

    if(exponent < 6) {
        shortNumber += suffixes[0];
    } else if(exponent < 9) {
        shortNumber += suffixes[1];
    } else if(exponent < 12) {
        shortNumber += suffixes[2];
    } else if(exponent < 16) {
        shortNumber += suffixes[3];
    }

    return shortNumber;
}

Update: This code (updated according to feedback) is available on npm.

converting to string just to get the length won't work if there is a decimal or it's large enough that the string conversion uses scientific notation.

var size = floor(log(num)/log(10))+1;

This will give the place of the highest significant digit (1 to 9 results in 1, 10 to 99 results in 2, 100 to 999 results in 3, etc...)

None of the given answers - or the original code for that - is actually correct.

Here is a minimal test harness to test the heart of the whole problem: Figuring out the right exponent for a given number:

function test(input, expected, func) {
    var result = func(input);
    if (result !== expected) {
        console.log("Invalid result for " + input + " expected: " + expected + " actual: " + result);
    }
    return result === expected;
}

function testHarness(funcName, func) {
    console.log("Testing " + funcName);
    var successful = true;
    for (var i = 1, number = 1; i <= 50; i++, number *= 10) {
        successful &= test(number, i, func);
        if (!successful) {
            break;
        }
    }
    if (successful) {
        console.log(funcName + " passed test correctly.")
    } else {
        console.log(funcName + " did NOT pass test!")
    }
    return successful;
}

The original answer fails at 1e21 because that is when Chrome decides to use scientific notation for floats, while ratchet freak's solution already gives the wrong result for 1000.

For reference here is the obvious implementation of an ilog10 algorithm that is as correct as possible (to the best of my knowledge) considering the inherent imprecision of floating point (you just cannot represent 1e55 or so as a IEEE-754 double so that's where this becomes problematic):

function ilog10(val) {
    var i = 1;
    var number = 10;
    while (val >= number) {
        i += 1;
        number *= 10;
    }
    return i;
}

What also seems to work - but I'd definitely want to write more test cases to be sure is to use Math.floor(Math.log10(val)) + 1. It passes the basic unit test in any case.


Making an array of spiral numbers Context
I was solving a task on CodeSignal here
You can view the task on the link I provided above.
I have also put the task at the bottom of the post.
Code
def check(matrix, num):
    for arr in matrix:
        for number in arr:
            if number != num:
                return True
    return False

def spiralNumbers(n):
    array = []
    array_dup = []
    for i in range(n):
        arr1 = []
        for j in range(n):
            arr1.append(j)
        array.append(arr1)

    for i in range(n):
        arr1 = []
        for j in range(n):
            arr1.append(j)
        array_dup.append(arr1)

    selected_row, selected_num_pos = 0, -1
    count = 1
    run = True
    while run:
        its_neg = False
        for i in range(selected_num_pos+1, n):
            if array_dup[selected_row][i] == -1:
                its_neg = True
                break
            array[selected_row][i] = count
            array_dup[selected_row][i] = -1
            count += 1
        if its_neg:
            selected_num_pos = i-1
        else:
            selected_num_pos = i

        its_neg = False
        for i in range(selected_row+1, n):
            if array_dup[i][selected_num_pos] == -1:
                its_neg = True
                break
            array[i][selected_num_pos] = count
            array_dup[i][selected_num_pos] = -1
            count += 1
        if its_neg:
            selected_row = i-1
        else:
            selected_row = i

        its_neg = False
        for i in range(selected_num_pos-1, -1, -1):
            if array_dup[selected_row][i] == -1:
                its_neg = True
                break
            array[selected_row][i] = count
            array_dup[selected_row][i] = -1
            count += 1
        if its_neg:
            selected_num_pos = i+1
        else:
            selected_num_pos = i

        its_neg = False
        for i in range(selected_row-1, -1, -1):
            if array_dup[i][selected_num_pos] == -1:
               its_neg = True
               break
            array[i][selected_num_pos] = count
            array_dup[i][selected_num_pos] = -1
            count += 1
        if its_neg:
            selected_row = i+1
        else:
            selected_row = i

        run = check(array_dup, -1)

    return array

Question
The Code I wrote works without any error and returns the expected output, but the code seems a bit long for this problem. I wanted to know how can I make this code shorter and more efficient?
The Task

You're using non-standard names. Usual names are A for the matrix, i for the row index, and j for the column index.
List repetition and comprehension make the initialization shorter and faster.
Using deltas for the four directions can avoid quadrupling code.
You can know when to change direction by checking whether the next element in the current direction is already set.
Your check is inefficient. Instead of searching the matrix for an unset spot, just do while count <= n**2:. Or, try to loop through the range of numbers.
Your current code crashes for n = 0 because it always enters the loop, as you compute run only at the end. With while count <= n**2: you'd succeed.

def spiralNumbers(n):
    A = [[0] * n for _ in range(n)]
    i = j = di = 0
    dj = 1
    for A[i][j] in range(1, n**2 + 1):
        if A[(i+di) % n][(j+dj) % n]:
            di, dj = dj, -di
        i += di
        j += dj
    return A

The % n is just a little trick to avoid checking for index-out-of-bounds.

I've implemented a simple solution. I found this question on LeetCode and mine works with O(n) time and O(n) space complexity.
Let me know if you have questions.

class Solution:
    def spiralOrder(self, array: List[List[int]]) -> List[int]:
        # Time: O(n)
        # Space: O(n)
        if(not array or not array[0]):
            return []
        n, m = len(array), len(array[0]) # get number of row and column
        startRow, endRow = 0, n - 1
        startCol, endCol = 0, m - 1

        arr = []

        while(startRow <= endRow and startCol <= endCol):

            #move right
            for col in range(startCol, endCol + 1):
                num = array[startRow][col]
                arr.append(num)

            #move down
            for row in range(startRow + 1, endRow + 1):
                num = array[row][endCol]
                arr.append(num)

            #move left
            for col in reversed(range(startCol, endCol)):
                if(startRow == endRow):
                    break
                num = array[endRow][col]
                arr.append(num)

            #move up
            for row in reversed(range(startRow + 1, endRow)):
                if(startCol == endCol):
                    break
                num = array[row][startCol]
                arr.append(num)

            #iterate
            startRow += 1
            endRow -=1
            startCol += 1
            endCol -= 1

        return arr

```


String/text manipulation utility class I'd like to get some expert's view on this first piece of code especially in the area of

performance - (e.g. avoidable copies)
good practice (e.g. static members?)

The final goal is the provide some abstractions for text manipulation like cleansing, stop-word removal and tokenization. The code base should grow substantially in the future so a lot more string manipulation methods should be supported. I understand that this should be bundled in a library in the end, however, I'd like to get feedback on the general code style first.
#include <fstream>
#include <iostream>
#include <regex>
#include <sstream>
#include <string>
#include <vector>

class TextManipulator {
 public:
  static std::string replace(std::string &string, const std::string pattern,
                             const std::string toreplace) {
    return std::regex_replace(string, std::regex(pattern), toreplace);
  }

  static std::string toLowerCase(std::string &string) {
    std::locale loc;
    std::string res;
    for (auto elem : string) {
      res += std::tolower(elem, loc);
    }
    return res;
  }

  static std::vector<std::string> split(const std::string &text,
                                        char seperator) {
    std::vector<std::string> tokens;
    std::size_t start = 0, end = 0;
    while ((end = text.find(seperator, start)) != std::string::npos) {
      std::string extr = text.substr(start, end - start);
      if (!extr.empty()) {
        tokens.push_back(extr);
      }
      start = end + 1;
    }
    tokens.push_back(text.substr(start));
    return tokens;
  }
};

int main() {
  std::ifstream input(
      "/example_docs/Pride_and_Prejudice.txt");
  std::stringstream buffer;
  buffer << input.rdbuf();
  std::string text = buffer.str();

  text = TextManipulator::replace(text, "\r\n", " ");
  text = TextManipulator::replace(text, ",", "");
  text = TextManipulator::replace(text, ":", "");
  text = TextManipulator::replace(text, ".", "");
  text = TextManipulator::toLowerCase(text);
  std::vector<std::string> tokens = TextManipulator::split(text, ' ');

  return 0;
}

Don't use a class
There is no need to create a class just to hold a collection of static functions. Instead, just declare the functions in the global namespace. If you want to avoid polluting the global namespace, consider putting them in a namespace instead, like so:
namespace TextManipulation {

std::string replace(...) {
    ...
};

...
}

Don't write unnecessary trivial wrapper functions
There is no need to create TextManipulator::replace(), when all it does is call std::regex_replace with almost exactly the same arguments. Why not call std::regex_replace() directly instead?
The name replace() also hides the fact that pattern is a regular expression.
Consider renaming toLowerCase() to tolower()
It's a bit annoying to have different naming conventions in one program, and since you already have tolower() for single characters, it would be very convenient to reuse that for whole strings as well. So:
std::string tolower(const std::string &str) {
    ...
}

Note: you forget to add const to the function parameter here, as well as for the first parameter of replace(), but you did it correctly for the other string parameters.

Whenever possible, use boost::string_ref in your code, this will reduce the number of copy operations with std::string. Check the places where you have copy operations and replace them with boost::string_ref operations if possible.


Calculating the ranks of classmates' exam grades The questions from hackerearth:

  Geeko is in worry now because an exam is coming up and he has to know
  what rank he can get on exams. So he goes back into the the school records
  and finds the amazing pattern.

  He finds that if a student is having a current rank \$n\$, then his rank on
  the final exam will be the count positive numbers between in the range
  \$[1,n]\$ which are relatively prime to \$n\$.

  As being a geek, he became curious now and wants to calculate the rank of
  all his classmates on the final exam.  But he finds this task a bit hard,
  so he asks you programmers to solve this task for him.

  Input: The first line of each test file contains a integer \$t\$ denoting
  the number of test case.  Each test case contains a numbers \$n\$
  representing the current rank of each student

  Output: for each test case output single integer the rank of student
  in final exam in new line.

  Constraints:

  \$1 <= t <= 2000\$

  \$1 <= n < 10^6\$

My solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

class relative {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        ArrayList<Integer> input = new ArrayList<Integer>();

        ArrayList<Integer> result = new ArrayList<Integer>();
        // int input[] = new int[t];
        // int result[] = new int[t];
        for (int i = 0; i < t; i++) {
            int count = 1;
            int in;
            input.add(in = Integer.parseInt(br.readLine()));
            for (int j = 2; j < in; j++) {
                if (in % j == 0)
                    continue;
                else if (checkRelativePrime(j, in))
                    count++;
            }
            result.add(count);
        }
        for (int i : result)
            System.out.println(i);
    }

    static boolean checkRelativePrime(int a, int b) {
        int i = 2;
        while (a > 1) {
            if (a % i == 0) {
                {
                    if (b % i == 0)
                        return false;
                }
                a = a / i;
            } else
                i++;
        }

        return true;
    }
}

in your checkRelativePrime method you have

static boolean checkRelativePrime(int a, int b) {
    int i = 2;
    while (a > 1) {
        if (a % i == 0) {
            {
                if (b % i == 0)
                    return false;
            }
            a = a / i;
        } else
            i++;
    }

    return true;
}

you have an extra set of brackets
you have a statement in purgatory.

a = a / i;

it sits in-between the ending bracket of your if statement and the else statement that is supposed to be attached to the if statement
if you use brackets for one part of an if statement, you should use them for the entire if statement. I recommend using brackets even for one-liners no matter what, it's cleaner and leaves less room for mistakes.

I think you wanted to keep that if statement separate from the declaration to the a variable, but you don't need to do that(especially if you are using brackets properly)

like this

while (a > 1) {
    if (a % i == 0) {
        if (b % i == 0) {
            return false;
        }
        a = a / i;
    } else {
        i++;
    }
}

if you enter that if statement and return false then a = a /i; will never happen and your boolean method will return false

Give meaningful class names to your classes, e.g. "relative" does not seem to describe anything about the data type of the object. A more meaningful name could have been "RankFinder" in the context of your problem.
Always stick to Hungarian notation while naming your classes and functions. http://en.wikipedia.org/wiki/Hungarian_notation
The function checkRelativePrime seems wrong to me. Simply make use of an auxiliary function to compute gcd(a, b) and check if it's one. The gcd computation function is pretty standard and can works as follows.

function gcd(a, b)
while b ≠ 0
    t := b;
    b := a mod b;
    a := t;
return a

You don't really need the array result. You can simply print the numbers in the first for loop.


Simple Java program - Coding bat sumNumbers The problem is stated as follows:

Given a string, return the sum of the numbers appearing in the string, ignoring all other characters. A number is a series of 1 or more digit chars in a row. (Note: Character.isDigit(char) tests if a char is one of the chars '0', '1', .. '9'. Integer.parseInt(string) converts a string to an int.)
sumNumbers("abc123xyz") → 123
sumNumbers("aa11b33") → 44
sumNumbers("7 11") → 18

Here's the program I wrote based on Character.isDigit(char) and Integer.parseInt(string).
public int sumNumbers(String str) {
  int sum = 0;
  for (int i = 0; i < str.length(); i++) {
      if (Character.isDigit(str.charAt(i))) {
          int count = 0;
          for (int j = i; j < str.length(); j++) {
              if (Character.isDigit(str.charAt(j))) count++;
              else break;
          }
          sum += Integer.parseInt(str.substring(i, i + count));
          i += count;
      }
  }
  return sum;
}

I'm not sure if I should make it more modular since it's pretty straightforward. I was wondering if I could do this without count. Also, I know it's nit-picky, but I want to know if the way I format my for loops and if else statements is good style. This is just a standalone program, so I'm not really concerned about the public/private issue.

There are a couple things you can do here to make things simpler. The first is to make your inner loop a while loop instead of a for loop. With this idea, you  can build up each number char by char, using Character.getNumericValue() which will return 1 for '1' etc. With charVal, we can incrementally build up our number by multiplying the by 10 and adding the new digit. When we reach a non-digit, we add the current num to our sum, and set sum to 0. Since the code now only operates one char at a time, we don't need i, or j either. With these changes, your updated code is

public int sumNumbers(String str) {
    int sum = 0;
    int num = 0;
    for (char ch : exampleString.toCharArray()) {
        int digit = Character.getNumericValue(ch);
        if (digit >= 0 && digit <= 9) {
            num = num * 10 + digit;
        } else {
            sum += num;
            num = 0;
        }
    }
    return sum + num;
}

Here is my simple code for this one

public int sumNumbers(String str) {
  String num = "";
  int total= 0;

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

    if(Character.isDigit(str.charAt(i))){
        int pos = i;
        while(pos < str.length() && Character.isDigit(str.charAt(pos))){
          pos++;

        }

         total += Integer.parseInt(str.substring(i,pos));
          i = pos;
    }

  }

  return total;

}


Project Euler 18/67: Maximum Path Sum Solution I wrote my solution to Project Euler #18 and #67 in C++ (which I'm relatively new to), and was just wondering what everyone else thinks of it. It executes in 3-4ms and works flawlessly (even for triangles not given by the website). But I'm not a professional programmer or anything, so I wouldn't know if it's necessarily good or not. Anyone have any potential improvements?

The website's instructions:

  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

   3
  7 4
 2 4 6
8 5 9 3

  That is, 3 + 7 + 4 + 9 = 23.

  Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one   hundred rows.

My code:

#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <sstream>
#include <vector>

int main()
{
    using namespace std;

    clock_t starttim = clock();
    //prog
    vector<vector<int>> lines;

    ifstream istrm("triangle.txt");
    string line;
    while (getline(istrm, line))
    {
        int num;
        stringstream ss(line);
        vector<int> curvec;
        while (ss >> num)
        {
            curvec.push_back(num);
        }
        lines.push_back(curvec);
    }

    for (int currow = lines.size() - 1; currow >= 0; currow--)
    {
        if (currow != 0)
        {
            for (int curidx = 0; curidx <= lines[currow].size() - 2; curidx++)
            {
                int num1 = lines[currow][curidx];
                int num2 = lines[currow][curidx + 1];
                int greater = (num1 > num2 ? num1 : num2);
                lines[currow - 1][curidx] += greater;
            }
        }
        else cout << lines[0][0] << endl;
    }

    //endprog
    cout << "Execution time - " << (((clock() - starttim) / (double)CLOCKS_PER_SEC) * 1000) << "ms." << endl;
    system("PAUSE");
    return 0;
}

This is pretty good code for a C++ beginner.  I believe you got the right algorithm.  Its running time is linear in the number of entries.  You visit every element once; I don't believe it is possible to do better than that.  Its memory usage is also linear in the number of entries.  The memory usage, however, can be improved.  Instead of processing the rows bottom-up, if you do it top-down, you can process the rows as you read them, keeping just two rows' worth of data at any given time.

It would be slightly more elegant to implement a simple abstraction layer for parsing the input.  I would also avoid hard-coding the filename.

Writing using namespace std; is considered bad practice.

The if-else inside the for-loop is pointless.  It just means that currow >= 0 was a poor termination condition.

I find the "cur…" prefixes on your variable names annoying.  What's "curve c"?  What's "currow" — does it rhyme with "furrow"?  As for "curidx", how about just i?

The timing printout should go to standard error to avoid contaminating the output.  You can avoid the (double) cast by writing 1000.0 to trigger floating-point arithmetic.

#include <ctime>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

template<typename T>
class Input {
  public:
    Input<T>(std::istream &in) : in(in) {}

    bool next_row(std::vector<T> &entries) {
        entries.clear();
        std::string line;
        if (!std::getline(this->in, line)) {
            return false;
        }
        std::stringstream ss(line);
        for (T n; ss >> n; ) {
            entries.push_back(n);
        }
        return true;
    }

  private:
    std::istream &in;
};

int main(int argc, char *argv[]) {
    std::clock_t start_time = clock();

    // Input from either a file or STDIN
    // http://stackoverflow.com/a/2159469/1157100
    std::shared_ptr<std::istream> input(&std::cin, [](...) -> void {});
    if (argc >= 2 && std::string("-") != argv[1]) {
        input.reset(new std::ifstream(argv[1]));
    }
    Input<int> triangle(*input);

    // For each entry in each row "b", add the greater of the two entries in
    // row "a" above.  Row "b" then contains the maximum path sum from the
    // top up to that point.
    std::vector<int> a, b;
    for (triangle.next_row(a); triangle.next_row(b); a = b) {
        b[0] += a[0];
        for (std::vector<int>::size_type i = 1; i < a.size(); i++) {
            b[i] += std::max(a[i - 1], a[i]);
        }
        b[b.size() - 1] += a[a.size() - 1];
    }
    std::cout << *std::max_element(a.begin(), a.end()) << std::endl;

    std::cerr << "Execution time - "
              << ((std::clock() - start_time) * 1000.0 / CLOCKS_PER_SEC)
              << "ms." << std::endl;
}

Your code is great, formatted well, and perfect-functioning. Except that, there is no need to do insider loops, and the memory issue can be parried without saturating it with horrible amounts of data.
What do I understand from the least informations I received: the XML structure of the triangle is unique, meaning two digit numbers intermediated by one character space like this example with two lines:

<digit> <digit> <CR> <LF>

<digit> <digit> <space> <digit> <digit>

So, if the file size is \$n\$, \$k\$th (last) line length should be a triangular number of an arithmetic series of distance \$3\$ (two digits number+space+two digits linefeed) starting from 4 until \$k\$.

Calculating \$k\$:

For a regular standard arithmetic series of distance 1, last line length is

\$ k=\sqrt{2(n+1)} \$

For our case:

\$ square=\sqrt{\frac{2(n+1)}{3}}\$
If \$square\$ is perfect square \$k=3*square\$.
If \$square\$ is not perect square
\$k=3*(square)+\frac{2(n+1)-3*square(square+1)}{square+1}\$

This last number \$k\$ should be perfect integer except if there is some XML misformatting.
instead of:

ifstream istrm("triangle.txt");

use

FILE*istrm=fopen("triangle.txt","r");

The library stdio.h must be included in the header.
Position the file cursor to the last but one line:

fseek(istrm, 0, SEEK_END);
int n=ftell(istrm),k;
double square=pow(2*(n+1)/3,0.5);
fseek(istrm, -(k= (square==(int)square) ?3*square: (int) 3*(int)square-2+ ( 2*(n+1)-3*((int)square*((int)square+1)) )/((int)square+1) ), SEEK_END);

Subtract 3 from the value of \$k\$ regularily until you come accross \$k=4\$ then stop! Meanwhile, just use a two-dimensional array and add it to the next (upper) line values until you finish calculating.

for(int curidx=0;k>3;curidx++)
{
    int num1;
    if(curidx>k/3)
        fseek(istrmm, -(k=k-3)-k-5+(curidx=0), SEEK_CUR);
    fscanf(istrmm,"%d",&num1);
    lines[0][curidx] = num1+lines[1][curidx];

    if(curidx>0)
    {
        int greater = (lines[0][curidx] > lines[0][curidx-1] ? lines[0][curidx] : lines[0][curidx-1]);
        lines[1][curidx-1] = greater;
     }
}

About variable declaration: don't declare the same variables repeatedly, just initialize it once:

int num1

int greater

for(int num1,greater,curidx=0;k>3;curidx++)

The overall code should look like:

using namespace std;

clock_t starttim = clock();

//lines is two dimensional
int* lines[2];

//open a file located in C:

FILE*istrmm=fopen("c:\\triangle.txt","r");

fseek(istrmm, 0, SEEK_END);
int n=ftell(istrmm),k;
double square=pow(2*(n+1)/3,0.5);
fseek(istrmm, -(k= (square==(int)square) ?3*square: (int) 3*(int)square-2+ ( 2*(n+1)-3*((int)square*((int)square+1)) )/((int)square+1) ), SEEK_END);

//initialize
lines[0]=(int*)malloc(sizeof(int)*k);
lines[1]=(int*)malloc(sizeof(int)*(k-1));
memset(*lines,0,4*k);
memset(*(lines+1),0,4*(k-1));

// one pass loop
for(int num1,greater,curidx=0;k>3;curidx++)
{
    // no need to num2, and greater should be declared once.
    if(curidx>k/3)
        fseek(istrmm, -(k=k-3)-k-5+(curidx=0), SEEK_CUR);
    //printf("%d   \n",ftell(istrmm));
    fscanf(istrmm,"%d",&num1);
    //printf("%d    %d   \n\n",num1,ftell(istrmm));
    lines[0][curidx] = num1+lines[1][curidx];

    if(curidx>0)
    {
        greater = (lines[0][curidx] > lines[0][curidx-1] ? lines[0][curidx] : lines[0][curidx-1]);
        lines[1][curidx-1] = greater;
    }
}

printf("%d ",(lines[0][1] > lines[0][0] ? lines[0][1] : lines[0][0]));
cout << "Execution time - " << (((clock() - starttim) / (double)CLOCKS_PER_SEC) * 1000) << "ms." << endl;
system("PAUSE");
return 0;


Determining if 2 images are the same This is my program code for comparing if 2 images are the same. It basically uses the open dialog and opens 1 image at a time and puts it in 1 picture box.

I heard that GetPixel() method may be slow. Is there a more efficient and faster way to compare 2 if 2 images are the same?

Bitmap image1 = null;
Bitmap image2 = null;

public Form1()
{
    InitializeComponent();
}

private void button1_Click(object sender, EventArgs e) //first image open
{
    OpenFileDialog openDialog = new OpenFileDialog();
    if (openDialog.ShowDialog() == DialogResult.OK)
    {
        image1 = new Bitmap(openDialog.FileName);
        pictureBox1.Image = image1;
    }
}

private void button2_Click(object sender, EventArgs e) //second image open
{

    OpenFileDialog openDialog = new OpenFileDialog();
    if (openDialog.ShowDialog() == DialogResult.OK)
    {
        image2 = new Bitmap(openDialog.FileName);
        pictureBox2.Image = image2;
    }
}

private void button3_Click(object sender, EventArgs e) //compare button
{
    if (compare(image1, image2))
    {
        MessageBox.Show("Same Image.");
    }

    else
    {
        MessageBox.Show("Different Image.");
    }
}

private bool compare(Bitmap bmp1, Bitmap bmp2)
{
    bool equals = true;
    bool flag = true;  //Inner loop isn't broken

    //Test to see if we have the same size of image
    if (bmp1.Size == bmp2.Size)
    {
        for (int x = 0; x < bmp1.Width; ++x)
        {
            for (int y = 0; y < bmp1.Height; ++y)
            {
                if (bmp1.GetPixel(x, y) != bmp2.GetPixel(x, y))
                {
                    equals = false;
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                break;
            }
        }
    }
    else
    {
        equals = false;
    }
    return equals;
}

You can use the LockBits method and pointers to access the image data directly.

Example for 24 bpp images:

bool equals = true;
Rectangle rect = new Rectangle(0, 0, bmp1.Width, bmp1.Height);
BitmapData bmpData1 = bmp1.LockBits(rect, ImageLockMode.ReadOnly, bmp1.PixelFormat);
BitmapData bmpData2 = bmp2.LockBits(rect, ImageLockMode.ReadOnly, bmp2.PixelFormat);
unsafe {
  byte* ptr1 = (byte*)bmpData1.Scan0.ToPointer();
  byte* ptr2 = (byte*)bmpData2.Scan0.ToPointer();
  int width = rect.Width * 3; // for 24bpp pixel data
  for (int y = 0; equals && y < rect.Height; y++) {
    for (int x = 0; x < width; x++) {
      if (*ptr1 != *ptr2) {
        equals = false;
        break;
      }
      ptr1++;
      ptr2++;
    }
    ptr1 += bmpData1.Stride - width;
    ptr2 += bmpData2.Stride - width;
  }
}
bmp1.UnlockBits(bmpData1);
bmp2.UnlockBits(bmpData2);

Have a look at this SO question.

https://stackoverflow.com/q/35151067/4062881

It decreases the size of image, turns it B&W, and then uses GetPixel() to generate hash.

It is much faster, efficient, and works! It is able to find equal images with:

different file formats (e.g. jpg, png, bmp)
rotation (90, 180, 270) - by changing the iteration order of i and j
different dimensions (same aspect is required)
different compression (tolerance is required in case of quality loss like jpeg artifacts) - you can accept a 99% equality to be the same image and 50% to be a different one.

Cheers..!!  ;)